|
|
A183109
|
|
Triangle read by rows: T(n,m) = number of n X m binary matrices with no zero rows or columns (n >= 1, 1 <= m <= n).
|
|
15
|
|
|
1, 1, 7, 1, 25, 265, 1, 79, 2161, 41503, 1, 241, 16081, 693601, 24997921, 1, 727, 115465, 10924399, 831719761, 57366997447, 1, 2185, 816985, 167578321, 26666530801, 3776451407065, 505874809287625
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
T(n,m) = T(m,n) is also the number of complete alignments between two strings of sizes m and n, respectively; i.e. the number of complete matchings in a bipartite graph
The matrices in the definition are a superset of the matrices in the comment to A019538 by Manfred Boergens.
Number of coverings of an n-element set by m nonempty subsets (not necessarily disjunct). For the disjunct case cf. A019538. (End)
|
|
LINKS
|
D. E. Knuth, Problem 11243, Am. Math. Montly 113 (8) (2006) page 759.
John Riordan and Paul R. Stein, Arrangements on chessboards, Journal of Combinatorial Theory, Series A 12.1 (1972): 72-80. See Table page 78.
|
|
FORMULA
|
T(n,m) = Sum_{j=0..m}(-1)^j*C(m, j)*(2^(m-j)-1)^n.
Recursion: T(m,n) = Sum_{k=1..m} T(k,n-1)*C(m,k)*2^k - T(m,n-1).
T(n,m) = Sum_{i = 0 .. n,j = 0 ..m}(-1)^(n+m+i+j)*C(n,i)*C(m,j)*2^(i*j).
Inverse formula of: 2^(n*m) = Sum_{i = 0 .. n , j = 0 ..m} C(n,i)*C(m,j)*T(i,j). (End)
|
|
EXAMPLE
|
Triangle begins:
1;
1, 7;
1, 25, 265;
1, 79, 2161, 41503;
1, 241, 16081, 693601, 24997921;
1, 727, 115465, 10924399, 831719761, 57366997447;
1, 2185, 816985, 167578321, 26666530801, 3776451407065, 505874809287625;
...
|
|
MAPLE
|
add((-1)^j*binomial(m, j)*(2^(m-j)-1)^n, j=0..m) ;
end proc:
|
|
MATHEMATICA
|
Flatten[Table[Sum[ (-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}], {n, 1, 7}, {m, 1, n}]] (* Indranil Ghosh, Mar 14 2017 *)
|
|
PROG
|
(PARI) tabl(nn) = {for(n=1, nn, for(m = 1, n, print1(sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n), ", "); ); print(); ); };
(Python)
import math
f = math.factorial
def C(n, r): return f(n)//f(r)//f(n - r)
def T(n, m):
return sum((-1)**j*C(m, j)*(2**(m - j) - 1)**n for j in range (m+1))
i=1
for n in range(1, 21):
for m in range(1, n+1):
print(str(i)+" "+str(T(n, m)))
|
|
CROSSREFS
|
Cf. A058482 (this gives the general formula, but values only for m=3).
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|