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]
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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Nov 14 2006
STATUS
approved