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

0, 0, 1, 0, 3, 4, 0, 10, 14, 16, 0, 37, 54, 63, 68, 0, 151, 228, 271, 296, 311, 0, 674, 1046, 1264, 1396, 1478, 1530, 0, 3263, 5178, 6349, 7084, 7555, 7862, 8065, 0, 17007, 27488, 34139, 38448, 41287, 43184, 44467, 45344, 0, 94828, 155642, 195494, 222044, 239976, 252230, 260690, 266584, 270724

Offset: 2

Author

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

Keywords

• easy
• nonn
• tabl

Comments

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

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

Examples

			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.
0;
0,1;
0,3,4;
0,10,14,16;
0,37,54,63,68;
0,151,228,271,296,311;
0,674,1046,1264,1396,1478,1530;
0,3263,5178,6349,7084,7555,7862,8065;
0,17007,27488,34139,38448,41287,43184,44467,45344;
0,94828,155642,195494,222044,239976,252230,260690,266584,270724;
0,562595,935534,1186845,1358452,1476959,1559602,1617737,1658952,1688379, 1709526;
		

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 = 2..100, flattened

Crossrefs

Cf. Bell numbers A005493.

Cf. A056857-A056863.

Programs

Maple

b:= proc(n, i, m, t) option remember; `if`(n=0, [1, 0],
      add((p-> p+[0, `if`(j (p-> seq(coeff(p, x, i), i=1..n-1))(b(n, 1, 0$2)[2]):
seq(T(n), n=2..12);  # Alois P. Heinz, Mar 24 2016

Mathematica

b[n_, i_, m_, t_] := b[n, i, m, t] = If[n == 0, {1, 0}, Sum[Function[p, p + {0, If[jJean-François Alcover, May 23 2016, after Alois P. Heinz *)

Formula

T(n,k) = B(n) - B(n-1) - A056861(n,k). - Franklin T. Adams-Watters, Jun 08 2006

Conjecture: T(n,3) = 2*A011965(n). - R. J. Mathar, Mar 08 2016

Extensions

Edited and extended by Franklin T. Adams-Watters, Jun 08 2006

Clarified definition and edited comment and example, Joerg Arndt, Mar 08 2016

Data corrected, R. J. Mathar, Mar 08 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.