TOPICS
Search

Multichoose


The number of multisets of length k on n symbols is sometimes termed "n multichoose k," denoted ((n; k)) by analogy with the binomial coefficient (n; k). n multichoose k is given by the simple formula

 ((n; k))=(n+k-1; k)=(n-1,k)!,

where (n-1,k)! is a multinomial coefficient. For example, 3 multichoose 2 is given by 6, since the possible multisets of length 2 on three elements {a,b,c} are {a,a}, {a,b}, {a,c}, {b,b}, {b,c}, and {c,c}.

The first few values of ((n; k)) are given in the following table.

k\n12345
112345
21361015
314102035
415153570
5162156126

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 9-1 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 ((9-1)+5; (9-1))=1287,


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

Multichoose

Cite this as:

Weisstein, Eric W. "Multichoose." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Multichoose.html

Subject classifications