Past exam of the mathematics course of the University of Cambridge / 2013 / ia / Paper 4 / 6E (Numbers and Sets)

Use a stars and bars bijection. For a tuple, place $N$ stars in $r+1$ consecutive blocks of lengths $n_0,\dots ,n_r$, separated by $r$ bars. The bar positions form an $r$-element subset of $\{1,\dots ,N+r\}$. Explicitly,They satisfy $1\le b_1<\cdots <b_r\le N+r$. Conversely, such a subset determinesThese numbers are nonnegative and sum to $N$, proving that the two constructions are inverse. HenceZero-length blocks are permitted, so the bijection also covers $N=0$.

For finitely many finite sets $A_1,\dots ,A_k$, the inclusion-exclusion principle statesTo see why, an element belonging to exactly $t\ge 1$ of the sets contributesby the binomial theorem. Elements outside the union contribute zero. Equivalently, if these sets lie in a finite universe $U$, the number avoiding all of them is

For bounded weak compositions, start with the unrestricted stars and bars set $S$ and let $A_i$ be its subset where $n_i\ge 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 ${\bigcap }_{i\in J}{A}_i$ to nonnegative tuples summing toThuswhere a negative remaining sum gives zero, in accordance with the stipulated convention. Apply the avoidance form of the inclusion-exclusion principle:Expanding by subset size gives the alternating single-index, pair-index and higher-index sums. The empty subset supplies $\left(\genfrac{}{}{0ex}{}{N+r}{r}\right)$.