Consider a function $f:\{{1,2,3,\cdots,13}\}$$\rightarrow$ $\{{1,2,3,\cdots,9}\}$ Given that function is surjective and non–decreasing, the probability that $f(7)=4$ is?
My solution:
Let $x_k$ denotes number of times $k$ appears in range. where $1\leq k \leq 9$
Then number of non decreasing and onto function $f:\{{1,2,3,\cdots,13}\}$$\rightarrow$ $\{{1,2,,3,\cdots,9}\}$ is equal to number of positive integral solution of equation $x_1+x_2+x_3+\cdots+x_9=13$ i.e., ${13-1\choose 9-1}= {12 \choose 8}$.
Total Function: ${12\choose4}$
Number of function satisfying above property is i.e., $f(7)=4$
is number of positive integral solution of $x_1+x_2+x_3+x_4=7$ and $x_4+x_5+x_6+x_7+x_8+x_9=6$ that is ${6 \choose 3}\times{6\choose 5}$.
Note:$x_4 \geq 0$ in $x_4+x_5+x_6+x_7+x_8+x_9=6$ and rest all $x_i \geq 1$
I've obtained the correct result i.e., $\frac{{6\choose 3}\cdot {6\choose1}}{{12\choose 4}}$as given in answer key.
I've edited the solution as commented by @mathlover.
Also is there any other approach for this problem.
Best Answer
Let $a_i$ is minimal $x$ such that $f(x)=i$. Then $a_1=1$, $a_{i+1}>a_i$, $a_9\leq 13$. There is $\binom{12}{8}$ ways to choose $a_2$, ..., $a_9$, so there are $\binom{12}{8}$ functions $f$. We believe that all these functions are equally probable, otherwise we need additional information to solve the problem.
If $f$ is such that $f(7)=4$ then $a_4\leq 7$ and $a_5 \geq 8$. Then there are $\binom{6}{3}$ ways to choose $a_2$, $a_3$, $a_4$ and there are $\binom{6}{5}$ ways to choose $a_5$, ... , $a_9$. Total numbers of functions $f$ satisfying $f(7)=4$ is $\binom{6}{3}\cdot \binom{6}{5}$.
The probability is $\frac{\binom{6}{3}\cdot \binom{6}{5}}{\binom{12}{8}}$.