An Initiative by SAARTHI IAS
Maarg Manthan · Topic 22.13

Distribution of Distinct or Identical Objects into Groups/Boxes

Quantitative Aptitude › Permutation, Combination and Probability · Topic 22.13

Distribution problems count the ways to place n objects into groups or boxes, including dividing objects into groups of given size. For n distinct objects into r distinct boxes the count is r to the power n, and for n identical objects into r distinct boxes it is (n + r - 1)C(r - 1).

Share:
Distribution of Distinct or Identical Objects into Groups/Boxes - Quantitative Aptitude - MaargX UPSC Maarg Manthan

Quick Answer

Distribution problems count the ways to place n objects into groups or boxes, including dividing objects into groups of given size. For n distinct objects into r distinct boxes the count is r to the power n, and for n identical objects into r distinct boxes it is (n + r – 1)C(r – 1).

At a Glance

  • Distinct into r distinct boxes rn
  • Identical, any number per box (n+r-1)C(r-1)
  • Identical, each box at least 1 (n-1)C(r-1)
  • Distinct into groups a, b, c n!/(a! b! c!)
  • Equal unlabelled groups Divide by the number of groups factorial

Where Does It Fit?

This topic closes the counting and probability macro. It applies the choosing ideas of Combination and Selection Problems and the repeated-letter methods of Permutation of Identical/Indistinguishable Objects, and it is a standard CAT counting question.

How Do You Distribute Distinct Objects Into Boxes?

In short: each of the n distinct objects can go into any of r distinct boxes independently, so the total number of ways is r multiplied by itself n times.

Distinct objects

  • n distinct objects into r distinct boxes (any number per box): rn
  • n distinct objects into groups of sizes a, b, c with a + b + c = n: n!/(a! b! c!)
  • n distinct objects into k equal groups that are not labelled: divide the group formula by k!
Case Calculation Ways
5 distinct balls into 3 distinct boxes 35 243
4 distinct letters into 3 distinct mailboxes 34 81
9 distinct books into groups of 4, 3, 2 9!/(4! 3! 2!) 1260
6 distinct people into 3 equal unlabelled groups of 2 6!/(2! 2! 2!)/3! 15

If the groups have different sizes, they are automatically distinguishable, so no division by k! is needed. If the groups are equal in size and unlabelled, such as three pairs, divide by 3! to remove repeated orders.

How Do You Distribute Identical Objects Into Boxes?

In short: use stars and bars. Place n identical stars in a row and put r – 1 bars between them to separate the boxes.

Identical objects (stars and bars)

  • n identical objects into r distinct boxes, empty boxes allowed: (n + r – 1)C(r – 1)
  • n identical objects into r distinct boxes, each at least 1: (n – 1)C(r – 1)
  • Non-negative integer solutions of x1 + x2 + … + xr = n: (n + r – 1)C(r – 1)
  • Empty boxes allowed: 8 identical sweets among 3 children gives (8 + 2)C2 = 10C2 = 45 ways.
  • At least one each: 8 identical sweets among 3 children with each child getting at least one gives 7C2 = 21 ways.
  • Minimum limits: if one box must have at least 2, give those 2 first and distribute the rest: x + y + z = 10 with x at least 2 becomes x’ + y + z = 8, so (8 + 2)C2 = 45 ways.

The number of positive integer solutions of x + y + z = 10 is 9C2 = 36, and the number of non-negative solutions is 12C2 = 66.

How Do You Decide Which Formula to Use?

In short: ask two questions: are the objects distinct or identical, and are the boxes or groups labelled or not?

Objects Boxes or groups Rule
Distinct Distinct boxes, any number each rn
Distinct Groups of fixed sizes n!/(a! b! c!)
Distinct Equal groups, unlabelled Divide by k!
Identical Distinct boxes, empty allowed (n+r-1)C(r-1)
Identical Distinct boxes, none empty (n-1)C(r-1)

Choose the group sizes one at a time using combinations. For two labelled groups of 5 and 5 from 10 distinct people, the count is 10C5 = 252, and if the two groups are not labelled, it is 252/2 = 126.

Solved Examples

Example 1

Question: In how many ways can 5 distinct balls be placed in 3 distinct boxes, if any box can hold any number of balls?

  1. Each ball has 3 choices of box.
  2. Total ways = 3 × 3 × 3 × 3 × 3 = 35.

Answer: 243 ways.

Example 2

Question: In how many ways can 8 identical sweets be given to 3 children if (a) any child may get none, (b) each child gets at least one?

  1. (a) Use (n + r – 1)C(r – 1) = (8 + 2)C2 = 10C2 = 45.
  2. (b) Use (n – 1)C(r – 1) = 7C2 = 21.

Answer: (a) 45 ways; (b) 21 ways.

Example 3

Question: In how many ways can 9 distinct books be divided into groups of 4, 3 and 2 books?

  1. Use n!/(a! b! c!) = 9!/(4! × 3! × 2!).
  2. 9! = 362880 and 4! 3! 2! = 24 × 6 × 2 = 288.
  3. 362880/288 = 1260.

Answer: 1260 ways.

Example 4

Question: In how many ways can 6 distinct people be divided into 3 unlabelled groups of 2 each?

  1. Labelled groups: 6!/(2! 2! 2!) = 720/8 = 90.
  2. The three groups are unlabelled, so divide by 3! = 6.
  3. 90/6 = 15.

