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

Question

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)!$

Answer 1

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.

Answer 2

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.