login
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

%I #76 Jul 15 2024 21:59:29

%S 1,1,7,1,25,265,1,79,2161,41503,1,241,16081,693601,24997921,1,727,

%T 115465,10924399,831719761,57366997447,1,2185,816985,167578321,

%U 26666530801,3776451407065,505874809287625

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

%C 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

%C From _Manfred Boergens_, Jul 25 2021: (Start)

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

%C 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.

%C For tuples with "nonempty" dropped see A092477 and A329943 (amendment by _Manfred Boergens_, Jun 24 2024). (End)

%H Indranil Ghosh, <a href="/A183109/b183109.txt">Rows 1..50, flattened</a>

%H Ch. A. Charalambides, <a href="https://doi.org/10.1016/0012-365X(79)90108-0">A problem of arrangements on chessboards and generalizations</a>, Discrete Mathematics 27.2 (1979): 179-186. (Generalizations.)

%H D. E. Knuth, <a href="http://dx.doi.org/10.2307/27642039">Problem 11243</a>, Am. Math. Montly 113 (8) (2006) page 759.

%H John Riordan and Paul R. Stein, <a href="https://doi.org/10.1016/0097-3165(72)90084-2">Arrangements on chessboards</a>, Journal of Combinatorial Theory, Series A 12.1 (1972): 72-80. See Table page 78.

%F T(n,m) = Sum_{j=0..m}(-1)^j*C(m, j)*(2^(m-j)-1)^n.

%F Recursion: T(m,n) = Sum_{k=1..m} T(k,n-1)*C(m,k)*2^k - T(m,n-1).

%F From _Robert FERREOL_, Mar 14 2017: (Start)

%F T(n,m) = Sum_{i = 0 .. n,j = 0 ..m}(-1)^(n+m+i+j)*C(n,i)*C(m,j)*2^(i*j).

%F Inverse formula of: 2^(n*m) = Sum_{i = 0 .. n , j = 0 ..m} C(n,i)*C(m,j)*T(i,j). (End)

%F A019538(j) <= a(j). - _Manfred Boergens_, Jul 25 2021

%e Triangle begins:

%e 1;

%e 1, 7;

%e 1, 25, 265;

%e 1, 79, 2161, 41503;

%e 1, 241, 16081, 693601, 24997921;

%e 1, 727, 115465, 10924399, 831719761, 57366997447;

%e 1, 2185, 816985, 167578321, 26666530801, 3776451407065, 505874809287625;

%e ...

%p A183109 := proc(n,m)

%p add((-1)^j*binomial(m,j)*(2^(m-j)-1)^n,j=0..m) ;

%p end proc:

%p seq(seq(A183109(n,m),m=1..n),n=1..10) ; # _R. J. Mathar_, Dec 03 2015

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

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

%o tabl(8); \\ _Indranil Ghosh_, Mar 14 2017

%o (Python)

%o import math

%o f = math.factorial

%o def C(n,r): return f(n)//f(r)//f(n - r)

%o def T(n,m):

%o return sum((-1)**j*C(m,j)*(2**(m - j) - 1)**n for j in range (m+1))

%o i=1

%o for n in range(1,21):

%o for m in range(1, n+1):

%o print(str(i)+" "+str(T(n, m)))

%o i+=1 # _Indranil Ghosh_, Mar 14 2017

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

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

%Y Main diagonal gives A048291.

%Y Column 2 is A058481.

%Y Cf. A019538, A092477, A329943.

%K nonn,tabl

%O 1,3

%A _Steffen Eger_, Feb 01 2011