login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A088699 Array read by antidiagonals of coefficients of generating function exp(x)/(1-y-xy). 13
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 (list; table; graph; refs; listen; history; text; internal format)
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

Row sums give A081124.

Main diagonal is A002720.

Cf. A099597, A176120.

Sequence in context: A108350 A086617 A094526 * A101515 A327913 A028657

Adjacent sequences:  A088696 A088697 A088698 * A088700 A088701 A088702

KEYWORD

nonn,tabl

AUTHOR

Michael Somos, Oct 08 2003

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 April 16 18:53 EDT 2021. Contains 343050 sequences. (Running on oeis4.)