login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A132581 Number of antichains in the first n elements of the infinite Boolean lattice. 2
1, 2, 3, 5, 6, 11, 14, 19, 20, 39, 53, 78, 84, 134, 148, 167, 168, 335, 483, 765, 849, 1466, 1681, 1988, 2008, 3700, 4414, 5489, 5573, 7265, 7413, 7580, 7581, 15161, 22574, 37252, 42825, 77388, 92864, 116454, 118462, 227503, 286776, 382574, 392247, 555662, 574114, 595481, 595649, 1176304, 1563955 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

COMMENTS

Every nonnegative integer represents a finite set of nonnegative integers and conversely, by the mapping that takes n into the exponents of 2 in its binary representation. Thus 0 represents the empty set and 9 represents {0,3}, etc.

The sequence counts the antichains in the partial ordering {0,1,...,n}, which is really the family of sets {emptyset,{0},{1},{0,1},{2},...}.

The sequence of differences, A132582, enumerates the antichains in the infinite Boolean lattice {0,1,2,...} whose largest element is n. For example, the five such antichains when n=6 are {6}, {1,6}, {3,6}, {5,6}, {3,5,6}.

The subsequence a(2^n+1), n=0,1,2,... of the present sequence, is the Dedekind numbers sequence A000372. - Renzo Benedetti, Jul 24 2012

REFERENCES

D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.4.

LINKS

Peter Koehler, Table of n, a(n) for n = 0..160 (terms 0..90 from Robert Israel)

Peter Koehler, C++-Program

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([$0..n]), n=-1..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}] (* Jean-Fran├žois Alcover, Jul 22 2020, after Robert Israel *)

CROSSREFS

Cf. A132582.

Sequence in context: A164830 A039037 A050049 * A238542 A184640 A240490

Adjacent sequences:  A132578 A132579 A132580 * A132582 A132583 A132584

KEYWORD

nonn

AUTHOR

Don Knuth, Nov 18 2007

EXTENSIONS

a(32)-a(50) from Robert Israel, Mar 08 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 | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 11 16:11 EDT 2021. Contains 342886 sequences. (Running on oeis4.)