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

Author

Don Knuth, Nov 18 2007

Keywords

• nonn

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.

Crossrefs

See A132581 for further information.

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(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 *)

PARI

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

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 Jose 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)

Extensions

More terms from Robert Israel, Mar 08 2017

Extended by Peter Koehler, Jul 07 2017