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
Examples
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]
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.
Programs
-
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 -
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
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.
Extensions
Terms a(44) and a(47) corrected by G. C. Greubel, Jan 16 2018
Comments