Question

2. Consider functions f : {1, 2, 3, 4, 5, 6} → {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

(a) How many of these functions are strictly increasing (i.e. f(1) < f(2) < f(3) < f(4) < f(5) < f(6))? Hint: How many different possibilities are there for the range of f? For each range of f, how many strictly increasing functions are there?

(b) How many of these functions are non-decreasing (i.e. f(1) ≤ f(2) ≤ f(3) ≤ f(4) ≤ f(5) ≤ f(6))? Hint: What are the yards? What are the trees? Or, if you prefer, what are the stars and what are the bars?

Answer 1

2. (a) How many strictly increasing functions f:{1,2,3,…,n}→{1,2,3,…,m} are there?

A function f:{1,2,3,…,n}→{1,2,3,…,m} is determined by how the values f(1),f(2),f(3),…,f(n) are assigned. Since f is a strictly increasing function, f(1)<f(2)<f(3)<…<f(n)

Thus, for a strictly increasing function, each value in the domain is mapped to a distinct element in the codomain. Since there are n elements in the domain and m elements in the codomain, the number of ways we can select the elements in the range is . Once we have selected these elements, there is only one way to assign them so that the function is strictly increasing, namely by assigning the smallest element in the range to be f(1), the next smallest to be f(2), and so forth. Hence, the number of strictly increasing functions is .

(b). How many nondecreasing functions f:{1,2,3,…,n}→{1,2,3,…,m} are there?

Since f is a nondecreasing function, the function is completely determined by how many values of j∈{1,2,3,…,n} are assigned to equal k∈{1,2,3,…,m}.

By similar reasoning, the number of nondecreasing functions f:{1,2,3,…,n}→{1,2,3,…,m} is equal to the number of ways we can insert m−1 addition signs in a row of n ones, which is

since we must select which m−1 of the n+m−1 symbols (n ones and m−1 addition signs) must be addition signs.

​​Thus Answer is

(a)  ​​​​​= 210

(b) 5005