Exercises: Counting, Permutations & Combinations
1. Route Planning
You can travel from Milan to Rome by train (4 departures per day) or by bus (3 departures per day). The two options never overlap in schedule.
(a) How many departure options do you have on a given day?
(b) You plan a round trip: train or bus to Rome, then train or bus back. How many distinct round-trip itineraries are possible?
2. Username System
A system allows usernames that are either:
- Type 1: exactly 3 lowercase letters (a–z), or
- Type 2: exactly 2 digits (0–9) followed by exactly 2 lowercase letters
How many distinct usernames are possible?
3. Go Board
A Go board has a 19 × 19 grid of points. Each point can be: empty, hold a black stone, or hold a white stone.
How many possible board configurations are there? How does this compare to the number of atoms in the observable universe (~1080)?
4. License Plates
A country issues license plates in two formats:
- Old format: 2 letters + 4 digits (e.g., AB 1234)
- New format: 2 letters + 3 digits + 2 letters (e.g., AB 123 CD)
(a) How many plates does each format support?
(b) How many total plates across both formats?
5. Student Survey
In a class of 200 students:
- 140 speak English
- 88 speak Italian
- 45 speak both
(a) How many speak English or Italian (or both)?
(b) How many speak neither?
6. Divisibility
How many integers from 1 to 1000 are divisible by 3 or by 5?
Hint: How many are divisible by both 3 and 5?
7. Letter Orderings
How many distinct orderings (anagrams) can be formed from the letters of:
(a) COUNTING (b) ENGINEERING (c) TENNESSEE
8. Smudged Passcode
Your phone has a 4-digit passcode. You notice smudge marks on the screen.
(a) If there are smudges on exactly 4 different digits, how many possible passcodes?
(b) If there are smudges on exactly 3 different digits (so one digit must be used twice), how many possible passcodes?
(c) If there are smudges on exactly 2 different digits, how many possible passcodes?
9. Photo Arrangement
Eight friends line up for a photo.
(a) How many arrangements are possible?
(b) How many if the tallest person must be in the center (position 4 or 5)?
(c) How many if Alice and Bob must stand next to each other?
10. Bookshelf
You have 4 math books, 3 CS books, and 2 novels. They must be arranged on a shelf so that books of the same subject are grouped together.
How many arrangements are possible?
11. Team Selection
A class has 15 students.
(a) How many ways to form a study group of 4?
(b) How many ways if two specific students (rivals) cannot both be in the group?
12. Committee with Roles
From 12 people, you must form a committee of 5 and then assign a chair and a secretary from those 5.
How many ways?
13. Pizza Toppings
A pizzeria offers 10 toppings. You can choose any number of toppings (including zero).
(a) How many different pizzas are possible?
(b) How many have exactly 3 toppings?
(c) How many have at least 2 toppings?
14. Hash Table
A hash function assigns 8 distinct strings to 4 buckets. Each string is independently mapped to one bucket.
(a) How many possible assignments are there?
(b) How many assignments put all 8 strings into the same bucket?
15. Startup Investment
A venture capital firm has €8M to invest across 3 startups, in €1M increments.
(a) How many ways can the firm allocate the money, if every euro must be invested?
(b) How many ways if each startup must receive at least €1M?
(c) How many ways if the firm is not required to invest all €8M?
16. Task Distribution
A company has 12 identical tasks to distribute among 4 engineers. Each engineer can receive any number of tasks (including zero).
How many ways can the tasks be distributed?
17. Data Center
A cloud provider must assign 10 distinct servers across 3 data centers with capacities of exactly 5, 3, and 2 racks respectively. Every server must be assigned.
How many ways can the servers be distributed?
18. Poker Hands
Five cards are dealt from a standard 52-card deck.
(a) What is the probability that all 5 cards are hearts?
(b) What is the probability of getting exactly one ace?
19. The Birthday Problem
In a room of 30 people, what is the probability that at least two share the same birthday? (Assume 365 equally likely birthdays, ignore leap years.)
Hint: Use the complement.
20. Quality Control
A batch of 50 chips contains 5 defective ones. An inspector randomly selects 8 chips for testing.
(a) What is the probability that none of the selected chips are defective?
(b) What is the probability that exactly 2 are defective?
21. Random Password
A system generates a random 4-character password where each character is independently chosen from {A–Z, 0–9} (36 symbols).
(a) How many total passwords are possible?
(b) What is the probability that a password has no repeated characters?
(c) What is the probability that a password contains at least one digit?