%I #47 Jan 30 2017 21:24:44

%S 1,1,3,13,74,530,4550,45570,521640,6717480,96117000,1512819000,

%T 25975395600,483169486800,9678799930800,207733600074000,

%U 4755768505488000,115681418156304000,2979408725813520000,80998627977002736000,2317937034142810080000,69649003197501567840000,2192459412316607834400000,72152830779716793506400000,2477756318984329979756160000

%N a(n) is the number of compositions of the set {1, 2, ..., n} into blocks, each of size 1, 2 or 3 (n >= 0).

%C Sequences of sets, each set having no more than 3 elements.

%H Alois P. Heinz, <a href="/A189886/b189886.txt">Table of n, a(n) for n = 0..424</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, 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, 2009)

%H Adi Dani, <a href="https://oeis.org/wiki/User:Adi_Dani_/Compositions_and_Partitions_of_sets">Compositions and partitions of sets</a>

%F a(n) = sum(m=0..n, sum(j=0..3*m-n, n!/(2^(n+j-2*m) * 3^(m-j)) * C(m,j) * C(j,n+2*j-3*m))) where C(n,k) is the binomial coefficient.

%F a(n) = n * a(n-1) + n*(n-1)/2 * a(n-2) + n*(n-1)*(n-2)/6 * a(n-3). - _Istvan Mezo_, Jun 06 2013

%F E.g.f.: 1/(1 - x - x^2/2 - x^3/6). - _Geoffrey Critzer_, Dec 04 2012

%e a(3) = 13 because all compositions of set {a,b,c} into blocks of size 1, 2, or 3 are:

%e 1: ({a,b,c}),

%e 2: ({a},{b,c}),

%e 3: ({b,c},{a}),

%e 4: ({b},{a,c}),

%e 5: ({a,c},{b}),

%e 6: ({c},{a,b}),

%e 7: ({a,b},{c}),

%e 8: ({a},{b},{c}),

%e 9: ({a},{c},{b}),

%e 10: ({b},{a},{c}),

%e 11: ({b},{c},{a}),

%e 12: ({c},{a},{b}),

%e 13: ({c},{b},{a}).

%p A189886 := proc(n) local m, j; add(add(2^(2*m-n-j)*3^(j-m)*n!

%p *binomial(m,j)*binomial(j,2*j-(3*m-n)),j=0..3*m-n),m=0..n) end:

%p seq(A189886(n),n=0..24); # _Peter Luschny_, May 02 2011

%p # second Maple program:

%p a:= proc(n) option remember; `if`(n=0, 1, add(

%p a(n-i)*binomial(n, i), i=1..min(n, 3)))

%p end:

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Sep 22 2016

%p # third Maple program:

%p a:= n-> n! * (<<0|1|0>, <0|0|1>, <1/6|1/2|1>>^n)[3, 3]:

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Sep 22 2016

%t Table[Sum[n!/(2^(n+j-2m)3^(m-j))*Binomial[m,j]*Binomial[j,n+2j-3m], {m,0,n},{j,0,3m-n}],{n,0,15}]

%o (PARI) a(n)=sum(m=0,n, 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))); /* _Joerg Arndt_, May 03 2011 */

%Y Cf. A144422, A000670, A001680.

%Y Column k=3 of A276921.

%K nonn

%O 0,3

%A _Adi Dani_, Apr 29 2011