Αn exercise in combinations.

Question

Let it be $m,n\in\mathbb{N}^\ast$.Find the displaying numbers of $f$:$[m]$ $\rightarrow$ $[n]$ when:

i)There are no restrictions

ii)Is $1-1$

iii)Is strictly increasing

iv)Ιs increasing

---

My thoughts on the first question are that if we have for example 2 sets, then we want to unite all the elements from [m] to [n].So every element in the domain have $n$ possible combinations.So if we multiply all together we will have $n^m$.Ιn the second question we must take a restriction.The cardinality of $[n]$ must be greater than or equal from $[m]$ otherwise we have error.Therefore applying the same logic we have $n(n-1)...(n-m+1)$ combinations.

Is my thinking correct? Can you help in the 3rd and 4th question because I can't understand their difference and their logic?

Answer 1

Your solutions of (i) and (ii) are correct.

For (iii), a strictly increasing function $f$ is completely determined once we know the set of values taken on by $f$, that is, the range of $f$. This range can be any $m$-element subset of $[n]$. There are no such functions if $n\lt m$. If $n\ge m$, there are $\binom{n}{m}$ ways to choose the range of $f$.

In Problem (iv), the author calls a function $f$ increasing if $f(x)\le f(y)$ whenever $x\lt y$. Such a function is sometimes called non-decreasing, or weakly increasing.

A weakly increasing function $f$ is completely determined once we know the multiset of values taken on by $f$. So we know $f$ once we know, for every $j\le n$, the number of $i\le m$ such that $f(i)=j$. Let this number be $x_j$.

Note that $x_1+x_2+\cdots +x_m=m$. We want to find the number of solutions of the equation $x_1+x_2+\cdots+x_m=m$. This problem is a standard Stars and Bars problem (please see the Wikipedia article). It turns out that there are $\binom{n+m-1}{m-1}$, or equivalently $\binom{n+m-1}{n}$ solutions.

Remark: For an interesting discussion of function-counting problems, please see the Wikipedia article The Twelvefold Way.