Permutations of colored balls with restrictions Consider $N$ balls, each in one of $K$ possible colors. We denote by $n_k$ the number of balls colored in the $k$-th color ($\sum_{k=1}^K n_k =N$). Is there a known formula for the total number of permutations of the $N$ balls subject to the restriction that concatenated copies of shorter sequences should be discounted? For example, if we have $3$ $b$lue-colored balls and $3$ $r$ed-colored balls then one should not count the permutations $brbrbr$ and $rbrbrb$.
 A: Yes you can. Using Möbius inversion, you can show that the number of sequences of length $N$, consisting of $n_k$ copies of color $k$ for each $k\in \{1,\dots,K\}$, is
$$
\sum_{d\mid \gcd(n_1,\dots,n_K)} \mu(d)\frac{(N/d)!}{(n_1/d)!(n_2/d)!\cdots (n_K/d)!},
$$
where $\mu$ is the Möbius $\mu$ function. The sum ranges over positive integers $d$ such that $d$ is a common divisor of $n_1,\dots,n_K$.
This is essentially the principle of inclusion exclusion. You add in all of the sequences with the $d=1$ term, then for $d=2$, you subtract away sequences which are a double of a smaller sequence. Similarly, for $d=3$, you subtract triple repeats of smaller sequences. But for $d=6$, since $\mu(6)=+1$, you add back in the six-tuple repeats, because these were doubly subtracted in the previous two steps. The $\mu()$ function magically makes everything cancel out to count the number of sequences which are not repeats of a smaller one.
A: From your examples I have a hunch that you consider cyclic shifts of the same sequence as equivalent. If that is the case, the word you are looking for is "necklace".
A: By way of enrichment here are some comments on the PIE construction.  For
PIE we need a poset, which in the present case has nodes $d$
representing permutations of the given distribution of colors that are
formed by repeating a string $d$ times, which does not mean that there
isn't another value $d'$ such that the permutation is formed by
repeating a string $d'$ times. It then follows by inspection that these
$d$ must be divisors of $g = \gcd(n_1, n_2, \ldots n_K)$ as the count of
every color in the basic segment is multiplied by $d.$ Hence we use for
the underlying poset of the PIE construction the divisor poset of $g$,
with nodes $d$ being the divisors of $g$, and the poset ordered by
divisibility of two nodes $f$ and $f'.$ The next step is to define the
weight function for every node of the poset. This weight function is
taken to be the Mobius function $\mu(d).$ With this setup we count in
two ways, first is by computing the total weight on a given permutation
and second is by summing the product of the weight and the cardinality
of the set of permutations represented at the node $d$, over all $d.$.
These two ways  of counting are what makes PIE work. Now what is the
total weight on  some specific permutation over all nodes? Let $r$ be the
maximum value such that  the permutation can be formed by repeating $r$
times a primitive segment that  does not further deconstruct into
repeated segments. It then  follows that the other deconstructions are
obtained  by grouping the primitive segments taking them $r'$ at a time
where  $r'|r$. This makes the permutation appear on node $r/r'.$ Hence
summing the total weight on a permutation over all  nodes $d$ where it is
present we obtain
$$\sum_{r'|r} \mu(r/r') = \sum_{r'|r} \mu(r') =
\begin{cases}
1 & \text{if}\quad r=1 \\
0 & \text{otherwise.}
\end{cases}$$
This is because we have $\sum_{d|n} \mu(d) = \prod_{p|n} (1-1) = 0$ where
the product is over prime divisors. So we  have precisely what we need,
with primitive permutations having total  weight one and all others
weight zero. Now we need the alternate count,  which requires the
cardinality of the set of permutations represented  at a node $d.$ This
is quite simply the multinomial $(N/d)!/\prod_k (n_k/d)!.$ Finally to
complete the count we multiply by the weight $\mu(d)$ and sum over all
nodes $d|g$ to get $\sum_{d|g} \mu(d) (N/d)!/\prod_k (n_k/d)!$ as noted
in  the companion answer. This completes the count by PIE.