Answer: 15 ways.

Example 5

Question: Find the number of non-negative integer solutions of x + y + z = 10 with x at least 2.

  1. Put x = 2 + x’, so x’ + y + z = 8 with all variables at least 0.
  2. Count = (8 + 2)C2 = 10C2.

Answer: 45 solutions.

Shortcuts and Tricks

  • For distinct objects into labelled boxes, each object has r choices, so the answer is rn.
  • For identical objects, think stars and bars: n stars and r – 1 bars.
  • If every box needs at least one object, give one to each first, then distribute the rest.
  • For equal groups that are not labelled, divide by the factorial of the number of groups.
  • Convert a lower limit on a variable into a shift: x at least 2 becomes x’ = x – 2 at least 0.

Common Mistakes

  • Using stars and bars for distinct objects, or rn for identical objects.
  • Dividing by k! when groups have different sizes, since they are already distinguishable.
  • Forgetting to divide by k! when the equal groups are unlabelled, which overcounts.
  • Using n – 1 and r – 1 when empty boxes are allowed, or n + r – 1 when each box must be non-empty.
  • Reversing r and n in rn, which gives a different number.

Practice Questions

  1. In how many ways can 4 distinct letters be posted in 3 distinct mailboxes?
  2. In how many ways can 7 identical balls be placed in 4 distinct boxes with none empty?
  3. In how many ways can 10 distinct people be split into two labelled groups of 5?
  4. In how many ways can 12 identical pens be given to 3 children with empty hands allowed?
  5. In how many ways can 6 distinct people be split into groups of 3, 2 and 1?
  6. Number of positive integer solutions of x + y + z = 10?

Answers: 1) 81; 2) 20; 3) 252; 4) 91; 5) 60; 6) 36.

Why Is This Topic Important?

What Comes Next?

The next macro begins with Set Theory – Union, Intersection, Complement and Venn Diagram Problems. It moves from counting to sets, with unions, intersections and Venn diagrams.

Key Terms and Formulas

  • Stars and bars A method for counting distributions of identical objects
  • Distinct objects Objects that can be told apart
  • Identical objects Objects that cannot be told apart
  • Labelled groups Groups that can be told apart by name or role
  • Unlabelled groups Groups that differ only by their members

Exam Corner

Points to Remember

  • n distinct into r distinct boxes: rn.
  • n identical into r boxes, empty allowed: (n+r-1)C(r-1).
  • n identical into r boxes, none empty: (n-1)C(r-1).
  • Groups of sizes a, b, c: n!/(a! b! c!).
  • Equal unlabelled groups: divide by k!.

Do Not Confuse With

  • Distinct vs identical Distinct objects use powers or multinomials; identical objects use stars and bars.
  • Empty allowed vs not allowed Allowing empty boxes uses n + r – 1; forbidding them uses n – 1.
  • Labelled vs unlabelled groups Unlabelled groups of equal size need division by k!.
  • r to the n vs n to the r Each of n objects has r choices, so it is r to the power n.

Memory Hook

Distinct: powers. Identical: stars and bars. Equal unlabelled: divide by k factorial.

GS Relevance

Distribution of objects into groups or boxes for CAT and SSC CGL: distinct and identical objects, stars and bars, and equal group formulas.

Frequently Asked Questions

How many ways can n distinct objects go into r distinct boxes?

There are r to the power n ways to place n distinct objects into r distinct boxes when any box can hold any number of objects. Each object independently has r choices of box, so the choices are multiplied n times.

What is the stars and bars method?

The stars and bars method counts ways to distribute n identical objects into r distinct boxes. Place n stars in a row and insert r minus 1 bars to separate the boxes, giving (n + r - 1) choose (r - 1) ways when empty boxes are allowed.

How many ways can 9 distinct books be split into groups of 4, 3 and 2?

The 9 distinct books can be split into groups of 4, 3 and 2 in 1260 ways. The count is 9 factorial divided by the product of 4 factorial, 3 factorial and 2 factorial, which is 362880 divided by 288.

When do you divide by the factorial of the number of groups?

Divide by the factorial of the number of groups when the groups are equal in size and are not labelled, because every ordering of the same groups would otherwise be counted separately. For three unlabelled pairs from six people, the count 90 is divided by 6 to give 15.

How do you count solutions of x + y + z = 10 in non-negative integers?

The number of non-negative integer solutions of x + y + z = 10 is 12 choose 2, which is 66, using stars and bars with 10 stars and 2 bars. If each variable must be positive, the count falls to 9 choose 2, which is 36.

PYQ Practice — Statement Analysis

1 The number of ways to place 5 distinct balls into 3 distinct boxes is 243.
True

Each ball has 3 choices, so the total is 3^5 = 243.

2 The number of ways to give 8 identical sweets to 3 children, with each child getting at least one, is 21.
True

With each child getting at least one, the count is 7C2 = 21.

3 Three unlabelled groups of 2 from 6 distinct people can be formed in 90 ways.
False

90 counts labelled groups; for unlabelled groups the count is 90/6 = 15.

4 The number of non-negative integer solutions of x + y + z = 10 is 66.
True

Using stars and bars, the count is 12C2 = 66.

Share: