# Permutation with Natural Ordering

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!)

-
Hello Michael. What do you exactly mean by natural ordering? –  Aryabhata Mar 27 '12 at 22:51
Hi?... I do not know what to do with your comment :) –  Michael Mar 27 '12 at 22:52
Read it again...? –  Aryabhata Mar 27 '12 at 22:53
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!) –  Michael Mar 27 '12 at 22:58
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$? –  Aryabhata Mar 27 '12 at 23:01

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

$$\binom{k+n-1}{n}$$

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

-
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! –  Michael Mar 27 '12 at 23:14
@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!}$. –  Aryabhata Mar 27 '12 at 23:16
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). –  Michael Mar 27 '12 at 23:19
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)). –  Michael Mar 27 '12 at 23:33
Ill give you the answer, because you helped me with the first section! Thanks so much. –  Michael Mar 27 '12 at 23:33