cp's OEIS Frontend

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

%I A189804 #26 Jan 17 2018 03:50:09
%S A189804 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 A189804 24,240,1560,7560,29400,90720,218400,369600,369600,0,0,0,0,0,120,1800,
%U A189804 16800,117600,667800,3137400,12243000,38808000,96096000,168168000,168168000
%N 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).
%C A189804 Row n has 3*n+1 entries.
%C A189804 Column sums give A188896, row sums give A144422. - _Adi Dani_, May 14 2011
%H A189804 G. C. Greubel, <a href="/A189804/b189804.txt">Table of n, a(n) for the first 50 rows, flattened</a>
%H A189804 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 A189804 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 A189804 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 A189804 E.g.f.: sum(n>=0, T(n, k)*x^k/k!) = (x+x^2/2+x^3/6)^k.
%e A189804 Triangle begins:
%e A189804 [1]
%e A189804 [0, 1, 1, 1]
%e A189804 [0, 0, 2, 6, 14, 20, 20]
%e A189804 [0, 0, 0, 6, 36, 150, 450, 1050, 1680, 1680]
%e A189804 [0, 0, 0, 0, 24, 240, 1560, 7560, 29400, 90720, 218400, 369600, 369600]
%e A189804 [0, 0, 0, 0, 0, 120, 1800, 16800, 117600, 667880, 3137400, 12243000, 3880800, 96096000, 168168000, 168168000]
%p A189804 T := proc(n, k)
%p A189804 option remember;
%p A189804 if n = k then 1;
%p A189804 elif k < n then 0;
%p A189804 elif n < 1 then 0;
%p A189804 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 A189804 end if;
%p A189804 end proc; for n from 0 to 12 do lprint([seq(T(n, k), k=0..3*n)]); od:
%t A189804 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 A189804 (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 A189804 nonn,tabf
%O A189804 0,8
%A A189804 _Adi Dani_, Apr 27 2011
%E A189804 Terms a(44) and a(47) corrected by _G. C. Greubel_, Jan 16 2018