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,4

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<=j<i} f(j). - R. J. Mathar, Mar 18 2016

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

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.

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

Example

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

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

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.

Sequence in context: A080510 A350772 A350783 * A074881 A142992 A145905

Adjacent sequences: A124493 A124494 A124495 * A124497 A124498 A124499

Keyword

nonn,tabl

Author

Emeric Deutsch, Nov 14 2006

Status

approved