A192012 Number of ways to use the elements of set {1,..,k}, 0<=k<=3*n, once each to form a collection of n (possibly empty) sets, each with at most 3 elements.

1, 4, 35, 877, 46173, 4108044, 550917287, 103674052788, 26046619272535, 8420151470990221, 3404266960229749907, 1682802564587905472500, 998472258682783813839141, 700281698972322460184258208, 573086115189070229131370358179, 541208343386984031504989621465925

Offset

0,2

Comments

Number of partitions of the set {0,1,...,3*n} into n parts of size <=3.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..100

R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.

Formula

a(n) = Sum_{k=0..3*n} Sum_{i=0..n} Sum_{j=0..3*i-k} k! *C(i,j) *C(j,k+2*j-3*i) / (i! * 3^(i-j) * 2^(k+j-2*i) ).

Example

a(0)=1=card{[e]})
a(1)=4=card{[e],[1],[12],[123]})
a(2) = 35 = card({ [e,e],[e,1],[e,12],[1,2],[e,123],[1,23],[2,13],[3,12],
[1,234],[2,134],[3,124],[4,123],[12,34],[13,24],[14,23],[12,345],[13,245],[14,235],[15,324],[23,145],[24,135],[25,134],[34,125],[35,124],[45,123],
[123,456],[124,356],[125,346],[126,345],[134,256],[135,246],[136,245],[145,236],[146,235],[156,234] }) where e denotes the empty set.

Mathematica

Table[Sum[k!/(i!3^(i - j)2^(k + j - 2i))Binomial[i, j] Binomial[j, k + 2j - 3i], {k, 0, 3n}, {i, 0, n}, {j, 0, 3i - k}], {n, 0, 15}]

Crossrefs

Partial sums of A144416.

Sequence in context: A129581 A356544 A120055 * A076818 A005026 A268416

Adjacent sequences: A192009 A192010 A192011 * A192013 A192014 A192015

Keyword

nonn

Author

Adi Dani, Jun 22 2011

Status

approved