The Central Idea
Suppose \(r\) objects are distributed among \(n\) boxes.
Before calculating anything, ask four questions:
- Are the objects distinct or identical?
- Are the boxes distinct or identical?
- May a box be empty?
- Are there minimum, maximum, or exact occupancy requirements?
Different answers produce fundamentally different counting models.
The Balls-and-Bins Model
A common abstract model represents distributed objects as balls and destinations as bins.
The terminology is generic. A ball might represent:
- a student;
- a file;
- a task;
- a vote;
- a customer;
- a token;
- a data item.
A bin might represent a room, server, category, recipient, day, box, or container.
Why Classification Comes First
Consider distributing \(5\) objects among \(3\) boxes.
If the objects are distinct and the boxes are labeled, each object chooses one of three destinations:
\[ 3^5. \]If the objects are identical and the boxes are labeled, only the occupancy counts matter:
\[ x_1+x_2+x_3=5. \]Those are different mathematical problems even though the words “five objects into three boxes” appear in both.
Case 1: Distinct Objects into Distinct Boxes
Suppose \(r\) distinct objects are placed into \(n\) labeled boxes, with no restriction on how many objects a box may contain.
Each object independently has \(n\) choices.
Therefore,
\[ \boxed{n^r}. \]Empty boxes are automatically allowed in this model.
Example: Five Files on Three Servers
Five distinct files are assigned independently to three labeled servers.
Each file has \(3\) choices.
\[ 3^5. \]Therefore,
\[ \boxed{243} \]assignments are possible.
Function Interpretation
Distributing \(r\) distinct objects among \(n\) distinct boxes is equivalent to choosing a function from an \(r\)-element object set to an \(n\)-element box set.
Each object is assigned exactly one image, or destination.
The number of such functions is
\[ \boxed{n^r}. \]Occupancy Vectors
Every distribution determines an occupancy vector
\[ (x_1,x_2,\ldots,x_n), \]where \(x_i\) is the number of objects placed in box \(i\).
The occupancies satisfy
\[ x_1+x_2+\cdots+x_n=r. \]For distinct objects, however, an occupancy vector does not usually identify a unique distribution because different objects may produce the same box counts.
Example: Same Occupancy, Different Assignments
Suppose objects \(A,B,C\) are placed into boxes \(1\) and \(2\).
The assignments
\[ \{A,B\}\text{ in box 1},\qquad \{C\}\text{ in box 2} \]and
\[ \{A,C\}\text{ in box 1},\qquad \{B\}\text{ in box 2} \]both have occupancy vector
\[ (2,1), \]but they are different distributions because the objects are distinct.
Fixed Occupancy Counts for Distinct Objects
Suppose \(r\) distinct objects are distributed among \(n\) labeled boxes with specified occupancies
\[ x_1,x_2,\ldots,x_n, \]where
\[ x_1+x_2+\cdots+x_n=r. \]The number of assignments realizing exactly those occupancies is
\[ \boxed{ \frac{r!}{x_1!x_2!\cdots x_n!} }. \]This is a multinomial coefficient.
Example: Exact Server Loads
Six distinct files are assigned to three labeled servers so that the server loads are exactly
\[ 3,\ 2,\ 1. \]The number of assignments is
\[ \frac{6!}{3!2!1!}. \]Therefore,
\[ \boxed{60}. \]Sequential Combination Interpretation
The same exact-load problem can be counted in stages.
Choose \(3\) of the \(6\) files for server \(1\):
\[ \binom{6}{3}. \]Choose \(2\) of the remaining \(3\) for server \(2\):
\[ \binom{3}{2}. \]The final file goes to server \(3\).
Thus,
\[ \binom{6}{3}\binom{3}{2} = 20\cdot3 = 60. \]This equals the multinomial coefficient.
Case 2: Identical Objects into Distinct Boxes
Suppose \(r\) identical objects are distributed among \(n\) labeled boxes.
Now only the occupancy counts matter.
The distribution corresponds to a nonnegative integer solution of
\[ x_1+x_2+\cdots+x_n=r. \]If empty boxes are allowed, stars and bars gives
\[ \boxed{\binom{r+n-1}{n-1}}. \]Example: Ten Identical Tokens
Ten identical tokens are distributed among four labeled boxes, with empty boxes allowed.
The occupancies satisfy
\[ x_1+x_2+x_3+x_4=10. \]Therefore,
\[ \binom{10+4-1}{4-1} = \binom{13}{3}. \]Thus,
\[ \boxed{286}. \]Stars and Bars Interpretation
Represent the \(r\) identical objects by stars and use \(n-1\) bars to separate the \(n\) boxes.
For example,
\[ ***|*||** \]represents the occupancy vector
\[ (3,1,0,2). \]Consecutive bars represent empty boxes.
Nonempty Boxes with Identical Objects
If each of the \(n\) labeled boxes must contain at least one identical object, then
\[ x_i\ge1. \]Reserve one object for each box.
This uses \(n\) objects, leaving
\[ r-n \]to distribute freely.
Therefore,
\[ \boxed{\binom{r-1}{n-1}}, \]provided \(r\ge n\).
Example: Every Box Nonempty
Ten identical tokens are distributed among four labeled boxes, with every box receiving at least one token.
Reserve one token for each box, leaving \(6\).
Then
\[ y_1+y_2+y_3+y_4=6. \]The number of distributions is
\[ \binom{6+4-1}{3} = \binom{9}{3}. \]Therefore,
\[ \boxed{84}. \]Minimum Occupancies
Suppose identical objects are distributed among labeled boxes with lower bounds
\[ x_i\ge a_i. \]Reserve the required minimum in each box:
\[ y_i=x_i-a_i. \]Then every \(y_i\ge0\), and stars and bars can be applied to the remaining total.
Example: Different Minimums
Distribute \(15\) identical tokens among three labeled boxes subject to
\[ x_1\ge2,\qquad x_2\ge3,\qquad x_3\ge1. \]Reserve
\[ 2+3+1=6 \]tokens.
Nine remain:
\[ y_1+y_2+y_3=9. \]Therefore,
\[ \binom{11}{2} = \boxed{55}. \]Capacity Limits
Upper bounds such as
\[ x_i\le c_i \]are more difficult because ordinary stars and bars includes distributions that may exceed the capacity.
Common tools include:
- case analysis;
- complementary counting;
- inclusion–exclusion;
- generating functions in more advanced work.
Example: One Capacity Limit
Count nonnegative integer solutions to
\[ x_1+x_2+x_3=9 \]subject to
\[ x_1\le4. \]First count all nonnegative solutions:
\[ \binom{11}{2}=55. \]Now count violations with
\[ x_1\ge5. \]Let
\[ y_1=x_1-5. \]Then
\[ y_1+x_2+x_3=4, \]giving
\[ \binom{6}{2}=15. \]Therefore,
\[ 55-15=\boxed{40}. \]Case 3: Distinct Objects, No Empty Distinct Boxes
Suppose \(r\) distinct objects are distributed among \(n\) labeled boxes and every box must receive at least one object.
This is equivalent to counting onto functions, or surjections, from the objects to the boxes.
The unrestricted count is
\[ n^r, \]but distributions leaving one or more boxes empty must be removed.
Inclusion–Exclusion Formula for Nonempty Boxes
For \(r\) distinct objects and \(n\) labeled boxes, every box nonempty, the number of distributions is
\[ \boxed{ \sum_{j=0}^{n} (-1)^j \binom{n}{j} (n-j)^r }. \]Equivalently,
\[ \boxed{ n^r - \binom{n}{1}(n-1)^r + \binom{n}{2}(n-2)^r -\cdots }. \]Why Inclusion–Exclusion Is Needed
Start with all
\[ n^r \]assignments.
Subtract assignments missing a particular box.
But assignments missing two boxes have now been subtracted twice, so add them back.
Continue alternating subtraction and addition according to the inclusion–exclusion principle.
Example: Four Distinct Objects into Three Nonempty Boxes
Four distinct objects are distributed among three labeled boxes, with every box nonempty.
All assignments:
\[ 3^4=81. \]Subtract assignments missing one specified box:
\[ \binom{3}{1}2^4=3\cdot16=48. \]Add back assignments using only one box:
\[ \binom{3}{2}1^4=3. \]Therefore,
\[ 81-48+3 = \boxed{36}. \]Another Way to Count the Same Example
Four distinct objects in three nonempty labeled boxes must have occupancy pattern
\[ 2,1,1. \]Choose which box receives two objects:
\[ 3. \]Choose the two objects for that box:
\[ \binom{4}{2}=6. \]Assign the two remaining distinct objects to the two remaining boxes:
\[ 2!. \]Therefore,
\[ 3\cdot6\cdot2 = \boxed{36}. \]The agreement provides a useful check.
Surjections and Stirling Numbers
The number of onto assignments from \(r\) distinct objects to \(n\) labeled boxes can also be written
\[ \boxed{n!\,S(r,n)}, \]where \(S(r,n)\) is a Stirling number of the second kind.
The Stirling number partitions the objects into \(n\) nonempty unlabeled groups, and the factor \(n!\) assigns those groups to the labeled boxes.
This notation is useful later, but inclusion–exclusion remains the primary elementary method here.
Exactly \(k\) Nonempty Labeled Boxes
Suppose \(r\) distinct objects are distributed among \(n\) labeled boxes and exactly \(k\) boxes must be occupied.
First choose which \(k\) boxes are used:
\[ \binom{n}{k}. \]Then distribute all \(r\) objects onto those \(k\) chosen boxes:
\[ k!S(r,k). \]Therefore,
\[ \boxed{ \binom{n}{k}k!S(r,k) }. \]Exactly \(k\) Nonempty Boxes by Inclusion–Exclusion
Without using Stirling notation, the onto count for the chosen \(k\) boxes is
\[ \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^r. \]Thus the total is
\[ \boxed{ \binom{n}{k} \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^r }. \]Example: Exactly Two Boxes Used
Four distinct objects are distributed among five labeled boxes, with exactly two boxes nonempty.
Choose the two occupied boxes:
\[ \binom{5}{2}=10. \]Assign the four objects to those two boxes but exclude the two assignments in which all objects go to only one of them:
\[ 2^4-2=14. \]Therefore,
\[ 10\cdot14 = \boxed{140}. \]Exactly One Object in Each Box
If \(r=n\) distinct objects are placed into \(n\) labeled boxes with exactly one object per box, the distribution is a permutation.
Therefore,
\[ \boxed{n!}. \]Each box receives one distinct object, and every object is used.
Example: One Person per Room
Six distinct people are assigned to six labeled single-occupancy rooms.
The number of assignments is
\[ \boxed{6!=720}. \]At Most One Object per Box
Suppose \(r\) distinct objects are placed into \(n\) labeled boxes, with at most one object per box and \(r\le n\).
Choose and assign \(r\) distinct boxes to the \(r\) objects:
\[ P(n,r) = \frac{n!}{(n-r)!}. \]Therefore,
\[ \boxed{P(n,r)}. \]Example: Parking in Distinct Spaces
Four distinct cars park in seven labeled parking spaces, with at most one car per space.
The count is
\[ P(7,4) = 7\cdot6\cdot5\cdot4. \]Therefore,
\[ \boxed{840}. \]Exactly One Object in Selected Boxes
If \(r\) distinct objects occupy \(r\) of \(n\) labeled boxes, exactly one object per occupied box, the count can also be written
\[ \binom{n}{r}r!. \]Choose the \(r\) occupied boxes, then assign the \(r\) objects.
Since
\[ \binom{n}{r}r! = \frac{n!}{(n-r)!}, \]this agrees with \(P(n,r)\).
Exactly Two Objects in Each Box
Suppose \(2n\) distinct objects are distributed among \(n\) labeled boxes, exactly two per box.
The occupancy vector is
\[ (2,2,\ldots,2). \]The multinomial coefficient gives
\[ \boxed{ \frac{(2n)!}{(2!)^n} }. \]Example: Eight People in Four Two-Person Rooms
Eight distinct people are assigned to four labeled rooms, exactly two people per room.
The count is
\[ \frac{8!}{2!2!2!2!}. \]Therefore,
\[ \boxed{2520}. \]Mixed Exact Capacities
Suppose labeled boxes must receive exact occupancies
\[ c_1,c_2,\ldots,c_n \]with
\[ c_1+c_2+\cdots+c_n=r. \]For \(r\) distinct objects, the number of assignments is
\[ \boxed{ \frac{r!}{c_1!c_2!\cdots c_n!} }. \]Example: Room Capacities \(3,2,2\)
Seven distinct people are assigned to three labeled rooms with exact occupancies
\[ 3,\ 2,\ 2. \]Therefore,
\[ \frac{7!}{3!2!2!} = \boxed{210}. \]Capacity Limits with Distinct Objects
If objects are distinct and boxes have upper capacities, counting often requires summing over legal occupancy vectors.
For each legal vector
\[ (x_1,\ldots,x_n), \]the number of assignments is
\[ \frac{r!}{x_1!\cdots x_n!}. \]Add these multinomial counts over all occupancy vectors satisfying the restrictions.
Example: Three Boxes, Capacity Two
Four distinct objects are distributed among three labeled boxes, with no box holding more than two objects.
The legal occupancy patterns, up to order, are
\[ (2,2,0) \]and
\[ (2,1,1). \]Count each labeled pattern carefully.
Count the \((2,2,0)\) Pattern
Choose the empty box:
\[ 3. \]For the two occupied labeled boxes, choose two of the four objects for one box:
\[ \binom{4}{2}=6. \]The remaining two objects go to the other box.
Thus,
\[ 3\cdot6 = 18. \]Count the \((2,1,1)\) Pattern
Choose which box receives two objects:
\[ 3. \]Choose the pair:
\[ \binom{4}{2}=6. \]Assign the remaining two distinct objects to the remaining two boxes:
\[ 2!. \]Therefore,
\[ 3\cdot6\cdot2 = 36. \]Finish the Capacity-Two Example
Add the disjoint occupancy cases:
\[ 18+36 = \boxed{54}. \]Thus \(54\) assignments satisfy the capacity limit.
Case 4: Identical Boxes
When the destination boxes themselves are identical, exchanging entire boxes may not produce a new distribution.
This introduces a new layer of symmetry.
For identical objects into identical boxes, the problem becomes one of integer partitions.
For distinct objects into identical nonempty boxes, the problem leads to set partitions and Stirling numbers of the second kind.
Identical Objects into Identical Boxes
Suppose \(r\) identical objects are placed into identical boxes.
Only the multiset of box occupancies matters.
For example, distributing \(5\) identical objects into exactly two nonempty identical boxes gives occupancy patterns
\[ 4+1 \]and
\[ 3+2. \]The reversed descriptions \(1+4\) and \(2+3\) are not new because the boxes are identical.
Integer Partition Interpretation
A distribution of \(r\) identical objects into exactly \(k\) nonempty identical boxes corresponds to a partition of \(r\) into exactly \(k\) positive parts.
Unlike stars and bars, there is no simple single factorial formula for all such partition counts.
This is why identifying whether boxes are labeled is so important.
Distinct Objects into Identical Nonempty Boxes
Suppose \(r\) distinct objects are divided into \(k\) nonempty unlabeled groups.
The number of such partitions is the Stirling number of the second kind
\[ \boxed{S(r,k)}. \]If the groups are then assigned labels, multiply by
\[ k!, \]producing the onto-function count
\[ k!S(r,k). \]Example: Four People into Two Unlabeled Teams
Four distinct people are divided into two nonempty unlabeled teams.
The number is
\[ S(4,2)=7. \]If the two teams were labeled Team A and Team B, the count would become
\[ 2!S(4,2) = 14. \]Why Labeled versus Unlabeled Matters
In labeled boxes,
\[ (3,2) \]and
\[ (2,3) \]can represent different distributions because box \(1\) and box \(2\) have different identities.
In identical boxes, those occupancy descriptions may represent the same outcome.
Exactly \(k\) Objects in a Particular Box
Suppose \(r\) distinct objects are distributed among \(n\) labeled boxes, and a particular box must contain exactly \(k\) objects.
Choose those \(k\) objects:
\[ \binom{r}{k}. \]Each remaining object may go to any of the remaining \(n-1\) boxes:
\[ (n-1)^{r-k}. \]Therefore,
\[ \boxed{ \binom{r}{k}(n-1)^{r-k} }. \]Example: Exactly Two Files on Server One
Six distinct files are assigned to four labeled servers, and server \(1\) must receive exactly two files.
Choose the two files:
\[ \binom{6}{2}=15. \]Each remaining file chooses among the other three servers:
\[ 3^4=81. \]Therefore,
\[ 15\cdot81 = \boxed{1215}. \]At Least One Object in a Particular Box
For \(r\) distinct objects and \(n\) labeled boxes, count all assignments:
\[ n^r. \]Subtract assignments in which the particular box is empty:
\[ (n-1)^r. \]Therefore,
\[ \boxed{ n^r-(n-1)^r }. \]Example: A Required Server
Five distinct files are assigned to three servers. How many assignments use server \(1\) at least once?
All assignments:
\[ 3^5=243. \]Assignments avoiding server \(1\):
\[ 2^5=32. \]Therefore,
\[ 243-32 = \boxed{211}. \]Exactly One Empty Box
Suppose \(r\) distinct objects are distributed among \(n\) labeled boxes, with exactly one box empty.
Choose the empty box:
\[ n. \]Then distribute the objects onto the remaining \(n-1\) boxes so that all are nonempty.
Thus the count is
\[ \boxed{ n \sum_{j=0}^{n-1} (-1)^j \binom{n-1}{j} (n-1-j)^r }. \]Exactly \(m\) Empty Boxes
If exactly \(m\) of \(n\) labeled boxes are empty, then exactly
\[ n-m \]boxes are occupied.
Choose the empty boxes:
\[ \binom{n}{m}. \]Then count onto distributions to the remaining \(n-m\) boxes.
Collision Problems
An occupancy problem may ask whether two or more distinct objects land in the same box.
Such events are often called collisions.
Instead of counting collisions directly, it is often easier to count the complementary case in which every occupied box contains at most one object.
Example: At Least One Collision
Four distinct objects are assigned independently to six labeled boxes.
Total assignments:
\[ 6^4. \]Assignments with no collision:
\[ P(6,4) = 6\cdot5\cdot4\cdot3. \]Therefore, assignments with at least one collision total
\[ 6^4-P(6,4). \]Numerically,
\[ 1296-360 = \boxed{936}. \]Pigeonhole Connection
If more than \(n\) distinct objects are placed into \(n\) boxes, then at least one box must contain at least two objects.
This is the pigeonhole principle.
Occupancy models provide a natural setting for understanding why some restrictions are impossible before any detailed counting begins.
Example: Guaranteed Collision
Seven objects are placed into six boxes.
A distribution with at most one object per box would require at least seven boxes.
Therefore, every distribution must contain a collision.
Average Occupancy as a Guide
If \(r\) objects are distributed among \(n\) boxes, the average occupancy is
\[ \frac{r}{n}. \]The generalized pigeonhole principle guarantees that some box contains at least
\[ \boxed{\left\lceil\frac{r}{n}\right\rceil} \]objects.
Example: Generalized Pigeonhole Bound
Twenty-five objects are placed into six boxes.
Since
\[ \frac{25}{6}\approx4.17, \]at least one box must contain at least
\[ \boxed{5} \]objects.
Occupancy and Probability
In probability models, one often assumes each distinct object independently chooses one of \(n\) boxes uniformly.
Then the sample space contains
\[ n^r \]equally likely assignments.
Counting favorable assignments and dividing by \(n^r\) produces occupancy probabilities.
Example: Probability of No Collision
Suppose \(r\le n\) distinct objects independently choose among \(n\) equally likely boxes.
Total assignments:
\[ n^r. \]No-collision assignments:
\[ P(n,r). \]Therefore,
\[ \boxed{ \Pr(\text{no collision}) = \frac{P(n,r)}{n^r} }. \]Exactly One Box Receives All Objects
If \(r\) distinct objects are distributed among \(n\) labeled boxes, the number of assignments in which all objects occupy one common box is simply
\[ \boxed{n}. \]Choose which one box receives everything.
Exactly Two Occupied Boxes
For \(r\) distinct objects and \(n\) labeled boxes, exactly two occupied boxes can be counted by:
- choosing the two occupied boxes;
- assigning every object to one of those two boxes;
- excluding the two assignments that use only one of them.
Therefore,
\[ \boxed{ \binom{n}{2}(2^r-2) }. \]Example: Exactly Two Occupied Servers
Five distinct files are assigned among four servers, with exactly two servers used.
Choose the two servers:
\[ \binom{4}{2}=6. \]Assign all five files to those two servers, using both:
\[ 2^5-2=30. \]Therefore,
\[ 6\cdot30 = \boxed{180}. \]Distinguishing Selection from Distribution
Choosing a collection and distributing that collection are different stages.
For example, if \(5\) of \(10\) people are first selected and then assigned to two labeled teams, the selection count and distribution count must both be included.
A problem may therefore combine combinations with occupancy counting.
Example: Select and Assign
Choose \(5\) people from \(10\), then assign each selected person to one of two labeled projects.
Choose the people:
\[ \binom{10}{5}. \]Assign each selected person:
\[ 2^5. \]Therefore,
\[ \boxed{ \binom{10}{5}2^5 }. \]Occupancy Pattern versus Assignment
An occupancy pattern records only box counts.
An assignment records which distinct objects occupy which boxes.
When objects are distinct, many assignments may share the same occupancy pattern.
When objects are identical, the occupancy pattern usually determines the entire distribution for labeled boxes.
Example: Pattern \((2,1,1)\)
For four identical objects in three labeled boxes, the occupancy vector
\[ (2,1,1) \]identifies one distribution.
For four distinct objects, the same occupancy vector has
\[ \frac{4!}{2!1!1!} = 12 \]assignments.
Common Error: Using Stars and Bars for Distinct Objects
Stars and bars counts occupancy counts for identical objects.
If objects are distinct, different identities within the same box matter.
For five distinct objects and three labeled boxes, the unrestricted count is
\[ 3^5, \]not
\[ \binom{7}{2}. \]Common Error: Using \(n^r\) for Identical Objects
The power
\[ n^r \]treats the objects as individually distinguishable choices.
If the objects are identical and only box counts matter, use an occupancy equation and stars and bars instead.
Common Error: Ignoring Empty-Box Restrictions
The count
\[ n^r \]allows boxes to be empty.
If every labeled box must be used, an onto-function count is required.
Common Error: Treating Labeled Boxes as Identical
If boxes have names, numbers, addresses, servers, rooms, or recipients, then exchanging their contents usually creates a new outcome.
Do not divide by box permutations unless the boxes are genuinely indistinguishable in the problem.
Common Error: Dividing by \(n!\) for Unlabeled Boxes
When boxes are identical, it may be tempting to count labeled-box distributions and divide by \(n!\).
This is not always valid because distributions with repeated or empty box occupancies can have different symmetry sizes.
Unlabeled-box problems generally require partition-based methods rather than a blanket division by \(n!\).
Common Error: Applying Stars and Bars with Upper Bounds
Standard stars and bars assumes unlimited box capacity.
If a box may hold at most \(c\) objects, unrestricted stars and bars counts illegal solutions.
Use complements, cases, or inclusion–exclusion to enforce upper bounds.
Common Error: Forgetting Object Identity in Exact Loads
If six distinct objects must occupy labeled boxes in counts
\[ 3,\ 2,\ 1, \]there is not merely one distribution.
The object identities create
\[ \frac{6!}{3!2!1!} = 60 \]assignments.
A Reliable Classification Procedure
- Identify the objects being distributed.
- Decide whether those objects are distinct or identical.
- Identify the destinations.
- Decide whether the destinations are labeled or identical.
- Determine whether empty destinations are allowed.
- Record any minimum, maximum, or exact occupancy requirements.
- Translate the problem into the appropriate counting model.
A Reliable Formula Map
For \(r\) objects and \(n\) labeled boxes:
- distinct objects, empty allowed: \(\boxed{n^r}\);
- identical objects, empty allowed: \(\boxed{\binom{r+n-1}{n-1}}\);
- identical objects, every box nonempty: \(\boxed{\binom{r-1}{n-1}}\);
- distinct objects, every box nonempty: inclusion–exclusion or \(n!S(r,n)\);
- distinct objects, exact occupancies \(x_1,\ldots,x_n\): \(\boxed{\frac{r!}{x_1!\cdots x_n!}}\).
A Reliable Procedure for Distinct Objects
- Start by asking whether each object independently chooses a box.
- If unrestricted, use \(n^r\).
- If exact occupancies are specified, use a multinomial coefficient.
- If every box must be used, apply inclusion–exclusion.
- If at most one object may occupy a box, use permutations.
- If capacities vary, sum over legal occupancy patterns.
A Reliable Procedure for Identical Objects
- Represent box occupancies by variables \(x_1,\ldots,x_n\).
- Write \(x_1+\cdots+x_n=r\).
- Use nonnegative variables if empty boxes are allowed.
- Use positive variables if every box must be nonempty.
- Remove lower bounds by reserving minimum occupancies.
- Handle upper bounds by complements, cases, or inclusion–exclusion.
Example: Full Distinct-Object Workflow
Seven distinct tasks are assigned to three labeled workers, and every worker must receive at least one task.
The tasks are distinct and the workers are labeled.
Unrestricted assignments:
\[ 3^7. \]Subtract assignments missing one chosen worker:
\[ \binom{3}{1}2^7. \]Add back assignments using only one worker:
\[ \binom{3}{2}1^7. \]Therefore,
\[ 3^7-3(2^7)+3 = 2187-384+3 = \boxed{1806}. \]Example: Full Identical-Object Workflow
Twelve identical units are distributed among five labeled departments, with every department receiving at least one unit.
The occupancies satisfy
\[ x_1+x_2+x_3+x_4+x_5=12, \qquad x_i\ge1. \]Reserve one unit for each department, leaving \(7\).
Therefore,
\[ \binom{7+5-1}{5-1} = \binom{11}{4} = \boxed{330}. \]Practice 1: Distinct Objects, Empty Allowed
Six distinct files are assigned to four labeled servers. How many assignments are possible?
Practice 2: Identical Objects, Empty Allowed
Eight identical tokens are distributed among three labeled boxes. How many distributions are possible if boxes may be empty?
Practice 3: Identical Objects, No Empty Boxes
Eight identical tokens are distributed among three labeled boxes. How many distributions are possible if every box must receive at least one token?
Practice 4: Exact Occupancies
Seven distinct people are assigned to three labeled rooms with exact occupancies \(3,2,2\). How many assignments are possible?
Practice 5: Distinct Objects, Every Box Used
Five distinct objects are distributed among three labeled boxes, with every box nonempty. How many assignments are possible?
Practice 6: At Most One per Box
Four distinct cars are parked in nine labeled spaces, with at most one car per space. How many assignments are possible?
Practice 7: Exactly Two Occupied Boxes
Four distinct objects are distributed among six labeled boxes, with exactly two boxes occupied. How many assignments are possible?
Practice 8: One Required Minimum
Ten identical objects are distributed among three labeled boxes, with box \(1\) receiving at least four objects. How many distributions are possible?
Practice 9: At Least One Collision
Three distinct objects are assigned independently to five labeled boxes. How many assignments contain at least one collision?
Practice 10: Identify the Error
A student says that distributing six distinct objects among three labeled boxes gives
\[ \binom{8}{2}=28 \]possibilities.
Explain the model error and give the correct count.
Practice Answers
Practice 1
Each of six distinct files chooses one of four servers:
\[ 4^6 = \boxed{4096}. \]Practice 2
Solve
\[ x_1+x_2+x_3=8, \qquad x_i\ge0. \]Therefore,
\[ \binom{10}{2} = \boxed{45}. \]Practice 3
Require positive occupancies:
\[ \binom{8-1}{3-1} = \binom{7}{2} = \boxed{21}. \]Practice 4
\[ \frac{7!}{3!2!2!} = \boxed{210}. \]Practice 5
Use inclusion–exclusion:
\[ 3^5 - \binom{3}{1}2^5 + \binom{3}{2}1^5. \]Therefore,
\[ 243-96+3 = \boxed{150}. \]Practice 6
\[ P(9,4) = 9\cdot8\cdot7\cdot6 = \boxed{3024}. \]Practice 7
Choose the two occupied boxes:
\[ \binom{6}{2}=15. \]Assign four objects onto those two boxes:
\[ 2^4-2=14. \]Therefore,
\[ 15\cdot14 = \boxed{210}. \]Practice 8
Reserve four objects for box \(1\), leaving six identical objects:
\[ y_1+x_2+x_3=6, \qquad y_1,x_2,x_3\ge0. \]Therefore,
\[ \binom{8}{2} = \boxed{28}. \]Practice 9
Total assignments:
\[ 5^3=125. \]No-collision assignments:
\[ P(5,3) = 5\cdot4\cdot3 = 60. \]Therefore,
\[ 125-60 = \boxed{65}. \]Practice 10
The stars-and-bars count
\[ \binom{8}{2} \]treats the six objects as identical.
Here the objects are distinct, so each object independently chooses one of three labeled boxes:
\[ \boxed{3^6=729}. \]What to Remember
Occupancy problems are classified before they are calculated.
For \(r\) objects and \(n\) labeled boxes:
- distinct objects, empty boxes allowed: \(\boxed{n^r}\);
- identical objects, empty boxes allowed: \(\boxed{\binom{r+n-1}{n-1}}\);
- identical objects, every box nonempty: \(\boxed{\binom{r-1}{n-1}}\);
- distinct objects with fixed occupancies: \(\boxed{\frac{r!}{x_1!\cdots x_n!}}\);
- distinct objects, every box nonempty: use inclusion–exclusion or \(n!S(r,n)\);
- distinct objects, at most one per box: \(\boxed{P(n,r)}\).
Labeled versus identical boxes, object identity, empty-box rules, and capacity restrictions all change the model.
The central habit is therefore: classify the objects, classify the destinations, and encode the occupancy restrictions before choosing a formula.
Where We Go Next
Occupancy problems show how structural restrictions change a basic counting model. The same issue appears in arrangements: particular objects may be required to stay together, remain apart, occupy certain positions, avoid certain positions, or satisfy several constraints simultaneously.
The next lesson, Arrangements with Restrictions, develops systematic methods for handling those constrained permutation and arrangement problems.