0
$\begingroup$

Let $ A= \{ 1,2,3,4,5,6,7,8,9 \} $ consider functions $f:A \to A$ that are onto how many of these functions satisfy that for all even x. $f(x) \neq x$

Firstly i notice that a is finite so this is a bijective map if it is onto implying that this is a permutation on 10 symbols so there are 10! unique functions. now i now i need to perform a Derangement of all the even numbers in the set while doing what i please with the odd numbers.

What i would really like to do is consider all of the derangement's then divide it by 2 and subtract the number from n! but im not sure that would actually be the right number.

$\endgroup$
1
  • 1
    $\begingroup$ Did you mean $A=\{1\ldots 10\}$? $\endgroup$ Mar 1, 2017 at 7:01

1 Answer 1

1
$\begingroup$

We can count them using Inclusion-Exclusion as we do for derangements, but we restrict to the even numbers:

  • Include $9!$ permutations.

  • Exclude $\binom{4}{1} 8!$ permutations which map at least one even number to itself.

  • Include $\binom{4}{2} 7!$ permutations which map at least two even numbers to themselves.

  • Exclude $\binom{4}{3} 6!$ permutations which map at least three even numbers to themselves.

  • Include $\binom{4}{4} 5!$ permutations which map all four even numbers to themselves.

Thus, Inclusion-Exclusion gives $$9!-\binom{4}{1} 8!+\binom{4}{2} 7!-\binom{4}{3} 6!+\binom{4}{4} 5!=229080.$$

This number can be verified using the GAP code

Number(SymmetricGroup(9),alpha->ForAll([2,4,6,8],i->i^alpha<>i));

which returns 229080, or we could even generate them all using

Filtered(SymmetricGroup(9),alpha->ForAll([2,4,6,8],i->i^alpha<>i));
$\endgroup$

You must log in to answer this question.

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