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,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

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)

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.

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

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

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

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(); ); };
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

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.

Sequence in context: A064051 A147385 A147347 * A082172 A053288 A282917

Adjacent sequences: A183106 A183107 A183108 * A183110 A183111 A183112

Keyword

nonn,tabl

Author

Steffen Eger, Feb 01 2011

Status

approved