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


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

  • 2
    $\begingroup$ 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$. $\endgroup$ Nov 29, 2018 at 23:26

2 Answers 2


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:


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:


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:


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:


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.

  • $\begingroup$ 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 $\endgroup$
    – Toby
    Nov 29, 2018 at 23:50
  • 1
    $\begingroup$ @Toby I attempted to extend the explanation a bit more. $\endgroup$
    – JMoravitz
    Nov 30, 2018 at 0:20
  • $\begingroup$ That was a crystal clear explanation, I understand it now! Thank you. $\endgroup$
    – Toby
    Nov 30, 2018 at 0:49

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .