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).

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

Offset: 1

Author

Steffen Eger, Feb 01 2011

Keywords

• nonn
• tabl

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

From Manfred Boergens, Jul 25 2021: (Start)

The matrices in the definition are a superset of the matrices in the comment to A019538 by Manfred Boergens.

T(n,m) is the number of coverings of [n] by tuples (A_1,...,A_m) in P([n])^m with nonempty A_j, with P(.) denoting the power set (corrected for clarity by Manfred Boergens, May 26 2024). For the disjoint case see A019538.

For tuples with "nonempty" dropped see A092477 and A329943 (amendment by Manfred Boergens, Jun 24 2024). (End)

Examples

			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;
  ...
		

Links

• Indranil Ghosh, Rows 1..50, flattened
• Ch. A. Charalambides, A problem of arrangements on chessboards and generalizations, Discrete Mathematics 27.2 (1979): 179-186. (Generalizations.)
• 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.

Crossrefs

Cf. A218695 (same sequence with restriction m<=n dropped).

Cf. A058482 (this gives the general formula, but values only for m=3).

Main diagonal gives A048291.

Column 2 is A058481.

Cf. A019538, A092477, A329943.

Programs

Maple

A183109 := proc(n,m)
    add((-1)^j*binomial(m,j)*(2^(m-j)-1)^n,j=0..m) ;
end proc:
seq(seq(A183109(n,m),m=1..n),n=1..10) ; # R. J. Mathar, Dec 03 2015

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 *)

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(););};
tabl(8); \\ Indranil Ghosh, Mar 14 2017

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)))
        i+=1 # Indranil Ghosh, Mar 14 2017

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).

From Robert FERREOL, Mar 14 2017: (Start)

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)

A019538(j) <= a(j). - Manfred Boergens, Jul 25 2021