login
First differences of A132581.
3

%I #85 Jun 27 2024 10:04:27

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