Skip to content
Tutorials Center
My learning

Topics

Lesson 42 of 86 ยท Permutations, Combinations and Probability

Combinations

Learn nCr and when order does not matter: committees, handshakes, diagonals, dividing into groups and sharing objects, with a runnable nCr table.

A permutation counts arrangements, where order matters. A combination counts selections, where it does not. Choosing a committee of three people from ten is a combination: the committee {Asha, Ben, Chen} is the same committee no matter who you name first. Choosing a president, a secretary and a treasurer from the same ten people is a permutation, because the roles differ.

This lesson explains the combination formula nCr, then applies it to committees with conditions, handshakes, diagonals and lines, dividing people into groups, and sharing identical objects. It builds on Counting Principles and Permutations, so be comfortable with factorials first. Many probability questions later, starting with Probability, count outcomes with nCr.

The formula

The number of ways to choose r objects from n distinct objects, ignoring order, is

nCr = n! / (r! ร— (n โˆ’ r)!)

The idea behind it: nPr counts ordered selections, and each group of r objects appears r! times (once per ordering), so we divide nPr by r!.

For example, 10C3 = (10 ร— 9 ร— 8) / (3 ร— 2 ร— 1) = 720 / 6 = 120. In practice, write r factors going down from n on top and r! on the bottom, then cancel.

Facts that save time:

  • Symmetry: nCr = nC(n โˆ’ r). Choosing 3 to include equals choosing 7 to leave out, so 10C3 = 10C7. Always compute with the smaller of r and n โˆ’ r.
  • Edges: nC0 = nCn = 1 and nC1 = n.
  • Pascal's rule: nCr = (n โˆ’ 1)C(r โˆ’ 1) + (n โˆ’ 1)Cr. Choosing r from n either includes a specific object (choose r โˆ’ 1 from the rest) or excludes it (choose r from the rest).
flowchart TB
    A["Choose r objects from n"] --> B["Ordered: nPr ways"]
    B --> C["Each group counted r! times"]
    C --> D["nCr = nPr / r!"]

Divide the ordered count by the r! orderings of each group.

Committees and conditions

Combine the multiplication rule with nCr: choose a number from each category and multiply.

Example 1: exact numbers. A committee has 2 men and 2 women, chosen from 6 men and 4 women. Choose the men in 6C2 = 15 ways, the women in 4C2 = 6 ways, and multiply: 15 ร— 6 = 90.

Example 2: "at least one". A committee of 3 is formed from 5 men and 4 women, with at least one woman. Use the complement: all committees minus those with no women. All: 9C3 = 84. No women (all men): 5C3 = 10. So 84 โˆ’ 10 = 74.

Check by direct counting: 1 woman and 2 men gives 4 ร— 10 = 40; 2 women and 1 man gives 6 ร— 5 = 30; 3 women gives 4. Total 40 + 30 + 4 = 74. โœ“

Example 3: specific people. From 8 people choose a team of 4 that includes person A. Fix A, then choose 3 from the other 7: 7C3 = 35. If the team must exclude A: choose 4 from 7 = 7C4 = 35 as well (coincidence of symmetry: 7C3 = 7C4).

flowchart TB
    A["Committee with a condition"] --> B{"At least one?"}
    B -->|Yes| C["Total minus the none case"]
    B -->|No, exact numbers| D["Multiply nCr for each group"]
    A --> E{"Specific person in or out?"}
    E --> F["Fix them, choose the rest"]

For "at least one", the complement method is usually the shortest path.

Handshakes, diagonals and lines

Anything that is a pair chosen from n objects uses nC2 = n(n โˆ’ 1) / 2.

  • Handshakes: at a party of 12 people, each person shakes hands with every other once. The number of handshakes is 12C2 = 66.
  • Matches: in a tournament with 10 players where each pair plays once, there are 10C2 = 45 matches.
  • Lines: through 10 points, no three on a line, you can draw 10C2 = 45 lines. Three points define a triangle, so the same points give 10C3 = 120 triangles.
  • Diagonals of a polygon with n sides: choose any 2 vertices (nC2) and remove the n sides: nC2 โˆ’ n = n(n โˆ’ 3) / 2. A decagon (10 sides) has 10 ร— 7 / 2 = 35 diagonals, an octagon has 8 ร— 5 / 2 = 20.

