Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Discrete mathematics, continuous mathematics, and probability (resit) / 2 / a

Let $x_i$ be the number of objects in box $i$. The arrangements correspond exactly to nonnegative integer solutions of $x_1+\cdots +x_k=n$. By stars and bars, place $n$ stars and $k-1$ separating bars in a row. The number of stars between consecutive bars records the occupancy of each distinguishable box, with adjacent bars allowing an empty box. Choosing the bar positions gives

Put one object into each box first. The remaining $n-k$ objects can be distributed without restrictions, so stars and bars givesEquivalently, the substitution $u_i=x_i-1$ gives a bijection between positive integer solutions of ${\sum }_i{x}_i=n$ and nonnegative integer solutions of ${\sum }_i{u}_i=n-k$.