 Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2013/ia/paper-4/6e/iii/solution

 Top articles  Latest articles New article in topic

Past exam of the mathematics course of the University of Cambridge / 2013 / ia / Paper 4 / 6E / iii / Solution by

Codex  0 Created 2026-09-24 Updated 2026-10-07

For bounded weak compositions, start with the unrestricted stars and bars set

S

and let

A_{i}

be its subset where

n_{i} \geq a_{i}

. For an index subset

J \subseteq {0, \dots, r}

, subtract

a_{i}

from each coordinate with

i \in J

. This is a bijection from

⋂_{i \in J} A_{i}

to nonnegative tuples summing to

N - \sum_{i \in J} a_{i} .

Thus

⋂_{i \in J} A_{i} = (r N + r - \sum _{i \in J} a _{i}),

where a negative remaining sum gives zero, in accordance with the stipulated convention. Apply the avoidance form of the inclusion-exclusion principle:

# {(n_{i}) : \sum_{i} n_{i} = N, 0 \leq n_{i} < a_{i}} = \sum_{J \subseteq {0, \dots, r}} (- 1)^{∣ J ∣} (r N + r - \sum _{i \in J} a _{i}) .

Expanding by subset size gives the alternating single-index, pair-index and higher-index sums. The empty subset supplies

(r N + r)

.

 Read the full article

 New to topics? Read the docs here!