login
Number of partitions of [n] such that the number of blocks of size k is a multiple of k for every k.
5

%I #15 Jul 04 2024 20:16:15

%S 1,1,1,1,4,16,46,106,316,1604,8156,33716,125456,1073216,10233224,

%T 69873896,364469561,2296961801,19124734801,147200743489,960313414036,

%U 6422446261456,52845891370966,461844834503746,3779922654292324,31131912140021452,296987899271509252

%N Number of partitions of [n] such that the number of blocks of size k is a multiple of k for every k.

%H Alois P. Heinz, <a href="/A374320/b374320.txt">Table of n, a(n) for n = 0..579</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) = 1: 1|2.

%e a(3) = 1: 1|2|3.

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

%e a(5) = 16: 12|34|5, 12|35|4, 12|3|45, 13|24|5, 13|25|4, 13|2|45, 14|23|5, 15|23|4, 1|23|45, 14|25|3, 14|2|35, 15|24|3, 1|24|35, 15|2|34, 1|25|34, 1|2|3|4|5.

%e a(9) = 1604: 123|456|789, 123|457|689, 123|458|679, 123|459|678, ..., 1|2|3|49|5|6|78, 1|2|3|4|59|6|78, 1|2|3|4|5|69|78, 1|2|3|4|5|6|7|8|9.

%p b:= proc(n, i) option remember; `if`(n=0 or i=1, 1,

%p add(combinat[multinomial](n, i$i*j, n-i^2*j)*

%p b(n-i^2*j, i-1)/(i*j)!, j=0..n/i^2))

%p end:

%p a:= n-> b(n$2):

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

%Y Cf. A374262, A374319, A374321, A374329.

%K nonn

%O 0,5

%A _Alois P. Heinz_, Jul 04 2024