login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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(n-1), where B(n) are the Bell numbers. - Franklin T. Adams-Watters, 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[n-1, j, Max[m, j], t+1]], {j, 1, m+1}]];

T[n_] := BellB[n] - BellB[n-1] - Function[p, Table[Coefficient[p, x, i], {i, 1, n-1}]][b[n, 1, 0, 0][[2]]];

Table[T[n], {n, 2, 12}] // Flatten (* Jean-Fran├žois Alcover, May 23 2016, after Alois P. Heinz *)

CROSSREFS

Cf. Bell numbers A005493, A011965.

Cf. A056857-A056863.

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 24 16:34 EST 2020. Contains 331207 sequences. (Running on oeis4.)