Let $A = \{a_1,a_2,...,a_{100}\}$ and $B= \{1,2,...,50\}$. Determine the number of surjective functions f from A to B such that $f(a_1)≤f(a_2)≤...≤f(a_{100})$. What if $f$ does not need to be surjective?
My approach:
Number of Surjective functions: First $f(a_1)=1$ (otherwise f is not surjective). Of $a_2,..., a_{100}$, choose any $49$. Order them based on increasing order of index and assign values $2$ to $50$ to the $a_i$'s based on their order.
For example if I chose $a_2, a_5, a_{10},..a_{96}$ (some $49$ elements from $A$) then,- $f(a_2)$ is the first element that equals 2 (first based on ordering)
- $f(a_5)$ is the first element that equals 3...
- $f(a_{96})$ is the first element that equals 50
- The remaining 50 elements are fixed. Answer: $_{99}C_{49}$.
The problem can be recast as the block walking problem so the answer is $_{149}C_{49}$.
Let $k_i= |f^{-1}(i)|$, then since $f$ is surjective we have $k_i\geq 1$.
So we are interested in number of solutions of the equation $$k_1+k_2+...+k_{50}= 100\;\;\; (*)$$ Put $n_i= k_i-1\geq 0$ and count the solution of $$n_1+n_2+...+n_{50}= 50$$
This we usualy do with stars and bars and a solution is $${99\choose 50}$$
If $f$ is not surjective then some $k_i$ can be $0$ and we simply solve $(*)$, so we $${149\choose 50}$$ such functions.
So, I can not disagree with your solutions.