4
$\begingroup$

I am supposed to solve the following problem:

How many permutations of the set $\{1, 2,. . . , 8\}$ do not leave any even number in its place?

What I tried:

$$8!-\left ( \binom{8}{1}7!-\binom{8}{ 2}6!+\binom{8}{3}5!-\binom{8}{4}4! \right )$$

But I know that this is incorrect.

Can anyone tell me why?

$\endgroup$

2 Answers 2

3
$\begingroup$

Let $A_k$ be the number of permutations that fix the $2k$-th element. By Inclusion-Exclusion, $$|A_1\cup A_2\cup A_3\cup A_4|=\sum_{1\leq w\leq4}|A_w|- \sum_{1\leq w<x\leq4}|A_w\cap A_x| +\sum_{1\leq w<x<y\leq4}|A_w\cap A_x\cap A_y|- \sum_{1\leq w<x<y<z\leq4}|A_w\cap A_x\cap A_y\cap A_z|$$ $$=\binom{4}{1}\cdot 7!-\binom{4}{2}\cdot 6!+\binom{4}{3}\cdot 5!-\binom{4}{4}\cdot4!=16296.$$This counts the number of permutations that fix at least one of the even elements, so our final answer is $8!-16296=24024$.

$\endgroup$
2
  • $\begingroup$ Oh okay, but if I will choose just 1 from 4, how can I make sure that 7! does not include the even place for even number? $\endgroup$
    – Peter F.
    Oct 27, 2019 at 17:06
  • 1
    $\begingroup$ For any $1\leq w\leq4$, the first term counts the number of ways to permute the set without changing a fixed element. This term therefore evaluates to $7!$ times the number of ways to choose such $w$, which is $\binom{4}{1}$. The other terms are calculated analogously. $\endgroup$
    – ViHdzP
    Oct 27, 2019 at 17:16
3
$\begingroup$

Let $S_j$ be the set of arrangements with $2j$ left in place. Then $$ N_k=\overbrace{\ \ \ \binom{n}{k}\ \ \ }^{\substack{\text{number of}\\\text{ways to pick}\\\text{the $k$ fixed}\\\text{numbers}}}\overbrace{\vphantom{\binom{n}{k}}(2n-k)!}^{\substack{\text{arrangements}\\\text{of the}\\\text{remaining}\\\text{numbers}}} $$ According to the Generalized Inclusion-Exclusion Principle, the number of arrangements in none of the $S_j$ is $$ \sum_{k=0}^n(-1)^kN_k $$ for $n=4$, this gives $$ \binom{4}{0}8!-\binom{4}{1}7!+\binom{4}{2}6!-\binom{4}{3}5!+\binom{4}{4}4!=24024 $$

$\endgroup$
0

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.