A362893 Number of partitions of [n] whose blocks can be ordered such that the i-th block has at least i elements and no block j > i has an element smaller than the i-th smallest element of block i.

1, 1, 1, 2, 5, 12, 28, 69, 193, 614, 2103, 7359, 25660, 88914, 309502, 1102146, 4092840, 16046224, 66410789, 286905421, 1273646720, 5729762139, 25881820352, 116872997038, 527375160184, 2384407416357, 10856086444051, 50097994816979, 235937202788389

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..890

Wikipedia, Partition of a set

Example

a(0) = 1: (), the empty partition.
a(1) = 1: 1.
a(2) = 1: 12.
a(3) = 2: 123, 1|23.
a(4) = 5: 1234, 12|34, 13|24, 14|23, 1|234.
a(5) = 12: 12345, 123|45, 124|35, 125|34, 12|345, 134|25, 135|24, 13|245, 145|23, 14|235, 15|234, 1|2345.
a(6) = 28: 123456, 1234|56, 1235|46, 1236|45, 123|456, 1245|36, 1246|35, 124|356, 1256|34, 125|346, 126|345, 12|3456, 1345|26, 1346|25, 134|256, 1356|24, 135|246, 136|245, 13|2456, 1456|23, 145|236, 146|235, 14|2356, 156|234, 15|2346, 16|2345, 1|23456, 1|23|456.
a(7) = 69: 1234567, 12345|67, 12346|57, 12347|56, 1234|567, 12356|47, 12357|46, 1235|467, 12367|45, 1236|457, 1237|456, 123|4567, 12456|37, 12457|36, 1245|367, 12467|35, 1246|357, 1247|356, 124|3567, 12567|34, 1256|347, 1257|346, 125|3467, 1267|345, 126|3457, 127|3456, 12|34567, 12|34|567, 13456|27, 13457|26, 1345|267, 13467|25, 1346|257, 1347|256, 134|2567, 13567|24, 1356|247, 1357|246, 135|2467, 1367|245, 136|2457, 137|2456, 13|24567, 13|24|567, 14567|23, 1456|237, 1457|236, 145|2367, 1467|235, 146|2357, 147|2356, 14|23567, 14|23|567, 1567|234, 156|2347, 157|2346, 15|23467, 167|2345, 16|23457, 17|23456, 1|234567, 1|234|567, 15|23|467, 1|235|467, 16|23|457, 1|236|457, 17|23|456, 1|237|456, 1|23|4567.

Maple

b:= proc(n, t) option remember; `if`(n=0 or n=t, 1,
      add(b(n-j, t+1)*binomial(n-t, j-t), j=t..n))
    end:
a:= n-> b(n, 1):
seq(a(n), n=0..28);

Crossrefs

Cf. A000110, A362549, A362635.

Sequence in context: A024960 A291234 A346051 * A326760 A238828 A326761

Adjacent sequences: A362890 A362891 A362892 * A362894 A362895 A362896

Keyword

nonn

Author

Alois P. Heinz, May 08 2023

Status

approved