# Number of combinations without reversed repeats

I have a unique constraint for needing to calculate the number of possible permutations.

I have 6 objects, each of which can be in 4 states. Superficially this could be expressed as 4^6 which is 4096.

However I need to strip out any mirrored repeats.

If we represented this problem numerically where I had 6 digits that could range from 1-4, this would mean:

111112 211111

are considered equivalent and I would want to not count them.

Similarly 123123 = 321321 and so on.

Can anyone come up with this solution and a means of calculating it?

• Possible strategy. Count the number that are the same forwards and backwards. Then add half the remaining number. Sep 30 '16 at 16:47

I’ll generalize to strings of $2n$ objects, each of which can be in $m$ states; these can be represented by strings of length $2n$ over $[m]=\{1,\ldots,m\}$. There are $m^n$ different strings of length $n$, each of which gives rise to exactly one palindrome of length $2n$ by concatenation with its reversal, and each palindrome of length $2n$ arises in this way, so there are $m^n$ palindromes of length $2n$. Each of these palindromes is equivalent only to itself. The remaining $m^{2n}-m^n$ strings come in equivalent pairs, so they fall into $\frac12(m^{2n}-m^n)$ equivalence classes, and the total number of equivalence classes is therefore

$$m^n+\frac12\left(m^{2n}-m^n\right)=\frac12\left(m^{2n}+m^n\right)=\frac{m^n\left(m^n+1\right)}2\;.$$

In your case $n=3$ and $m=4$, and you get

$$\frac{4^3\left(4^3+1\right)}2=32\cdot 65=2080$$

equivalence classes.

For strings of length $2n+1$ over $[m]$ each palindrome is determined by the first $n+1$ elements, so there are $m^{n+1}$ of them, and the same reasoning leads to the conclusion that there are

$$m^{n+1}+\frac12\left(m^{2n+1}-m^{n+1}\right)=\frac{m^{n+1}\left(m^n+1\right)}2$$

equivalence classes.

In general, then, for strings of length $n$ over $[m]$ there are

$$\frac12m^{\lceil n/2\rceil}\left(m^{\lfloor n/2\rfloor}+1\right)$$

equivalence classes.

• Incredibly detailed answer. Thanks so much! Oct 2 '16 at 8:36
• @monkeymatrix: You're very welcome! Oct 2 '16 at 8:52