A124496 - OEIS

%I #35 Jan 10 2022 08:11:33

%S 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,

%T 2469,1101,400,125,35,8,1,1,12611,5625,2046,635,175,44,9,1,1,69161,

%U 30846,11226,3488,952,236,54,10,1,1,404663,180474,65676,20425,5579,1366,309,65,11,1,1

%N 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.

%C 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

%C This is table 9.2 in the Gould-Quaintance reference. - _Peter Luschny_, Apr 25 2016

%H Alois P. Heinz, <a href="/A124496/b124496.txt">Rows n = 1..141, flattened</a>

%H H. W. Gould and Jocelyn Quaintance, <a href="http://www.doiserbia.nb.rs/img/doi/1452-8630/2007/1452-86300702371G.pdf">A linear binomial recurrence and the Bell numbers and polynomials</a>. Applicable Analysis and Discrete Mathematics, 1 (2007), 371-385.

%F 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.

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

%F Conjectures: T(n,n-3) = A000096(n). T(n,n-4)= A055831(n+1). - _R. J. Mathar_, Mar 13 2016

%e T(4,2) = 4 because we have 13|24, 14|23, 12|34 and 1|2|34.

%e Triangle starts:

%e   1;

%e   1,1;

%e   3,1,1;

%e   9,4,1,1;

%e   31,14,5,1,1;

%e   121,54,20,6,1,1;

%e   523,233,85,27,7,1,1;

%e   2469,1101,400,125,35,8,1,1;

%e   12611,5625,2046,635,175,44,9,1,1;

%e   69161,30846,11226,3488,952,236,54,10,1,1;

%e   404663,180474,65676,20425,5579,1366,309,65,11,1,1;

%e   2512769,1120666,407787,126817,34685,8494,1893,395,77,12,1,1;

%e   ...

%p 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;

%p # second Maple program:

%p T:= proc(n, k) option remember; `if`(n=k, 1,

%p       add(T(n-j, k)*binomial(n-1, j-1), j=1..n-k))

%p     end:

%p seq(seq(T(n, k), k=1..n), n=1..12);  # _Alois P. Heinz_, Jul 05 2016

%t T[n_, k_] := T[n, k] = If[n == k, 1, Sum[T[n-j, k]*Binomial[n-1, j-1], {j, 1, n-k}]];

%t Table[Table[T[n, k], {k, 1, n}], {n, 1, 12}] // Flatten; (* _Jean-François Alcover_, Jul 21 2016, after _Alois P. Heinz_ *)

%Y 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.

%Y T(2n,n) gives A297924.

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

%K nonn,tabl

%O 1,4

%A _Emeric Deutsch_, Nov 14 2006