A088699 Array read by antidiagonals of coefficients of generating function exp(x)/(1-y-xy).

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 4, 1, 1, 5, 13, 13, 5, 1, 1, 6, 21, 34, 21, 6, 1, 1, 7, 31, 73, 73, 31, 7, 1, 1, 8, 43, 136, 209, 136, 43, 8, 1, 1, 9, 57, 229, 501, 501, 229, 57, 9, 1, 1, 10, 73, 358, 1045, 1546, 1045, 358, 73, 10, 1, 1, 11, 91, 529, 1961, 4051, 4051, 1961

Offset: 0

Author

Michael Somos, Oct 08 2003

Keywords

• nonn
• tabl

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

Examples

			      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
		

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

Crossrefs

Row sums give A081124.

Main diagonal is A002720.

Cf. A099597, A176120.

Programs

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

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

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