Given a set of unique elements, the total number of (unique) permutations is n!.

For the purpose of my problem, there's an addition to normal equality rules (ABCD == ABCD):

  • Two permutations are equal if one is the reverse of the other: ABCD == DCBA

I've found the following lower bounds (elements = lower bound):

  • 2 = 1
  • 3 = 3
  • 4 = 15

After the number of permutations reach the lower bound, any computation is stopped, because further permutations are guaranteed to be equal to earlier permutations.

My question is:

How is the lower bound for the number of permutations of n distinct elements calculated, that satisfies the condition ABCD == DCBA?

  • $\begingroup$ How did you find the bounds you give? $\endgroup$ Dec 21 '18 at 20:19
  • 1
    $\begingroup$ Each permutation is matched with exactly one other permutation and the matching is bijective. You should be able to convince yourself rather quickly that in doing so you have effectively cut the total number of "different" permutations in half. (with the exception of the case where $n=1$) $\endgroup$
    – JMoravitz
    Dec 21 '18 at 20:19
  • 1
    $\begingroup$ As an aside, $\dfrac{4!}{2}=12\neq 15$... if you were brute force writing each of these out, you should be more careful and check again your work for $n=4$. $\endgroup$
    – JMoravitz
    Dec 21 '18 at 20:20
  • $\begingroup$ @MiloBrandt I wrote it out by hand $\endgroup$ Dec 21 '18 at 20:25
  • $\begingroup$ The whole purpose of an introductory combinatorics course (or really, any maths course beyond elementary school) is to learn how to do calculations without having to resort to brute force listing things out and counting with your fingers and toes. Doing so to try to spot patterns is fine to a certain extent, however it should never be relied on. Brute force counting is dangerously prone to mistakes (as evidenced here). $\endgroup$
    – JMoravitz
    Dec 21 '18 at 20:31

First, it's worth commenting on the notation, because this is a case where clear notation makes the answer easy to see. Usually, instead of redefining equality (which leads to all sorts of headaches), one instead defines an equivalence relation, which is just some rule for grouping together objects. A common notation is to write $a\sim b$ to mean that objects $a$ and $b$ are equivalent. So, you might write your question as:

Let us define a relation $\sim$ on the set of permutations where a permutation $ABCD$ is equivalent exactly to itself $ABCD$ and its reverse $DCBA$.

Where you would write then be able to write $ABCD\sim DCBA$ with it being clear what was meant.

Then, there are things called equivalence classes which are the sets of equivalent elements; so $\{ABCD,DCBA\}$ is an equivalence class. Your question is essentially how many equivalence classes there are, since each equivalence class represents one "distinct" permutation under your notion of equivalence.

For instance, for permutations of three elements, the equivalence classes are as follows $$\{ABC,CBA\}$$ $$\{ACB,BCA\}$$ $$\{BAC,CAB\}.$$ If you want to find a maximal set of permutations, no two equivalent to each other, you can just choose one element from each set. You can also come up with a rule to choose one element - for instance "choose the permutations whose first item is alphabetically before its last item" will give you one representative from each class.

However, then the general count is clear: as long as you have at least two items to permute, no permutation is the reverse of itself, so every equivalence class has $2$ elements. There are $n!$ permutations, so there must be $\frac{n!}2$ equivalence classes.

Note that there are some rules to what qualifies as an equivalence relation - basically, they amount to saying that the equivalence classes really do group the elements - there is never any overlap between distinct classes and every element is in some class. There's plenty of resources giving more formal descriptions that one can find knowing the term.


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.