login
This site is supported by donations 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). 12
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

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

D. E. Knuth, Problem 11243, Am. Math. Montly 113 (8) (2006) page 759.

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)

- Robert FERREOL, Mar 14 2017

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 (0, m+1)])

i=1

for n in range(1, 51):

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

Diagonal gives A048291.

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 19 03:23 EST 2019. Contains 329310 sequences. (Running on oeis4.)