A144422 -id:A144422 - cp's OEIS frontend

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

Adi Dani, Apr 29 2011

nonn

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

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

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

Cf. A144422, A000670, A001680.

Column k=3 of A276921.

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

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}]

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 */

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

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

Original entry on oeis.org

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, 24, 240, 1560, 7560, 29400, 90720, 218400, 369600, 369600, 0, 0, 0, 0, 0, 120, 1800, 16800, 117600, 667800, 3137400, 12243000, 38808000, 96096000, 168168000, 168168000

Offset: 0

Adi Dani, Apr 27 2011

Row n has 3*n+1 entries.

Column sums give A188896, row sums give A144422. - Adi Dani, May 14 2011

			Triangle begins:
[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, 24, 240, 1560, 7560, 29400, 90720, 218400, 369600, 369600]
[0, 0, 0, 0, 0, 120, 1800, 16800, 117600, 667880, 3137400, 12243000, 3880800, 96096000, 168168000, 168168000]

G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
Moa Apagodu, David Applegate, N. J. A. Sloane, and Doron Zeilberger, Analysis of the Gift Exchange Problem, arXiv:1701.08394 [math.CO], 2017.
David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009.

T := proc(n, k)
option remember;
if n = k then 1;
elif k < n then 0;
elif n < 1 then 0;
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);
end if;
end proc; for n from 0 to 12 do lprint([seq(T(n, k), k=0..3*n)]); od:

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

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

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

E.g.f.: sum(n>=0, T(n, k)*x^k/k!) = (x+x^2/2+x^3/6)^k.

Terms a(44) and a(47) corrected by G. C. Greubel, Jan 16 2018

cp's OEIS Frontend

A144906 a(0) = 1; thereafter a(n) = A144422(n)/n.

Views

Author

Keywords

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Programs

Maple

Mathematica

PARI

Formula

Extensions