22
$\begingroup$

I stumbled upon a question given like:

Let $m$ and $n$ be two integers such that $m \geq n \geq 1$.

Count the number of functions $$f: \{1, 2, · · · , n\} \to \{1, 2, · · · , m\}$$ of the following two types:

(a) strictly increasing; i.e., whenever $x < y, f(x) < f(y)$, and

(b) non-decreasing; i.e., whenever $x < y, f(x) \leq f(y)$.

I tried in the following way.

For (a). We can say $f(n)>f(n-1)$ AND $f(n)>f(n-2) \ldots f(n)>f(1)$ (total $n-1$ elements)

Similarly for $f(n-1)>f(n-2), f(n-1)>f(n-3) \ldots f(n-1)>f(1)$ (total $n-2$ elements)...

and $f(2)>1$

Like this $$(n-1) + (n-2) + \ldots + (1) = \frac{n(n-1)}{2}$$

Is this correct?

For (b). Since there's equality, it will be $$n + (n-1) + ... (1) = \frac{n(n+1)}{2}$$

Is my approach correct? Any help is appreciated. Thanks in advance.

$\endgroup$
20
  • 1
    $\begingroup$ Ahh. That would usually be written either $f(1)=2$ or $1\mapsto 2$. When you mean that $2$ is output, you would never write $f(2)$. The place inside the parentheses is always an input and never an output. But still, in the first case, $f$ cannot map $1$ to $m$, because what would $f(2)$ be then? $\endgroup$
    – Arthur
    Apr 13, 2017 at 7:56
  • 1
    $\begingroup$ It means that the output of $f$ when given $x$ is strictly less than the output of $f$ when given $y$. $\endgroup$
    – Arthur
    Apr 13, 2017 at 7:59
  • 1
    $\begingroup$ $f$ being a strictly increasing function means exactly that its output when given $1$ (generically called $f(1)$) is strictly smaller than $f(2)$, its output when given $2$, which again is strictly smaller than $f(3)$, and so on. That means we cannot have $f(1)=5$ and $f(2)=3$ at the same time. $\endgroup$
    – Arthur
    Apr 13, 2017 at 8:12
  • 1
    $\begingroup$ Oh, right, I think I know what you've misunderstood now: a function being increasing does not mean that the output is greater than the input. It means that increasing the input necessarily increases the output. $\endgroup$
    – Arthur
    Apr 13, 2017 at 8:22
  • 1
    $\begingroup$ Yes, that is correct. At the same time, $f(n-1)>f(n-2)$ and $f(n-1)>f(n-3)$... $f(n-1)>f(1)$, all the way down to $f(2)>f(1)$. $\endgroup$
    – Arthur
    Apr 13, 2017 at 8:27

3 Answers 3

68
$\begingroup$

How many strictly increasing functions $f:\{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$ are there?

A function $$f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$$ is determined by how the values $$f(1), f(2), f(3), \ldots, f(n)$$ are assigned. Since $f$ is a strictly increasing function, $$f(1) < f(2) < f(3) < \ldots < 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 $\binom{m}{n}$. 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 $$\binom{m}{n}$$

How many nondecreasing functions $f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$ are there?

Since $f$ is a nondecreasing function, the function is completely determined by how many values of $j \in \{1, 2, 3, \ldots, n\}$ are assigned to equal $k \in \{1, 2, 3, \ldots, m\}$. To see why, consider functions $$f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6, 7\}$$ If two values are assigned to equal $3$, one value is assigned to equal $4$, and two values are assigned to equal $7$, then since $f$ is nondecreasing, $f$ must be the function defined by $f(1) = f(2) = 3$, $f(3) = 4$, $f(4) = f(5) = 7$.

Let $x_k$, $1 \leq k \leq m$, be the number of values of $j \in \{1, 2, 3, \ldots, n\}$ such that $f(j) = k$. Then $$x_1 + x_2 + x_3 + \ldots + x_m = n$$ which is an equation in the nonnegative integers. A particular solution corresponds to the placement of $m - 1$ addition signs in a row of $n$ ones.

