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.

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,1

Comments

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

Links

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

Formula

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

Example

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;
  ...

Maple

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

Mathematica

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

Prog

(Sage) 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
(Magma) [Factorial(k)*Evaluate(LaguerrePolynomial(k, n-k), -1): k in [1..n], n in [1..10]]; // G. C. Greubel, Feb 23 2021
(PARI) T(i, j) = j!*pollaguerre(j, i-j, -1); \\ Michel Marcus, Feb 23 2021

Crossrefs

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.

Sequence in context: A287628 A319863 A320948 * A324598 A229794 A331318

Adjacent sequences: A086882 A086883 A086884 * A086886 A086887 A086888

Keyword

nonn,easy,tabl

Author

Hugo Pfoertner, Aug 22 2003

Status

approved