|
%I #83 Feb 09 2023 05:05:53
%S 1,1,2,1,5,3,5,1,19,14,25,6,50,14,19,1,167,148,282,84,617,215,307,20,
%T 1692,714,1075,84,1692,148,167,1,7580,7413,14678,5573,34563,15476,
%U 23590,2008,109041,59273,95798,9673,163415,18452,21367,168,580655,387651,668175,82404,1226845,169396,201394,2008
%N First differences of A132581.
%C 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
%C 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
%C 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
%H J. M. Aranda, <a href="/A132582/b132582.txt">Table of n, a(n) for n = 0..211</a> (first 91 terms from Robert Israel; terms 91..160 from Peter Koehler)
%H J. M. Aranda, <a href="/A132582/a132582_1.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.
%F From _M. F. Hasler_, Jun 01 2021: (Start)
%F a(n) = A132581(n+1) - A132581(n) for n >= 0, by definition.
%F a(2^(k+1) - 2^m -1) = a(2^k + 2^m -1) = A132581(2^k - 2^m) for all k > m >= 0.
%F a(3*2^k -1) = A132581(2^k) = A000372(k), for all k >= 0.
%F a(2^k -1) = A132581(0) =1, for all k>=0.
%F (End)
%F From _J. M. Aranda_, Jun 09 2021: (Start)
%F A132581(2^k) = a(2^k + 2^((k-1)/2) -1) + a(2^k +2^((k+1)/2) -1), for k odd, k>0.
%F A132581(2^k)= 2*a(2^k + 2^(k/2) -1), for k even, k>=0.
%F (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
%p 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(select(s -> Incomp[s,n], [$1..n-1])), n=0..N); # _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}] // Differences (* _Jean-François Alcover_, Feb 09 2023, after _Robert Israel_ *)
%o (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
%Y See A132581 for further information.
%K nonn
%O 0,3
%A _Don Knuth_, Nov 18 2007
%E More terms from _Robert Israel_, Mar 08 2017
%E Extended by _Peter Koehler_, Jul 07 2017
|
