Cfrgtkky

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

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=2cdot 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 1times (n-2)times (n-3)times (n-4)times cdots times 2times 1 = frac{n}{2}(n-2)!$ total arrangements.

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.