To make this concrete, consider nondecreasing functions $$f: \{1, 2, 3, 4, 5\} \to \{1, 2, 3, 4, 5, 6, 7\}$$ Then we have $$x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 = 5$$ The assignment $$+ + 1 1 + 1 + + + 1 1$$ corresponds to the above example that $x_1 = x_2 = 0$, $x_3 = 2$, $x_4 = 1$, $x_5 = x_6 = 0$, and $x_7 = 2$, that is, the function defined by $f(1) = f(2) = 3$, $f(3) = 4$, $f(4) = f(5) = 7$. In this case, the number of such functions is the number of ways we can insert six addition signs in a row of five ones, which is $$\binom{5 + 6}{6} = \binom{11}{6}$$ since we must choose which six of the eleven symbols (five ones and six addition signs) will be addition signs.

By similar reasoning, the number of nondecreasing functions $$f: \{1, 2, 3, \ldots, n\} \to \{1, 2, 3, \ldots, m\}$$ is equal to the number of ways we can insert $m - 1$ addition signs in a row of $n$ ones, which is $$\binom{n + m - 1}{m - 1}$$ since we must select which $m - 1$ of the $n + m - 1$ symbols ($n$ ones and $m - 1$ addition signs) must be addition signs.

$\endgroup$
3
  • 4
    $\begingroup$ Excellent Explaination !! $\endgroup$ Jul 27, 2017 at 2:45
  • 3
    $\begingroup$ Supreme.Well done $\endgroup$ Dec 8, 2019 at 8:20
  • 1
    $\begingroup$ A note for readers: the counting technique used here for nondecreasing functions is called stars and bars. $\endgroup$ Jan 11, 2022 at 18:06
2
$\begingroup$

A different approach for the non-decreasing case.

Set $F(n,m) = |\{ f : \{1, \ldots, n\} \to \{1,\ldots,m\} \mid f \mbox{ is non-decreasing. } \}|$. Then, $F(n,1) = 1$. Furthermore, we have the following recurrence relation: $$ F(n,m) = \sum_{i=0}^n F(n - i, m - 1). \quad (*) $$ Proof. If $f : \{1,\ldots,n\} \to \{1,\ldots,m\}$ is non-decreasing, set $k = |f^{-1}(1)|$. Then, $f^{-1}(1) = \{1,\ldots, k \}$ (possibly empty) and $f$ restricted to $\{ k + 1, \ldots, n \}$ (also possibly empty) could be seen as a non-decreasing function from $\{k+1,\ldots,n\}$ to $\{2,\ldots,m-1\}$. For the restriction, we have $F(n - k, m - 1)$ many possibilities (the concrete naming of the numbers does not matter, just that they form a consecutive order) and each possibility is determined uniquely. Conversely, from any non-decreasing function $g : \{1,\ldots,n\}\to \{1,\ldots,m\}$ and $0 \le k \le n$ we can uniquely construct a non-decreasing function $f : \{1,\ldots,n+k\} \to \{1,\ldots, m+1\}$ by setting $$ f(x) = \left\{ \begin{array}{ll} 1 & 1 \le x \le k \\ g(x) + 1 & \mbox{otherwise.} \end{array} \right. $$ So, we have shown the recurrence equation. QED

Now, for the binomial coefficient, the following formula is valid: $$ \binom{m}{m} + \binom{m + 1}{m} + \binom{m + 2}{m} + \ldots + \binom{m + n}{m} = \binom{n + m + 1}{m+1}, $$ which is easy to prove by induction. Setting $$ G(n,m) = \binom{n + m - 1}{m-1}, $$ we see that $G$ fulfills Equation (*) above, and $G(n,1) = 1$. Hence, inductively, $F(n,m) = G(n,m)$.

A concrete example. Let $a < b < c$, then, non-decreaasing functions with codomain of size three could be interpreted as ordered strings over $\{a,b,c\}$. Then, for the domain of size three, we have the strings $$ aaa, aab, aac, abb, abc, acc, bbb, bbc, bcc, ccc. $$ I hope it could be seen how to construct these strings out of the ordered strings over $\{b,c\}$ of length at most three by appending runs of $a$'s in front of them.

$\endgroup$
0
$\begingroup$

Problem with your approach is that function cannot map one number to multiple different numbers. On the other hand you can map multiple different numbers to one number.

$\endgroup$
2
  • $\begingroup$ Example of one function in a) case: f(1) = 2, f(2) = 3,..., f(n) = n + 1 (because m is bigger than n). Continue in that manner. Similar in b). $\endgroup$
    – omas13
    Apr 13, 2017 at 8:15
  • $\begingroup$ The question has been edited since you posted your answer. $\endgroup$ Apr 13, 2017 at 9:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .