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

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A056859 Triangle of number of falls in set partitions of n. 1
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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

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

EXAMPLE

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;

MAPLE

b:= proc(n, i, m) option remember;

      `if`(n=0, x, expand(add(b(n-1, j, max(m, j))*

      `if`(j<i, x, 1), j=1..m+1)))

    end:

T:= n-> (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 *)

CROSSREFS

Cf. A000110 (row sums).

Cf. A056857-A056863.

Sequence in context: A140648 A153342 A144258 * A272098 A291929 A327807

Adjacent sequences:  A056856 A056857 A056858 * A056860 A056861 A056862

KEYWORD

easy,nonn,tabl

AUTHOR

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

EXTENSIONS

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

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 21 13:55 EST 2020. Contains 331113 sequences. (Running on oeis4.)