A144643 Triangle read by rows: T(n,k) = number of partitions of [1..k] into n nonempty clumps of sizes 1, 2, 3 or 4 (n >= 0, 0 <= k <= 4n).

1, 0, 1, 1, 1, 1, 0, 0, 1, 3, 7, 15, 25, 35, 35, 0, 0, 0, 1, 6, 25, 90, 280, 770, 1855, 3675, 5775, 5775, 0, 0, 0, 0, 1, 10, 65, 350, 1645, 6930, 26425, 90475, 275275, 725725, 1576575, 2627625, 2627625, 0, 0, 0, 0, 0, 1, 15, 140, 1050, 6825, 39795, 211750, 1033725, 4629625

Offset: 0

Author

David Applegate and N. J. A. Sloane, Jan 25 2009

Keywords

• nonn
• tabf

Examples

			Irregular triangle begins:
  1;
  0, 1, 1, 1, 1;
  0, 0, 1, 3, 7, 15, 25,  35,  35;
  0, 0, 0, 1, 6, 25, 90, 280, 770, 1855, 3675, 5775, 5775;
  ...
		

Links

• G. C. Greubel, Rows n = 0..25 of the irregular triangle, 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.

Crossrefs

Row sums give A144508.

See A144644 and A144645 for other versions.

Cf. A144299, A144385.

Programs

Magma

function t(n,k)
  if k eq n then return 1;
  elif k le n-1 or n le 0 then return 0;
  else return (&+[Binomial(k-1,j)*t(n-1,k-j-1): j in [0..3]]);
  end if;
end function;
A144643:= func< n,k | t(n,k) >;
[A144643(n,k): k in [0..4*n], n in [0..8]]; // G. C. Greubel, Oct 11 2023

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) + 1/6*(k - 1)*(k - 2)*(k - 3)*T(n - 1, k - 4);
end if;
end proc;

Mathematica

T[n_, k_]:= T[n, k]= Which[n==k, 1, kJean-François Alcover, Mar 20 2014, after Maple *)
Table[BellY[k, n, {1,1,1,1}], {n,0,12}, {k,0,4*n}]//Flatten (* G. C. Greubel, Oct 11 2023 *)

SageMath

@CachedFunction
def t(n,k):
    if (k==n): return 1
    elif (kA144643(n,k): return t(n,k)
flatten([[A144643(n,k) for k in range(4*n+1)] for n in range(13)]) # G. C. Greubel, Oct 11 2023

Formula

T(n, k) = Sum_{j=0..3} binomial(k-1, j) * T(n-1, k-j-1), with T(n, n) = 1, T(n, k) = 0 if n < 1 or n > k.

Sum_{k=0..4*n} T(n, k) = A144508(n).