2
$\begingroup$

Question

Let $S_n$ be a set of permutations of the set $ \{\ 1, \dots ,n \}\ $.

Call a permutation good if the odd integers appear in the odd positions in the permutation and the even integers appear in the even positions.

For example, the permutation 1432 is good.

Determine the number of good permutations in $S_n$.

My solution

Notice that for the first position we have an odd number. We can therefore choose $ \lceil \frac{n}{2} \rceil $ numbers for this position. The next position is an even number and we can therefore choose $ \lfloor \frac{n}{2} \rfloor $ numbers for this position.

We end up with a pattern: $ \lceil \frac{n}{2} \rceil \cdot \lfloor \frac{n}{2} \rfloor \cdot \lceil \frac{n}{2} \rceil -1 \cdot \lfloor \frac{n}{2} \rfloor -1 \dots1 = $ $$ \lceil \frac{n}{2} \rceil ! \cdot \lfloor \frac{n}{2} \rfloor !$$

What do you think?

$\endgroup$
  • 1
    $\begingroup$ Yes. It's the count of arrangements of the odd numbers in the odd positions times the count of arrangements of the even numbers in the even positions. $\endgroup$ – Graham Kemp Mar 19 '14 at 12:54
  • 1
    $\begingroup$ The formula is fine. I would prefer $k!k!$ if $n=2k$ and $(k+1)!k!$ if $n=2k+1$. $\endgroup$ – André Nicolas Mar 19 '14 at 13:51

Your Answer

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

Browse other questions tagged or ask your own question.