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
.
Compute the total number of nondecreasing sequences of 10 throws.
Solution
Let be the set of all (finite) sequences of length , with all entries being whole numbers between and . Similarly, let be the set of all (finite) sequences of length , with all entries being either or . We denote elements of or by a letter such as , and a subscripted denotes the th entry in .
Let be the subset of that have exactly five entries equal to , so the cardinality of is . We now set up a bijection from to the set of nondecreasing sequences in . We first set up a map from to : is such that and for . This defines uniquely. is clearly injective since preserves the information about which entries in equal . It is also clear that is nondecreasing.
Now, delete and also delete if . We are left with a nondecreasing sequence of length , and so is a map from to . A little thought shows that we can reconstruct from , and so is injective. We deduce that is injective. is nondecreasing because is nondecreasing, and it is now straightforward to deduce that . We have constructed a bijection from to , and so the cardinality of is .