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,3

Comments

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..576

Wikipedia, Partition of a set

Formula

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

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

Example

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.

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

Crossrefs

Cf. A000040, A000110, A275043.

Sequence in context: A024998 A148570 A148571 * A148572 A320174 A248603

Adjacent sequences: A345397 A345398 A345399 * A345401 A345402 A345403

Keyword

nonn

Author

Alois P. Heinz, Jun 17 2021

Status

approved