OFFSET
0,3
COMMENTS
Sequences of sets, each set having no more than 3 elements.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..424
Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394, 2017.
David Applegate and N. J. A. Sloane, The Gift Exchange Problem (arXiv:0907.0513, 2009)
Adi Dani, Compositions and partitions of sets
FORMULA
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.
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
E.g.f.: 1/(1 - x - x^2/2 - x^3/6). - Geoffrey Critzer, Dec 04 2012
EXAMPLE
a(3) = 13 because all compositions of set {a,b,c} into blocks of size 1, 2, or 3 are:
1: ({a,b,c}),
2: ({a},{b,c}),
3: ({b,c},{a}),
4: ({b},{a,c}),
5: ({a,c},{b}),
6: ({c},{a,b}),
7: ({a,b},{c}),
8: ({a},{b},{c}),
9: ({a},{c},{b}),
10: ({b},{a},{c}),
11: ({b},{c},{a}),
12: ({c},{a},{b}),
13: ({c},{b},{a}).
MAPLE
A189886 := proc(n) local m, j; add(add(2^(2*m-n-j)*3^(j-m)*n!
*binomial(m, j)*binomial(j, 2*j-(3*m-n)), j=0..3*m-n), m=0..n) end:
seq(A189886(n), n=0..24); # Peter Luschny, May 02 2011
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
a(n-i)*binomial(n, i), i=1..min(n, 3)))
end:
seq(a(n), n=0..25); # Alois P. Heinz, Sep 22 2016
# third Maple program:
a:= n-> n! * (<<0|1|0>, <0|0|1>, <1/6|1/2|1>>^n)[3, 3]:
seq(a(n), n=0..25); # Alois P. Heinz, Sep 22 2016
MATHEMATICA
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}]
PROG
(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 */
CROSSREFS
KEYWORD
nonn
AUTHOR
Adi Dani, Apr 29 2011
STATUS
approved