login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,5

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<i, s_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

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

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

EXAMPLE

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;

MAPLE

b:= proc(n, i, m, t) option remember; `if`(n=0, [1, 0],

      add((p-> p+[0, `if`(j<i, p[1]*x^t, 0)])(

        b(n-1, j, max(m, j), t+1)), j=1..m+1))

    end:

T:= n-> (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[j<i, p[[1]]*x^t, 0]}][b[n-1, j, Max[m, j], t+1]], {j, 1, m+1}]];

T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n - 1}]][b[n, 1, 0, 0][[2]]];

Table[T[n], {n, 2, 12}] // Flatten (* Jean-Fran├žois Alcover, May 23 2016, after Alois P. Heinz *)

CROSSREFS

Cf. Bell numbers A005493.

Cf. A056857-A056863.

Sequence in context: A308642 A158674 A213280 * A113035 A099447 A078067

Adjacent sequences:  A056859 A056860 A056861 * A056863 A056864 A056865

KEYWORD

easy,nonn,tabl

AUTHOR

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

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 24 10:24 EST 2020. Contains 331193 sequences. (Running on oeis4.)