login
A059202
Triangle T(n,m) of numbers of m-block T_0-covers of a labeled n-set, m = 0..2^n - 1.
17
1, 0, 1, 0, 0, 3, 1, 0, 0, 3, 29, 35, 21, 7, 1, 0, 0, 0, 140, 1015, 2793, 4935, 6425, 6435, 5005, 3003, 1365, 455, 105, 15, 1, 0, 0, 0, 420, 13965, 126651, 661801, 2533135, 7792200, 20085000, 44307120, 84651840, 141113700, 206251500, 265182300
OFFSET
0,6
COMMENTS
A cover of a set is a T_0-cover if for every two distinct points of the set there exists a member (block) of the cover containing one but not the other point.
Also, T(n,m) is the number of n X m (0,1)-matrices with pairwise distinct nonzero columns and pairwise distinct nonzero rows, up to permutation of columns.
LINKS
Robert Israel, Table of n, a(n) for n = 0..4094 (rows 0 to 11, flattened).
FORMULA
T(n, m) = (1/m!)*Sum_{1..m + 1} stirling1(m + 1, i)*[2^(i - 1) - 1]_n, where [k]_n := k*(k - 1)*...*(k - n + 1), [k]_0 = 1.
E.g.f: Sum((1+x)^(2^n-1)*log(1+y)^n/n!, n=0..infinity)/(1+y). - Vladeta Jovovic, May 19 2004
Also T(n, m) = Sum_{i=0..n} Stirling1(n+1, i+1)*binomial(2^i-1, m). - Vladeta Jovovic, Jun 04 2004
T(n,m) = A181230(n,m)/m! - n*T(n-1,m) - T(n,m-1) - n*T(n-1,m-1). - Max Alekseyev, Dec 11 2017
EXAMPLE
[1],
[0,1],
[0,0,3,1],
[0,0,3,29,35,21,7,1],
...
There are 35 4-block T_0-covers of a labeled 3-set.
MAPLE
with(combinat): for n from 0 to 10 do for m from 0 to 2^n-1 do printf(`%d, `, (1/m!)*sum(stirling1(m+1, i)*product(2^(i-1)-1-j, j=0..n-1), i=1..m+1)) od: od:
MATHEMATICA
T[n_, m_] = Sum[ StirlingS1[n + 1, i + 1]*Binomial[2^i - 1, m], {i, 0, n}]; Table[T[n, m], {n, 0, 5}, {m, 0, 2^n - 1}] (* G. C. Greubel, Dec 28 2016 *)
CROSSREFS
Cf. A059201 (row sums), A059203 (column sums), A094000 (main diagonal).
Binary matrices with distinct rows and columns, various versions: A059202, A088309, A088310, A088616, A089673, A089674, A093466, A094000, A094223, A116532, A116539, A181230, A259763
Sequence in context: A122848 A272481 A054548 * A244963 A144452 A217334
KEYWORD
easy,nonn,tabf
AUTHOR
Vladeta Jovovic, Goran Kilibarda, Jan 18 2001
EXTENSIONS
More terms from James A. Sellers, Jan 24 2001
STATUS
approved