Tutorial Sheet 2 – Combinatorics & Probability

Q1

Committee Formation

From a group of 7 men and 6 women, five persons are to be selected to form a committee so that at least 3 men are there on the committee. In how many ways can it be done?

▼

💡 Hints

"Selected" implies order does NOT matter → Use Combinations (nCr).
"At least 3 men" means you can have 3, 4, or 5 men.
These are mutually exclusive cases. Calculate each case and ADD them.

📝 What's Being Asked

We need to pick 5 people total from (7M + 6W).

Constraint: Men count ≥ 3.

Valid compositions: (3M, 2W) OR (4M, 1W) OR (5M, 0W).

📚 Concepts Used

Addition Principle

If cases are mutually exclusive (cannot happen at same time), ADD their counts.

Multiplication Principle

If tasks happen in sequence (Select Men AND Select Women), MULTIPLY their counts.

Total Ways = C(Men) × C(Women)

✍️ Full Solution

Case 1: 3 Men and 2 Women

Choose 3 men from 7: C(7,3)

Choose 2 women from 6: C(6,2)

Ways = C(7,3) × C(6,2) = 35 × 15 = 525

Case 2: 4 Men and 1 Woman

Choose 4 men from 7: C(7,4)

Choose 1 woman from 6: C(6,1)

Ways = C(7,4) × C(6,1) = 35 × 6 = 210

Case 3: 5 Men and 0 Women

Choose 5 men from 7: C(7,5)

Choose 0 women from 6: C(6,0)

Ways = C(7,5) × 1 = 21

Total Ways

Total = Case 1 + Case 2 + Case 3

525 + 210 + 21 = 756

Final Answer: 756

🔄 How Examiners Twist This

"At most": E.g., at most 2 men (Cases: 0, 1, or 2 men).
"Particular person included/excluded": Fix that person first, then choose the rest.
"Majority": Committee of 5, men must be in majority (Men > Women).

🎯 Exam Perspective

Marks Weight: 3 marks (Easy/Standard)

Common Mistake: Calculating C(7,3) × C(10, 2) (Selecting 3 men first, then any 2 from remaining). This is WRONG because it overcounts (introduces order among the men). Always use mutually exclusive cases.

Q2

Word Arrangements

In how many ways can the letters of the word STATISTICS be arranged? In how many of these do the vowels occur together?

▼

💡 Hints

Part 1: Permutation of multiset. Formula: n! / (p! q! r!...)
Part 2: "String Method". Tie the vowels (A, I, I) together as one "super-letter".
Don't forget to arrange the vowels inside the super-letter group!

📝 What's Being Asked

Total distinct permutations of "STATISTICS".
Permutations where [A, I, I] are adjacent blocks (e.g., STT[AII]STCS).

📚 Concepts Used

Multinomial Coefficient

Number of ways to arrange n items where n1 are alike, n2 are alike...

N = n! / (n1! × n2! × ...)

String Method

To keep items together, treat them as a single unit. Then multiply by internal arrangements.

✍️ Full Solution

Analysis of Word

S-T-A-T-I-S-T-I-C-S (10 letters)

S: 3 times
T: 3 times
I: 2 times
A: 1 time
C: 1 time

Part 1: Total Arrangements

Ways = 10! / (3! × 3! × 2! × 1! × 1!)
= 3,628,800 / (6 × 6 × 2)
= 3,628,800 / 72
= 50,400

Part 2: Vowels Together

Vowels: {A, I, I}. Consonants: {S, S, S, T, T, T, C}.

Treat {A, I, I} as one unit X.

Now we arrange {S, S, S, T, T, T, C, X}. Total 8 units.

Outer Arrangement: 8! / (3! × 3!) (S repeated 3, T repeated 3)
Inner Arrangement of {A, I, I}: 3! / 2! (I repeated 2)

Total = [8! / (6×6)] × [3! / 2!]

= [40320 / 36] × 3

= 1120 × 3 = 3360

Answers: 50,400 (Total), 3,360 (Vowels Together)

🎯 Exam Perspective

Marks Weight: 3-4 marks

Common Mistake: Forgetting internal arrangement of the tied group (even if identical, check n!/p!). Here {A,I,I} has 3!/2! arrangements, not just 1.

Q3

Round Table

In how many ways can 5 men and 2 ladies be arranged at a round table if two ladies are never together?

▼

💡 Hints

Use "Gap Method".
Seat the majority group (Men) first in a circle.
Then place Women in the gaps created by Men.
Arranging n things in circle = (n-1)!. Placing in gaps is linear permutation.

