login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 06:59 EDT 2018. Contains 315226 sequences. (Running on oeis4.)