Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 36 ยท Projects and Practice

Practice Set: Counting Problems

Ten counting problems with worked formulas and brute-force checks: license plates, MISSISSIPPI, committees, stars and bars, circular seating, inclusion-exclusion and more.

The best way to learn counting is to solve problems, then verify the answer by brute force. This set has ten problems. Try each on paper first (the formulas are the standard ones from the whole course), then run the code: every TryIt prints the formula result next to a brute-force count so you can see whether you were right.

How to attack a counting problem

  1. Decide what is being counted and what makes two outcomes the same (order? labels? rotations?).
  2. Look for a sum (disjoint cases) or product (independent steps) structure.
  3. If it is easier to count what you do not want, use the complement.
  4. Check a small case by hand or by program before trusting a formula for a big one.

Problems 1 to 5

  1. License plates. A plate has 3 distinct capital letters followed by 3 digits (digits may repeat). How many plates?
  2. Arrangements. How many distinct arrangements are there of the letters of MISSISSIPPI?
  3. Committees. From 6 men and 4 women, choose a committee of 5 with at least 2 women.
  4. Stars and bars. How many solutions to x1 + x2 + x3 + x4 = 12 with x_i >= 0? With every x_i >= 1?
  5. Round table. 7 people sit around a table; two particular people, A and B, must sit next to each other. Rotations count as the same seating.
Python Problems 1-5: formula against brute force

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed answers are:

  1. 26 * 25 * 24 * 1000 = 15,600,000 (letters distinct: a product of 26, 25, 24 choices).
  2. 11!/(4! 4! 2!) = 34,650 (M once, I four times, S four times, P twice).
  3. 186 (split by number of women: 2, 3 or 4).
  4. binom(15,3) = 455 for x_i >= 0 (stars and bars with 12 stars and 3 bars), and binom(11,3) = 165 when every x_i >= 1 (give each variable 1 first).
  5. 240: glue A and B into one block (2 internal orders), then arrange 6 units around a circle: 5! ways, so 2 * 120.

Problems 6 to 10

  1. Inclusion-exclusion. How many integers from 1 to 1000 are divisible by 3, 5 or 7?
  2. Derangements. In how many ways can 6 letters be placed in 6 addressed envelopes so that no letter is in its own envelope?
  3. Separating vowels. How many arrangements of the letters of COMPUTER have no two vowels adjacent?
  4. Surjections. How many functions from a 6-element set onto a 3-element set?
  5. No adjacent ones. How many binary strings of length 10 have exactly three 1s, no two adjacent?
Python Problems 6-10: formula against brute force

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

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The answers:

  1. 543 by inclusion-exclusion: add the three single counts (333 + 200 + 142), subtract the pairwise overlaps (66 + 47 + 28), add back the triple (9).
  2. 265 (D_6 = 6! * sum (-1)^k/k!).
  3. 14,400: arrange the 5 consonants (5!), choose 3 of the 6 gaps for the vowels (binom(6,3)), order the vowels (3!).
  4. 540: 3^6 - 3 * 2^6 + 3 * 1 = 729 - 192 + 3. Equivalent to 3! * S(6,3), see Stirling numbers.
  5. 56: put the 7 zeros in a row, creating 8 gaps, and place the 3 ones in different gaps: binom(8,3).
flowchart TD
    P["Problem"] --> Q{"Order matters?"}
    Q -->|"yes"| R["Permutations / product rule"]
    Q -->|"no"| S["Combinations / stars and bars"]
    P --> T{"Constraint 'at least one' or 'none of'?"}
    T --> U["Inclusion-exclusion or complement"]
    P --> V{"Symmetry (rotation, labels)?"}
    V --> W["Divide by symmetry or use Burnside"]

A quick decision guide for choosing a counting method.

If your brute-force count disagrees with your formula, find the smallest input where they differ. That usually exposes the overlap or the missing case in the reasoning.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many solutions does x1 + x2 + x3 = 10 have in non-negative integers?

    Stars and bars: binom(10 + 2, 2) = 66.
  2. 2. A committee of 3 is chosen from 5 people. Which count is correct?

    Order does not matter: binom(5,3) = 10.
  3. 3. Arrangements of the word BANANA?

    6!/(3! * 2!) = 60: three As and two Ns.
  4. 4. 7 people sit around a round table, rotations equal. How many seatings?

    (7-1)! = 720.
  5. 5. Which technique counts integers up to N divisible by at least one of several numbers?

    Add single counts, subtract pairs, add back triples, and so on.

Summary

  • Always define what makes outcomes the same: order, labels, rotation.
  • Standard tools: product and sum rules, permutations with repeats, binomials, stars and bars, circular arrangements, gaps for non-adjacency, inclusion-exclusion, derangements, surjections.
  • Verify each formula against brute force on a small case.

Next: Practice Set: Advanced Counting