# Counting Permutations: How many permutations of this set are there?

Question: Let $$n \geq 2$$ be an even integer. A permutation $$a_1; a_2; \ldots; a_n$$ of the set $$\{1,2, \ldots, n\}$$ is called awesome if $$a_2 = 2a_1$$. For example, if $$n = 6$$, then the permutation $$3; 6; 4; 1; 5; 2$$ is awesome, whereas the permutation $$3; 5; 4; 1; 6; 2$$ is not awesome. How many awesome permutations of the set $$\{1,2, \ldots, n\}$$ are there?

Answer: $$\frac{n}{2} \cdot (n-2)!$$

Attempt:

My understanding was since we need $$a_2 = 2a_1$$ then $$a_1 = a_2/2$$. So $$a_1$$ should be the form $$n/2$$. For $$a_2$$, I assumed since $$a_1$$ was already chosen to be $$n$$, then $$a_2$$ should be $$n-1$$. So the total permutations should be $$(n/2) \cdot (n-1)!$$

• How do you get $a_2 = n-1$ if $a_1 = n$? See the given condition carefully. Also, if $a_1$ is a natural number of the form $\frac n2$, then what does this say about $n$? You are also wrongly assigning $n$ to $a_1$ above : it should be to $a_2$. Nov 29, 2018 at 23:26

Not quite. $$a_1$$ should not necessarily be $$\frac{n}{2}$$; rather, it can be any number which is at most $$\frac{n}{2}$$. For example, $$2,4,1,3,6,5$$ would be awesome. So there's $$\frac{n}{2}$$ choices for $$a_1$$ in an awesome permutation, and once this is chosen, only one choice for $$a_2$$ (because it has to be $$2a_1$$). The rest of the $$n-2$$ numbers can be ordered arbitrarily in $$(n-2)!$$ ways, for a total of $$\frac{n}{2} (n-2)!$$ permutations.

First pick what $$a_2$$ is. It must be an even number from $$\{1,2,3,\dots,n\}$$. You should be able to convince yourself that you have exactly $$n/2$$ options for this step, namely picking from $$\{2,4,6,8,\dots,n\}$$ since if you were to pick an odd number instead then $$a_2/2$$ would not be an integer. Now that $$a_2$$ is selected, you then select $$a_1$$ and here we have no choices to make. Whatever you chose $$a_2$$ to be then $$a_1$$ must be half of that. From there we still have $$n-2$$ remaining positions to fill with the remaining numbers which can be done in $$(n-2)!$$ ways.

Let us have a running example of the results of our choices. Suppose that $$n=6$$ for now and let us display what we know about our permutation and underscores for missing information.

Setup: We have permutation of length six that we know nothing else about:

$$\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}$$

Step 1 : Pick what $$a_2$$ is. You have $$\frac{n}{2}$$ choices to make. In our case we can choose $$a_2$$ to be one of the numbers $$2,4,6$$. We have $$n/2$$ options available.

For illustrative purposes suppose that we selected $$4$$ as our choice. Our permutation currently looks like:

$$\underline{~~~}~~\underline{~4~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}$$

Step 2: Now that we know what $$a_2$$ looks like, we fill in $$a_1$$. Whatever $$a_2$$ happened to be, in order for $$a_2=2\cdot a_1$$ to be true that means that $$a_1$$ must be half of $$a_2$$. We have only one option for what $$a_1$$ looks like since we have already chosen what $$a_2$$ looks like. Yes, without having knowledge of what $$a_2$$ is, we would have many choices for $$a_1$$... however that is not the point. The point is that once $$a_2$$ has been decided we lose all control over what $$a_1$$ may be and we are left with only a single option for its value.

In our running example, since we had earlier selected $$a_2$$ to be $$4$$, that means that $$a_1$$ must be half of that, i.e. $$2$$. Our running example now looks like this:

$$\underline{~2~}~~\underline{~4~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}$$

Step 3: Now, let us choose what $$a_3$$ is. We cannot repeat whatever was selected for either of $$a_2$$ or $$a_1$$, leaving us with $$n-2$$ choices remaining.

In our running example, $$a_3$$ may be any of $$\{1,3,5,6\}$$ for a total of $$n-2=6-2=4$$ choices. Let us for illustrative purposes suppose we select $$5$$ for this value. Our running example now looks like this:

$$\underline{~2~}~~\underline{~4~}~~\underline{~5~}~~\underline{~~~}~~\underline{~~~}~~\underline{~~~}$$

Steps 4 - 6: Continue filling in the next entry in the sequence, making sure not to repeat anything previously selected. These steps have $$3,2,1$$ options remaining respectively.

Multiplying the number of options available for each step, we get $$\frac{n}{2}\times 1\times (n-2)\times (n-3)\times (n-4)\times \cdots \times 2\times 1 = \frac{n}{2}(n-2)!$$ total arrangements.

• why don't we have no choices for a1 in this case? Shouldn't a1 have n choices? And if it doesn't have any choice, then shouldn't the remaining permutations be (n-1)!? Because only a2 was assigned n/2 choices? I maybe confused about this
– Toby
Nov 29, 2018 at 23:50
• @Toby I attempted to extend the explanation a bit more. Nov 30, 2018 at 0:20
• That was a crystal clear explanation, I understand it now! Thank you.
– Toby
Nov 30, 2018 at 0:49