0
$\begingroup$

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.

  • 0
    defined by the problem (i just read)$(a,b)$where a <= b. This is a problem off of TopCoder.com. I have never taken a probability class (or really learned anything about combanitorics). So i am very lost! But i did learn a lot more today by reading several online articles!2012-03-27

1 Answers 1

2

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.

  • 0
    Thanks. I am new, but i understand more.2012-03-28