# Number of possible permutations

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.

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.

$${3!\over 3!0!}p^4 + {4!\over3!1!}p^4q + {5!\over3!2!}p^4q^2 + {6!\over3!3!}p^4q^3$$
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$