A124496 Triangle read by rows: T(n,k) is the number of set partitions of {1,2,...,n} in which the size of the last block is k, 1<=k<=n; the blocks are ordered with increasing least elements.

1, 1, 1, 3, 1, 1, 9, 4, 1, 1, 31, 14, 5, 1, 1, 121, 54, 20, 6, 1, 1, 523, 233, 85, 27, 7, 1, 1, 2469, 1101, 400, 125, 35, 8, 1, 1, 12611, 5625, 2046, 635, 175, 44, 9, 1, 1, 69161, 30846, 11226, 3488, 952, 236, 54, 10, 1, 1, 404663, 180474, 65676, 20425, 5579, 1366, 309, 65, 11, 1, 1

Offset: 1

Author

Emeric Deutsch, Nov 14 2006

Keywords

• nonn
• tabl

Comments

Number of restricted growth functions of length n with a multiplicity k of the maximum value. RGF's are here defined as f(1)=1, f(i) <= 1+max_{1<=jR. J. Mathar, Mar 18 2016

This is table 9.2 in the Gould-Quaintance reference. - Peter Luschny, Apr 25 2016

Examples

			T(4,2) = 4 because we have 13|24, 14|23, 12|34 and 1|2|34.
Triangle starts:
  1;
  1,1;
  3,1,1;
  9,4,1,1;
  31,14,5,1,1;
  121,54,20,6,1,1;
  523,233,85,27,7,1,1;
  2469,1101,400,125,35,8,1,1;
  12611,5625,2046,635,175,44,9,1,1;
  69161,30846,11226,3488,952,236,54,10,1,1;
  404663,180474,65676,20425,5579,1366,309,65,11,1,1;
  2512769,1120666,407787,126817,34685,8494,1893,395,77,12,1,1;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• H. W. Gould and Jocelyn Quaintance, A linear binomial recurrence and the Bell numbers and polynomials. Applicable Analysis and Discrete Mathematics, 1 (2007), 371-385.

Crossrefs

Row sums are the Bell numbers (A000110). It seems that T(n, 1), T(n, 2), T(n, 3) and T(n, 4) are given by A040027, A045501, A045499 and A045500, respectively. A121207 gives a very similar triangle.

T(2n,n) gives A297924.

Cf. A000110, A040027, A045501, A045499, A045500, A186020, A160185.

Programs

Maple

Q[1]:=t*s: for n from 2 to 12 do Q[n]:=expand(t*s*subs(t=1,Q[n-1])+s*diff(Q[n-1],s)+t*Q[n-1]-Q[n-1]) od:for n from 1 to 12 do P[n]:=sort(subs(s=1,Q[n])) od: for n from 1 to 12 do seq(coeff(P[n],t,j),j=1..n) od;
# second Maple program:
T:= proc(n, k) option remember; `if`(n=k, 1,
      add(T(n-j, k)*binomial(n-1, j-1), j=1..n-k))
    end:
seq(seq(T(n, k), k=1..n), n=1..12);  # Alois P. Heinz, Jul 05 2016

Mathematica

T[n_, k_] := T[n, k] = If[n == k, 1, Sum[T[n-j, k]*Binomial[n-1, j-1], {j, 1, n-k}]];
Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten; (* Jean-François Alcover, Jul 21 2016, after Alois P. Heinz *)

Formula

The row enumerating polynomial P[n](t)=Q[n](t,1), where Q[1](t,s)=ts and Q[n](t,s)=s*dQ[n-1](t,s)/ds +(t-1)Q[n-1](t,s)+tsQ[n-1](1,s) for n>=2.

A008275^-1*ONES*A008275 or A008277*ONES*A008277^-1 where ONES is a triangle with all entries = 1. [From Gerald McGarvey, Aug 20 2009]

Conjectures: T(n,n-3) = A000096(n). T(n,n-4)= A055831(n+1). - R. J. Mathar, Mar 13 2016