2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Bettybel Jul 12 '17 at 13:11
  • $\begingroup$ You say you're pretty sure your intuition is wrong. Why do you say this? $\endgroup$ – abiessu Jul 12 '17 at 13:11
  • $\begingroup$ Are you sure that "increasing" does not mean "strictly increasing" here? $\endgroup$ – Did Jul 12 '17 at 13:12
  • $\begingroup$ 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$. $\endgroup$ – G Tony Jacobs Jul 12 '17 at 13:55
10
$\begingroup$

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,$$

$\endgroup$
9
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ really slick! :) $\endgroup$ – muzzlator Jul 12 '17 at 14:02
3
$\begingroup$

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*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.