Computing a lower bound for permutations where ABCD is equal to its reverse (DCBA)?

Question

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?

Answer 1

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.