A270952 T(n, k) is the number of k-element connected subposets of the n-th Boolean lattice, 0 <= k <= 2^n.

1, 1, 1, 2, 1, 1, 4, 5, 4, 1, 1, 8, 19, 42, 61, 56, 28, 8, 1, 1, 16, 65, 304, 1129, 3200, 6775, 10680, 12600, 11386, 8002, 4368, 1820, 560, 120, 16, 1, 1, 32, 211, 1890, 14935, 97470

Offset

0,4

Comments

The n-th Boolean lattice is the set of all subsets of {1,2,...,n}, partially ordered by inclusion.

Links

Table of n, a(n) for n=0..41.

Eric Weisstein's World of Mathematics, Boolean Algebra.

Example

The triangle begins:
n\k 0  1   2    3     4     5    6     7     8     9   10   11   12  13  14
0   1  1
1   1  2   1
2   1  4   5    4     1
3   1  8  19   42    61    56   28     8     1
4   1 16  65  304  1129  3200 6775 10680 12600 11386 8002 4368 1820 560 120
5   1 32 211 1890 14935 97470  ...
For T(2, 2) = 5: [{},{1}], [{},{2}], [{},{1,2}], [{1},{1,2}], [{2},{1,2}].

Prog

(Sage)
def ConnectedSubs(n): # Returns row n of T(n, k).
    Bn = posets.BooleanLattice(n)
    counts = [0]*(2^n+1)
    for X in Subsets(range(2^n)):
        if Bn.subposet(X).is_connected():
            counts[len(X)] += 1
    return counts

Crossrefs

Columns: A000012 (k = 0, 2^n), A000079 (k = 1, 2^n - 1), A001047 (k = 3).

Sequence in context: A208061 A078047 A329689 * A143392 A090668 A307977

Adjacent sequences: A270949 A270950 A270951 * A270953 A270954 A270955

Keyword

nonn,more,tabf

Author

Danny Rorabaugh, Mar 26 2016

Status

approved