Find $F(n,k)$ number of monotonic sequences in length $k$ from $n$ elements $\{1,2,3,..,n\}$

Question

I have the following question :

Find $F(n,k)$ number of monotonic sequences in length $k$ from $n$ elements $\{1,2,3,..,n\}$

for example $n=6,k=5$ the sequence $1,2,2,3,5$ is monotonic and the sequence $1,2,2,3,2$ is not monotonic.

I did the following :

I looked at $k$ element in the sequences there are three possiblilies :

• The same element as the $k-1$ element in the sequences hences, $F(n,k-1)$

• Doesn't add the next number after $k-1$ element $F(n-1,k)$

• Add the next number after $k-1$ element $F(n-1,k-1)$

Therefore,

$$F(n,k)=F(n,k-1)+F(n-1,k)+F(n-1,k-1)$$

The answer I seen in the answer is different than mine, I think that my answer is true too,

I'll be glad if someone could tell me.

Thank You.

Answer 1

The correct recurrence is $F(n, k) = F(n, k-1) + F(n-1, k)$.

$F(n, k-1)$ handles the case where we add $n$ to the solution so far. $F(n-1, k)$ handles the case where we choose to skip $n$.

You also have the $F(n-1, k-1)$ case in your recurrence, but this is incorrect. You are now overcounting, because this is the same as first adding $n$ and then skipping $n$.

Answer 2

Well, you just choose $k$ numbers among the $n$ numbers $\,\{1,\dots,n\}$, and if $k>1$, you order them in one of the two natural orders, so that $$ F(n,k) = \begin{cases} n &\text{if }\,k=1,\\[1ex] 2\dbinom{n}{k} &\text{if }\,k>1. \end{cases}$$