I have searched the web for this answer and now must ask a community. Hello community. So say i can choose n items out of a numbered list no higher than k. So if i could choose 2 items from a list of 10 (1 - 10) then i would 100 possibilities. The probability, obviously, is 1/100.

Now things get tricky...,

There exists a constraint that the numbers must be in natural ordering. This is where i am getting to my first problem. I do not know how to calculate this (i have referenced several online combinatorics guides, they never seem to touch on this case). So if there is natural order required and n = 2 and k = 10 i will have to provide the probability i could guess the correct answer. This has been provided for me (this is not homework, this is my own self studying, but i am stumped!) which is 1/55. 45 of the answers ({3, 2}, {7, 1}, ... etc, since 7 comes after 1, its not in natural ordering) are not allowed. So how would i calculate such this probability?

The second problem is what if i need to not only have natural ordering, but repetitions are not allowed? Then how would calculate that???

Now i am not just coming here as my first attempt. I have spent about 2 hours googling key words and reading articles trying to find such answers. I keep running into the same 4 problems/answers (Permutation: order matters, does not matter (not referring to natural ordering) and Combination: Repetitions allowed, not allowed (but not combined in my case!)

Thank you very much. If you are confused on my question, please leave a comment.

  • $\begingroup$ Hello Michael. What do you exactly mean by natural ordering? $\endgroup$
    – Aryabhata
    Mar 27, 2012 at 22:51
  • $\begingroup$ Hi?... I do not know what to do with your comment :) $\endgroup$ Mar 27, 2012 at 22:52
  • $\begingroup$ Read it again...? $\endgroup$
    – Aryabhata
    Mar 27, 2012 at 22:53
  • $\begingroup$ I think it should be more english friendly now :) (I did not proof read and i did several section rewrites, i eventually got a mixture of like 4 different thoughts!) $\endgroup$ Mar 27, 2012 at 22:58
  • $\begingroup$ By natural ordering (for the $n=2$ case) you mean pairs $(a,b)$ where $a \lt b$? And in general $(a_1, a_2, \dots, a_n)$ where $a_1 \lt a_2 \lt \dots a_n$? $\endgroup$
    – Aryabhata
    Mar 27, 2012 at 23:01

1 Answer 1


First let us deal with the case where you want to select $n$ numbers $a_1, a_2, \dots a_n$ such that $a_1 \lt a_2 \lt \dots a_n$.

A way to do this is select any $n$ distinct numbers and sort them.

This is given by the binomial coefficient: $$\binom{k}{n}$$

Now you want to select numbers such that $a_1 \le a_2 \le \dots a_n$, i.e. repetitions are allowed, but you want to maintain order.

The typical tactic for that is to transform your numbers, so that you can use the 'distinct' version of the problem.

For this, you set

$b_i = a_i + i$

The $b_i$ are distinct, and are in $\{2, 3, \dots, k+n\}$

Thus you select $n$ distinct numbers from $k+n-1$ possiblities, giving you


For the probability of a specific ordering, just invert the total number of possibilities, assuming they all are equally likely.

  • $\begingroup$ I am not to good at combinatorics. Does this mean the equation is, using the example data, ((10 - 2 + 1)! / 2!(10 - 2)!) ? I also do not know how to do sweet editing tricks like you do, i am new to the math.so! $\endgroup$ Mar 27, 2012 at 23:14
  • $\begingroup$ @Michael: No. For $k=10, n=2$, the second (non-distinct case) is $\binom{9}{2} = \frac{9!}{2!7!}$. The distinct case is $\binom{10}{2} = \frac{10!}{2!8!}$. $\endgroup$
    – Aryabhata
    Mar 27, 2012 at 23:16
  • $\begingroup$ The distinct case i am getting 45, which is the number that is provided on the solution, but the non-distinct case i am not getting the same answer. I get 36 (which they say the answer is 55). $\endgroup$ Mar 27, 2012 at 23:19
  • $\begingroup$ If both order matters and repetitions are not allowed, the site says (TopCoder.com) 1/45 is the probability (given the example i gave you). I found the answer. Its ((k + n - 1) / (n - 1)). $\endgroup$ Mar 27, 2012 at 23:33
  • $\begingroup$ Ill give you the answer, because you helped me with the first section! Thanks so much. $\endgroup$ Mar 27, 2012 at 23:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .