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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A141765 Triangle T, read by rows, such that row n equals column 0 of matrix power M^n where M is a triangular matrix defined by M(k+m,k) = binomial(k+m,k) for m=0..2 and zeros elsewhere. Width-2-restricted finite functions. 0
1, 1, 1, 1, 1, 2, 4, 6, 6, 1, 3, 9, 24, 54, 90, 90, 1, 4, 16, 60, 204, 600, 1440, 2520, 2520, 1, 5, 25, 120, 540, 2220, 8100, 25200, 63000, 113400, 113400, 1, 6, 36, 210, 1170, 6120, 29520, 128520, 491400, 1587600, 4082400, 7484400, 7484400, 1, 7, 49, 336, 2226 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

T(k,n) is the number of distinct ways in which n labeled objects can be distributed in k labeled urns allowing at most 2 objects to fall in each urn. - N-E. Fahssi, Apr 22 2009

T(k,n) is the number of functions f:[n]->[k] such that the preimage set under f of any element of [k] has size 2 or less. - Dennis P. Walsh, Feb 15 2011

LINKS

Table of n, a(n) for n=0..53.

Dennis Walsh, Width-restricted finite functions

FORMULA

T(k,n) = n!sum(binomial(k,i)*binomial(i,n-i)*2^(i-n), i=ceiling(n/2)..k). - Dennis P. Walsh, Feb 15 2011

T(n,2*n) = (2n)!/2^n; thus the rightmost border of T equals A000680.

Main diagonal (central terms) equals A012244.

Other diagonals include A036774 and A003692.

Row sums of triangle T equals A003011, the number of permutations of up to n kinds of objects, where each kind of object can occur at most two times.

T(k,n) = n![x^n](1+x+x^2/2)^k. Double E.G.F.: sum_{k,n}(T(k,n)z^k/k!*x^n/n!)=exp(z(1+x+x^2/2)). - N-E. Fahssi, Apr 22 2009

T(j+k,n)=sum(binomial(n,i)*T(j,i)*T(k,n-i),i=0..n). - Dennis P. Walsh, Feb 15 2011

EXAMPLE

This triangle T begins:

1;

1, 1, 1;

1, 2, 4, 6, 6;

1, 3, 9, 24, 54, 90, 90;

1, 4, 16, 60, 204, 600, 1440, 2520, 2520;

1, 5, 25, 120, 540, 2220, 8100, 25200, 63000, 113400, 113400;

1, 6, 36, 210, 1170, 6120, 29520, 128520, 491400, 1587600, 4082400, 7484400, 7484400; ...

Let M be the triangular matrix that begins:

1;

1, 1;

1, 2, 1;

0, 3, 3, 1;

0, 0, 6, 4, 1;

0, 0, 0, 10, 5, 1; ...

where M(k+m,k) = C(k+m,k) for m=0,1,2 and zeros elsewhere.

Illustrate that row n of T = column 0 of M^n for n>=0 as follows.

The matrix square M^2 begins:

1;

2, 1;

4, 4, 1;

6, 12, 6, 1;

6, 24, 24, 8, 1;

0, 30, 60, 40, 10, 1; ...

with column 0 of M^2 forming row 2 of T.

The matrix cube M^3 begins:

1;

3, 1;

9, 6, 1;

24, 27, 9, 1;

54, 96, 54, 12, 1;

90, 270, 240, 90, 15, 1;

90, 540, 810, 480, 135, 18, 1; ...

with column 0 of M^3 forming row 3 of T.

T(2,3)=6 because there are 6 ways to lodge 3 distinguishable balls, labeled by numbers 1,2 and 3, in 2 distinguishable boxes, each of which can hold at most 2 balls. - N-E. Fahssi, Apr 22 2009

T(5,8)=63000 because there are 63000 ways to assign 8 students to a dorm room when there are 5 different two-bed dorm rooms that are available. (See link for details of the count.) - Dennis P. Walsh, Feb 15 2011

MAPLE

seq(seq(n!*sum(binomial(k, j)*binomial(j, n-j)*2^(j-n), j=ceil(n/2)..k), n=0..2*k), k=1..10); # Dennis P. Walsh, Feb 15 2011

MATHEMATICA

T[k_, n_] := If[n == 0, 1, n! Coefficient[(1 + x + x^2/2)^k, x^n]]; TableForm[Table[T[k, n], {k, 0, 10}, {n, 0, 2 k}]] (* N-E. Fahssi, Apr 22 2009 *)

PROG

(PARI) {T(n, k)=local(M=matrix(n+1, n+1, n, k, if(n>=k, if(n-k<=2, binomial(n-1, k-1))))); if(k>2*n, 0, (M^n)[k+1, 1])}

CROSSREFS

Cf. A003011 (row sums), A000680 (right border); diagonals: A012244, A036774, A003692.

Sequence in context: A083718 A055948 A071083 * A234574 A010587 A213473

Adjacent sequences:  A141762 A141763 A141764 * A141766 A141767 A141768

KEYWORD

nonn,tabf

AUTHOR

Paul D. Hanna, Jul 28 2008

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 22 06:47 EDT 2014. Contains 248388 sequences.