The Central Idea
In an ordinary set, an element is either present or absent.
For example,
\[ \{A,B,C\} \]contains one copy of each element.
A multiset may contain repeated copies:
\[ \{A,A,B,C,C,C\}. \]Here, \(A\) appears twice, \(B\) once, and \(C\) three times.
The number of copies of an element is called its multiplicity.
What Is a Multiset?
A multiset is a collection in which elements may occur more than once.
Unlike an ordinary set, a multiset records how many copies of each element are present.
Thus,
\[ \{A,A,B\} \]and
\[ \{A,B\} \]are different multisets because the multiplicity of \(A\) differs.
Multiplicity
The multiplicity of an element is the number of times that element appears in the multiset.
For
\[ M=\{A,A,A,B,C,C\}, \]the multiplicities are
\[ m(A)=3,\qquad m(B)=1,\qquad m(C)=2. \]These multiplicities completely describe how many copies of each element occur.
Order Does Not Matter in a Multiset
A multiset records membership and multiplicity, not order.
Therefore,
\[ \{A,A,B,C\} \]and
\[ \{C,A,B,A\} \]represent the same multiset.
This is why multiset selection problems are combination problems rather than permutation problems.
Sets versus Multisets
In a set, repeated entries collapse into one membership:
\[ \{A,A,B\}=\{A,B\} \]if interpreted as an ordinary set.
In a multiset, the repeated copy remains meaningful:
\[ \{A,A,B\}\ne\{A,B\}. \]The difference is entirely in multiplicity.
Multiset Size
The size of a multiset counts all copies, including repeated ones.
For
\[ M=\{A,A,A,B,C,C\}, \]the total size is
\[ 3+1+2=6. \]So \(M\) is a multiset of size \(6\).
Multiset Notation by Multiplicity
A multiset can be described by listing each distinct type together with its multiplicity.
For example,
\[ \{A,A,A,B,B,C\} \]may be summarized by
\[ m(A)=3,\qquad m(B)=2,\qquad m(C)=1. \]In counting problems, the multiplicities are often more useful than the literal repeated listing.
Multiset Selection
Suppose there are \(n\) available types and we want to select \(r\) total objects, with unlimited copies of each type allowed.
The order of selection does not matter, but repetition does.
This is called a combination with repetition or an \(r\)-element multiset chosen from \(n\) types.
Example: Choosing Three Scoops
An ice-cream shop offers four flavors:
\[ V,\ C,\ S,\ M. \]We choose three scoops, and flavors may repeat.
The selections
\[ VVC \]and
\[ CVV \]represent the same multiset because scoop order does not matter.
But
\[ VVC \]and
\[ VCC \]are different because their flavor multiplicities differ.
Encoding a Multiset as Counts
Suppose \(r\) objects are selected from \(n\) available types with repetition allowed.
Let
\[ x_1,x_2,\ldots,x_n \]represent the number of copies chosen from each type.
Then
\[ x_1+x_2+\cdots+x_n=r, \]where
\[ x_i\ge0. \]Counting multisets is therefore equivalent to counting nonnegative integer solutions to this equation.
Stars and Bars
The standard method for counting nonnegative integer solutions to
\[ x_1+x_2+\cdots+x_n=r \]is called stars and bars.
Represent the \(r\) selected objects by stars:
\[ *\ *\ *\ \cdots\ *. \]Use \(n-1\) bars to divide the stars into \(n\) categories.
A Small Stars-and-Bars Example
Suppose \(5\) objects are distributed among \(3\) types.
The pattern
\[ **|*|** \]represents
\[ x_1=2,\qquad x_2=1,\qquad x_3=2. \]There are \(5\) stars and \(2\) bars.
Every arrangement of those symbols corresponds to one solution.
The Combination-with-Repetition Formula
To choose \(r\) objects from \(n\) types with repetition allowed and order irrelevant, we arrange
\[ r \]stars and
\[ n-1 \]bars.
There are
\[ r+n-1 \]total positions.
Choose which \(r\) positions contain stars:
\[ \boxed{\binom{n+r-1}{r}}. \]Equivalently,
\[ \boxed{\binom{n+r-1}{n-1}}. \]Why the Two Forms Are Equal
By the combination symmetry identity,
\[ \binom{n+r-1}{r} = \binom{n+r-1}{(n+r-1)-r}. \]Since
\[ (n+r-1)-r=n-1, \]we obtain
\[ \boxed{\binom{n+r-1}{r}=\binom{n+r-1}{n-1}}. \]Example: Three Scoops from Four Flavors
Choose \(3\) scoops from \(4\) flavors with repetition allowed.
Here,
\[ n=4,\qquad r=3. \]Therefore,
\[ \binom{4+3-1}{3} = \binom{6}{3}. \]Thus,
\[ \boxed{20} \]flavor multisets are possible.
Example: Selecting Five Items from Three Types
Suppose \(5\) items are selected from \(3\) available types, with unlimited repetition and no concern for order.
The count is
\[ \binom{3+5-1}{5} = \binom{7}{5}. \]Therefore,
\[ \boxed{21}. \]Example: Donut Selection
A bakery offers \(8\) donut varieties. How many ways can a customer choose \(12\) donuts if any variety may be chosen repeatedly?
This is a multiset of size \(12\) chosen from \(8\) types.
\[ \binom{8+12-1}{12} = \binom{19}{12}. \]Therefore,
\[ \boxed{\binom{19}{12}=\binom{19}{7}=50388}. \]Order Matters in Repeated Sequences but Not in Multisets
Suppose \(4\) types are available and \(3\) selections are made.
If order matters and repetition is allowed, the count is
\[ 4^3=64. \]If order does not matter and repetition is allowed, the count is
\[ \binom{6}{3}=20. \]The difference is whether sequences such as
\[ ABC \]and
\[ CBA \]represent distinct outcomes.
Ordinary Combinations versus Multiset Combinations
If repetition is forbidden, choosing \(r\) objects from \(n\) distinct objects gives
\[ \binom{n}{r}. \]If repetition is allowed and only type counts matter, the count becomes
\[ \boxed{\binom{n+r-1}{r}}. \]These are different models even though both ignore order.
Example: Choose Two from Five Types
Without repetition,
\[ \binom{5}{2}=10. \]With repetition allowed,
\[ \binom{5+2-1}{2} = \binom{6}{2} = 15. \]The additional outcomes are the repeated-type selections
\[ AA,\ BB,\ CC,\ DD,\ EE. \]Stars and Bars as Integer Solutions
The formula
\[ \binom{n+r-1}{r} \]also counts the nonnegative integer solutions to
\[ x_1+x_2+\cdots+x_n=r. \]Each solution specifies the multiplicity of every type in the multiset.
Example: Nonnegative Integer Solutions
How many nonnegative integer solutions satisfy
\[ x_1+x_2+x_3=7? \]There are \(7\) stars and \(2\) bars.
Therefore,
\[ \binom{7+3-1}{7} = \binom{9}{7} = \boxed{36}. \]Positive Integer Solutions
Suppose instead that
\[ x_1+x_2+\cdots+x_n=r \]must satisfy
\[ x_i\ge1. \]Give one object to every variable first.
This uses \(n\) objects, leaving
\[ r-n \]objects to distribute freely.
The Positive-Solution Formula
For
\[ x_1+x_2+\cdots+x_n=r \]with every \(x_i\ge1\), the number of solutions is
\[ \boxed{\binom{r-1}{n-1}}, \]provided \(r\ge n\).
This is the stars-and-bars count after one unit has been reserved for each variable.
Example: Positive Integer Solutions
Count the positive integer solutions to
\[ x_1+x_2+x_3=8. \]Give one unit to each variable, leaving
\[ 8-3=5 \]units to distribute freely.
Therefore,
\[ \binom{8-1}{3-1} = \binom{7}{2} = \boxed{21}. \]Lower Bounds Other Than One
Suppose
\[ x_1+x_2+\cdots+x_n=r \]has lower bounds
\[ x_i\ge a_i. \]Define
\[ y_i=x_i-a_i. \]Then every \(y_i\ge0\), and the equation becomes
\[ y_1+y_2+\cdots+y_n = r-(a_1+a_2+\cdots+a_n). \]Now ordinary stars and bars applies.
Example: Minimum Requirements
Count the integer solutions to
\[ x_1+x_2+x_3=12 \]with
\[ x_1\ge2,\qquad x_2\ge1,\qquad x_3\ge3. \]Reserve the required minimum:
\[ 2+1+3=6. \]Let
\[ y_1=x_1-2,\qquad y_2=x_2-1,\qquad y_3=x_3-3. \]Then
\[ y_1+y_2+y_3=6. \]The number of nonnegative solutions is
\[ \binom{6+3-1}{3-1} = \binom{8}{2} = \boxed{28}. \]Distributing Identical Objects into Distinct Boxes
Stars and bars also counts distributions of identical objects into distinct boxes.
Suppose \(r\) identical objects are placed into \(n\) labeled boxes.
Let \(x_i\) be the number of objects placed in box \(i\).
Then
\[ x_1+x_2+\cdots+x_n=r. \]If empty boxes are allowed, the number of distributions is
\[ \boxed{\binom{n+r-1}{r}}. \]Example: Identical Balls into Boxes
Distribute \(10\) identical balls among \(4\) labeled boxes, with empty boxes allowed.
The equation is
\[ x_1+x_2+x_3+x_4=10. \]Therefore,
\[ \binom{10+4-1}{10} = \binom{13}{10} = \boxed{286}. \]No Empty Boxes
If every box must receive at least one identical object, then
\[ x_i\ge1. \]The number of distributions is
\[ \boxed{\binom{r-1}{n-1}}, \]provided \(r\ge n\).
Example: No Empty Boxes
Distribute \(10\) identical balls among \(4\) labeled boxes, with every box receiving at least one ball.
Reserve one ball for each box, leaving
\[ 10-4=6. \]Then distribute the remaining \(6\) freely:
\[ \binom{6+4-1}{4-1} = \binom{9}{3}. \]Therefore,
\[ \boxed{84}. \]Identical versus Distinct Objects
Stars and bars assumes the distributed objects are identical.
If the objects are distinct, then assigning them to boxes creates many more outcomes.
For example, \(r\) distinct objects distributed independently among \(n\) labeled boxes give
\[ n^r \]assignments if boxes may be empty.
The distinction between identical and distinct objects is fundamental.
Example: Identical versus Distinct
Place three objects into two labeled boxes.
If the objects are identical, the possible counts are
\[ (3,0),\ (2,1),\ (1,2),\ (0,3), \]so there are
\[ \boxed{4} \]distributions.
If the three objects are distinct, each object independently chooses one of two boxes:
\[ 2^3=\boxed{8}. \]Upper Bounds Make the Problem Harder
Ordinary stars and bars handles lower bounds easily.
Upper bounds such as
\[ x_i\le b_i \]require additional reasoning because some stars-and-bars solutions may violate the maximum.
Common methods include:
- complementary counting;
- inclusion–exclusion;
- case analysis;
- generating functions in more advanced settings.
Example: One Upper Bound
Count the nonnegative integer solutions to
\[ x_1+x_2+x_3=8 \]with
\[ x_1\le3. \]First count all nonnegative solutions:
\[ \binom{10}{2}=45. \]Now count solutions with
\[ x_1\ge4. \]Let
\[ y_1=x_1-4. \]Then
\[ y_1+x_2+x_3=4, \]giving
\[ \binom{6}{2}=15. \]Therefore,
\[ 45-15=\boxed{30}. \]Example: Limited Inventory
Suppose \(6\) items are selected from three types \(A,B,C\), but at most \(2\) copies of \(A\) are available.
The unrestricted multiset count would include impossible selections with \(3\) or more copies of \(A\).
Therefore, either count by cases
\[ x_A=0,\ 1,\ 2 \]or count all multisets and subtract those violating the bound.
Inventory limits convert an unlimited-multiplicity problem into a bounded multiset problem.
Counting by Cases with an Upper Bound
Continue the previous example:
\[ x_A+x_B+x_C=6, \qquad 0\le x_A\le2. \]If \(x_A=0\), then
\[ x_B+x_C=6, \]giving \(7\) solutions.
If \(x_A=1\), then
\[ x_B+x_C=5, \]giving \(6\) solutions.
If \(x_A=2\), then
\[ x_B+x_C=4, \]giving \(5\) solutions.
Therefore,
\[ 7+6+5=\boxed{18}. \]Multisets and Repeated-Object Permutations
A multiset describes which objects and multiplicities are present.
If that multiset is then arranged in order, the repeated-object permutation formula applies.
For example, the multiset
\[ \{A,A,B,B,B,C\} \]has \(6\) total objects with multiplicities \(2,3,1\).
Its distinguishable linear arrangements total
\[ \boxed{\frac{6!}{2!\,3!}}. \]Selection First, Arrangement Second
Some problems have two stages:
- choose a multiset;
- arrange the chosen objects.
The first stage is unordered repeated selection.
The second stage may require a repeated-object permutation count based on the multiplicities chosen.
Keeping these stages separate prevents model confusion.
Multisets as Frequency Vectors
A multiset over \(n\) types can be represented by a vector
\[ (x_1,x_2,\ldots,x_n), \]where \(x_i\) is the multiplicity of type \(i\).
For a multiset of total size \(r\),
\[ x_1+x_2+\cdots+x_n=r. \]This frequency-vector viewpoint is especially useful in combinatorics, probability, statistics, and discrete optimization.
Example: Frequency Vector
The multiset
\[ \{A,A,B,C,C,C\} \]over the ordered type list
\[ A,B,C \]has frequency vector
\[ \boxed{(2,1,3)}. \]The entries sum to
\[ 2+1+3=6, \]the total multiset size.
Multisets and Monomials
Frequency vectors also resemble exponents in monomials.
For example, the multiset with multiplicities
\[ (2,1,3) \]can be associated with
\[ x_1^2x_2x_3^3. \]The total degree
\[ 2+1+3=6 \]equals the total multiset size.
This observation helps explain later connections between multisets and multinomial expansions.
Counting Monomials of Fixed Total Degree
How many monomials of total degree \(r\) can be formed from \(n\) variables if exponents are nonnegative integers?
A monomial
\[ x_1^{a_1}x_2^{a_2}\cdots x_n^{a_n} \]has total degree \(r\) when
\[ a_1+a_2+\cdots+a_n=r. \]Therefore, the number of such monomials is
\[ \boxed{\binom{n+r-1}{r}}. \]Example: Degree-Four Monomials
Count the monomials of total degree \(4\) in the variables \(x,y,z\).
The exponents satisfy
\[ a+b+c=4, \qquad a,b,c\ge0. \]Therefore,
\[ \binom{4+3-1}{4} = \binom{6}{4} = \boxed{15}. \]Multisets and Occupancy
A multiset count can also be interpreted as an occupancy problem.
The multiplicity of each type tells how many objects occupy the corresponding category.
Thus,
\[ x_1+x_2+\cdots+x_n=r \]simultaneously describes:
- a multiset of size \(r\) from \(n\) types;
- a distribution of \(r\) identical objects into \(n\) labeled boxes;
- a nonnegative integer solution;
- a frequency vector with total \(r\).
These Are Different Interpretations of the Same Structure
One counting formula may solve problems that look very different on the surface.
The formula
\[ \boxed{\binom{n+r-1}{r}} \]can count repeated selections, integer solutions, identical-object distributions, and fixed-degree monomials.
Recognizing the shared structure is one of the main goals of combinatorial reasoning.
Example: Distributing Identical Tokens
Twelve identical tokens are distributed among five labeled recipients. Some recipients may receive none.
Let \(x_i\) be the number received by person \(i\).
\[ x_1+x_2+x_3+x_4+x_5=12. \]Therefore,
\[ \binom{12+5-1}{12} = \binom{16}{12} = \boxed{1820}. \]Example: Everyone Receives at Least Two
Twelve identical tokens are distributed among four labeled recipients, with each person receiving at least two.
Reserve
\[ 2\cdot4=8 \]tokens.
Four tokens remain to distribute freely.
Therefore,
\[ \binom{4+4-1}{4} = \binom{7}{4} = \boxed{35}. \]Example: Select with Minimum Multiplicity
Select \(9\) objects from three types \(A,B,C\), with repetition allowed, but at least two copies of each type must be selected.
Reserve
\[ 2+2+2=6 \]objects.
Three selections remain unrestricted.
The number of multisets is
\[ \binom{3+3-1}{3} = \binom{5}{3} = \boxed{10}. \]Example: Select at Least One of Every Type
Choose \(8\) objects from \(5\) types, with repetition allowed, and include every type at least once.
Reserve one object of each type, using \(5\) selections.
Three selections remain.
Therefore,
\[ \binom{3+5-1}{3} = \binom{7}{3} = \boxed{35}. \]Boundary Case: Selecting Nothing
There is exactly one multiset of size \(0\) chosen from \(n\) types: the empty multiset.
The formula gives
\[ \binom{n+0-1}{0} = \boxed{1}. \]Boundary Case: One Available Type
If only one type is available and \(r\) objects must be selected with repetition allowed, every selected object must be of that type.
Therefore, there is exactly one multiset:
\[ \boxed{1}. \]The formula confirms this:
\[ \binom{1+r-1}{r} = \binom{r}{r} = 1. \]Common Error: Using \(n^r\)
The expression
\[ n^r \]counts ordered sequences with repetition allowed.
A multiset ignores order.
Therefore, choosing \(3\) objects from \(4\) types as a multiset gives
\[ \binom{6}{3}=20, \]not
\[ 4^3=64. \]Common Error: Using \(\binom{n}{r}\)
The ordinary combination formula
\[ \binom{n}{r} \]assumes no type is selected more than once.
If repetition is allowed, use
\[ \boxed{\binom{n+r-1}{r}}. \]Common Error: Confusing Types with Total Objects
In the multiset formula,
\[ \binom{n+r-1}{r}, \]\(n\) is the number of available types.
The value \(r\) is the total number of selected objects.
These roles should not be reversed.
Common Error: Forgetting That Bars Equal \(n-1\)
To divide stars into \(n\) categories, we need
\[ n-1 \]separators.
For example, three categories require two bars:
\[ ***|**|*. \]Using \(n\) bars would create \(n+1\) regions.
Common Error: Using Nonnegative Stars and Bars for Positive Solutions
The equation
\[ x_1+x_2+x_3=8 \]has different counts depending on whether zero is allowed.
For nonnegative solutions:
\[ \binom{10}{2}=45. \]For positive solutions:
\[ \binom{7}{2}=21. \]Lower-bound conditions must be handled before applying the formula.
Common Error: Ignoring Upper Bounds
The standard stars-and-bars formula assumes unlimited capacity.
If a variable has an upper limit such as
\[ x_i\le4, \]unrestricted stars and bars will count invalid solutions.
Use complements, cases, or inclusion–exclusion to remove the violations.
Common Error: Treating Distinct Objects as Identical
Stars and bars tracks only how many objects enter each category.
It does not distinguish individual objects.
If the objects themselves are distinct, a different counting model is usually required.
A Reliable Procedure for Multiset Selection
- Identify the available types.
- Let \(n\) be the number of types.
- Identify the total number \(r\) of objects selected.
- Confirm that repetition is allowed.
- Confirm that order does not matter.
- If multiplicities are unlimited, use \(\binom{n+r-1}{r}\).
- If every type must appear, reserve one of each type first.
- If larger lower bounds apply, subtract those minimums first.
- If upper bounds apply, use cases, complements, or inclusion–exclusion.
- Check that the resulting multiplicities sum to \(r\).
A Reliable Procedure for Stars and Bars
- Write the counting problem as an integer equation.
- Identify whether variables are nonnegative or positive.
- Convert positive or larger lower bounds to nonnegative variables.
- Count stars as the remaining total to distribute.
- Use one fewer bar than the number of categories.
- Choose the bar positions or star positions.
- Inspect upper bounds separately.
Example: Full Multiset Workflow
A store sells \(6\) types of notebooks. A customer buys \(10\) notebooks, and may buy any number of each type.
There are
\[ n=6 \]types and
\[ r=10 \]total selections.
Repetition is allowed and order does not matter.
Therefore,
\[ \binom{6+10-1}{10} = \binom{15}{10}. \]Thus,
\[ \boxed{\binom{15}{10}=3003}. \]Practice 1: Basic Multiset
How many multisets of size \(4\) can be chosen from \(5\) available types?
Practice 2: Repeated Selection
A bakery offers \(7\) cookie varieties. How many ways can a customer choose \(9\) cookies if any variety may be chosen repeatedly?
Practice 3: Nonnegative Integer Solutions
How many nonnegative integer solutions satisfy
\[ x_1+x_2+x_3+x_4=6? \]Practice 4: Positive Integer Solutions
How many positive integer solutions satisfy
\[ x_1+x_2+x_3=10? \]Practice 5: Minimum Requirement
How many nonnegative integer solutions satisfy
\[ x_1+x_2+x_3=14 \]with
\[ x_1\ge2,\qquad x_2\ge3,\qquad x_3\ge1? \]Practice 6: Identical Objects into Boxes
How many ways can \(8\) identical balls be distributed among \(5\) labeled boxes if empty boxes are allowed?
Practice 7: No Empty Boxes
How many ways can \(9\) identical balls be distributed among \(4\) labeled boxes if every box must receive at least one ball?
Practice 8: At Least One of Every Type
How many multisets of size \(10\) can be chosen from \(4\) types if every type must appear at least once?
Practice 9: One Upper Bound
How many nonnegative integer solutions satisfy
\[ x_1+x_2+x_3=7 \]with
\[ x_1\le2? \]Practice 10: Identify the Error
A student says that choosing \(5\) objects from \(3\) types with repetition allowed gives
\[ 3^5=243 \]possibilities.
Explain why this is not the correct multiset count and give the correct answer.
Practice Answers
Practice 1
\[ \binom{5+4-1}{4} = \binom{8}{4} = \boxed{70}. \]Practice 2
\[ \binom{7+9-1}{9} = \binom{15}{9} = \boxed{5005}. \]Practice 3
\[ \binom{6+4-1}{4-1} = \binom{9}{3} = \boxed{84}. \]Practice 4
Give one unit to each variable, leaving \(7\):
\[ \binom{10-1}{3-1} = \binom{9}{2} = \boxed{36}. \]Practice 5
Reserve
\[ 2+3+1=6. \]Eight units remain:
\[ y_1+y_2+y_3=8. \]Therefore,
\[ \binom{8+3-1}{3-1} = \binom{10}{2} = \boxed{45}. \]Practice 6
\[ \binom{8+5-1}{8} = \binom{12}{8} = \boxed{495}. \]Practice 7
Reserve one ball for each box, leaving \(5\):
\[ \binom{5+4-1}{4-1} = \binom{8}{3} = \boxed{56}. \]Practice 8
Reserve one of each of the four types. Six selections remain:
\[ \binom{6+4-1}{6} = \binom{9}{6} = \boxed{84}. \]Practice 9
Count all nonnegative solutions:
\[ \binom{9}{2}=36. \]Count solutions with \(x_1\ge3\). Let \(y_1=x_1-3\):
\[ y_1+x_2+x_3=4. \]This gives
\[ \binom{6}{2}=15. \]Therefore,
\[ 36-15=\boxed{21}. \]Practice 10
The expression
\[ 3^5 \]counts ordered sequences of five selections from three reusable types.
A multiset ignores order.
The correct count is
\[ \binom{3+5-1}{5} = \binom{7}{5} = \boxed{21}. \]What to Remember
A multiset is an unordered collection in which repeated elements are allowed and multiplicity matters.
Choosing \(r\) objects from \(n\) available types with unlimited repetition gives
\[ \boxed{\binom{n+r-1}{r}}. \]The same formula counts nonnegative integer solutions to
\[ x_1+x_2+\cdots+x_n=r. \]If every variable must be positive, then
\[ \boxed{\binom{r-1}{n-1}}. \]Lower bounds can be removed by reserving the required minimum first. Upper bounds usually require complements, case analysis, or inclusion–exclusion.
The most important distinction is to identify whether the problem concerns ordered repeated selections, unordered repeated selections, or arrangements of a fixed repeated collection.
Where We Go Next
Combination counts appear throughout discrete mathematics, and the numbers \(\binom{n}{r}\) have a rich internal structure of their own.
The next lesson, Binomial Coefficients, studies these numbers directly, including their identities, symmetry, recursive behavior, and role in counting.