ISI2018-MMA-20

Question

Consider the set of all functions from $\{1, 2, . . . ,m\}$ to $\{1, 2, . . . , n\}$,where $n > m$. If a function is chosen from this set at random, the probability that it will be strictly increasing is

• A. $\binom{n}{m}/n^m\\$
• B. $\binom{n}{m}/m^n\\$
• C. $\binom{m+n-1}{m-1}/n^m\\$
• D. $\binom{m+n-1}{m}/m^n$

Answer 1

Total no. of functions is $n^m$. [For every value from ${1,2....,n}$ there are m possibilities].

We choose an m-element subset of n, number of such subsets $=\binom{n}{m}$

Since it is an increasing function, we can order the elements in only one way, i.e in ascending order.

Therefore , probability is $\frac{\binom{n}{m}}{n^m}$

Comments

@Arkaprava

Here condition is $n> m$

Suppose, $2$ questions,

$1)$ If there are $5$ children, and $2$ orange want to divide among them, possible?No.

$2)$ If there are $3$ children and $5$ orange, and each children gets $2$ orange possible?No.

So, how non-decreasing with repetitive order possible everytime?

---

n>m, but we are selecting m items from n types of items. Sort the elements in order, then you'll get your sequence.

---

I havenot got. Plz solve those two questions:(

Answer 2

Surjective function (ONTO)

SO , nCm/ n^m