1
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Thanks @Laars for the answer. Actually I couldn't understand why it should work. What is $N$? $\endgroup$
    – lore10
    Mar 8, 2018 at 16:38
  • $\begingroup$ 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. $\endgroup$ Mar 8, 2018 at 22:31
  • $\begingroup$ 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? $\endgroup$
    – lore10
    Mar 9, 2018 at 9:17
  • $\begingroup$ I deleted the final formula. There was nothing wrong with it but it wasn’t related to your question. The first formula is the only one that you need. I have edited my answer above accordingly. $\endgroup$ Mar 9, 2018 at 21:39
  • $\begingroup$ 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$. $\endgroup$
    – lore10
    Mar 12, 2018 at 11:06

You must log in to answer this question.

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