4
$\begingroup$

Sorry I don't know the correct math terms here, I haven't had a math class in some time. That's probably why I have trouble finding an existing question like this, too. Let's say there are 4 differnt kinds of coins: penny (P), nickle (N), dime (D), and quarter (Q). How many ways can you have 3 coins? Since there are 3 coins and 4 posibilities for each my first thought was 4x4x4, or 64, but that's not right. 2 pennies and a nickle are still just 2 pennies and a nickle no matter if its PPN, PNP, or NPP. The order doesn't matter. I listed out all the possiblities and counted them, but what's the correct formula to use here?

 1. PPP
 2. PPN
 3. PPD
 4. PPQ
 5. PNN
 6. PND
 7. PNQ
 8. PDD
 9. PDQ
10. PQQ
11. NNN
12. NND
13. NNQ
14. NDD
15. NDQ
16. NQQ
17. DDD
18. DDQ
19. DQQ
20. QQQ
$\endgroup$
4
$\begingroup$

You have three balls, and you want to put them into four buckets, named $P$, $N$, $D$, and $Q$. This is a classic application of stars and bars, and the answer is $$\left(\dbinom{4}{3}\right) = \dbinom{4+3-1}{3} = \dbinom{6}{3} = 20.$$

$\endgroup$
2
$\begingroup$

You're correct that the answer is ${6 \choose 3} = 20$. You can use the stars and bars method to figure this out.

This is equivalent to picking four non-negative integers which sum to 3, which are the number of pennies, nickels, dimes, and quarters respectively. Each possible such sum can be written by arranging three stars (*) and three bars (|) which separate them. There are ${6 \choose 3}$ such arrangements, which look like $$*||*|*$$. This corresponds to the 4-tuple $(1, 0, 1, 1)$, or one penny, no nickels, one dime, and one quarter.

$\endgroup$
1
$\begingroup$

Here's a solution using a much more general method, the Pólya-Burnside lemma.

We consider the three choices of coins as a single object with three slots that must be filled. The three slots are indistinguishable, so any permutation of them is considered a symmetry of this object; its symmetry group is therefore $S_3$, the symmetric group on three elements.

Suppose there are $N$ choices of coins for each slot. The Pólya-Burnside lemma says that to find the number of ways of filling all the slots, adjusted for symmetry, is to find the number of fillings that are left fixed by each of the six symmetries, and average those six numbers.

The six symmetries fall into three conjugacy classes:

  1. The identity symmetry, with three orbits
  2. The three symmetries that exchange two slots and leave one fixed, with two orbits each
  3. The two symmetries that permute the slots cyclically, with one orbit each

In each conjugacy class, the number of ways to assign coins to the slots so that the assignment is left unchanged by that symmetry is $N^k$ where $k$ is the number of orbits and $N$ is the number of types of coins. The identity symmetry contributes $N^3$ ways; the three symmetries of type 2 contribute $N^2$ ways each for a total of $3N^2$, and the two symmetries of type 3 contribute $N$ ways each for a total of $2N$. Averaging these we find that the number of ways of assigning $N$ types of coins to the three slots is always $$\frac{N^3+3N^2 + 2N}6$$ and taking $N=4$ we find that the particular answer is $$\frac{4^3+3\cdot4^2+2\cdot 4}6 = \frac{120}{6} = 20.$$

We can also observe that $$\frac{N^3+3N^2 + 2N}6 = \frac{N(N+1)(N+2)}{3!} = \binom{N+2}{3},$$ which agrees with the solution found by the stars-and-bars method described elsewhere in this thread.

This is a big hammer to use for a little problem, but I think it's instructive as a simple example of how to use the Pólya-Burnside lemma.

$\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.