login
A270952
T(n, k) is the number of k-element connected subposets of the n-th Boolean lattice, 0 <= k <= 2^n.
0
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
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
KEYWORD
nonn,more,tabf
AUTHOR
Danny Rorabaugh, Mar 26 2016
STATUS
approved