A132581 Number of antichains in the first n elements of the infinite Boolean lattice.

1, 2, 3, 5, 6, 11, 14, 19, 20, 39, 53, 78, 84, 134, 148, 167, 168, 335, 483, 765, 849, 1466, 1681, 1988, 2008, 3700, 4414, 5489, 5573, 7265, 7413, 7580, 7581, 15161, 22574, 37252, 42825, 77388, 92864, 116454, 118462, 227503, 286776, 382574, 392247, 555662, 574114, 595481, 595649, 1176304, 1563955

Offset: 0

Author

Don Knuth, Nov 18 2007

Keywords

• nonn

Comments

Every nonnegative integer represents a finite set of nonnegative integers and conversely, by the mapping that takes n into the exponents of 2 in its binary representation. Thus 0 represents the empty set and 9 represents {0,3}, etc.

The sequence [more precisely a(n+1) - Ed.] counts the antichains in the partial ordering {0,1,...,n}, which is really the family of sets {emptyset,{0},{1},{0,1},{2},...}.

The sequence of differences, A132582, enumerates the antichains in the infinite Boolean lattice {0,1,2,...} whose largest element is n [for A132582(n) = a(n+1) - a(n)]. For example, the five such antichains when n = 6 are {6}, {1,6}, {3,6}, {5,6}, {3,5,6}.

Examples

			From _M. F. Hasler_, Jun 01 2021: (Start)
For n = 0, we consider the first zero elements of the lattice, i.e., no element at all. Thus a(0) = 1 counts the only antichain with elements in the empty set, i.e., no elements, which is the empty antichain {}.
For n = 1, we consider the first element of the lattice, represented by the first nonnegative integer, 0: This element is the empty set. Hence a(1) = 2 counts the antichains with elements in { {} }, the singleton containing the empty set. These two antichains are again the empty antichain, and the singleton antichain containing just the empty set, { {} }.
For n = 2, we consider the first two elements of the lattice, represented by the integers 0 and 1, which are {} and {0}. So a(2) = 3 counts the antichains with elements in { {}, {0} }: These three antichains are the empty antichain {} and the two singleton antichains { {} } and { {0} }.
For n = 3, we consider the first three elements of the lattice, represented by 0, 1 and 2; these are the sets {}, {0}, {1}. Hence a(3) counts the 5 antichains with elements in { {}, {0}, {1} }: the empty antichain {}, and the three singleton antichains { {} }, { {0} }, { {1} }, and the antichain { {0}, {1} }.
For n = 4, the first 4 elements of the lattice, represented by 0, 1, 2 and 3, form the power set P({0, 1}) = { {}, {0}, {1}, {0, 1} }. Hence a(4) counts all 6 antichains of subsets of {0, 1}, which is equivalent to considering the antichains of subsets of {1, 2} as counted by A000372(2), see example there.
(End)
		

References

• D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.4.

Links

• J. M. Aranda, Table of n, a(n) for n = 0..212 (terms 0..90 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.
• Peter Koehler, C++ program

Crossrefs

Cf. A132582.

Programs

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([$0..n]), n=-1..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}] (* Jean-François Alcover, Jul 22 2020, after Robert Israel *)

PARI

M132581 = Map(); A132581(n) = { if( mapisdefined(M132581,n,&n), n, n<3, n+1, my(e=exponent(n)); mapput(M132581, n, e = if( n==2^e, for( b=e\/2, e, iferr( e=A132581(n-2^b)+ A132581(n-n>>b); break, e,)); type(e)=="t_INT"|| error(e); e, n==2<A132581(2^e-1)+A132581(n-1), n==2<A132581(2^e-2) + A132581(n-1), n==2^e + 1, iferr( A132581(n\/2) + 2*A132581(n-3), e, 2*A132581(n-2) + 1), n==2^e + 2, iferr( A132581(n\2) + 3*A132581(n-4), e, A132581(n-4) + A132581(n-3) + A132581(n-2)), mapisdefined(M132581,[-n],&e), mapdelete(M132581,[-n]);  mapdelete(M132581,[n]); error(e" without success."), mapisdefined(M132581,[n]), mapput(M132581,[-n],Str("Trying to use A132582("n")")); A132581(n+1)-A132582(n)-mapdelete(M132581,[-n]), mapput(M132581,[n],0); A132581(n-1)+A132582(n-1)+mapdelete(M132581,[n]))); e)} \\ So far, not all values can be computed. - M. F. Hasler, Jun 04 2021

Formula

a(2^n) = A000372(n) (Dedekind numbers), for n >= 0, 1, 2, ... - Renzo Benedetti, Jul 24 2012, corrected by M. F. Hasler, May 31 2021

From J. M. Aranda, Apr 29 2021: (Start)

a(2^n) = a(2^n-2^m) + a(2^n-2^(n-m)) for n >= m >= 0.

a(2^n+2) = a(2^n) + a(2^n-1) + a(2^n-2) = 3*a(2^n-2) + a(2^(n-1)+1) for n >= 1.

a(2^n+1) = 2*a(2^n-2) + a(2^(n-1)+1) = 2*a(2^n-1) + 1 for n >= 1.

a(2^n-1) = a(2^n-2) + a(2^(n-1)-1) for n >= 1.

a(2^n-2) = a(2^n-3) + a(2^(n-1)-2) for n >= 2.

(End)

Extensions

a(32)-a(50) from Robert Israel, Mar 08 2017

Edited by M. F. Hasler, Jun 01 2021