Maths Olympiad Prep

Library / /288 of 462

Combinatorics Difficulty 6.1 National Olympiad Prove it Ireland

A sequence of throws of a die is called nondecreasing if the result of each successive throw is at least as large as the previous one in the sequence. For instance, one example of a nondecreasing sequence of 10 throws is
1,2,2,2,2,4,4,4,4,4,51, 2, 2, 2, 2, 4, 4, 4, 4, 4, 5.
Compute the total number of nondecreasing sequences of 10 throws.

Solution

Let SnS_n be the set of all (finite) sequences of length nn, with all entries being whole numbers between 11 and 66. Similarly, let BnB_n be the set of all (finite) sequences of length nn, with all entries being either 00 or 11. We denote elements of SnS_n or BnB_n by a letter such as xx, and a subscripted xix_i denotes the iith entry in xx.
Let BB be the subset of B5B_5 that have exactly five entries equal to 11, so the cardinality of BB is (155)\binom{15}{5}. We now set up a bijection from BB to the set SS of nondecreasing sequences in S10S_{10}. We first set up a map ff from BB to S10S_{10}: y=f(x)y = f(x) is such that y1=1y_1 = 1 and yi+1yi=xiy_{i+1} - y_i = x_i for 1i151 \le i \le 15. This defines ff uniquely. ff is clearly injective since yy preserves the information about which entries in xx equal 11. It is also clear that yy is nondecreasing.
Now, delete y1y_1 and also delete yiy_i if xi=1x_i = 1. We are left with a nondecreasing sequence z=g(y)z = g(y) of length 1010, and so gg is a map from f(B)f(B) to S10S_{10}. A little thought shows that we can reconstruct yy from zz, and so gg is injective. We deduce that h:=gfh := g \circ f is injective. zz is nondecreasing because yy is nondecreasing, and it is now straightforward to deduce that h(B)=Sh(B) = S. We have constructed a bijection hh from BB to SS, and so the cardinality of SS is (1510)\binom{15}{10}.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.