Number of monotonically increasing functions from the set $\{1,2,3,4,5,6\}$ to itself with the property that $f(x)\ge x$ While working on P&C problems, I stumbled upon this problem.
The number of monotonically increasing functions from the set $\{1,2,3,4,5,6\}$ to itself with the property that $f(x)\ge x$  for all x, is equal to $\frac{2}{k}.C^{11}_5$, where k equals...?
Using dummy variables I could figure out number of non-decreasing functions as $C^{11}_6$, but it doesn't take into consideration the condition $f(x) \ge x.$ How to proceed further?
 A: Imagine a "tree" of possibilities. At the top, there is all the possibilities for $f(6)$ (which is just $6$). There are branches coming from that one option for $f(6)$, going down to all the options for $f(5)$, etc.
Below is the tree if we replaced $3$ with $6$.

Now, define $g(n,k)$ to be the number of possibilities when $f(k+1)=n$. For example, in the above tree, $g(2,1)=2$, since the possibilities from $f(2)=2$ are $1,2$. Also, $g(3,2)=5$.
Now, we want to find $g(6,5)$. But:
$$g(6,5)=g(5,4)+g(6,4)$$
$$=2g(4,3)+2g(5,3)+g(6,3)$$
$$=5g(3,2)+5g(4,2)+3g(5,2)+g(6,2)$$
$$=14g(2,1)+14g(3,1)+9g(4,1)+4g(5,1)+g(6,1)$$
$$=42g(1,0)+42g(2,0)+28g(3,0)+14g(4,0)+5g(5,0)+g(6,0)$$
By definition, $g(n,0)=1\forall n$, hence $g(6,5)=132$. So $k=7$ in your question

Now, that was interesting and all, but it required a lot of casework. Also, doing smaller cases, you get the Catalan numbers every time! What's going on?  I'm leaving this as an exercise for you to figure out, I'll just leave you with two hints:

*

*Look at the "bash" that I had above. Note that $1,2,5,14,42,132$ are all Catalan numbers


*Examine the recursive definition(s) of Catalan numbers.
