login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 6
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 (list; graph; refs; listen; history; text; internal format)
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: A156154 A334785 A020094 * A333890 A009382 A110193

Adjacent sequences:  A189883 A189884 A189885 * A189887 A189888 A189889

KEYWORD

nonn

AUTHOR

Adi Dani, Apr 29 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 11 23:56 EDT 2021. Contains 342909 sequences. (Running on oeis4.)