OFFSET
0,5
COMMENTS
A(n,m) is the number of ways to pair the elements of two sets (with respectively n and m elements), where each element of either set may be paired with zero or one elements of the other set; number of n X m matrices of zeros and ones with at most one one in each row and column. E.g., A(2,2)=7 because we can pair {A,B} with {C,D} as {AB,CD}, {AC,BD}, {AC,B,D}, {AD,B,C}, {BC,A,D}, {BD,A,C}, or {A,B,C,D}. - Franklin T. Adams-Watters, Feb 06 2006
Compare with A086885. - Peter Bala, Sep 17 2008
A(n,m) is the number of vertex covers and independent vertex sets in the n X m lattice (rook) graph K_n X K_m. - Andrew Howroyd, May 14 2017
LINKS
Andrew Howroyd, Table of n, a(n) for n = 0..1274
R. J. Mathar, The number of binary nXm matrices with at most k 1's in each row or column, (2014) Table 1.
Eric Weisstein's World of Mathematics, Rook Graph
Eric Weisstein's World of Mathematics, Vertex Cover
Wikipedia, Rook polynomial
FORMULA
E.g.f.: exp(x)/(1-y-xy)=Sum_{i, j} A(i, j) y^j x^i/i!.
A(i, j) = A(i-1, j)+j*A(i-1, j-1)+(i==0) = A(j, i).
T(n, k) = sum{j=0..k, C(n, k-j)*k!/j!} = sum{j=0..k, (k-j)!*C(k, j)C(n, k-j)}. - Paul Barry, Nov 14 2005
A(i,j) = sum_k C(i,k)*C(j,k)*k!. E.g.f.: sum_{i,j} a(i,j)*x^i/i!*y^j/j! = e^{x+y+xy}. - Franklin T. Adams-Watters, Feb 06 2006
The LDU factorization of this array, formatted as a square array, is P * D * transpose(P), where P is Pascal's triangle A007318 and D = diag(0!, 1!, 2!, ... ). Compare with A099597. - Peter Bala, Nov 06 2007
A(i,j) = (-1)^-i HypergeometricU(-i, 1 - i + j, -1). - Eric W. Weisstein, May 10 2017
EXAMPLE
1 1 1 1 1 1 1 1 1
1 2 3 4 5 6 7 8 9
1 3 7 13 21 31 43 57 73
1 4 13 34 73 136 229 358 529
1 5 21 73 209 501 1045 1961 3393
1 6 31 136 501 1546 4051 9276 19081
1 7 43 229 1045 4051 13327 37633 93289
1 8 57 358 1961 9276 37633 130922 394353
1 9 73 529 3393 19081 93289 394353 1441729
MAPLE
A088699 := proc(i, j)
add(binomial(i, k)*binomial(j, k)*k!, k=0..min(i, j)) ;
end proc: # R. J. Mathar, Feb 28 2015
MATHEMATICA
max = 11; se = Series[E^x/(1 - y - x*y), {x, 0, max}, {y, 0, max}] // Normal // Expand; a[i_, j_] := SeriesCoefficient[se, {x, 0, i}, {y, 0, j}]*i!; Flatten[ Table[ a[i - j, j], {i, 0, max}, {j, 0, i}]] (* Jean-François Alcover, May 15 2012 *)
PROG
(PARI) A(i, j)=if(i<0 || j<0, 0, i!*polcoeff(exp(x+x*O(x^i))*(1+x)^j, i))
(PARI) A(i, j)=if(i<0 || j<0, 0, i!*polcoeff(exp(x/(1-x)+x*O(x^i))*(1-x)^(i-j-1), i))
(PARI) A(i, j)=local(M); if(i<0 || j<0, 0, M=matrix(j+1, j+1, n, m, if(n==m, 1, if(n==m+1, m))); (M^i)[j+1, ]*vectorv(j+1, n, 1)) /* Michael Somos, Jul 03 2004 */
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Michael Somos, Oct 08 2003
STATUS
reviewed