Please show all work Thank you How many increasing functions

Please show all work. Thank you.

How many increasing functions are there from {1, 2, 3, 4, 5) to (1, 2,...,9}? b) Explain how part (a) can be used to answer the question of how many ways one may select five donuts from a large supply of nine types.

Solution

(a)

To see how each such choice defines an increasing function, say that you choose the set {6,3,7,9,4}. If this is the range of an increasing function, then the smallest element in the set (namely 3) must be f(1), the next smallest must be f(2), and so on. Thus the function has to be specified by f(1)=3, f(2)=4, f(3)=6, f(4)=7, f(5)=9.

One way of counting the number of such functions is to think about the range of the function. Since f maps a set containing 5 elements into a set containing 9 elements, the range of f must consist of five of the numbers from 1 to 9. Suppose for example that the range of f consists of the numbers 3,5,6,7,9. Then in order to be an increasing function, f must map 1 to 3, 2 to 5, 3 to 6, 4 to 7 and 5 to 9. In other words, given the range of f, you can completely reconstruct the function f itself

(b)

You have 9 choices for the first donut. For the second donut, since you are allowed repeats, you have to \"add\" that choice back into the mix. This happens again with the third, fourth, and fifth choices, so you\'ve had to \"add\" back in 4 choices. So the actual number of choices is (9+4) choose 5 or 13 choose 5 which is 13!/8!5!. Since there are 5 choices, there are 5-1 times that you have to add something back in, whether it be a dividing line, or something (I called it another choice) that increases that starting number.