

A056861


Triangle T(n,k) is the number of restricted growth strings (RGS) of set partitions of {1..n} that have an increase at index k (1<=k<n).


2



1, 3, 2, 10, 7, 6, 37, 27, 23, 21, 151, 114, 97, 88, 83, 674, 523, 446, 403, 378, 363, 3263, 2589, 2217, 1999, 1867, 1785, 1733, 17007, 13744, 11829, 10658, 9923, 9452, 9145, 8942, 94828, 77821, 67340, 60689, 56380, 53541, 51644, 50361, 49484, 562595
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,2


COMMENTS

Number of rises s_{k+1} > s_k in an RGS [s_1, ..., s_n] of a set partition of {1, ..., n}, where s_i is the subset containing i, and s_i <= 1 + max(j<i, s_j).
Note that the number of equalities at any index is B(n1), where B(n) are the Bell numbers.  Franklin T. AdamsWatters, Jun 08 2006


REFERENCES

W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [apparently unpublished, Joerg Arndt, Mar 05 2016]


LINKS

Alois P. Heinz, Rows n = 2..100, flattened


EXAMPLE

For example, [1, 2, 1, 2, 2, 3] is the RGS of a set partition of {1, 2, 3, 4, 5, 6} and has 3 rises, at i = 1, i = 3 and i = 5.
1;
3,2;
10,7,6;
37,27,23,21;
151,114,97,88,83;
674,523,446,403,378,363;
3263,2589,2217,1999,1867,1785,1733;
17007,13744,11829,10658,9923,9452,9145,8942;
94828,77821,67340,60689,56380,53541,51644,50361,49484;
562595,467767,406953,367101,340551,322619,310365,301905,296011,291871;
3535027,2972432,2599493,2348182,2176575,2058068,1975425,1917290,1876075, 1846648,1825501;


MATHEMATICA

b[n_, i_, m_, t_] := b[n, i, m, t] = If[n == 0, {1, 0}, Sum[Function[p, p + {0, If[j<i, p[[1]]*x^t, 0]}][b[n1, j, Max[m, j], t+1]], {j, 1, m+1}]];
T[n_] := BellB[n]  BellB[n1]  Function[p, Table[Coefficient[p, x, i], {i, 1, n1}]][b[n, 1, 0, 0][[2]]];
Table[T[n], {n, 2, 12}] // Flatten (* JeanFrançois Alcover, May 23 2016, after Alois P. Heinz *)


CROSSREFS

Cf. Bell numbers A005493, A011965.
Cf. A056857A056863.
Sequence in context: A227631 A246830 A268531 * A302846 A214844 A214966
Adjacent sequences: A056858 A056859 A056860 * A056862 A056863 A056864


KEYWORD

easy,nonn,tabl


AUTHOR

Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000


EXTENSIONS

Edited and extended by Franklin T. AdamsWatters, Jun 08 2006
Clarified definition and edited comment and example, Joerg Arndt, Mar 08 2016
Several terms corrected, R. J. Mathar, Mar 08 2016


STATUS

approved