📝 What's Being Asked

Circular arrangement of 7 people.

Constraint: No two L are adjacent (L-L is forbidden).

📚 Concepts Used

Circular Permutation

Number of ways to arrange n distinct objects in a circle = (n-1)!.

Gap Method

To ensure NO TWO items of Type B are together: Arrange Type A first. Then put Type B in gaps.

✍️ Full Solution

Step 1: Seat the Men

5 Men in a circle.

Ways = (5 - 1)! = 4! = 24.

Step 2: Identify Gaps

5 Men create 5 gaps (spaces between them) in a circle.

_ M _ M _ M _ M _ M _

Step 3: Seat the Ladies

We need to place 2 Ladies in 5 available gaps.

Order matters (Ladies are distinct persons).

Ways = P(5, 2) = 5 × 4 = 20.

Total Ways

= (Ways to seat Men) × (Ways to seat Ladies)
= 24 × 20
= 480

Final Answer: 480

🔄 How Examiners Twist This

Necklace: Beads on a necklace can be flipped. Divide by 2.
Specific Neighbors: "A and B must sit together" (String method in circle).

🎯 Exam Perspective

Marks Weight: 3 marks

Q4

Distributing Distinct Objects

In how many ways can 5 distinct prizes be distributed among 4 students if each student can receive any number of prizes?

▼

💡 Hints

Think from the perspective of the PRIZE, not the student.
Take Prize 1. How many options does it have? (4 students).
Take Prize 2. How many options? (Still 4, because "any number" allowed).

📝 What's Being Asked

Distribute 5 DISTINCT items into 4 DISTINCT bins.

No restriction on bin capacity (can be empty, can full).

📚 Concepts Used

Distribution (Distinct to Distinct)

If distributing 'r' distinct objects into 'n' distinct boxes with replacement (repetition allowed):

Ways = n^r

✍️ Full Solution

Step-by-Step Selection

Prize 1 can go to Student A, B, C, or D -> 4 options.
Prize 2 can go to Student A, B, C, or D -> 4 options.
...
Prize 5 can go to Student A, B, C, or D -> 4 options.

Calculation

Total Ways = 4 × 4 × 4 × 4 × 4

= 4⁵ = 1024

Final Answer: 1024

🎯 Exam Perspective

Marks Weight: 2 marks

CONFUSION ALERT: Is it 4⁵ or 5⁴? Always ask "Who has the choice?". The Prize has 4 choices of students. The Student does not pick prizes (passive). So (Choices)^Objects.

Q5

Stars and Bars (Identical Objects)

In how many ways can 10 identical chocolates be distributed among 3 children so that each gets at least one?

▼

💡 Hints

Objects are identical. Order doesn't matter, only count matters.
"Distribute n identical items into r bins".
Constraint: "At least one" (Positive Integral Solutions).
Formula: C(n-1, r-1).

📝 What's Being Asked

Solve x1 + x2 + x3 = 10

Where x1, x2, x3 ≥ 1 (integers).

📚 Concepts Used

Stars and Bars (Positive Constraints)

To distribute n identical items to r bins with each bin ≥ 1:

C(n - 1, r - 1)

Visual: Place n items in a row. Choose (r-1) gaps out of (n-1) possible gaps to place dividers.

✍️ Full Solution

Identify Parameters

Number of items n = 10.

Number of bins r = 3.

Constraint: Each ≥ 1.

Apply Formula

Ways = C(n-1, r-1)

= C(10-1, 3-1)

= C(9, 2)

Calculation

= (9 × 8) / (2 × 1)
= 72 / 2
= 36

Final Answer: 36

🔄 How Examiners Twist This

Non-negative (≥0): Formula changes to C(n+r-1, r-1).
Lower bounds: "x1 ≥ 2". Give 2 items first, then distribute rest.

🎯 Exam Perspective

Marks Weight: 3 marks

Q6

The Birthday Paradox

In a room of n people, find the probability that at least two people share the same birthday. At what value of n does this probability exceed 50%?

▼

💡 Hints

Use Complement Rule: It is easier to find P(No one shares a birthday).
For no shared birthdays, everyone must have a distinct birthday.
First person: 365 options. Second: 364... nth: (365-n+1).

📝 What's Being Asked

Calculate P(At least one overlap).

Find minimum 'n' such that P > 0.5.

📚 Concepts Used

Complementary Probability

P(Match) = 1 - P(No Match)

Permutations with Large Numbers

P(n) = 1 - [P(365, n) / 365ⁿ]

✍️ Full Solution

Step 1: Calculate P(No Match)

