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.
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
KEYWORD
AUTHOR
Hugo Pfoertner, Aug 22 2003
STATUS
approved