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

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

Offset: 2

Author

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

Keywords

• easy
• nonn
• tabl

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

Note that the number of equalities at any index is B(n-1), where B(n) are the Bell numbers. - Franklin T. Adams-Watters, Jun 08 2006

Examples

			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;
		

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

Crossrefs

Cf. Bell numbers A005493, A011965.

Cf. A056857-A056863.

Programs

Mathematica

b[n_, i_, m_, t_] := b[n, i, m, t] = If[n == 0, {1, 0}, Sum[Function[p, p + {0, If[jJean-François Alcover, May 23 2016, after Alois P. Heinz *)

Extensions

Edited and extended by Franklin T. Adams-Watters, Jun 08 2006

Clarified definition and edited comment and example, Joerg Arndt, Mar 08 2016

Several terms corrected, R. J. Mathar, Mar 08 2016

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.