login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 5 06:18 EDT 2022. Contains 355088 sequences. (Running on oeis4.)