cp's OEIS Frontend

A056862 Triangle T(n,k) is the number of restricted growth strings (RGS) of set partitions of {1..n} that have a decrease at index k (1<=k

%I A056862 #28 May 23 2016 02:46:24
%S A056862 0,0,1,0,3,4,0,10,14,16,0,37,54,63,68,0,151,228,271,296,311,0,674,
%T A056862 1046,1264,1396,1478,1530,0,3263,5178,6349,7084,7555,7862,8065,0,
%U A056862 17007,27488,34139,38448,41287,43184,44467,45344,0,94828,155642,195494,222044,239976,252230,260690,266584,270724
%N A056862 Triangle T(n,k) is the number of restricted growth strings (RGS) of set partitions of {1..n} that have a decrease at index k (1<=k<n).
%C A056862 Number of falls s_k > s_{k+1} in a RGS [s_1, ..., s_n] of a set partition of {1, ..., n}, where s_i is the subset containing i, s_1 = 1 and s_i <= 1 + max(j<i, s_j).
%C A056862 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
%D A056862 W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [apparently unpublished, _Joerg Arndt_, Mar 05 2016]
%H A056862 Alois P. Heinz, <a href="/A056862/b056862.txt">Rows n = 2..100, flattened</a>
%F A056862 T(n,k) = B(n) - B(n-1) - A056861(n,k). - _Franklin T. Adams-Watters_, Jun 08 2006
%F A056862 Conjecture: T(n,3) = 2*A011965(n). - _R. J. Mathar_, Mar 08 2016
%e A056862 For example, [1, 2, 1, 2, 2, 3] is the RGS of a set partition of {1, 2, 3, 4, 5, 6} and has 1 fall, at i = 2.
%e A056862 0;
%e A056862 0,1;
%e A056862 0,3,4;
%e A056862 0,10,14,16;
%e A056862 0,37,54,63,68;
%e A056862 0,151,228,271,296,311;
%e A056862 0,674,1046,1264,1396,1478,1530;
%e A056862 0,3263,5178,6349,7084,7555,7862,8065;
%e A056862 0,17007,27488,34139,38448,41287,43184,44467,45344;
%e A056862 0,94828,155642,195494,222044,239976,252230,260690,266584,270724;
%e A056862 0,562595,935534,1186845,1358452,1476959,1559602,1617737,1658952,1688379, 1709526;
%p A056862 b:= proc(n, i, m, t) option remember; `if`(n=0, [1, 0],
%p A056862       add((p-> p+[0, `if`(j<i, p[1]*x^t, 0)])(
%p A056862         b(n-1, j, max(m, j), t+1)), j=1..m+1))
%p A056862     end:
%p A056862 T:= n-> (p-> seq(coeff(p, x, i), i=1..n-1))(b(n, 1, 0$2)[2]):
%p A056862 seq(T(n), n=2..12);  # _Alois P. Heinz_, Mar 24 2016
%t A056862 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 A056862 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n - 1}]][b[n, 1, 0, 0][[2]]];
%t A056862 Table[T[n], {n, 2, 12}] // Flatten (* _Jean-François Alcover_, May 23 2016, after _Alois P. Heinz_ *)
%Y A056862 Cf. Bell numbers A005493.
%Y A056862 Cf. A056857-A056863.
%K A056862 easy,nonn,tabl
%O A056862 2,5
%A A056862 Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000
%E A056862 Edited and extended by _Franklin T. Adams-Watters_, Jun 08 2006
%E A056862 Clarified definition and edited comment and example, _Joerg Arndt_, Mar 08 2016
%E A056862 Data corrected, _R. J. Mathar_, Mar 08 2016