login
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

%I #26 Jan 17 2018 03:50:09

%S 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,

%T 24,240,1560,7560,29400,90720,218400,369600,369600,0,0,0,0,0,120,1800,

%U 16800,117600,667800,3137400,12243000,38808000,96096000,168168000,168168000

%N 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).

%C Row n has 3*n+1 entries.

%C Column sums give A188896, row sums give A144422. - _Adi Dani_, May 14 2011

%H G. C. Greubel, <a href="/A189804/b189804.txt">Table of n, a(n) for the first 50 rows, flattened</a>

%H Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, <a href="http://arxiv.org/abs/1701.08394">Analysis of the Gift Exchange Problem</a>, arXiv:1701.08394 [math.CO], 2017.

%H David Applegate and N. J. A. Sloane, <a href="http://arxiv.org/abs/0907.0513">The Gift Exchange Problem</a>, arXiv:0907.0513 [math.CO], 2009.

%F 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).

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

%e Triangle begins:

%e [1]

%e [0, 1, 1, 1]

%e [0, 0, 2, 6, 14, 20, 20]

%e [0, 0, 0, 6, 36, 150, 450, 1050, 1680, 1680]

%e [0, 0, 0, 0, 24, 240, 1560, 7560, 29400, 90720, 218400, 369600, 369600]

%e [0, 0, 0, 0, 0, 120, 1800, 16800, 117600, 667880, 3137400, 12243000, 3880800, 96096000, 168168000, 168168000]

%p T := proc(n, k)

%p option remember;

%p if n = k then 1;

%p elif k < n then 0;

%p elif n < 1 then 0;

%p 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);

%p end if;

%p end proc; for n from 0 to 12 do lprint([seq(T(n, k), k=0..3*n)]); od:

%t 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

%o (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

%K nonn,tabf

%O 0,8

%A _Adi Dani_, Apr 27 2011

%E Terms a(44) and a(47) corrected by _G. C. Greubel_, Jan 16 2018