|
%I #39 Feb 27 2018 02:51:45
%S 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,
%T 73,73,31,7,1,1,8,43,136,209,136,43,8,1,1,9,57,229,501,501,229,57,9,1,
%U 1,10,73,358,1045,1546,1045,358,73,10,1,1,11,91,529,1961,4051,4051,1961
%N Array read by antidiagonals of coefficients of generating function exp(x)/(1-y-xy).
%C 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
%C Compare with A086885. - _Peter Bala_, Sep 17 2008
%C 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
%H Andrew Howroyd, <a href="/A088699/b088699.txt">Table of n, a(n) for n = 0..1274</a>
%H R. J. Mathar, <a href="/A247158/a247158.pdf">The number of binary nXm matrices with at most k 1's in each row or column</a>, (2014) Table 1.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Rook_polynomial">Rook polynomial</a>
%F E.g.f.: exp(x)/(1-y-xy)=Sum_{i, j} A(i, j) y^j x^i/i!.
%F A(i, j) = A(i-1, j)+j*A(i-1, j-1)+(i==0) = A(j, i).
%F 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
%F 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
%F 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
%F A(i,j) = (-1)^-i HypergeometricU(-i, 1 - i + j, -1). - _Eric W. Weisstein_, May 10 2017
%e 1 1 1 1 1 1 1 1 1
%e 1 2 3 4 5 6 7 8 9
%e 1 3 7 13 21 31 43 57 73
%e 1 4 13 34 73 136 229 358 529
%e 1 5 21 73 209 501 1045 1961 3393
%e 1 6 31 136 501 1546 4051 9276 19081
%e 1 7 43 229 1045 4051 13327 37633 93289
%e 1 8 57 358 1961 9276 37633 130922 394353
%e 1 9 73 529 3393 19081 93289 394353 1441729
%p A088699 := proc(i,j)
%p add(binomial(i,k)*binomial(j,k)*k!,k=0..min(i,j)) ;
%p end proc: # _R. J. Mathar_, Feb 28 2015
%t 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 *)
%o (PARI) A(i,j)=if(i<0 || j<0,0,i!*polcoeff(exp(x+x*O(x^i))*(1+x)^j,i))
%o (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))
%o (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 */
%Y Row sums give A081124.
%Y Main diagonal is A002720.
%Y Cf. A099597, A176120.
%K nonn,tabl
%O 0,5
%A _Michael Somos_, Oct 08 2003
|
