cp's OEIS Frontend

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

%I A056859 #20 May 24 2016 03:06:34
%S A056859 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,
%T A056859 128,1304,2062,624,22,0,0,0,256,3949,10163,6042,730,7,0,0,0,512,11567,
%U A056859 45298,45810,12170,617,1,0,0,0,1024,33056,187941,296017,141822,18325,385,0,0,0,0
%N A056859 Triangle of number of falls in set partitions of n.
%C A056859 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.
%C A056859 The maximum number of falls is in a set partition like 1,2,1,3,2,1,... - _Franklin T. Adams-Watters_, Jun 08 2006
%D A056859 W. C. Yang, Conjectures on some sequences involving set partitions and Bell numbers, preprint, 2000. [Apparently unpublished]
%H A056859 Alois P. Heinz, <a href="/A056859/b056859.txt">Rows n = 1..100, flattened</a>
%e A056859 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.
%e A056859 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
%e A056859 1;
%e A056859 2,0;
%e A056859 4,1,0;
%e A056859 8,7,0,0;
%e A056859 16,32,4,0,0;
%e A056859 32,121,49,1,0,0;
%e A056859 64,411,360,42,0,0,0;
%e A056859 128,1304,2062,624,22,0,0,0;
%e A056859 256,3949,10163,6042,730,7,0,0,0;
%e A056859 512,11567,45298,45810,12170,617,1,0,0,0;
%e A056859 1024,33056,187941,296017,141822,18325,385,0,0,0,0;
%e A056859 2048,92721,739352,1708893,1318395,330407,21605,176,0,0,0,0;
%p A056859 b:= proc(n, i, m) option remember;
%p A056859       `if`(n=0, x, expand(add(b(n-1, j, max(m, j))*
%p A056859       `if`(j<i, x, 1), j=1..m+1)))
%p A056859     end:
%p A056859 T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 1, 0)):
%p A056859 seq(T(n), n=1..12);  # _Alois P. Heinz_, Mar 24 2016
%t A056859 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 A056859 T[n_] := Function[p, Table[Coefficient[p, x, i], {i, 1, n}]][b[n, 1, 0]];
%t A056859 Table[T[n], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, May 24 2016, after _Alois P. Heinz_ *)
%Y A056859 Cf. A000110 (row sums).
%Y A056859 Cf. A056857-A056863.
%K A056859 easy,nonn,tabl
%O A056859 1,2
%A A056859 Winston C. Yang (winston(AT)cs.wisc.edu), Aug 31 2000
%E A056859 Corrected and extended by _Franklin T. Adams-Watters_, Jun 08 2006