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
    Hello Michael. What do you exactly mean by natural ordering?2012-03-27
  • 0
    Hi?... I do not know what to do with your comment :)2012-03-27
  • 0
    Read it again...?2012-03-27
  • 0
    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!)2012-03-27
  • 0
    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$?2012-03-27
  • 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
    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!2012-03-27
  • 0
    @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!}$.2012-03-27
  • 0
    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).2012-03-27
  • 0
    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)).2012-03-27
  • 0
    Ill give you the answer, because you helped me with the first section! Thanks so much.2012-03-27
  • 0
    I still cannot seem to get the answer for Requires in order, but non unique. This one is hard, and the answer your giving me is incorrect. Given this, the solution says that k = 93 and n = 8 (where natural order matters and non-distinct) should be equal to (probability wize) k = 100 and n = 8 (natural order and distinctive)2012-03-27
  • 0
    @Michael: I had switched a $+$ and $-$ sign. You should get the right answer now.2012-03-27
  • 0
    I think your missing part of the question or i forgot to ask part of the question. What if they are requiring `natural ordering` only? So repetitions can occur2012-03-28
  • 0
    @Michael: "Natural Ordering" is not a term which you can just use and expect people to just understand what your intention is. You ought to give some examples! Anyway...2012-03-28
  • 0
    Thanks. I am new, but i understand more.2012-03-28