Total possible birthday assignments for n people = 365ⁿ.

Favorable assignments (all distinct):

365 × 364 × ... × (365 - n + 1) = P(365, n).

Step 2: Apply Complement Rule

P(Match) = 1 - [365! / (365-n)!] / 365ⁿ

Step 3: Finding n for 50%

We check values:

n=22: P ≈ 0.476
n=23: P ≈ 0.507

Minimum n = 23

Final Answer: P = 1 - P(365,n)/365ⁿ; n = 23

🎯 Exam Perspective

Marks Weight: 4 marks

Common intuition says you need 366 people to be 100% sure (Pigeonhole Principal). But for 50% chance, you only need 23! This counter-intuitive result is why it's a favorite interview/exam question.

Q7

Sampling With vs Without Replacement

Urn contains 5 Red and 3 Black balls. Two balls are drawn. Find P(Both Red) if drawn (i) With Replacement (ii) Without Replacement.

▼

💡 Hints

Replacement: Events are independent. Probs don't change.
Without Replacement: Second draw depends on first. Total decreases by 1.

📝 What's Being Asked

Compare probabilities of RR outcome under two sampling methods.

📚 Concepts Used

Hypergeometric vs Binomial

With Rep = Binomial (Independent).

Without Rep = Hypergeometric (Dependent).

✍️ Full Solution

Total Balls

5 Red + 3 Black = 8 Balls.

(i) With Replacement

Draw 1: P(R1) = 5/8. Ball put back.

Draw 2: P(R2) = 5/8.

P(RR) = (5/8) × (5/8) = 25/64 ≈ 0.39

(ii) Without Replacement

Draw 1: P(R1) = 5/8. Ball kept out.

Draw 2: Total balls = 7. Red balls = 4.

P(R2 | R1) = 4/7.

P(RR) = (5/8) × (4/7) = 20/56 = 5/14 ≈ 0.357

Answer: (i) 25/64, (ii) 5/14

🎯 Exam Perspective

Marks Weight: 2 marks (Basic Concept Check)

Q8

Poker Hands: Full House

In a 5-card poker hand dealt from a standard 52-card deck, find the number of ways to get a "Full House" (3 cards of one rank, 2 of another).

▼

💡 Hints

Structure: {x, x, x, y, y}.
Two distinct ranks needed (e.g., Kings and Aces). Order of ranks matters (3 Kings, 2 Aces is diff from 3 Aces, 2 Kings).
Choose Rank 1 (for trip), choose 3 suits.
Choose Rank 2 (for pair), choose 2 suits.

📝 What's Being Asked

Count valid Full House combinations.

📚 Concepts Used

Card Terminology

Ranks: 2,3...10,J,Q,K,A (13 total).

Suits: ♣, ♦, ♥, ♠ (4 total).

✍️ Full Solution

Step 1: Choose Rank for the Triplet

Any of 13 ranks can be the triplet. C(13, 1).

Choose 3 suits out of 4 for this rank: C(4, 3).

Ways = 13 × 4 = 52.

Step 2: Choose Rank for the Pair

Any of remaining 12 ranks. C(12, 1).

Choose 2 suits out of 4: C(4, 2).

Ways = 12 × 6 = 72.

Step 3: Combine

Total = 52 × 72 = 3744

Final Answer: 3,744 ways

🎯 Exam Perspective

Marks Weight: 3-4 marks

Mistake: Choosing 2 ranks simultaneously C(13, 2). This assumes 3 Kings/2 Aces is same as 2 Kings/3 Aces, which is FALSE. The groups are different sizes (3 vs 2), so order of selection matters.

Q9

Grid Path Counting

Find number of paths from (0,0) to (6,4) on a grid moving only Right (R) and Up (U). How many pass through (3,2)?

▼

💡 Hints

Total steps needed = dx + dy = 6 + 4 = 10.
You must choose exactly 4 steps to be UP (or 6 to be RIGHT).
Constraint: Path passes through A(3,2). Split into (0,0)->(3,2) AND (3,2)->(6,4).

📝 What's Being Asked

1. Total monotonic paths.

2. Constrained paths via intermediate point.

📚 Concepts Used

Grid Path Formula

To go from (0,0) to (m, n), ways = C(m+n, m) or C(m+n, n).

✍️ Full Solution

Part 1: Total Paths (Unconstrained)

m=6, n=4. Total steps = 10.

Ways = C(10, 4) = 210

Part 2: Via (3,2)

Phase A: (0,0) to (3,2)

steps = 3+2 = 5. Way A = C(5, 2) = 10.