If a question gives the count and asks for n, solve nC2 = 45: n(n โˆ’ 1) = 90, so n = 10.

Dividing into groups and distributing objects

Distinct people into labelled groups. Choose the first group, then the second from those left, and so on. Split 12 people into three labelled groups of 4 (say groups A, B and C): 12C4 ร— 8C4 ร— 4C4 = 495 ร— 70 ร— 1 = 34,650, which equals 12! / (4! 4! 4!).

Unlabelled groups of equal size. If the three groups of 4 are unlabelled, every split has been counted 3! = 6 times (once per labelling), so divide: 34,650 / 6 = 5,775. Divide by k! only when k groups have the same size and no labels.

Identical objects to distinct people (stars and bars). To give r identical objects to k people:

  • Any number (including zero) per person: (r + k โˆ’ 1)C(k โˆ’ 1).
  • At least one each: (r โˆ’ 1)C(k โˆ’ 1).

For 10 identical sweets among 3 children: with zeros allowed, 12C2 = 66; with at least one each, 9C2 = 36.

A quick reason for the second formula: line up the 10 sweets and choose 2 of the 9 gaps between them to place dividers, which cuts the row into 3 non-empty groups.

Permutation or combination?

Question says Use
arrange, order, rank, form a number permutation
select, choose, committee, team, hand combination
both selection and arrangement choose first (nCr), then arrange (r!)

Example: choose 3 of 5 people and then seat them in a row. The selection is 5C3 = 10, the seating is 3! = 6, and the total is 60, which equals 5P3.

An nCr table and checker

The script prints a Pascal's triangle (each row is nC0 through nCn), checks symmetry and Pascal's rule, and verifies the worked examples by listing the actual selections.

JS nCr table and identities

Press Run (or Ctrl + Enter) to see the console output here.

No output.

A brute-force check is the best way to trust a formula. This second script lists every committee of 3 from 5 men and 4 women and counts those with at least one woman, then counts the ways to give 10 sweets to 3 children by trying every split.

JS Brute-force the committees and sweets

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In how many ways can a committee of 3 be chosen from 7 people?

    7C3 = (7 x 6 x 5) / (3 x 2 x 1) = 210 / 6 = 35. Order does not matter, so it is a combination.
  2. 2. At a party every guest shakes hands with every other guest exactly once, and there are 45 handshakes. How many guests are there?

    nC2 = 45 means n(n - 1) = 90, so n = 10.
  3. 3. A committee of 3 is chosen from 5 men and 4 women with at least one woman. How many committees are possible?

    All committees: 9C3 = 84. Committees of only men: 5C3 = 10. At least one woman: 84 - 10 = 74.
  4. 4. How many diagonals does a polygon with 10 sides have?

    10C2 - 10 = 45 - 10 = 35, which equals n(n - 3) / 2 = 10 x 7 / 2.
  5. 5. In how many ways can 10 identical sweets be shared among 3 children if every child gets at least one?

    At least one each uses (r - 1)C(k - 1) = 9C2 = 36. The count 66 would allow a child to receive none.

Summary

  • nCr = n! / (r! (n - r)!) counts selections where order does not matter, and nCr = nC(n - r).
  • Committees with exact numbers: multiply nCr for each category; for "at least one", subtract the none case from the total.
  • Pairs from n objects (handshakes, matches, lines) use nC2; diagonals of an n-gon are nC2 - n = n(n - 3)/2.
  • Labelled groups use a product of nCr; divide by k! when k equal groups are unlabelled.
  • Identical objects shared among k people: (r + k - 1)C(k - 1) allowing zeros, (r - 1)C(k - 1) with at least one each.

Next: Circular Arrangements and Restrictions, where seats form a circle and some people must stay together.