A345400 Number of colored set partitions of [n] where (i mod d) identifies the color of i and d is the number of available colors such that within each block the frequency of all colors is equal.

1, 1, 3, 6, 19, 53, 225, 878, 4281, 21212, 117489, 678571, 4238024, 27644438, 191326221, 1383029112, 10490101937, 82864869805, 682358388107, 5832742205058, 51733248275075, 474870253871245, 4507061060486642, 44152005855084347, 445973953222607799

Offset: 0

Author

Alois P. Heinz, Jun 17 2021

Keywords

• nonn

Comments

All block lengths and n are multiples of the number of available colors d.

Examples

			a(0) = 1: (), the empty partition.
a(1) = 1: 1a.
a(2) = 3: 1a2b, 1a2a, 1a|2a.
a(3) = 6: 1a2b3c, 1a2a3a, 1a2a|3a, 1a3a|2a, 1a|2a3a, 1a|2a|3a.
a(4) = 19: 1a2b3c4d, 1a2b3a4b, 1a2b|3a4b, 1a4b|2b3a, 1a2a3a4a, 1a2a3a|4a, 1a2a4a|3a, 1a2a|3a4a, 1a2a|3a|4a, 1a3a4a|2a, 1a3a|2a4a, 1a3a|2a|4a, 1a4a|2a3a, 1a|2a3a4a, 1a|2a3a|4a, 1a4a|2a|3a, 1a|2a4a|3a, 1a|2a|3a4a, 1a|2a|3a|4a.
Here the colors a, b, c, ... are used.
		

Links

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

Crossrefs

Cf. A000040, A000110, A275043.

Programs

Maple

A:= proc(n, k) option remember; `if`(n=0, 1, add(
      binomial(n, j)^k*(n-j)*A(j, k), j=0..n-1)/n)
    end:
a:= n-> `if`(n=0, 1, add(A(n/d, d), d=numtheory[divisors](n))):
seq(a(n), n=0..28);

Mathematica

A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[Binomial[n, j]^k*(n - j)*A[j, k], {j, 0, n - 1}]/n];
a[n_] := If[n == 0, 1, Sum[A[n/d, d], {d, Divisors[n]}]];
Table[a[n], {n, 0, 28}] (* Jean-François Alcover, Aug 25 2021, after Alois P. Heinz *)

Formula

a(n) = Sum_{d|n} A275043(n/d,d) for n > 0, a(0) = 1.

a(p) = 1 + A000110(p) for prime p.