4
$\begingroup$

I have this homework question I'm kind of stumped on...

"A permutation of the numbers $(1,2,3,\ldots,n)$ is a rearrangement of the numbers in which each number appears exactly once. For example, $(2,5,1,4,3)$ is a permutation of $(1,2,3,4,5)$.

Let $\pi = (x_1,x_2,x_3,\ldots,x_n)$ be a permutation of the numbers $(1,2,3,\ldots,n)$. A fixed point of $\pi$ is an integer $k~(1\le k\le n)$ such that $x_k=k$. For example, $4$ is a fixed point of the permutation $(2,5,1,4,3)$.

How many permutations of $(1,2,3,4,5,6,7)$ have at least one even fixed point?"

Here's my work so far. Am I going in the right direction? Should I be thinking differently?

$(1)$ can have 1 fixed point permutation.

$(1,2)$ can have 1 fixed point permutation

$(1, 2, 3)$ can have 4 fixed point permutations?

$(1, 2, 3, 4)$ can have 15 fixed points?

I couldn't find any correlations or patterns here...

$(1)$ can have 0 even fixed point permutations

$(1, 2)$ can have 1 even fixed point permutation

$(1, 2, 3)$ can have 2 even fixed point permutations

$(1, 2, 3, 4)$ can have 6 even fixed point.

It's not factorials, or triangular numbers, so I'm kind of stuck here. What should I do next?

$\endgroup$
  • 1
    $\begingroup$ Search oeis. You will probably find it there $\endgroup$ – Per Alexandersson Jun 18 '15 at 1:21
  • 1
    $\begingroup$ The opposite problem is counting derangements (permutations with no fixed points). You can google this keyword for more information. In particular, you can count the number of derangements using the inclusion-exclusion principle. $\endgroup$ – whacka Jun 18 '15 at 1:24
3
$\begingroup$

There are $7!$ permutations of the set $\{1,...,7\}$. $6!$ permutations fix $2$, $6!$ fix $4$ and $6!$ fix $6$. $5!$ permutations fix any two elements from $\{2,4,6\}$ and $4!$ permutations fix all three.

So the total number of permutations that fix at least one element from $\{2,4,6\}$ is $3*6!-3*5!+4!=1824$ (by the inclusion-exclusion principle).

$\endgroup$
  • 1
    $\begingroup$ Thanks Edward! I forgot about PIE here. $\endgroup$ – Kbot Jun 18 '15 at 1:41

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.