|
| |
|
|
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
|
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
|
|
|
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 *)
|
|
|
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: A168085 A287950 A287628 * A229794 A082734 A021425
Adjacent sequences: A086882 A086883 A086884 * A086886 A086887 A086888
|
|
|
KEYWORD
|
nonn,easy,tabl
|
|
|
AUTHOR
|
Hugo Pfoertner, Aug 22 2003
|
|
|
STATUS
|
approved
|
| |
|
|
