|
|
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.
|
|
10
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
T(m, n) gives the number of matchings in the complete bipartite graph K_{m,n}. - Eric W. Weisstein, Apr 25 2017
|
|
LINKS
|
Eric Weisstein's World of Mathematics, Matching
|
|
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) = 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
|
add( binomial(n, j)*binomial(k, j)*j!, j=0..min(n, k)) ;
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|