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

1, 1, 3, 13, 74, 530, 4550, 45570, 521640, 6717480, 96117000, 1512819000, 25975395600, 483169486800, 9678799930800, 207733600074000, 4755768505488000, 115681418156304000, 2979408725813520000, 80998627977002736000, 2317937034142810080000, 69649003197501567840000, 2192459412316607834400000, 72152830779716793506400000, 2477756318984329979756160000

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

Cf. A144422, A000670, A001680.

Column k=3 of A276921.

Sequence in context: A334785 A349533 A020094 * A343787 A333890 A009382

Adjacent sequences: A189883 A189884 A189885 * A189887 A189888 A189889

Keyword

nonn

Author

Adi Dani, Apr 29 2011

Status

approved