cp's OEIS Frontend

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

%I A056858 #22 May 23 2016 02:46:08
%S A056858 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,
%T A056858 1,1,28,322,1268,1709,732,79,1,1,36,588,3571,8136,6794,1887,133,1,1,
%U A056858 45,1002,8878,31532,44924,24717,4654,221,1,1,55,1617,20053,104927,234412,221857,84170,11113,364,1
%N A056858 Triangle of number of rises in restricted growth strings (RGS) for the set partitions of n.
%C A056858 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.
%D A056858 W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [apparently unpublished, _Joerg Arndt_, Mar 05 2016]
%H A056858 Alois P. Heinz, <a href="/A056858/b056858.txt">Rows n = 1..100, flattened</a>
%e A056858 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.
%e A056858 1;
%e A056858 1,1;
%e A056858 1,3,1;
%e A056858 1,6,7,1;
%e A056858 1,10,26,14,1;
%e A056858 1,15,71,89,26,1;
%e A056858 1,21,161,380,267,46,1;
%e A056858 1,28,322,1268,1709,732,79,1;
%e A056858 1,36,588,3571,8136,6794,1887,133,1;
%e A056858 1,45,1002,8878,31532,44924,24717,4654,221,1;
%e A056858 1,55,1617,20053,104927,234412,221857,84170,11113,364,1;
%e A056858 1,66,2497,41965,310255,1025377,1528351,1006028,272557,25903,596,1;
%p A056858 b:= proc(n, i, m) option remember; expand(
%p A056858       `if`(n=0, x, add(b(n-1, j, max(m, j))*
%p A056858       `if`(j>i, x, 1), j=1..m+1)))
%p A056858     end:
%p A056858 T:= n->(p-> seq(coeff(p, x, i), i=1..n))(b(n, 1, 0)):
%p A056858 seq(T(n), n=1..12);  # _Alois P. Heinz_, Mar 24 2016
%t A056858 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 A056858 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, 1, 0]];
%t A056858 Table[T[n], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, May 23 2016, after _Alois P. Heinz_ *)
%Y A056858 Cf. A000110 (row sums).
%Y A056858 Cf. A056857-A056863.
%Y A056858 Column 1 is triangular numbers (A000217); diagonal T(n, n-1) appears to be A001924.
%K A056858 easy,nonn,tabl
%O A056858 1,5
%A A056858 Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000
%E A056858 More terms from _Franklin T. Adams-Watters_, Jun 08 2006
%E A056858 Clarified definition and edited comment and example, _Joerg Arndt_, Mar 05 2016