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
FORMULA
G.f.: A(x,z) = 1 + Sum_{i>0} x^i*z^(i-1) * Product_{k=1..i} (z-1)/(z - (x*(z-1) + 1)^k). - John Tyler Rascoe, Apr 29 2026
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.
Triangle begins:
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 *)
PROG
(PARI) A_xz(N) = {my(x='x+O('x^(N+1)), A = 1 + sum(i=1, N, x^i*z^(i-1) * prod(k=1, i, (z-1)/(z - (x*(z-1) + 1)^k)))); vector(N+1, n, Vecrev(polcoeff(A, n-1)))} \\ John Tyler Rascoe, Apr 29 2026
CROSSREFS
KEYWORD
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