A189804 Triangle read by rows: T(n,k) is the number of compositions of set {1, 2, ..., k} into exactly n blocks, each of size 1, 2 or 3 (n >= 0, 0 <= k <= 3*n).

1, 0, 1, 1, 1, 0, 0, 2, 6, 14, 20, 20, 0, 0, 0, 6, 36, 150, 450, 1050, 1680, 1680, 0, 0, 0, 0, 24, 240, 1560, 7560, 29400, 90720, 218400, 369600, 369600, 0, 0, 0, 0, 0, 120, 1800, 16800, 117600, 667800, 3137400, 12243000, 38808000, 96096000, 168168000, 168168000

Offset

0,8

Comments

Row n has 3*n+1 entries.

Column sums give A188896, row sums give A144422. - Adi Dani, May 14 2011

Links

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened

Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394 [math.CO], 2017.

David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009.

Formula

T(n, k) = k*T(n-1, k-1) + (1/2)*k*(k-1)*T(n-1, k-2) + (1/6)*k*(k-1)*(k-2)*T(n-1, k-3).

E.g.f.: sum(n>=0, T(n, k)*x^k/k!) = (x+x^2/2+x^3/6)^k.

Example

Triangle begins:
[1]
[0, 1, 1, 1]
[0, 0, 2, 6, 14, 20, 20]
[0, 0, 0, 6, 36, 150, 450, 1050, 1680, 1680]
[0, 0, 0, 0, 24, 240, 1560, 7560, 29400, 90720, 218400, 369600, 369600]
[0, 0, 0, 0, 0, 120, 1800, 16800, 117600, 667880, 3137400, 12243000, 3880800, 96096000, 168168000, 168168000]

Maple

T := proc(n, k)
option remember;
if n = k then 1;
elif k < n then 0;
elif n < 1 then 0;
else =k *T(n - 1, k - 1) +  (1/2)*k*(k - 1)*T(n - 1, k - 2)+ (1/6)*k* (k - 1)*(k - 2)*T(n - 1, k - 3);
end if;
end proc; for n from 0 to 12 do lprint([seq(T(n, k), k=0..3*n)]); od:

Mathematica

Table[Sum[ n!/(2^(n + j - 2m)3^(m - j))Binomial[m, j]Binomial[j, n + 2j - 3m], {j, 0, 3m - n}], {m, 0, 5}, {n, 0, 3m}]//Flatten

Prog

(PARI) for(m=0, 7, for(n=0, 3*m, print1(sum(j=0, 3*m-n, (n!/(2^(n+j-2*m)*3^(m-j)))*binomial(m, j)*binomial(j, n+2*j-3*m)), ", "))) \\ G. C. Greubel, Jan 16 2018

Crossrefs

Sequence in context: A163777 A215807 A140525 * A308394 A246068 A032643

Adjacent sequences: A189801 A189802 A189803 * A189805 A189806 A189807

Keyword

nonn,tabf

Author

Adi Dani, Apr 27 2011

Extensions

Terms a(44) and a(47) corrected by G. C. Greubel, Jan 16 2018

Status

approved