Combinations

Combinations are about selection — how many ways can we choose things when the order doesn’t matter. Picking 3 people for a team is a combination problem because we just care about WHO is on the team, not the order we picked them. The only difference from permutations is: in combinations, ABC = ACB = BAC = BCA = CAB = CBA — they’re all the same selection.

Permutation vs Combination — The Key Difference

Permutation: Arrangement matters → choosing a president, VP, and secretary → nPr

Combination: Only selection matters → choosing a 3-person committee → nCr

In simple language: if we’re assigning roles or positions, it’s a permutation. If we’re just picking a group, it’s a combination.

Quick test: After selecting, does rearranging the chosen items give something different? If yes → permutation. If no → combination.

Key Formulas

Understanding nCr

nCr = n! / [r! × (n-r)!]

This gives us the number of ways to choose r items from n distinct items, where order doesn’t matter.

The relationship: nCr = nPr / r!. We take the permutation (which overcounts because order matters) and divide by r! (the number of ways to arrange the r chosen items) to remove the ordering.

Key Properties

• nC0 = 1 — there’s exactly one way to choose nothing
• nCn = 1 — there’s exactly one way to choose everything
• nC1 = n — choosing 1 item from n gives n choices
• nCr = nC(n-r) — choosing r items to include is the same as choosing (n-r) items to exclude. So 10C7 = 10C3 (use this to simplify calculations!)

Quick Calculation Trick

Always use the smaller of r and (n-r) to minimize computation.

10C3 = (10 × 9 × 8) / (3 × 2 × 1) = 720/6 = 120

We only need to multiply r terms going down from n, then divide by r!. Much faster than computing full factorials.

Useful Values to Know

Committee / Team Selection

This is the bread-and-butter application of combinations.

Basic Selection

“Choose r people from n” = nCr. That’s it.

Selection with Constraints

These are where exams get tricky:

“At least k” type: Calculate for each valid value and add up, OR use complement: nCr(at least k) = Total − nCr(fewer than k)

“At most k” type: Calculate for 0, 1, 2, …, k and add up.

“Exactly k from group A and exactly j from group B”: Multiply the individual combinations.

The “Must Include / Must Exclude” Approach

• Person X must be included: Fix X in the team, choose remaining (r-1) from remaining (n-1). Answer: (n-1)C(r-1)
• Person X must be excluded: Choose all r from remaining (n-1). Answer: (n-1)Cr
• Both X and Y must be included: Fix both, choose (r-2) from (n-2)
• At least one of X or Y: Total − Neither = nCr − (n-2)Cr

Handshakes and Diagonals

Handshakes

If n people are in a room and each shakes hands with everyone else:

Number of handshakes = nC2 = n(n-1)/2

Each handshake involves 2 people, and order doesn’t matter (A shaking B’s hand = B shaking A’s hand).

Diagonals of a Polygon

Each diagonal connects 2 non-adjacent vertices.

Diagonals = nC2 − n = n(n-1)/2 − n = n(n-3)/2

We subtract n because nC2 counts all connections (including the n sides, which are not diagonals).

Distribution Problems

Identical Objects into Distinct Groups

Distributing n identical objects into r distinct groups (each group can get 0 or more):

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

This is the “stars and bars” theorem. Think of it like: we have n stars (objects) and need (r-1) bars (dividers) to create r groups.

Distinct Objects into Distinct Groups

Each object has r choices → r^n ways (each of the n objects independently goes to one of r groups).

Shortcut Methods and Tricks

Trick 1: Symmetry saves time 20C17 = 20C3 = (20 × 19 × 18) / 6 = 1140. Always reduce to the smaller side.

Trick 2: Committee with groups “Select 5 from 6 men and 4 women with at least 2 women” → don’t calculate “at least” directly. Calculate: (2W, 3M) + (3W, 2M) + (4W, 1M). It’s usually faster.

Trick 3: Complementary counting “At least 1” = Total − “none” is almost always faster than direct calculation.

Trick 4: Points and lines/triangles

• Lines from n points (no 3 collinear): nC2
• Triangles from n points (no 3 collinear): nC3
• If k points are collinear: subtract kC2 from lines (or kC3 from triangles) and add back what the collinear points contribute (1 line for collinear points, 0 triangles)

Worked Examples

Example 1: Basic Combination

A class has 12 students. In how many ways can a team of 4 be chosen?

12C4 = (12 × 11 × 10 × 9) / (4 × 3 × 2 × 1) = 11880 / 24 = 495 ways

Example 2: Committee with Constraints

From 5 men and 4 women, a committee of 4 is to be formed with at least 2 women. How many ways?

We need: (2W, 2M) or (3W, 1M) or (4W, 0M)

• 2W, 2M: 4C2 × 5C2 = 6 × 10 = 60
• 3W, 1M: 4C3 × 5C1 = 4 × 5 = 20
• 4W, 0M: 4C4 × 5C0 = 1 × 1 = 1

Total = 60 + 20 + 1 = 81 ways

Example 3: Handshakes

In a party of 10 people, everyone shakes hands with everyone else. How many handshakes?

10C2 = 10 × 9 / 2 = 45 handshakes

Example 4: Must Include / Must Exclude

From 8 students, a team of 5 is chosen. In how many ways if (a) a particular student must be in the team, and (b) two particular students cannot both be in the team?

(a) Fix that student. Choose remaining 4 from 7: 7C4 = 35. 35 ways.

(b) Total − Both in = 8C5 − 6C3. Total = 8C5 = 56. Both in (fix both, choose 3 from 6) = 6C3 = 20. Answer = 56 − 20 = 36 ways.

Example 5: Points and Triangles

There are 10 points in a plane, no 3 collinear. How many triangles can be formed? How many straight lines?

Triangles = 10C3 = (10 × 9 × 8) / 6 = 120 triangles

Lines = 10C2 = (10 × 9) / 2 = 45 lines

Follow-up: If 4 of the 10 points are collinear, triangles = 10C3 − 4C3 = 120 − 4 = 116 triangles. Lines = 10C2 − 4C2 + 1 = 45 − 6 + 1 = 40 lines (we remove the 6 lines those 4 points would have made and add back the 1 line they actually form).

Common Exam Variations

1. Committee formation — with constraints on gender, age group, or department representation
2. Handshakes and diagonals — sometimes combined (e.g., at a conference, each table has n people)
3. Selection from groups — “choose 3 books from 5 math and 4 science, with at least 1 from each”
4. Identical objects — distributing chocolates, fruits, or balls into groups
5. Cards — choosing hands from a deck of 52 (very common in probability problems too)

Practice Problems

Q1: How many diagonals does a dodecagon (12-sided polygon) have?

Q2: A box contains 5 red and 4 blue balls. In how many ways can 3 balls be drawn such that at least 1 is red?

Q3: From a group of 7 men and 6 women, a committee of 5 is to be formed such that there are at least 3 men. Find the number of ways.

Answers

A1: Diagonals = 12 × (12-3) / 2 = 12 × 9 / 2 = 54 diagonals.

A2: Total ways to draw 3 from 9 = 9C3 = 84. Ways with NO red (all blue) = 4C3 = 4. At least 1 red = 84 − 4 = 80 ways. (Complement method — much faster than calculating 1 red + 2 red + 3 red separately.)

A3: Cases: (3M, 2W) + (4M, 1W) + (5M, 0W) = 7C3 × 6C2 + 7C4 × 6C1 + 7C5 × 6C0 = 35 × 15 + 35 × 6 + 21 × 1 = 525 + 210 + 21 = 756 ways.