A132582 First differences of A132581.

1, 1, 2, 1, 5, 3, 5, 1, 19, 14, 25, 6, 50, 14, 19, 1, 167, 148, 282, 84, 617, 215, 307, 20, 1692, 714, 1075, 84, 1692, 148, 167, 1, 7580, 7413, 14678, 5573, 34563, 15476, 23590, 2008, 109041, 59273, 95798, 9673, 163415, 18452, 21367, 168, 580655, 387651, 668175, 82404, 1226845, 169396, 201394, 2008

Offset

0,3

Comments

a(n) is the number of antichains containing n when the elements of the infinite Boolean lattice are represented by 0, 1, 2, ... - Robert Israel, Mar 08 2017, corrected and edited by M. F. Hasler, Jun 01 2021

When the elements of the Boolean lattice are considered to be subsets of {0, 1, 2, ...} with the inclusion relation, then an integer n (as in "containing n" in the above comment) means the set whose characteristic function is the binary expansion of n, for example, n = 3 = 11[2] represents the set {0, 1} and n = 4 = 100[2] represents the set {2}. See A132581 for details and examples. - M. F. Hasler, Jun 01 2021

The terms come in groups of length 2^k, k >= 0, delimited by the '1's at indices 2^k-1. Within each group, there is a symmetry: a(2^k - 1 + 2^m) = a(2^(k+1) - 1 - 2^m) for 0 <= m < k. The smallest term within each group is exactly in the middle (m = k-1), and equals A000372(k-1). A similar pattern holds recursively: the smallest term within the first half (and also within the second half) of the group is again exactly in the middle of that range, and so on. - M. F. Hasler, Jun 01 2021

Links

J. M. Aranda, Table of n, a(n) for n = 0..211 (first 91 terms from Robert Israel; terms 91..160 from Peter Koehler)

J. M. Aranda, C++ program

J. Berman and P. Köhler, On Dedekind Numbers and Two Sequences of Knuth, J. Int. Seq., Vol. 24 (2021), Article 21.10.7.

Formula

From M. F. Hasler, Jun 01 2021: (Start)

a(n) = A132581(n+1) - A132581(n) for n >= 0, by definition.

a(2^(k+1) - 2^m -1) = a(2^k + 2^m -1) = A132581(2^k - 2^m) for all k > m >= 0.

a(3*2^k -1) = A132581(2^k) = A000372(k), for all k >= 0.

a(2^k -1) = A132581(0) =1, for all k>=0.

(End)

From J. M. Aranda, Jun 09 2021: (Start)

A132581(2^k) = a(2^k + 2^((k-1)/2) -1) + a(2^k +2^((k+1)/2) -1), for k odd, k>0.

A132581(2^k)= 2*a(2^k + 2^(k/2) -1), for k even, k>=0.

(End)

Maple

N:= 63:
Q:= [seq(convert(n+64, base, 2), n=0..N)]:
Incomp:= Array(0..N, 0..N, proc(i, j) local d; d:= Q[i+1]-Q[j+1]; has(d, 1) and
  has(d, -1) end proc):
AntichainCount:= proc(S) option cache; local t, r;
1 + add(procname(select(s -> Incomp[s, S[t]], S[1..t-1]))  , t = 1..nops(S));
end proc:
seq(AntichainCount(select(s -> Incomp[s, n], [$1..n-1])), n=0..N); # Robert Israel, Mar 08 2017

Mathematica

M = 63;
Q = Table[IntegerDigits[n+64, 2], {n, 0, M}];
Incomp[i_, j_] := Module[{d}, d = Q[[i+1]] - Q[[j+1]]; MemberQ[d, 1] && MemberQ[d, -1]];
AntichainCount[S_] := AntichainCount[S] = Module[{t, r}, 1 + Sum[AntichainCount[Select[S[[1 ;; t-1]], Incomp[#, S[[t]]]&]], {t, 1, Length[S]}]];
Table[AntichainCount[Range[0, n]], {n, -1, M}] // Differences (* Jean-François Alcover, Feb 09 2023, after Robert Israel *)

Prog

(PARI) apply( A132582(n, e=exponent(n))={if(n++<3 || n==2<<e, 1, setsearch([1, 2]<<e+[1, -1]<<valuation(n, 2), n), A132581(2^e-2^valuation(n, 2)), A132581(n)-A132581(n-1))}, [0..10]) \\ M. F. Hasler, Jun 03 2021

Crossrefs

See A132581 for further information.

Sequence in context: A075303 A076062 A295563 * A262211 A345967 A094512

Adjacent sequences: A132579 A132580 A132581 * A132583 A132584 A132585

Keyword

nonn

Author

Don Knuth, Nov 18 2007

Extensions

More terms from Robert Israel, Mar 08 2017

Extended by Peter Koehler, Jul 07 2017

Status

approved