A176120 -id:A176120 - cp's OEIS frontend

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

Michael Somos, Oct 08 2003

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

			      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

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

Row sums give A081124.
Main diagonal is A002720.
Cf. A099597, A176120.

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

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

A(i,j)=if(i<0 || j<0,0,i!*polcoeff(exp(x+x*O(x^i))*(1+x)^j,i))

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

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

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

A086885 Lower triangular matrix, read by rows: T(i,j) = number of ways i seats can be occupied by any number k (0<=k<=j<=i) of persons.

Original entry on oeis.org

2, 3, 7, 4, 13, 34, 5, 21, 73, 209, 6, 31, 136, 501, 1546, 7, 43, 229, 1045, 4051, 13327, 8, 57, 358, 1961, 9276, 37633, 130922, 9, 73, 529, 3393, 19081, 93289, 394353, 1441729, 10, 91, 748, 5509, 36046, 207775, 1047376, 4596553, 17572114, 11, 111, 1021, 8501

Offset: 1

Hugo Pfoertner, Aug 22 2003

Compare with A088699. - Peter Bala, Sep 17 2008

T(m, n) gives the number of matchings in the complete bipartite graph K_{m,n}. - Eric W. Weisstein, Apr 25 2017

			One person:
T(1,1)=a(1)=2: 0,1 (seat empty or occupied);
T(2,1)=a(2)=3: 00,10,01 (both seats empty, left seat occupied, right seat occupied).
Two persons:
T(2,2)=a(3)=7: 00,10,01,20,02,12,21;
T(3,2)=a(5)=13: 000,100,010,001,200,020,002,120,102,012,210,201,021.
Triangle starts:
  2;
  3  7;
  4 13  34;
  5 21  73 209;
  6 31 136 501 1546;
  ...

Robert Israel, Table of n, a(n) for n = 1..10011 (rows 1 to 141, flattened)
Ed Jones, Number of seatings, discussion in newsgroup sci.math, Aug 9, 2003.
R. J. Mathar, The number of binary nxm matrices with at most k 1's in each row or columns, Table 1.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Luca Zecchini, Tobias Bleifuß, Giovanni Simonini, Sonia Bergamaschi, and Felix Naumann, Determining the Largest Overlap between Tables, Proc. ACM Manag. Data (SIGMOD 2024) Vol. 2, No. 1, Art. 48. See p. 48:6.
Index entries for sequences related to Laguerre polynomials

Diagonal: A002720, first subdiagonal: A000262, 2nd subdiagonal: A052852, 3rd subdiagonal: A062147, 4th subdiagonal: A062266, 5th subdiagonal: A062192, 2nd row/column: A002061. With column 0: A176120.

[Factorial(k)*Evaluate(LaguerrePolynomial(k, n-k), -1): k in [1..n], n in [1..10]]; // G. C. Greubel, Feb 23 2021

A086885 := proc(n,k)
    add( binomial(n,j)*binomial(k,j)*j!,j=0..min(n,k)) ;
end proc: # R. J. Mathar, Dec 19 2014

Table[Table[Sum[k! Binomial[n, k] Binomial[j, k], {k, 0, j}], {j, 1, n}], {n, 1, 10}] // Grid (* Geoffrey Critzer, Jul 09 2015 *)
Table[m! LaguerreL[m, n - m, -1], {n, 10}, {m, n}] // Flatten (* Eric W. Weisstein, Apr 25 2017 *)

T(i, j) = j!*pollaguerre(j, i-j, -1); \\ Michel Marcus, Feb 23 2021

flatten([[factorial(k)*gen_laguerre(k, n-k, -1) for k in [1..n]] for n in (1..10)]) # G. C. Greubel, Feb 23 2021

a(n) = T(i, j) with n=(i*(i-1))/2+j; T(i, 1)=i+1, T(i, j)=T(i, j-1)+i*T(i-1, j-1) for j>1.
The role of seats and persons may be interchanged, so T(i, j)=T(j, i).
T(i, j) = j!*LaguerreL(j, i-j, -1). - Vladeta Jovovic, Aug 25 2003
T(i, j) = Sum_{k=0..j} k!*binomial(i, k)*binomial(j, k). - Vladeta Jovovic, Aug 25 2003

A293985 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals, where column k is the expansion of e.g.f. exp(x/(1-x))/(1-x)^k.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 7, 13, 1, 4, 13, 34, 73, 1, 5, 21, 73, 209, 501, 1, 6, 31, 136, 501, 1546, 4051, 1, 7, 43, 229, 1045, 4051, 13327, 37633, 1, 8, 57, 358, 1961, 9276, 37633, 130922, 394353, 1, 9, 73, 529, 3393, 19081, 93289, 394353, 1441729, 4596553

Offset: 0

Seiichi Manyama, Oct 21 2017

			Square array begins:
    1,    1,    1,    1,     1, ... A000012;
    1,    2,    3,    4,     5, ... A000027;
    3,    7,   13,   21,    31, ... A002061;
   13,   34,   73,  136,   229, ... A135859;
   73,  209,  501, 1045,  1961, ...
  501, 1546, 4051, 9276, 19081, ...
Antidiagonal rows begin as:
  1;
  1, 1;
  1, 2,  3;
  1, 3,  7, 13;
  1, 4, 13, 34,  73;
  1, 5, 21, 73, 209, 501; - _G. C. Greubel_, Mar 09 2021

