|
| |
|
|
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^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.
|
|
|
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 J. M. 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)
|
|
|
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
|
|
|
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^e-2^valuation(n, 2)), A132581(n)-A132581(n-1))}, [0..10]) \\ M. F. Hasler, Jun 03 2021
|
|
|
CROSSREFS
|
See A132581 for further information.
Sequence in context: A075303 A076062 A295563 * A262211 A345967 A094512
Adjacent sequences: A132579 A132580 A132581 * A132583 A132584 A132585
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Don Knuth, Nov 18 2007
|
|
|
EXTENSIONS
|
More terms from Robert Israel, Mar 08 2017
Extended by Peter Koehler, Jul 07 2017
|
|
|
STATUS
|
approved
|
| |
|
|
