how many monotonic function f:[1...k]→[1...n]f:[1...k]→[1...n], are they, such that...

Question

I had this question in my h.w, and i don't have a clue how to solve it. The question is:

For $k \leq n$:

1. How many non increasing monotonic functions $f:[1, \dots, k]\to[1, \dots, n]$ that satisfy ($i<j\implies f(i)\geq f(j)$) are there and $f(1)=n$ and $f(k)=1$?

2. How many decreasing monotonic functions $f:[1, \dots, k]\to[1, \dots, n]$ that satisfy ($i<j\implies f(i)>f(j)$) are there ?

Answer 1

You just have to select the difference between consecutive elements. There are $k-1$ such differences. They must add up to $n-1$.

For the first example $0$ is a valid difference, so we just have to count the number of solutions to $a_1+a_2+\dots +a_{k-1}=n-1$. This is a standard stars and bars problem. There are $n-1$ stars and $k-2$ bars, so the answer is $\binom{n+k-3}{n-1}$.

For the second example is is $\binom{n}{k}$ as it suffices to select the terms that appear in the sequence. ( as was noted by WICK3D POISON in the comments)

Answer 2

Hint:

Instead of thinking of the values for each input, think of the CHANGE from one point to the next.

Because you want $f(1)=n$ and $f(k)=1$, there must be a total of $n-1$ such decreases that occur. So, the problem basically becomes figuring out where to put those decreases, and how many to put at each location.

Those decreases can occur in any one of $k-1$ bins (namely $f(2),f(3),\ldots,f(k)$).

This is starting to sound a lot like a problem of distributing identical balls between labeled boxes.

Answer 3

For decreasing case: $$^nC_k$$ Just choose $k$ from $n$ elements and arrange them in decreasing order.

For non-increasing case: $$^{n+(k-2)-1}C_{k-2}$$ Since $f(1)=n$ and $f(k)=1$, we can choose $k-2$ elements with repetition from $n$ and arrange them in non-increasing order.