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 
,
See also
Ball Picking, Binomial Coefficient, Choose, Combination, Figurate Number, Hypergeometric Distribution, Multinomial Coefficient, Multiset, Permutation, String
Explore with Wolfram|Alpha
References
Feller, W. An Introduction to Probability Theory and Its Applications, Vol. 1, 3rd ed. New York: Wiley, 1968.Scheinerman, E. R. Mathematics: A Discrete Introduction. Pacific Grove, CA: Brooks/Cole, 2000.
Referenced on Wolfram|Alpha
Cite this as:
Weisstein, Eric W. "Multichoose." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Multichoose.html