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!)
A056858 Triangle of number of rises in restricted growth strings (RGS) for the set partitions of n. 3
1, 1, 1, 1, 3, 1, 1, 6, 7, 1, 1, 10, 26, 14, 1, 1, 15, 71, 89, 26, 1, 1, 21, 161, 380, 267, 46, 1, 1, 28, 322, 1268, 1709, 732, 79, 1, 1, 36, 588, 3571, 8136, 6794, 1887, 133, 1, 1, 45, 1002, 8878, 31532, 44924, 24717, 4654, 221, 1, 1, 55, 1617, 20053, 104927, 234412, 221857, 84170, 11113, 364, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

Number of rises s_{i+1} > s_i in the RGS [s_1, ..., s_n] for a set partition of {1, ..., n}, where s_i is the index of the subset containing i, s_1 = 1 and s_i <= 1 + max_{j<i} s_j.

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 = 1..100, flattened

EXAMPLE

For example [1, 2, 1, 2, 2, 3] is the RGS for a set partition of {1, 2, 3, 4, 5, 6} and has 3 rises, at i = 1, i = 3 and i = 5.

1;

1,1;

1,3,1;

1,6,7,1;

1,10,26,14,1;

1,15,71,89,26,1;

1,21,161,380,267,46,1;

1,28,322,1268,1709,732,79,1;

1,36,588,3571,8136,6794,1887,133,1;

1,45,1002,8878,31532,44924,24717,4654,221,1;

1,55,1617,20053,104927,234412,221857,84170,11113,364,1;

1,66,2497,41965,310255,1025377,1528351,1006028,272557,25903,596,1;

MAPLE

b:= proc(n, i, m) option remember; expand(

      `if`(n=0, x, add(b(n-1, j, max(m, j))*

      `if`(j>i, x, 1), j=1..m+1)))

    end:

T:= n->(p-> seq(coeff(p, x, i), i=1..n))(b(n, 1, 0)):

seq(T(n), n=1..12);  # Alois P. Heinz, Mar 24 2016

MATHEMATICA

b[n_, i_, m_] := b[n, i, m] = Expand[If[n == 0, x, Sum[b[n - 1, j, Max[m, j]]*If[j > i, x, 1], {j, 1, m + 1}]]];

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

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

CROSSREFS

Cf. A000110 (row sums).

Cf. A056857-A056863.

Column 1 is triangular numbers (A000217); diagonal T(n, n-1) appears to be A001924.

Sequence in context: A133713 A008278 A213735 * A137251 A158359 A046716

Adjacent sequences:  A056855 A056856 A056857 * A056859 A056860 A056861

KEYWORD

easy,nonn,tabl

AUTHOR

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

EXTENSIONS

More terms from Franklin T. Adams-Watters, Jun 08 2006

Clarified definition and edited comment and example, Joerg Arndt, Mar 05 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 February 24 00:51 EST 2020. Contains 332195 sequences. (Running on oeis4.)