Permutations Discrete Math

Question

Roll a standard die n times. For finding the number of permutations of getting exactly k 3's you would do ${n\choose k} \cdot {5} ^{n-k} $ But what about finding at least k 3's? I was thinking of going along the lines of $6^{n}-5^{n}-5^{n - 1} ...-5^{n-k+1}$ which would be total - all rolls without the number 3 minus all the rolls with one 3 minus all the rolls... and keep subtracting until you get to $n - k + 1$ spaces to fill without a 3. This could be wrong and furthermore is there a better equation?

Answer 1

Arthur's right in both points - multiply by the binomial coefficients and there aren't any "better" equations except maybe approaching it from the opposite direction.

However, you can sometimes find shortcuts. For example, let's say you flip the coin 5 times and want to know how many ways there are to get 3 or more tails. Well, we can split the results into the following possibilities:

0 tails, 1 tail, 2 tails, 3 tails, 4 tails, 5 tails

What we want is the latter three options (3, 4 or 5 tails). The first three options have the "heads" equivalent:

0 tails = 5 heads 1 tail = 4 heads 2 tails = 3 heads

So what you now have as your list of options:

5 heads, 4 heads, 3 heads, 3 tails, 4 tails, 5 tails

The number of ways to get 3 heads will (for obvious reasons) be equal to the number of ways to get 3 tails. Similarly for 4 of each and 5 of each. So the number of ways to get at least 3 tails = $\frac 12$ of the total possiblities. Total possibilities = $2^5$, so to get 3 or more tails = $\frac 12 * 2^5 = 2^4$. To find the number of outcomes with 2 or more tails out of 5 tosses, you can take half of the total and just add the number of 2-tail results.

This approach works well for odd numbers of tosses, as it splits easily in half. An even number of tosses is a little tougher. Here you could figure out the total, drop the middle one, and then split the rest in half. For example, with 4 tosses we have $2^4 = 16$ possible outcomes. We don't have a natural place to split this in half, though, as the possible outcomes are:

4 heads, 3 heads, 2 heads/2 tails, 3 tails, 4 tails

We do have a natural midpoint, though - the 2H/2T result. For this, we can subtract out the # of 2H/2T possibilities $\binom 42$ and split the rest in half to group them. Therefore we'd know that there are 5 possibilities of either 3 or 4 H, 6 possible outcomes of 2H/2T, and 5 outcomes of 3 or 4 tails.