cp's OEIS Frontend

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

%I A056861 #26 May 23 2016 02:46:17
%S A056861 1,3,2,10,7,6,37,27,23,21,151,114,97,88,83,674,523,446,403,378,363,
%T A056861 3263,2589,2217,1999,1867,1785,1733,17007,13744,11829,10658,9923,9452,
%U A056861 9145,8942,94828,77821,67340,60689,56380,53541,51644,50361,49484,562595
%N A056861 Triangle T(n,k) is the number of restricted growth strings (RGS) of set partitions of {1..n} that have an increase at index k (1<=k<n).
%C A056861 Number of rises s_{k+1} > s_k in an RGS [s_1, ..., s_n] of a set partition of {1, ..., n}, where s_i is the subset containing i, and s_i <= 1 + max(j<i, s_j).
%C A056861 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 A056861 W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [apparently unpublished, _Joerg Arndt_, Mar 05 2016]
%H A056861 Alois P. Heinz, <a href="/A056861/b056861.txt">Rows n = 2..100, flattened</a>
%e A056861 For example, [1, 2, 1, 2, 2, 3] is the RGS of a set partition of {1, 2, 3, 4, 5, 6} and has 3 rises, at i = 1, i = 3 and i = 5.
%e A056861 1;
%e A056861 3,2;
%e A056861 10,7,6;
%e A056861 37,27,23,21;
%e A056861 151,114,97,88,83;
%e A056861 674,523,446,403,378,363;
%e A056861 3263,2589,2217,1999,1867,1785,1733;
%e A056861 17007,13744,11829,10658,9923,9452,9145,8942;
%e A056861 94828,77821,67340,60689,56380,53541,51644,50361,49484;
%e A056861 562595,467767,406953,367101,340551,322619,310365,301905,296011,291871;
%e A056861 3535027,2972432,2599493,2348182,2176575,2058068,1975425,1917290,1876075, 1846648,1825501;
%t A056861 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 A056861 T[n_] := BellB[n] - BellB[n-1] - Function[p, Table[Coefficient[p, x, i], {i, 1, n-1}]][b[n, 1, 0, 0][[2]]];
%t A056861 Table[T[n], {n, 2, 12}] // Flatten (* _Jean-François Alcover_, May 23 2016, after _Alois P. Heinz_ *)
%Y A056861 Cf. Bell numbers A005493, A011965.
%Y A056861 Cf. A056857-A056863.
%K A056861 easy,nonn,tabl
%O A056861 2,2
%A A056861 Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000
%E A056861 Edited and extended by _Franklin T. Adams-Watters_, Jun 08 2006
%E A056861 Clarified definition and edited comment and example, _Joerg Arndt_, Mar 08 2016
%E A056861 Several terms corrected, _R. J. Mathar_, Mar 08 2016