# How do I count the number of increasing functions from $\{1, 2, 7\}$ to $\{1, 2, 3, 4, 5, 6, 7, 8\}$?

I can't seem to figure it out, one way I thought about it is:

Let's take $f(1) = 1$:

• $f(2) = 1$ (because it's not strictly increasing) so for $f(7)$ I have $8$ possibilities
• $f(2) = 2$ so $f(7)$ now has $7$ possibilities
• $f(2) = 3$ so $f(7)$ now has $6$ possibilities
.
.
and so on.

So for $f(1) = 1$ we have $8+7+6+5+...+1$ functions (this can be expressed as the formula $\frac{(n+1)n}{2}$)

So for $f(1) = 2$:

• $f(2) = 2$ results in $7$ possibilities of $f(7)$
.
.
and so on and it result in $7+6+5+..+1$

so by my reasoning I would say that the number of increasing functions is equal to: $S_8 + S_7 + S_6 + ... + S_1$ (where $S_n = \frac{(n+1)n}{2}$ )

But I'm pretty sure that's not right but I don't know how to think about it.

• Consider the derivative instead. $g(n)=f(x_{n+1})-f(x_{n})$, where $x_1=1, x_2=2, x_3=7$. Find how many solutions does this inequality has $g(1)+g(2)\leq 8$. Turn the inequality into an equality $g(1)+g(2)+Y=8$ with $g(1),g(2),y\geq 0$. – Bettybel Jul 12 '17 at 13:11
• You say you're pretty sure your intuition is wrong. Why do you say this? – abiessu Jul 12 '17 at 13:11
• Are you sure that "increasing" does not mean "strictly increasing" here? – Did Jul 12 '17 at 13:12
• Your reasoning for counting the number of non-decreasing functions seems spot-on. If that answer (120) is not correct, then you must be looking for strictly increasing functions, of which there are $\binom83$. – G Tony Jacobs Jul 12 '17 at 13:55

First, to count the number of strictly increasing functions, note that any combination of $3$ numbers from the set $\{1,2,\ldots, 8\}$ gives such a function and all such functions correspond to a combination. So there are $8 \choose 3$ strictly increasing functions.

Second, count the number of functions $f(x)$ where two numbers go to the same image and one is different. Either $f(1)=f(2) \neq f(7)$ or $f(1)\neq f(2) =f(7)$. These two cases are identical, so we count the first one and multiply by $2$. By the same reasoning above, there are $2{8 \choose 2}$ of these functions.

Third, count the number of functions with $f(1)=f(2)=f(3)$. There are $8$ of these.

Final tally: $${8 \choose 3} +2 {8 \choose 2} +8 = 120,$$

The function $g$ given by $g(1)=f(1)$, $g(2)=f(2)+1$, $g(7)=f(7)+2$ is a strictly increasing map to $\{1,2,\ldots,10\}$ for every increasing $f$ and vice versa. The number of such $g$ is simly the number of ways to pick three distinct elements of a ten-element set, so $10\choose 3$.

• really slick! :) – muzzlator Jul 12 '17 at 14:02

A small variation of the theme. Note, that in order to determine the number of increasing functions the elements of the domain $\{1,2,7\}$ are not relevant. Just the number of elements $|\{1,2,7\}|=3$ of the domain is essential.

We can reformulate the problem: Find the number of triples $(x_1,x_2,x_3)$ of positive integers with \begin{align*} 1\leq x_1\leq x_2\leq x_3\leq 8\tag{1} \end{align*}

This can be solved using stars and bars, here with $n=3$ and $k=8$ giving \begin{align*} \binom{n+k-1}{n}=\binom{10}{3}=120 \end{align*}