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

%I #32 May 15 2023 16:06:43

%S 1,1,2,4,9,23,64,187,566,1777,5820,19944,71343,264719,1011292,3953381,

%T 15756609,63945484,264384828,1115246518,4806957739,21189601861,

%U 95516470253,439777682222,2064164172616,9853934668051,47736608806520,234235866539512,1162618720397931

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

%H Alois P. Heinz, <a href="/A362549/b362549.txt">Table of n, a(n) for n = 0..888</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Partition_of_a_set">Partition of a set</a>

%e a(0) = 1: (), the empty partition.

%e a(1) = 1: 1.

%e a(2) = 2: 12, 1|2.

%e a(3) = 4: 123, 12|3, 13|2, 1|23.

%e a(4) = 9: 1234, 123|4, 124|3, 12|34, 134|2, 13|24, 14|23, 1|234, 1|23|4.

%e a(5) = 23: 12345, 1234|5, 1235|4, 123|45, 1245|3, 124|35, 125|34, 12|345, 12|34|5, 1345|2, 134|25, 135|24, 13|245, 13|24|5, 145|23, 14|235, 14|23|5, 15|234, 1|2345, 1|234|5, 15|23|4, 1|235|4, 1|23|45.

%e a(6) = 64: 123456, 12345|6, 12346|5, 1234|56, 12356|4, ..., 1|2356|4, 1|235|46, 16|23|45, 1|236|45, 1|23|456.

%p b:= proc(n, t) option remember; `if`(n<=t, 1,

%p add(b(j, t+1)*binomial(n-t, j), j=0..n-t))

%p end:

%p a:= n-> b(n, 1):

%p seq(a(n), n=0..30);

%Y Cf. A000110, A007476, A092920, A210540, A362635, A362637, A362893.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Apr 24 2023