Phase B: (3,2) to (6,4)

dx = 6-3 = 3. dy = 4-2 = 2. steps = 5.

Way B = C(5, 2) = 10.

Total Constrained Ways

Total = 10 × 10 = 100

Answer: 100

🎯 Exam Perspective

Marks Weight: 3 marks

Q10

Derangements (Hat Check)

4 people check their hats. In how many ways can they carry back hats such that NO ONE gets their own hat?

▼

💡 Hints

This is the classic Derangement problem (D_n).
Use formula: D_n = n! [1/0! - 1/1! + 1/2! - ... + (-1)ⁿ/n!]
Or use Inclusion-Exclusion principle manually.

📝 What's Being Asked

Number of permutations of {1, 2, 3, 4} such that p(i) ≠ i for all i.

📚 Concepts Used

Derangement Formula

D(n) ≈ n!/e (closest integer).

Recurrence: D(n) = (n-1) [D(n-1) + D(n-2)].

✍️ Full Solution

Method 1: Formula

For n=4:

D(4) = 4! (1 - 1 + 1/2 - 1/6 + 1/24)

= 24 (1/2 - 1/6 + 1/24)

= 12 - 4 + 1

= 9

Method 2: Listing (Verification)

If Order is 1234:

Valid: 2143, 2341, 2413...

(Logic: 1 can go to 2, 3, or 4 - 3 options. Then solve reduced problems).

Final Answer: 9

🎯 Exam Perspective

Marks Weight: 3 marks

Memorize: D(3)=2, D(4)=9, D(5)=44. Saves time!

Q11

Multinomial Theorem

Find the coefficient of x³y⁴z² in the expansion of (x + y + z)⁹.

▼

💡 Hints

Check if powers sum to n (3+4+2 = 9). Yes.
Use Multinomial Coefficient formula: n! / (k1! k2! k3!).
This is equivalent to arranging letters xxx, yyyy, zz.

📝 What's Being Asked

Coefficient of specific term in multinomial expansion.

📚 Concepts Used

Multinomial Theorem

Coefficient of x1^k1...xm^km in (x1+...+xm)^n is:

n! / (k1! k2! ... km!)

Provided k1 + k2 + ... + km = n.

✍️ Full Solution

Identify Values

n = 9

k1 (power of x) = 3

k2 (power of y) = 4

k3 (power of z) = 2

Check: 3 + 4 + 2 = 9. Valid.

Calculate Coefficient

Coef = 9! / (3! × 4! × 2!)

= 362,880 / (6 × 24 × 2)

= 362,880 / 288

= 1260

Final Answer: 1260

🎯 Exam Perspective

Marks Weight: 2 marks

Q12

Inclusion-Exclusion Principle

Find the number of integers between 1 and 1000 (inclusive) that are divisible by 2 or 3 or 5.

▼

💡 Hints

Let A = div by 2, B = div by 3, C = div by 5.
Use |A ∪ B ∪ C| = Σ|A| - Σ|A ∩ B| + |A ∩ B ∩ C|.
Count(n, k) = floor(n/k).

📝 What's Being Asked

Cardinality of Union of 3 sets.

📚 Concepts Used

Inclusion-Exclusion (3 Sets)

N(A∪B∪C) = N(A)+N(B)+N(C) - [N(AB)+N(BC)+N(CA)] + N(ABC)

✍️ Full Solution

Step 1: Single Sets (Add)

|2| = floor(1000/2) = 500

|3| = floor(1000/3) = 333

|5| = floor(1000/5) = 200

Sum = 1033

Step 2: Pairwise Intersections (Subtract)

|2∩3| = |6| = floor(1000/6) = 166

|3∩5| = |15| = floor(1000/15) = 66

|2∩5| = |10| = floor(1000/10) = 100

Sum = 332

Step 3: Triple Intersection (Add)

|2∩3∩5| = |30| = floor(1000/30) = 33

Final Calculation

Total = 1033 - 332 + 33 = 734

Final Answer: 734

🎯 Exam Perspective

Marks Weight: 3 marks

Q13

Integer Solutions

Find the number of non-negative integer solutions to x + y + z + w = 20 with x ≥ 1, y ≥ 2, z ≥ 0, w ≥ 0.

▼

💡 Hints

Transform variables to remove lower bound constraints.
Let x' = x - 1 (so x' ≥ 0).
Let y' = y - 2 (so y' ≥ 0).
Rewrite equation for new variables and use Stars and Bars.

📝 What's Being Asked

Number of solutions to linear Eq with constraints.

