COMP2121 Chap.5 Counting Principles, Permutations and Combinations
Counting Principles, Permutations and Combinations
Two rules and their consequences
Multiply counts for choices made in sequence and add them for alternatives that cannot both happen. Permutations count ordered arrangements, arrangements of a multiset divide out the orders of identical objects, and combinations count subsets.
Pascal's identity follows by deciding whether one fixed object is chosen.
Distributions and the pigeonhole principle
Sharing identical objects among distinct people is counted with stars and bars, which also counts non-negative integer solutions of a sum.
The pigeonhole principle and its general form guarantee that some box holds at least the ceiling of N over k objects.
Where counting answers lose marks
The most common error is an overcount caused by treating identical objects or unordered groups as distinct. A useful check is to compute the answer two ways, for instance by choosing positions first and then filling them, or by counting a complement.
Another frequent slip is mixing the sum rule and the product rule: alternatives that cannot both happen add, while stages that happen in sequence multiply.
Every counting answer should state the reason beside the formula.
Combinatorial identities by counting
Pascal's identity, n choose k equals n minus 1 choose k minus 1 plus n minus 1 choose k, follows from asking whether one fixed element belongs to the chosen subset. The symmetry n choose k equals n choose n minus k follows from matching each subset with its complement.
Proving identities by counting the same set in two ways is shorter than algebra and is the style the lecture notes use, so it is worth practising both directions of each argument.
What this chapter covers
- 01
Product and sum rules
- 02
Permutations
- 03
Arrangements with identical objects
- 04
Combinations and Pascal's identity
- 05
Stars and bars
- 06
Pigeonhole principle
Worked example · free
Share identical tokens with stars and bars
- 2Encode a distribution as a row of tokens and bars.
- 2Count the positions of the bars.
- 2Shift the lower bounds for the second count.
Key terms
- Permutation
- An ordered arrangement of distinct objects.
- Combination
- An unordered selection of objects, counted by the binomial coefficient.
- Pigeonhole principle
- The rule that k plus 1 objects in k boxes put two objects in one box.
Counting Principles, Permutations and Combinations FAQ
When do I divide by a factorial?
Divide when your count treats as different some arrangements that are really the same, such as orders within a chosen group or swaps of identical objects. The factorial is the number of such duplicate orders.
What does stars and bars count?
It counts ways to share r identical objects among n distinct recipients, equivalently the non-negative integer solutions of a sum of n variables equal to r. The answer is n plus r minus 1 choose r.
How do I choose the pigeonholes?
Pick boxes so that two objects in one box gives the conclusion you need, such as equal remainders, nearby points or equal handshake counts. A good choice makes the proof one line long.
How do I count arrangements with identical letters?
Divide the factorial of the total length by the factorial of each letter's repetition count. For a word with two equal letters among six, the count is six factorial divided by two, because swapping the identical letters gives the same string.
What is the generalised pigeonhole principle?
Putting N objects into k boxes forces some box to contain at least the ceiling of N divided by k objects. With 25 objects in 6 boxes, some box holds at least 5. The argument is the same as the basic version: if every box held fewer, the total would be too small.
Exam move
For each counting problem, write two answers before any formula: whether order matters and whether objects repeat. Test every formula on a case small enough to list. Practise lower-bound shifts in stars and bars, and for pigeonhole proofs write down the boxes explicitly before counting objects. Whenever an answer looks too large, look for a pair of arrangements your method counted twice, and divide or redefine the stages.
Mix permutation, combination and distribution problems in one sitting so that choosing the model becomes the skill you practise.
Working through Counting Principles, Permutations and Combinations in COMP2121? Sia is AskSia’s AI Computer Science tutor — ask any COMP2121 Counting Principles, Permutations and Combinations question and get a clear, step-by-step explanation grounded in how COMP2121 is taught and assessed. Read this chapter free, then take your hardest questions to Sia.