0
$\begingroup$

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

$\endgroup$
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

4
$\begingroup$

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.

$\endgroup$
0
3
$\begingroup$

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.

$\endgroup$
3
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.