1
$\begingroup$

So I just finished working out a probability question which I came across on the Brilliant website, where there is a game of tennis that finishes when someone reaches four points (ignoring deuces, it's just the first person to reach 4 points). Person A has probability p to win one point, with his opponent having probability q to win (obviously q = 1 - p). The aim is to find the probability of Person A winning the entire match (this is the question here). After a while, I came up with the solution, which was correct, of the probability of Person A winning the whole match being:

$p^4 + 4p^4q+10p^4q^2 + 20p^4q^3$

However, to work out the number of permutations that existed for each different possible point distribution, I simply wrote out each one manually. EG:

$ qqpppp $, $qpqppp$, $qppqpp$,

until I had written out every permutation for that combination of p and q. My question, therefore, is this: how can you figure out the amount of different permutations without writing this all down manually. Keep in mind you cannot end the permutation with q, as as soon as p has won the 4th point the game ends.

I have given this problem multiple attempts, all of which have been unsuccessful. The closest I came was taking the number of digits and subtracting one, and then multiplying that by itself minus 1 for every instance of q in the permutation (long story short, it didn't work). If anyone can explain how to achieve this, it would be much appreciated.

Many thanks in advance.

$\endgroup$
2
$\begingroup$

First of all since you can't end with $p$ you only have to consider reordering of the outcomes up to the last $p$. You wan't to know how many ways you can reorder $qqppp$ (and then you're going to append a $p$ to all of these ways). The way you do this is that you consider how many way you can place the first $q$ which is $5$, then the second $q$ can be put in $4$ places which makes this $5\times 4 = 20$ ways you can place two $q$'s (and the $p$'s have to be placed at the rest of the places).

But this is only true if it differs if there's a difference in the $q$'s, but there isn't - it doesn't matter if you first place a $q$ as the second, and the next as first or you first place a $q$ as first and then the next $q$ as second.

To correct for this you consider you're $q$'s distinct and count the number of ways you can permunte them. This is done in a similar way. Given the positions where you have them you select one of them in the first position, which can be done in $2$ ways. Then for the second position you have only one $q$ left and that can be selected in one way.

If you generalize this: if you have $k$ $q$s to be placed in $n$ places (that is you have $n-k$ $p$s) you have $n(n-1)\cdots(n-k+1)=n!/(n-k)!$ ways to do this and to correct for the order which the $q$s are placed you have $k$ ways to arrange the $q$s without making any difference. So you have ${n!\over(n-k!)k!}$ way's to do this.

Using this your formula becomes:

$${3!\over 3!0!}p^4 + {4!\over3!1!}p^4q + {5!\over3!2!}p^4q^2 + {6!\over3!3!}p^4q^3$$

$\endgroup$
1
$\begingroup$

You don't want $q$ on the last position. In other words - you want $p$ on the last position. So the problem where you want to permutate $k$ $q$s and $m$ $p$s with no $q$ on the last position is the same as the problem, where you permutate $k$ $q$s and $m-1$ $p$s with no additional conditions.

Now you have $k+m-1$ places, where you can place $k$ $q$s ($p$s will go on not selected places). You may pick then $k$ places out of $k+m-1$. Nomber of ways you can do this is equal to the number of combinations, ie. $C_k^{m+k-1}={m+k-1 \choose k}$.

For example - to place $4$ $p$s and $2$ $q$s:

$m=4, k=2$

$C_2^{4+2-1} = {5 \choose 2}=10$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.