Number of Unique Sequences with Circular Shifts

I'm trying to determine the number of binary sequences containing exactly $a$ $1$'s and $b$ $0$'s if two sequences are considered identical if they can be reached from the each other by a series of circular shifts (moving the first bit to the end). For instance, for $a=b=4$, $10110010$ and $11001010$ would be considered the same.

At first, I assumed that there would simply be $\frac{(a+b-1)!}{a!b!}$ unique sequences because there are $\frac{(a+b)!}{a!b!}$ different sequences without circular shifts and each unique sequences with can reach $a+b$ different sequences with them; but some sequences, such as $10101010$ can become themselves after a series of circular shifts (in this case $2$, $4$, or $6$). Thus, there are actually more unique sequences. Thank you in advance for any assistance you can provide on this topic.

Edit: If the general solution is too difficult, I'm especially interested in situations where $a+b = p$ or $a = b = p$ for some prime $p$.

Solution 1:

The answer (number of distinct sequences with $a$ $1$'s and $b$ $0$'s, where rotations are treated as equivalent) is a sum over common divisors of $a$ and $b$:

$$\frac1{a+b} \sum_{d \,\mid\, \gcd(a,b)} \phi(d) \binom{a/d + b/d}{a/d}$$

Proof below, but for the special cases you mentioned:

• when $a + b = p$ is prime and both $a$ and $b$ are nonzero (or more generally whenever $\gcd(a, b) = 1$), then the only common divisor of $a$ and $b$ is $1$, so the number is: $$\frac{1}{a+b} \binom{a+b}{a} = \frac{1}{a+b} \frac{(a+b)!}{a!b!}$$

• when $a = b = p$ for some prime $p$, then the common divisors of $a$ and $b$ are $1$ and $p$, so $$\frac{\binom{a+b}{a} + (p-1)\binom{1+1}{1}}{2p} = \frac{\binom{2p}{p} + 2(p-1)}{2p}$$

