# Determine the number of permutations of $\ \{1,2,3,4,5,6,7,8,9,10\} \$ that have exactly 3 numbers in their natural position

Determine the number of permutations of $\ \{1,2,3,4,5,6,7,8,9,10\} \$ that have exactly 3 numbers in their natural position.  Is it $\ \ \begin{pmatrix} 10 \\ 3 \end{pmatrix} \times 7 ! \$ ?

• The answer is no, because some of those $7!$ orderings will put additional numbers in their natural position. – vadim123 Apr 18 '17 at 18:44

No, because $7!$ allows for extra elements to be in their natural position. After the $3$ fixed position items are selected, you need a derangement of the remaining $7$ items.
You need choose $3$ elements that stay on their positions in $\binom{10}{3} = 120$ and multiply it by the number $!7$ of permutations of special kind called derangement on remaining $7$ elements. There are many ways to compute number $!k$ (see link), particularly it is known to be equal to $\frac{k!}{e}$ rounded to the nearest integer. Therefore $\frac{5040}{e} \approx 1854 =\,!7$ and the desired number of permutations on $10!$ elements keeping exactly $3$ of them in place is $\binom{10}{3} \cdot\,!7 = 120 \cdot 1854 = 222\,480$.
Another way to compute number of such permutation is inclusion-exclusion principle. There are $\binom{10}{3}\cdot 7!$ ways to select $3$ elements to stay in place and permute all remaining. But for each of $\binom{10}{4}$ ways to select $4$ elements each permutation that keeps them in place was computed $4$ times, but should not be computed at all. Continuing these thoughts we get that the right number of desired permutations is $$\binom{10}{3}\cdot 7! - \binom{10}{4} \cdot 6! \cdot \binom{4}{3} + \binom{10}{5} \cdot 5! \cdot \binom{5}{3} - \binom{10}{6} \cdot 4! \cdot \binom{6}{3}\\ + \binom{10}{7} \cdot 3! \cdot \binom{7}{3} - \binom{10}{8} \cdot 2! \cdot \binom{8}{3} + \binom{10}{9} \cdot 1! \cdot \binom{9}{3} - \binom{10}{10} \cdot 0! \cdot \binom{10}{3}\\ = 604800 - 604800 + 302400 - 100800 + 25200 - 5040 + 840 - 120 = 222480.$$
$\binom{n}{3}[!(n-3)]$ where $n=10$ and $$!k = k! \sum_{i=0}^k \frac{(-1)^i}{i!}$$.
No. The number of permutations in $S_{10}$ which have exactly $3$ fixed points is ${10 \choose 3} \times D_7$, where $D_7$ denotes the number of permutations of a $7$-element set which contain no fixed points (the number $D_7$ of derangements in $S_7$ can be computed using the principle of inclusion-exclusion).