

A132582


First differences of A132581.


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,3


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^k1. 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 = k1), and equals A000372(k1). 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



FORMULA

a(2^(k+1)  2^m 1) = a(2^k + 2^m 1) = A132581(2^k  2^m) for all k > m >= 0.
a(2^k 1) = A132581(0) =1, for all k>=0.
(End)
A132581(2^k) = a(2^k + 2^((k1)/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)


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..t1])) , t = 1..nops(S));
end proc:
seq(AntichainCount(select(s > Incomp[s, n], [$1..n1])), 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 ;; t1]], Incomp[#, S[[t]]]&]], {t, 1, Length[S]}]];


PROG

(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^e2^valuation(n, 2)), A132581(n)A132581(n1))}, [0..10]) \\ M. F. Hasler, Jun 03 2021


CROSSREFS

See A132581 for further information.


KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



