1
$\begingroup$

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?

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.