Say I have $n$ indistinguishable beads and $k$ different colours. Suppose here and for the rest of the writeup that $k \mid n$ unless otherwise stated.
I want to colour all the $n$ beads using exactly $k$ colours, such that each colour is used exactly $n \over k$ times. For the purpose of this question, rotations that result from the same initial configuration are considered the same, whereas reflections are considered distinct.
-
In how many ways can this be done if I am to form a strip?
-
In how many ways can this be done if I am to form a necklace?
-
It is more of a general question, but is there any rule of thumb / way of thinking / mathematical formulation, that transforms a combinatorial "line" question to a "loop" question? I.E, asking questions 1 & 2, with same rule of rotations/reflections, but about a different set of configurations.
My progress so far:
The initial textbook question was formatted differently, but imagining it as necklaces and beads finally led me to search the right keywords and I found what I believe to be the correct approach to this problem. This wikipedia page seems to be talking exactly about that. The $N_k(n)$ , $L_k(n)$ , $B_k(n)$ are different countings of the necklaces under slightly different rules. Formulas are given for each, using common number-theoretical functions.
All $3$ functions allow $k \nmid n$ cases. $B_k(n)$ uses PET to count reflections as equivalent as well, and thus isn't what I am looking for. To my understanding, $N_k(n)$ allows any number of colours up to $k$ to be used, again not quite my goal. But The $L_k(n)$ formula seems promising, as it counts the configurations using exactly $k$ colours. The difference is that $L_k(n)$ counts $1$ red bead, $2$ yellow beads and $3$ green beads as a valid configuration (because it uses 3 colours), whereas my question deems it invalid, as it uses each colour a different number of times. I believe a modification to it can answer my original question but I cannot see how exactly and I also might be wrong.
Fortunately, the wikipedia page lists 2 examples with pictures that comply with my question rules. The $n=6 , k = 3$ case yields $16$ results. The $n=6 , k = 2$ yields $4$ results.
Also useful to watch and take results from is this page, listing results and configurations of $N_k(n)$ and $B_k(n)$ for arbitrary values of $n$ and $k$.
Best Answer
For the case of necklaces we have the cycle index
$$Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}.$$
We get with $k$ colors $Q_j$ (this is PET)
$$[Q_1^{n/k} \cdots Q_k^{n/k}] Z\left(C_n; \sum_{j=1}^k Q_j\right) = \frac{1}{n} \sum_{d|n} \varphi(d) [Q_1^{n/k} \cdots Q_k^{n/k}] \left(\sum_{j=1}^k Q_j^d\right)^{n/d}.$$
We see that $d$ must divide $n/k:$
$$\frac{1}{n} \sum_{d|n/k} \varphi(d) [Q_1^{n/k} \cdots Q_k^{n/k}] \sum_{m_1+\cdots+m_k = n/d} {n/d\choose m_1,\ldots, m_k} \prod_{j=1}^k Q_j^{d m_j}.$$
Here the $m_j$ are non-negative. Now we must have $d m_j = n/k$ so that $m_j = n/k/d$ and we get
$$\frac{1}{n} \sum_{d|n/k} \varphi(d) \frac{(n/d)!}{(n/k/d)!^k}$$
or alternatively
$$\bbox[5px,border:2px solid #00A000]{ \frac{1}{n} \sum_{d|n/k} \varphi(n/k/d) \frac{(kd)!}{d!^k}.}$$
As a sanity check with just one color $k=1$ we get $\frac{1}{n} \sum_{d|n} \varphi(n/d) = 1$, which is correct. With $k=n$ colors we get $\frac{1}{n} \sum_{d=1} \varphi(1/d) \frac{(nd)!}{(d!)^n} = \frac{1}{n} n! = (n-1)!$ which is correct as well. This is OEIS A208183.