Determine the number of elements $f$ of $S_n$ for which $f(1) \ne 1$ and $f(2) \ne 2$.

Question

$S_n$ is the group consisting of the set of all bijections from $\{1,2,...,n\}$ to $\{1,2,...,n\}$.

For $n\geq 2$, determine the number of elements $f$ of $S_n$ for which $f(1) \ne 1$ and $f(2) \ne 2$.

The way I tried to solve it is by using the fact that $$|A \cup B|=|A|+|B|-|A\cap B|$$ Where $|A|$ is the amount of possible functions such that $f(1)\ne 1$ and $|B|$ is the amount of possible functions such that $f(2)\ne 2$. With this in mind, I let $|A| = n^n-n$ and $|B|=n^n-n$ but now I am stuck. Please help!

Answer 1

Normally $S_n$ denotes the set of permutations of $\{1,2,\ldots,n\}$, that is the bijections from the set to itself. I'll assume you mean $S_n$ in the remainder of your question. If you really mean $F_n$ you will have to amend the argument appropriately.

Better to let $A$ and $B$ denote the sets of elements of $S_n$ with $f(1)=1$ and $f(2)=2$ respectively. The number of elements of $S_n$ with both $f(1)\ne1$ and $f(2)\ne2$ is then $$|S_n|-|A\cup B|=|S_n|-|A|-|B|+|A\cap B|.$$

As we are dealing with permutations, $|S_n|=n!$. Now $A$ is basically the set of permutations of $\{2,3,\ldots,n\}$ so $|A|=(n-1)!$. Similarly $|B|=(n-1)!$. Then $A\cap B$ is formed of the permutations with $f(1)=1$ and $f(2)=2$. These permute $\{3,4,\ldots,n\}$ freely, so there are $(n-2)!$ of them, etc.

Answer 2

I would do like this: Let $A_i$ be a set of functions with $f(i)=i$. Then $|A_i|= (n-1)!$ and $|A_i\cap A_j|=(n-2)!$. You are interested in $|A_1'\cap A_2'|$

$$|A_1'\cap A_2'| = n!-|A_1\cup A_2| = n!-2(n-1)!+(n-2)!$$ $$= (n-2)!(n^2-n-2n+2+1)=(n-2)!(n^2-3n+3)$$

Answer 3

You made two major mistakes in what you started with.

First, letting $A$ represent the set of functions such that $f(1)\neq 1$ and $B$ the set of functions where $f(2)\neq 2$, the amount $|A\cup B|$ then represents the amount of functions such that $f(1)\neq 1$ OR $f(2)\neq 2$. The problem statement as you wrote it is actually looking for $|A\cap B|$.

Second, in your attempt you calculated $|A|=n^n-n$. This is also incorrect. In calculating $|A|$, approach with multiplication principle (a.k.a. rule of product). Choose the value of $f(1)$. Then choose the value of $f(2),f(3),\dots$. You should find that $|A|=(n-1)\times (n-1)\times (n-2)\times (n-3)\times \cdots=(n-1)\times (n-1)!$

It is possible that part of your confusion here is in forgetting that $S_n$ represents the set of permutations.

As for an approach on how to calculate $|A\cap B|$, approach with a mix of multiplication principle and addition principle.

Break into cases. Either $f(1)=2$ or $f(1)\neq 2$.

In the first case, we have one option for $f(1)$, then $f(2)$ has $n-1$ options. Each following value has a decreasing number of options ranging from $n-2$ to $1$, giving $1\times (n-1)\times (n-2)!$ functions in this case.

In the second case, we have $n-2$ options for $f(1)$, then $f(2)$ has $n-2$ options as well. Each following value has a decreasing number of options again ranging from $n-2$ to $1$, giving $(n-2)\times (n-2)\times (n-2)!$ functions in this case.

This gives a total of $((n-1)+(n-2)^2)(n-2)!$ total such functions.

---

If you intend it to be $F_n$ instead of $S_n$, then most of my criticisms above are still valid and you would have instead $|A|=(n-1)\times n^{n-1}=n^n-n^{n-1}$, not $n^n-n$ and you would have $|A\cap B|=(n-1)^2n^{n-2}$