A056859 Triangle of number of falls in set partitions of n.

1, 2, 0, 4, 1, 0, 8, 7, 0, 0, 16, 32, 4, 0, 0, 32, 121, 49, 1, 0, 0, 64, 411, 360, 42, 0, 0, 0, 128, 1304, 2062, 624, 22, 0, 0, 0, 256, 3949, 10163, 6042, 730, 7, 0, 0, 0, 512, 11567, 45298, 45810, 12170, 617, 1, 0, 0, 0, 1024, 33056, 187941, 296017, 141822, 18325, 385, 0, 0, 0, 0

Offset: 1

Author

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

Keywords

• easy
• nonn
• tabl

Comments

Number of falls s_i > s_{i+1} in a set partition {s_1, ..., s_n} of {1, ..., n}, where s_i is the subset containing i, s(1) = 1 and s(i) <= 1 + max of previous s(j)'s.

The maximum number of falls is in a set partition like 1,2,1,3,2,1,... - Franklin T. Adams-Watters, Jun 08 2006

Examples

			For example {1, 2, 1, 2, 2, 3} is a set partition of {1, 2, 3, 4, 5, 6} and has 1 fall, at i = 2.
T(n=3,f=0)=4 counts the partitions {1,1,1}, {1,1,2}, {1,2,2}, and {1,2,3}. T(n=3,f=1) counts the partition {1,2,1}. - _R. J. Mathar_, Mar 04 2016
1;
2,0;
4,1,0;
8,7,0,0;
16,32,4,0,0;
32,121,49,1,0,0;
64,411,360,42,0,0,0;
128,1304,2062,624,22,0,0,0;
256,3949,10163,6042,730,7,0,0,0;
512,11567,45298,45810,12170,617,1,0,0,0;
1024,33056,187941,296017,141822,18325,385,0,0,0,0;
2048,92721,739352,1708893,1318395,330407,21605,176,0,0,0,0;
		

References

• W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [Apparently unpublished]

Links

• Alois P. Heinz, Rows n = 1..100, flattened

Crossrefs

Cf. A000110 (row sums).

Cf. A056857-A056863.

Programs

Maple

b:= proc(n, i, m) option remember;
      `if`(n=0, x, expand(add(b(n-1, j, max(m, j))*
      `if`(j (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] = If[n == 0, x, Expand[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 24 2016, after Alois P. Heinz *)

Extensions

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