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

Author

Alois P. Heinz, May 08 2023

Keywords

• nonn

Examples

			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.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..890
• Wikipedia, Partition of a set

Crossrefs

Cf. A000110, A362549, A362635.

Programs

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);