# number of sequence of length $K$ from $N$ numbers sequence

I have a permutation of $3$ natural numbers taken from the set $S = \{1,2,..,10\}$ (so each number of the set can be taken once). Lets call this permutation $s$

Among all permutations of length $3$ of $S$, I want to compute how many of them have:

1. all $3$ numbers match the number of $s$ in same position
2. $2$ numbers match the number of $s$ in same position
3. $1$ number match the number of $s$ in same position
4. $0$ numbers match the number of $s$ in same position

Example $s = (2,4,7)$

1. the sequence $(2,4,7)$
2. all the sequences like

• $(2,4,x)$ where $x \neq 7$,
• $(2,x,7)$ where $x \neq 4$,
• $(x,4,7)$ where $x \neq 2$
3. all the sequences like

• $(2,x,y)$ where $x \neq 4 \wedge y \neq 7$
• $(x,4,y)$ where $x \neq 2 \wedge y \neq 7$
• $(x,y,7)$ where $x \neq 2 \wedge y \neq 4$
4. all the sequence $(x,y,z)$ where $x \neq 2 \wedge y \neq 4 \wedge z \neq 7$

I already compute this via R, so I know the solutions. I would like to have a formula for this specific case and if possible a general formula.

Answer Solution to the problem via R is:

1. $1$
2. $21$
3. $171$
4. $527$

My attempt of solution is this (for point 2.):

I have $1$ way among $10$ to select the first element, $1$ way among $9$ to choose the second element and then $7$ ways among $8$ to choose the third element. So I have $1\cdot 1 \cdot7$ ways to choose the sequence.

Since the 2 "correct" elements can be in different position within the sequence, I have to compute in how many ways this happen, i.e. $\binom{3}{2} = 3$. So $3\cdot7=21$. This is matching R results.

Applying this procedure to point 3. is not giving me a correct result. I think I figured out the problem but i don't know how to model it.

I have $1$ way among $10$ to choose the first element, then $8$ ways among $9$ to choose the second and $7$ among $8$ to choose the third. So I have $1 \cdot 8 \cdot 7 = 56$ ways, that I need to multiply by $\binom{3}{1} = 3$, so $168$ ways instead of $171$.

I think this is due to the fact that if I choose as second element the third element of $s$, whichever elements I will choose as third element it will be different from the third element of $s$. The problem is that I don't know how to model with a formula this part.

I hope I have been clear enough.

Is there anyone who can help me? Or maybe there is a easier way to compute?

Thanks.

Fix a triple from $S$ and let $x$ be the number of terms from your selected triple. Then $$\sum_{x=0}^3\binom{3}{x}\binom{S-3}{3-x}$$ will count all of the scenarios you describe. Each term of the above sum counts one of your scenarios.
• Thanks @Laars for the answer. Actually I couldn't understand why it should work. What is $N$? Mar 8, 2018 at 16:38
• I should have said $S$ and not $N$. My answer has been edited accordingly. You are making 3 objects in $S$ special and the remaining $S -3$ elements not special. Each term in the sum I defined consists of two factors: the first factor counts the number of ways we can select $x$ objects from the special set and the second factor counts the number of ways we select $3-x$ objects from the non special set. Mar 8, 2018 at 22:31
• Suppose $x=1$ and $S=10$. $\binom{S}{3}\binom{3}{x}\binom{S-3}{3-x} = \binom{10}{3}\binom{3}{1}\binom{10-3}{3-1} = 120 \cdot 3 \cdot 21 = 7560$. This is even more than the total number of permutations of length $3$ of $S$ (that is $720$). Am I wrong? Mar 9, 2018 at 9:17
• I do not agree. That sum is just counting the total number of combinations (order doesn't matter) and each term of the sum is the number of favourable outcomes for each $x$. Mar 12, 2018 at 11:06