The ultimate tool for such problems (at least, ones that don't require Pólya theory) is Burnside's lemma ("the lemma that is not Burnside's"), which states that for a group $G$ acting on a set $X$, the number of distinct orbits is $$|X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g|.$$

For our case of counting necklaces (strings treated as equivalent under rotations (=circular shifts)), the group $G$ is that of the $n$ possible rotations. Suppose all the necklaces we are concerned about are of length $n$. For a particular rotation $g$ which is a rotation by some number $k$, the set $X^g$ denotes those sequences that are left invariant by a rotation by $k$, i.e. those in which every $k$th symbol is the same. If $\gcd(n, k) = n/d$, this means that there is essentially a string of length $n/d$, which is repeated $d$ times. And the number of $k$ such that $\gcd(n, k) = n/d$ is $\phi(d)$.

Thus, $$ \begin{align} |X/G| &= \frac1n \sum_{k=0}^{n-1} \text{(number of strings of length $\gcd(n, k)$)} \\ &= \frac1n \sum_{d \mid n} \phi(d) \cdot \text{(number of strings of length $n/d$)} \tag 1 \end{align}$$

just as in the necklace-counting theorem.

All the above is very general (to count necklaces of length $n$), but in our case, the number of strings of length $n/d$ is not $k^{n/d}$ as in the theorem that counts the number of $k$-ary necklaces. If we want to make a string of length $n$ containing $a$ $1$s and $b$ $0$'s, out of $d$ copies of a string of length $n/d$, then that smaller string must have $a/d$ $1$'s and $b/d$ $0$'s, which is only possible if $d$ divides both $a$ and $b$ (and therefore $\gcd(a, b)$). In that case, the number of strings of length $n/d = a/d + b/d$ that contain $a/d$ $1$'s and $b/d$ $0$'s is $\binom{a/d + b/d}{a/d}$. Plugging this into $(1)$ gives the expression stated at the beginning of the answer:

$$\frac1{a+b} \sum_{d \mid \gcd(a,b)} \phi(d) \binom{a/d + b/d}{a/d}$$

Solution 2:

The total number of sequences (without circular shifting) with precisely $a$ $1$'s and $b$ $0$'s is $\tbinom{a+b}{a}=\tbinom{a+b}{b}$. If either $a=0$ or $b=0$ then there is of course only one such sequence.

For any sequence of length $a+b$, the number of cyclic shifts $d$ required to return the original sequence is a divisor of $a+b$. In particular, if $a+b=p$ is prime we must have $d=1$ or $d=p$. If $d=1$ for some sequence then either $a=0$ or $b=0$. Hence if $a\neq0$ and $b\neq0$ then every sequence has precisely $a+b=p$ distinct cyclic shifts, including itself. The number of distinct sequences is therefore precisely $$\frac{1}{a+b}\binom{a+b}{a}=\frac{1}{p}\cdot\binom{p}{a}=\frac{(p-1)!}{a!\cdot b!}.$$

If $a+b=2p$ then for any sequence the number of cyclic shifts $d$ required to return to the original sequence is either $1$, $2$, $p$ or $2p$. Again if it is $1$, then either $a=0$ or $b=0$, and then there is only one such sequence. So suppose $a\neq0$ and $b\neq0$ for now.

There is only one sequence returned to its original after $2$ cyclic shifts; this is $1010\ldots1010$ up to shifting. For this we must have $a=b=p$.

A sequence that returns to its original after $p$ cyclic shifts is a sequence of length $p=(a+b)/2$ repeated twice. For the prime case we have already counted $$\frac{1}{(a+b)/2}\binom{(a+b)/2}{a/2}=\frac{1}{p}\cdot\binom{p}{a/2}=\frac{(p-1)!}{(a/2)!\cdot(b/2)!},$$ such sequences, and its a nice exercise to check that distinct sequences of length $p$ yield distinct sequences of length $2p$ when repeating them twice. So number of such sequences is precisely $$\frac{(p-1)!}{(a/2)!\cdot(b/2)!}.$$ For this we must have both $a$ and $b$ even.

This allows us to count the number of distinct sequences if $a+b=2p$. If $a$ and $b$ are not both even, and $a\neq p$ and $b\neq p$, then ever sequence has precisely $a+b=2p$ distinct cyclic shifts, so just like in the prime case the number is $$\frac{1}{a+b}\binom{a+b}{a}=\frac{1}{2p}\cdot\binom{2p}{a}=\frac{(2p-1)!}{a!\cdot b!}.$$ If $a$ and $b$ are both even (and nonzero) but $a\neq p$ and $b\neq p$, then we count seperately the sequences that are returned after $p$ cyclic shifts, and those that are not. The number is then $$\frac{1}{a+b}\left(\binom{a+b}{a}-\binom{(a+b)/2}{a/2}\right)+\frac{1}{(a+b)/2}\binom{(a+b)/2}{a/2}=\frac{1}{2p}\left(\binom{2p}{a}+\binom{p}{a/2}\right).$$ If $a=b=p$ but $a$ and $b$ are not both even, then we count seperately the sequences that are returned after $2$ cyclic shifts, and those that are not. The number is then: $$\frac{1}{a+b}\left(\binom{a+b}{a}-2\right)+1=\frac{1}{2p}\left(\binom{2p}{p}-2\right)+1.$$ The only remaining case is $a=b=2$, which is easily counted by 'brute force'.

To generalise these results, if you are familiar with some group theory you could try applying Burnside's lemma. You may also want to look at the problem of counting necklaces, which is related.

Solution 3:

Perhaps I can make a modest contribution to this fascinating discussion by encouraging everybody to give the Polya Enumeration Theorem (PET) a try which is no more difficult than Burnside. Both involve iterating over the disjoint cycle decompositions of the permutations from the group that permutes the slots on the "necklace" and therefore produce the cycle index anyway, so that nothing stops us from applying PET.

The cycle index $Z(C_n)$ of the cyclic group is given by $$ Z(C_n) = \frac{1}{n} \sum_{d|n} \varphi(d) a_d^{n/d}.$$

Then PET says that the number of circular shift sequences is given by $$ [A^a B^b] Z(C_n)(A+B).$$

Doing the substitution we get $$[A^a B^b] \frac{1}{n} \sum_{d|n} \varphi(d) (A^d+B^d)^{n/d}.$$

Now use the binomial theorem to get the equivalent formula $$[A^a B^b] \frac{1}{n} \sum_{d|n} \varphi(d) \sum_{q=0}^{n/d} {n/d\choose q} A^{qd} B^{(n/d-q)d}$$ which is $$[A^a B^b] \frac{1}{n} \sum_{d|n} \varphi(d) \sum_{q=0}^{n/d} {n/d\choose q} A^{qd} B^{n-qd}.$$

We see that the exponents of the powers of $A$ and $B$ sum to $n = a+b$, so if the term $A^a B^b$ occurs in the binomial expansion we must have $a=qd$ for some $q.$ But $d$ is a divisor of $n=a+b$ so if it divides $a$ it also divides $b$. Therefore we can restrict the sum as follows: $$[A^a B^b] \frac{1}{n} \sum_{d|\mathrm{GCD}(a,b)} \varphi(d) \sum_{q=0}^{n/d} {n/d\choose q} A^{qd} B^{n-qd}.$$

We are ready to conclude and proceed to apply the coefficient extraction operator in front by setting $q=a/d$ to get $$\frac{1}{n} \sum_{d|\mathrm{GCD}(a,b)} \varphi(d) {n/d\choose a/d}.$$

We may replace $n$ by $a+b$ to emphasize the dependence on the two types $A$ and $B$ which yields $$\frac{1}{a+b} \sum_{d|\mathrm{GCD}(a,b)} \varphi(d) {a/d+b/d\choose a/d}.$$