The University of Hong Kong · FACULTY OF COMPUTER SCIENCE

COMP2121 Chap.5 Counting Principles, Permutations and Combinations

- one subject, every graph, every model, every mark
6 Chapters4-page Bible
Our own words - no uploaded lecturer files
Updated for this semester
Chapter 5 of 11 · COMP2121

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.

In this chapter

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

Q [6 marks]. This practice weighting was set for revision and is not an official University marking scheme. In how many ways can 7 identical tokens be placed in 3 labelled boxes, and in how many if every box gets at least one?
One row of tokens and bars encodes one way to share identical objects.One row of tokens and bars encodes one way to share identical objects. Seven tokens and two bars fill nine positions; the bars cut the row into three boxes holding two, none and five, so choosing where the two bars go counts every distribution.box 1 gets 2box 2 gets 0box 3 gets 57 tokens and 2 bars in 9 positions
One row of tokens and bars encodes one way to share identical objects. Seven tokens and two bars fill nine positions; the bars cut the row into three boxes holding two, none and five, so choosing where the two bars go counts every distribution.
  • 2Encode a distribution as a row of tokens and bars.
  • 2Count the positions of the bars.
  • 2Shift the lower bounds for the second count.
A distribution is a row of 7 tokens and 2 bars, so there are 9 choose 2, which is 36, ways. If every box gets at least one, first give each box a token; the remaining 4 tokens are shared freely, giving 6 choose 2, which is 15, ways.
Sia tip — Decide whether order matters and whether repeats are allowed before choosing a formula.
Glossary

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.
FAQ

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.

Study strategy

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.

A+Everything unlocked
Unlocks this Bible + all 52 of your subjects at The University of Hong Kong, plus 1,000+ more Bibles across the AskSia library.
Sia - your COMP2121 tutor, unlimited, worked the way the exam marks it
The full 4-page Bible + practice bank with worked solutions
Chrome extension - sync your LMS so Sia knows your deadlines
Bilingual EN / Chinese on every Bible and every Sia answer
$0.99 Trial
30-day money-back · cancel in one tap · how it works