Seiichi Manyama, Antidiagonals n = 0..139, flattened
Wikipedia, Laguerre polynomials
Index entries for sequences related to Laguerre polynomials

Columns k=0..6 give: A000262, A002720, A000262(n+1), A052852(n+1), A062147, A062266, A062192.
Main diagonal gives A152059.
Similar table: A086885, A088699, A176120.

function t(n,k)
  if n eq 0 then return 1;
  else return Factorial(n-1)*(&+[(j+k)*t(n-j,k)/Factorial(n-j): j in [1..n]]);
  end if; return t;
end function;
[t(k,n-k): k in [0..n], n in [0..12]]; // G. C. Greubel, Mar 09 2021

t[n_, k_]:= t[n, k]= If[n==0, 1, (n-1)!*Sum[(j+k)*t[n-j,k]/(n-j)!, {j,n}]];
T[n_,k_]:= t[k,n-k]; Table[T[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Mar 09 2021 *)

@CachedFunction
def t(n,k): return 1 if n==0 else factorial(n-1)*sum( (j+k)*t(n-j,k)/factorial(n-j) for j in (1..n) )
def T(n,k): return t(k,n-k)
flatten([[T(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Mar 09 2021

A(0,k) = 1 and A(n,k) = (n-1)! * Sum_{j=1..n} (j+k)*A(n-j,k)/(n-j)! for n > 0.
A(0,k) = 1, A(1,k) = k+1 and A(n,k) = (2*n-1+k)*A(n-1,k) - (n-1)*(n-2+k)*A(n-2,k) for n > 1.
From Seiichi Manyama, Jan 25 2025: (Start)
A(n,k) = n! * Sum_{j=0..n} binomial(n+k-1,j)/(n-j)!.
A(n,k) = n! * LaguerreL(n, k-1, -1). (End)

A129833 a(n) = Sum_{k = 0..n } binomial(n + 1, k + 1)binomial(n, k)k!.

Original entry on oeis.org

1, 3, 11, 52, 309, 2221, 18703, 180216, 1952457, 23466223, 309577971, 4444537868, 68948023741, 1148825560377, 20455144724407, 387479309532976, 7778881684953873, 164942847995071611, 3682885668837002587, 86359724102207331876, 2121535102985378053061, 54482075844410029721893, 1459677302947807284662751

Offset: 0

Roger L. Bagula, May 21 2007

Seiichi Manyama, Table of n, a(n) for n = 0..443
F. Hivert, J.-C. Novelli and J.-Y. Thibon, Commutative combinatorial Hopf algebras, arXiv:math/0605262 [math.CO], 2006.

Cf. A052852, A176120.

[(&+[Binomial(n,k)^2*((n+1)*Factorial(k)/(k+1)): k in [0..n]]): n in [0..30]]; // G. C. Greubel, Mar 10 2021

A129833 := proc(n)
    add(A176120(n,k),k=0..n) ;
end proc: # R. J. Mathar, Feb 28 2015

a[n_]:= Sum[Binomial[n+1, k+1]*Binomial[n, k]*k!, {k,0,n}]; Table[a[n], {n,0,30}]

a(n) = sum(k= 0, n, binomial(n+1, k+1)*binomial(n, k)*k!); \\ Michel Marcus, Mar 10 2021

[sum( binomial(n,k)^2*((n+1)*factorial(k)/(k+1)) for k in (0..n)) for n in (0..30)] # G. C. Greubel, Mar 10 2021

Conjecture: +(n+1)*a(n) -n*(2*n+5)*a(n-1) +(n-1)*(n^2+6*n+3)*a(n-2) -(n-2)*(3*n^2-2)*a(n-3) +(n-2)*(n-3)*(3*n-4)*a(n-4) -(n-4)*(n-3)^2*a(n-5) = 0. - R. J. Mathar, Feb 28 2015
Conjecture: (n+1)*(n^2-4*n+2)*a(n) -n*(2*n^3-5*n^2-6*n+3)*a(n-1) +n*(n-1)*(n^3-2*n^2-2*n-2)*a(n-2) -(n-2)*(n^2-2*n-1)*(n-1)^2*a(n-3) = 0. - R. J. Mathar, Feb 28 2015
a(n) ~ exp(2*sqrt(n) - n - 1/2) * n^(n + 1/4) / sqrt(2) * (1 + 79/(48*sqrt(n))). - Vaclav Kotesovec, Oct 12 2016
From G. C. Greubel, Mar 10 2021: (Start)
a(n) = Sum_{k=0..n} binomial(n,k)^2 * ((n+1)*k!/(k+1)).
a(n) = (n+1)*Hypergeometric3F1([-n, -n, 1], [2], 1). (End)

Edited by N. J. A. Sloane, Sep 30 2007

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

PARI

Formula

A086885 Lower triangular matrix, read by rows: T(i,j) = number of ways i seats can be occupied by any number k (0<=k<=j<=i) of persons.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A293985 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals, where column k is the expansion of e.g.f. exp(x/(1-x))/(1-x)^k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

A129833 a(n) = Sum_{k = 0..n } binomial(n + 1, k + 1)*binomial(n, k)*k!.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

A129833 a(n) = Sum_{k = 0..n } binomial(n + 1, k + 1)binomial(n, k)k!.