📚 Concepts Used

Stars and Bars (Standard Form)

For x1 + ... + xr = n with xi ≥ 0:

Ways = C(n + r - 1, r - 1)

✍️ Full Solution

Step 1: Constraint Transformation

x' = x - 1 => x = x' + 1

y' = y - 2 => y = y' + 2

z' = z, w' = w

Substitute into original eq:

(x' + 1) + (y' + 2) + z' + w' = 20

x' + y' + z' + w' = 17

Step 2: Apply Formula

n = 17 (new sum)

r = 4 (variables)

Ways = C(17 + 4 - 1, 4 - 1)

= C(20, 3)

Calculation

= (20 × 19 × 18) / (3 × 2 × 1)
= 6840 / 6
= 1140

Final Answer: 1140

🎯 Exam Perspective

Marks Weight: 3 marks

Q14

Matching Shoes Problem

A closet contains 10 pairs of shoes. If 4 shoes are selected at random, find the number of ways to select them such that there is (i) No making pair (ii) Exactly one matching pair.

▼

💡 Hints

Think in terms of "Pairs" first, then "Left/Right".
(i) No pair: Select 4 distinct pairs, then pick L or R from each.
(ii) One pair: Select 1 pair (take both), then select 2 other distinct pairs and picking 1 from each.

📝 What's Being Asked

Subset selection constraints from paired set.

📚 Concepts Used

Constructive Counting

Build the selection step-by-step.

✍️ Full Solution

Total Shoes: 20 (10 pairs)

(i) No Matching Pair

Select 4 distinct pairs from 10: C(10, 4)
From each pair, choose Left or Right (2 options): 2⁴

Ways = C(10, 4) × 16 = 210 × 16 = 3360

(ii) Exactly One Matching Pair

Select 1 pair to be complete: C(10, 1) ways. (2 shoes used)
Need 2 more shoes from remaining 9 pairs with NO matches.
Select 2 pairs from 9: C(9, 2).
Select L or R from each: 2².

Ways = 10 × 36 × 4 = 1440

Answers: (i) 3360, (ii) 1440

🎯 Exam Perspective

Marks Weight: 4 marks

Q15

Elevator Problem

An elevator starts with 7 passengers and stops at 10 floors. Find the probability that no two passengers get off at the same floor.

▼

💡 Hints

Total Ways: Each passenger has 10 choices. 10⁷.
Favorable Ways: Each passenger chooses a DISTINCT floor. This is a Permutation problem.

📝 What's Being Asked

P(All passengers choose distinct floors).

📚 Concepts Used

Classic Probability

P = Favorable / Total

✍️ Full Solution

Step 1: Total Outcomes

Passenger 1: 10 choices

Passenger 2: 10 choices... etc.

Total = 10⁷ = 10,000,000.

Step 2: Favorable Outcomes

Passenger 1: 10 choices

Passenger 2: 9 choices (cannot match P1)

...

Passenger 7: 4 choices

Favorable = P(10, 7) = 10×9×8×7×6×5×4 = 604,800.

Step 3: Probability

P = 604,800 / 10,000,000 = 0.06048

Answer: ~6%

🎯 Exam Perspective

Marks Weight: 2 marks

Q16

MISSISSIPPI (Non-Adjacent)

In how many ways can the letters of MISSISSIPPI be arranged so that no two S's are next to each other?

▼

💡 Hints

Same as Question 3 (Round Table Gaps).
Arrange Non-S letters first: M, I, I, I, I, P, P.
Identify gaps between them.
Place the 4 S's into the gaps.

📝 What's Being Asked

Permutations with separation constraint on identical items.

📚 Concepts Used

Gap Method (Identical Items)

1. Permute Non-Target (N) items: Ways A.

2. Choose k gaps for Target items: C(spaces, k).

Total = A × C(spaces, k).

(Note: Since S's are identical, we just CHOOSE gaps, we don't arrange them).

✍️ Full Solution

Letters Analysis

S: 4 (Target)

Non-S: {M:1, I:4, P:2}. Total 7.

Step 1: Arrange Non-S

Arrange {M, I, I, I, I, P, P}:

Ways = 7! / (4! 2! 1!) = 5040 / (24 × 2) = 105.

Step 2: Place S's in Gaps

7 letters create 8 gaps: _ X _ X _ X _ X _ X _ X _ X _

We need to place 4 identical S's in 8 gaps.

Ways = C(8, 4) = 70.

Total Ways

Total = 105 × 70 = 7350

Final Answer: 7350

🎯 Exam Perspective

Marks Weight: 4 marks