Get inspired by the success stories of our students in IIT JAM MS, ISI MStat, CMI MSc Data Science. Learn More

Content

[hide]

This is a beautiful problem from ISI MStat 2018 PSA problem 13 based on probability of functions. We provide sequential hints so that you can try .

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

- \( {n \choose m} / m^{n} \)
- \( {n \choose m} / n^{m} \)
- \( {{m+n-1} \choose m} / m^{n} \)
- \( {{m+n-1} \choose m-1} / n^{m} \)

combination

But try the problem first...

Answer: is \( {n \choose m} / n^{m} \)

Source

Suggested Reading

ISI MStat 2018 PSA Problem 13

A First Course in Probability by Sheldon Ross

First hint

What is the total number of functions from \({1,2, \ldots, m}\) to \({1,2, \ldots, n}\) where (n>m)

You have to choose \(m\) numbers among \({1,2, \ldots, n}\) and assign it to the \({1,2, \ldots, m}\)

For each element of \({1,2, \ldots, m}\), there are \(n\) options from \({1,2, \ldots, n}\).

Hence \(n^m \) number of functions .

Second Hint

\(f(i) = a_i \)

The number of ways to select Select \(m\) elements among \({1,2, \ldots, n}\) is the same as the number of strictly ascending subsequences of length m taken from 1, 2, 3, ..., n, which is the same as the number of subsets of size m taken from {1,2,3,…,n}, which is \( {n \choose m} \) .

Final Step

Hence the probability that it will be strictly increasing \( \frac{ {n \choose m} }{ n^{m} } \)

Content

[hide]

This is a beautiful problem from ISI MStat 2018 PSA problem 13 based on probability of functions. We provide sequential hints so that you can try .

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

- \( {n \choose m} / m^{n} \)
- \( {n \choose m} / n^{m} \)
- \( {{m+n-1} \choose m} / m^{n} \)
- \( {{m+n-1} \choose m-1} / n^{m} \)

combination

But try the problem first...

Answer: is \( {n \choose m} / n^{m} \)

Source

Suggested Reading

ISI MStat 2018 PSA Problem 13

A First Course in Probability by Sheldon Ross

First hint

What is the total number of functions from \({1,2, \ldots, m}\) to \({1,2, \ldots, n}\) where (n>m)

You have to choose \(m\) numbers among \({1,2, \ldots, n}\) and assign it to the \({1,2, \ldots, m}\)

For each element of \({1,2, \ldots, m}\), there are \(n\) options from \({1,2, \ldots, n}\).

Hence \(n^m \) number of functions .

Second Hint

\(f(i) = a_i \)

The number of ways to select Select \(m\) elements among \({1,2, \ldots, n}\) is the same as the number of strictly ascending subsequences of length m taken from 1, 2, 3, ..., n, which is the same as the number of subsets of size m taken from {1,2,3,…,n}, which is \( {n \choose m} \) .

Final Step

Hence the probability that it will be strictly increasing \( \frac{ {n \choose m} }{ n^{m} } \)

Cheenta is a knowledge partner of Aditya Birla Education Academy

Advanced Mathematical Science. Taught by olympians, researchers and true masters of the subject.

JOIN TRIAL
Google