The number of multisets of length on symbols is sometimes termed " multichoose ," denoted by analogy with the binomial coefficient . multichoose is given by the simple formula
where is a multinomial coefficient. For example, 3 multichoose 2 is given by 6, since the possible multisets of length 2 on three elements are , , , , , and .
The first few values of are given in the following table.
1 | 2 | 3 | 4 | 5 | |
1 | 1 | 2 | 3 | 4 | 5 |
2 | 1 | 3 | 6 | 10 | 15 |
3 | 1 | 4 | 10 | 20 | 35 |
4 | 1 | 5 | 15 | 35 | 70 |
5 | 1 | 6 | 21 | 56 | 126 |
Multichoose problems are sometimes called "bars and stars" problems. For example, suppose a recipe called for 5 pinches of spice, out of 9 spices. Each possibility is an arrangement of 5 spices (stars) and dividers between categories (bars), where the notation indicates a choice of spices 1, 1, 5, 6, and 9 (Feller 1968, p. 36). The number of possibilities in this case is then ,