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

Question

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.

Answer 1

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.