A056858 Triangle of number of rises in restricted growth strings (RGS) for the set partitions of n.

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

Offset: 1

Author

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

Keywords

• easy
• nonn
• tabl

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

Examples

			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;
		

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

Crossrefs

Cf. A000110 (row sums).

Cf. A056857-A056863.

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

Programs

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 *)

Extensions

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

Clarified definition and edited comment and example, Joerg Arndt, Mar 05 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.