A144385 Triangle read by rows: T(n,k) is the number of partitions of [1, 2, ..., k] into exactly n blocks, each of size 1, 2 or 3 (n >= 0, 0 <= k <= 3n).

1, 0, 1, 1, 1, 0, 0, 1, 3, 7, 10, 10, 0, 0, 0, 1, 6, 25, 75, 175, 280, 280, 0, 0, 0, 0, 1, 10, 65, 315, 1225, 3780, 9100, 15400, 15400, 0, 0, 0, 0, 0, 1, 15, 140, 980, 5565, 26145, 102025, 323400, 800800, 1401400, 1401400, 0, 0, 0, 0, 0, 0, 1, 21, 266, 2520, 19425, 125895, 695695, 3273270, 12962950, 42042000, 106506400, 190590400, 190590400

Offset

0,9

Comments

Row n has 3n+1 entries.

Links

Table of n, a(n) for n=0..69.

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)

Formula

T(n, k) = T(n - 1, k - 1) + (k - 1)*T(n - 1, k - 2) + (1/2)*(k - 1)*(k - 2)*T(n - 1, k - 3).

E.g.f.: Sum_{ n >= 0, k >= 0 } T(n, k) y^n x^k / k! = exp( y*(x+x^2/2+x^3/6) ). That is, the coefficient of y^n is the e.g.f. for row n. E.g. the e.g.f. for row 2 is (1/2)*(x+x^2/2+x^3/6)^2 = 1*x^2/2! + 3*x^3/3! + 7*x^4/4! + 10*x^5/5! + 10*x^6/6!.

Example

Triangle begins:
[1]
[0, 1, 1, 1]
[0, 0, 1, 3, 7, 10, 10]
[0, 0, 0, 1, 6, 25, 75, 175, 280, 280]
[0, 0, 0, 0, 1, 10, 65, 315, 1225, 3780, 9100, 15400, 15400]
[0, 0, 0, 0, 0, 1, 15, 140, 980, 5565, 26145, 102025, 323400, 800800, 1401400, 1401400]

Maple

T := proc(n, k)
option remember;
if n = k then 1;
elif k < n then 0;
elif n < 1 then 0;
else T(n - 1, k - 1) + (k - 1)*T(n - 1, k - 2) + 1/2*(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:

Mathematica

t[n_, n_] = 1; t[n_ /; n >= 0, k_] /; 0 <= k <= 3*n := t[n, k] = t[n-1, k-1] + (k-1)*t[n-1, k-2] + (1/2)*(k-1)*(k-2)*t[n-1, k-3]; t[_, _] = 0; Table[t[n, k], {n, 0, 12}, {k, 0, 3*n}] // Flatten (* Jean-François Alcover, Jan 14 2014 *)

Crossrefs

See A144399, A144402, A144417, A111246 for other versions of this triangle.

Column sums give A001680, row sums give A144416. Taking last nonzero entry in each row gives A025035.

Diagonals include A000217, A001296, A027778, A144516; also A025035.

A generalization of the triangle in A144331 (and in several other entries).

Cf. A144643.

Sequence in context: A381762 A112105 A065501 * A144399 A310176 A138935

Adjacent sequences: A144382 A144383 A144384 * A144386 A144387 A144388

Keyword

nonn,tabf

Author

David Applegate and N. J. A. Sloane, Dec 07 2008, Dec 17 2008

Status

approved