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

%I #187 Dec 29 2021 09:51:37

%S 1,2,3,5,6,11,14,19,20,39,53,78,84,134,148,167,168,335,483,765,849,

%T 1466,1681,1988,2008,3700,4414,5489,5573,7265,7413,7580,7581,15161,

%U 22574,37252,42825,77388,92864,116454,118462,227503,286776,382574,392247,555662,574114,595481,595649,1176304,1563955

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

%C 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.

%C 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},...}.

%C 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}.

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

%H J. M. Aranda, <a href="/A132581/b132581.txt">Table of n, a(n) for n = 0..212</a> (terms 0..90 from Robert Israel; terms 91..160 from Peter Koehler)

%H J. M. Aranda, <a href="/A132581/a132581_4.cpp.txt">C++ Program</a>

%H J. Berman and P. Köhler, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Koehler/koehler5.html">On Dedekind Numbers and Two Sequences of Knuth</a>, J. Int. Seq., Vol. 24 (2021), Article 21.10.7.

%H Peter Koehler, <a href="/A132581/a132581.cpp.txt">C++ program</a>

%F 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

%F From _J. M. Aranda_, Apr 29 2021: (Start)

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

%F 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.

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

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

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

%F (End)

%e From _M. F. Hasler_, Jun 01 2021: (Start)

%e 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 {}.

%e 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, { {} }.

%e 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} }.

%e 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} }.

%e 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.

%e (End)

%p N:= 63:

%p Q:= [seq(convert(n+64,base,2),n=0..N)]:

%p 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):

%p AntichainCount:= proc(S) option cache; local t,r;

%p 1 + add(procname(select(s -> Incomp[s,S[t]],S[1..t-1])) , t = 1..nops(S));

%p end proc:

%p seq(AntichainCount([$0..n]), n=-1..N);

%p # _Robert Israel_, Mar 08 2017

%t M = 63;

%t Q = Table[IntegerDigits[n + 64, 2], {n, 0, M}];

%t Incomp[i_, j_] := Module[{d}, d = Q[[i + 1]] - Q[[j + 1]]; MemberQ[d, 1] && MemberQ[d, -1]];

%t AntichainCount[S_] := AntichainCount[S] = Module[{t, r}, 1 + Sum[ AntichainCount[Select[S[[1 ;; t - 1]], Incomp[#, S[[t]]]&]], {t, 1, Length[S]}]];

%t Table[AntichainCount[Range[0, n]], {n, -1, M}] (* _Jean-François Alcover_, Jul 22 2020, after _Robert Israel_ *)

%o (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<<e - 1, A132581(2^e-1)+A132581(n-1), n==2<<e - 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

%Y Cf. A132582.

%K nonn

%O 0,2

%A _Don Knuth_, Nov 18 2007

%E a(32)-a(50) from _Robert Israel_, Mar 08 2017

%E Edited by _M. F. Hasler_, Jun 01 2021