The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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.
Number of coverings of an n-element set by m nonempty subsets (not necessarily disjunct). For the disjunct case cf. A019538. (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. A058482 (this gives the general formula, but values only for m=3).
Main diagonal gives A048291.
Column 2 is A058481.
Cf. A019538.
Sequence in context: A064051 A147385 A147347 * A082172 A053288 A282917
KEYWORD
nonn,tabl
AUTHOR
Steffen Eger, Feb 01 2011
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 18 14:30 EDT 2024. Contains 372630 sequences. (Running on oeis4.)