login
Number of set partitions of [n] such that n is a multiple of each block size.
4

%I #11 May 17 2018 03:11:54

%S 1,1,2,2,11,2,167,2,1500,1206,16175,2,3486584,2,3188421,29226654,

%T 772458367,2,130880325103,2,4173951684174,623240762412,644066092301,2,

%U 220076136813712815,31580724696908,538897996103277,49207275464475052,44147498142028751570,2

%N Number of set partitions of [n] such that n is a multiple of each block size.

%H Alois P. Heinz, <a href="/A275429/b275429.txt">Table of n, a(n) for n = 0..587</a>

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

%F a(n) = n! * [x^n] exp(Sum_{d|n} x^d/d!) for n>0, a(0) = 1.

%F a(n) = A275422(n,n).

%F a(p) = 2 for p prime.

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

%e a(5) = 2: 12345, 1|2|3|4|5.

%p A:= proc(n, k) option remember; `if`(n=0, 1, add(

%p `if`(j>n, 0, A(n-j, k)*binomial(n-1, j-1)), j=

%p `if`(k=0, 1..n, numtheory[divisors](k))))

%p end:

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

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

%t A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[If[j > n, 0, A[n - j, k]* Binomial[n - 1, j - 1]], {j, If[k == 0, Range[n], Divisors[k]]}]];

%t a[n_] := A[n, n];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, May 17 2018, translated from Maple *)

%Y Main diagonal of A275422.

%K nonn

%O 0,3

%A _Alois P. Heinz_, Jul 27 2016