login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A269699 Irregular triangle read by rows: T(n, k) is the number of k-element proper ideals of the n-dimensional Boolean lattice, with 0 < k < 2^n. 1
1, 1, 2, 1, 1, 3, 3, 4, 3, 3, 1, 1, 4, 6, 10, 13, 18, 19, 24, 19, 18, 13, 10, 6, 4, 1, 1, 5, 10, 20, 35, 61, 95, 155, 215, 310, 387, 470, 530, 580, 605, 621, 605, 580, 530, 470, 387, 310, 215, 155, 95, 61, 35, 20, 10, 5, 1, 1, 6, 15, 35, 75, 156, 306, 605, 1110, 2045, 3512, 5913, 9415 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

The set of maximal elements of an ideal is an antichain; conversely, the down-set of a nonempty antichain is an ideal. The down-set of the top element of the n-dimensional Boolean lattice contains all 2^n elements of the lattice, and thus is not a proper ideal.

The table begins:

n\k 1 2  3  4  5  6  7   8   9  10  11  12  13  14  15  16  17

1   1

2   1 2  1

3   1 3  3  4  3  3  1

4   1 4  6 10 13 18 19  24  19  18  13  10   6   4   1

5   1 5 10 20 35 61 95 155 215 310 387 470 530 580 605 621 605 ...

Empirically, the rows are unimodal.

By the Markowsky paper, T(n, k) = T(n, 2^n - k).

Also, T(n,k) is the number of n-dimensional Ferrers diagrams with k nodes (i.e., (n-1)-dimensional partitions) that fit into a n-dimensional hypercube of side 2 (i.e., a Boolean or binary hupercube). T(n, k) = T(n, 2^n - k) follows from the map that takes a Ferrers diagram to its complement in the box. - Suresh Govindarajan, Apr 10 2016

LINKS

Danny Rorabaugh and Suresh Govindarajan, Table of n, a(n) for n = 1..279

George Markowsky, The level polynomials of the free distributive lattices, Discrete Math., 29 (1980), 275-285.

Wikipedia, Boolean algebra and Ideal.

EXAMPLE

For row n = 3, the k-element proper ideals are the down-sets of the following antichains:

T(3, 1) = 1: [{}];

T(3, 2) = 3: [{0}], [{1}], [{2}];

T(3, 3) = 3: [{0},{1}], [{0},{2}], [{1},{2}];

T(3, 4) = 4: [{0,1}], [{0,2}], [{1,2}], [{0},{1},{2}];

T(3, 5) = 3: [{0,1},{2}], [{0,2},{1}], [{1,2},{0}];

T(3, 6) = 3: [{0,1},{0,2}], [{0,1},{1,2}], [{0,2},{1,2}];

T(3, 7) = 1: [{0,1},{0,2},{1,2}].

E.g., the 5-element down-set of [{0,1},{2}] is [{},{0},{1},{2},{0,1}].

PROG

(Sage) # Returns row n.

def T(n):

  B = posets.BooleanLattice(n)

  t = [0]*(2^n + 1)

  for A in B.antichains():

    t[len(B.order_ideal(A))] += 1

  return t[1:-1]

CROSSREFS

Columns are: A000012 (k = 1), A000027 (k = 2), A000217 (k = 3), A000292 (k = 4), A095661 (k = 5).

Cf. A007153 (row sums), A007318, A059119.

Sequence in context: A284828 A101417 A260056 * A035636 A104554 A152414

Adjacent sequences:  A269696 A269697 A269698 * A269700 A269701 A269702

KEYWORD

nonn,tabf

AUTHOR

Danny Rorabaugh, Mar 03 2016

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 27 11:25 EDT 2017. Contains 288788 sequences.