Let D = {0, 1, ..., 9} be the set of n = 10 elements. If we have a sequence of k = 3 digits that are strictly increasing or decreasing, then all those digits must be distinct. Given any subset of D there is only one way to order them such that they are in increasing or decreasing order. Thus, the number of such sequences will be the unique number of ways we can choose k digits from n elements.
(a) (n choose k) = (10 choose 3) = 10! / (7! 3!) = 10 * 9 * 8 / 1 * 2 * 3 = 10 * 3 * 4 = 120
(b) Also (10 choose 3) = 120. [As an aside, these binomial coefficients are written with the numbers stacked on top of each other inside the parentheses. But I can't figure out how to format it that way here.]
Now let D_m be the multiset of D. That means we are allowed to choose the same element from it multiple times. Given any subset of D_m there is only one way to order them such that they are in non-increasing or non-decreasing order. (Remember, digits that are equal form an equivalent string.) Thus, the number of such sequences will be the unique number of ways we can multichoose k digits from n elements.
But there is a simple formula relating that to the standard binomial coefficients
((n multichoose k)) = (n + k -1 choose k)
(c) ((10 multichoose 3)) = (10 + 3 -1 choose 3) = (12 choose 3) = 12! / (9! 3!) = 12 * 11 * 10 / 1 * 2 * 3 = 2 * 110 = 220
Note that this question asked for sequences so the calculations were straightforward and all choices were valid. Sometimes we get questions like this where they ask about *numbers* and we have to discount some choices because the sequence isn't a valid way to write an integer, e.g. 000. So always take care that you are counting specifically what is asked for.
Feel free to contact me for tutoring if you'd like more help with discrete math. Cheers.
