Results 1 to 8 of 8

Math Help - Combinatorial Problem

  1. #1
    Newbie
    Joined
    Aug 2010
    Posts
    4

    Combinatorial Problem

    I am trying to derive an analytical formula for this problem.

    I have 10 numbers (n=10) and I choose k from them (ranging from 1 to 10 at the end). Let k = 4 for this example's sake.

    I want to find the probability that,
    all the numbers are that I choose are different,
    10*{1}/{10}*{9}/{10}*{8}/{10}*{7}/{10}

    all the numbers that I choose are thesame,
    10*{1}/{10}*{1}/{10}*{1}/{10}*{1}/{10}

    and the other respective combinations ?

    I think that the probability of choosing two distinct numbers, is
    1) the probability of choosing a sequence like xx yy
    2) the probability of choosing a sequence like xxx y

    such that
    10*{1}/{10}*{1}/{10}*{9}/{10}*{1}/{10}
    and
    10*{1}/{10}*{1}/{10}*{1}/{10}*{9}/{10}

    and the probability of choosing three distinct numbers should be given by
    10*{1}/{10}*{9}/{10}*{8}/{10}*{2}/{10}

    i know that these calculations have to be scaled by multiplying with the possible number of occurrences (combinations), but I'm a bit lost on how to continue!

    I would also gladly accept and alternative methods to tackle this solution

    thanks
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by davmt View Post
    I am trying to derive an analytical formula for this problem.

    I have 10 numbers (n=10) and I choose k from them (ranging from 1 to 10 at the end). Let k = 4 for this example's sake.
    Usually we use your wording of choosing k out of 10 numbers to mean "without replacement" although it's clear that you mean with replacement.

    Quote Originally Posted by davmt View Post
    I want to find the probability that,
    all the numbers are that I choose are different,
    10*{1}/{10}*{9}/{10}*{8}/{10}*{7}/{10}
    This calculation is correct, although I would write 10*1/10 as just 1.

    Quote Originally Posted by davmt View Post
    all the numbers that I choose are thesame,
    10*{1}/{10}*{1}/{10}*{1}/{10}*{1}/{10}
    This is also correct.

    Quote Originally Posted by davmt View Post
    and the other respective combinations ?
    What do you mean by "other respective combinations"?

    I'm not sure of your overall question. Are you saying you want an approach that's more based on combinatorics than on conditional probability? Because you already have correct values..
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2010
    Posts
    4
    i want an approach that makes it easier to derive an analytical formula

    yes the problem is with replacement because you can choose the same numbers

    for k = 4 for example
    i want to find the probability of choosing 2 distinct numbers from 4
    e.g. 1 1 2 and 2 or 1 1 1 and 2
    and choosing 3 distinct numbers from 4
    e.g. 1 2 3 1 or 1 2 3 2 or 1 2 3 3 for example

    and i don't care about the order

    eventually i want to derive a general formula, where the number of numbers picked (from to 1 to 10) vary
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by davmt View Post
    i want an approach that makes it easier to derive an analytical formula

    yes the problem is with replacement because you can choose the same numbers

    for k = 4 for example
    i want to find the probability of choosing 2 distinct numbers from 4
    e.g. 1 1 2 and 2 or 1 1 1 and 2
    and choosing 3 distinct numbers from 4
    e.g. 1 2 3 1 or 1 2 3 2 or 1 2 3 3 for example

    and i don't care about the order

    eventually i want to derive a general formula, where the number of numbers picked (from to 1 to 10) vary
    From what I understand, you want to do this: Given a positive integer n, and a positive integer k that is less than or equal to n, and given that we pick k elements from {1,...,n} with replacement, give closed-form expressions for (1) probability that all k elements are distinct, (2) probability that all k elements are identical.

    Of course it's possible to change "positive" to "nonnegative", possibly without change to the closed-form expressions.

    You say you want a simpler method, but from my view you already have a simple method. Here are some "hints" that are kind of like giving you the full answer, although I left a few blanks for you to fill in.

    Suppose (n,k) = (10,4).

    (1)

    1\cdot\frac{9}{10}\cdot\frac{8}{10}\cdot\frac{7}{1  0}=\frac{9!}{6!}\cdot\frac{1}{10^3}

    (2)

    1\cdot\frac{1}{10}\cdot\frac{1}{10}\cdot\frac{1}{1  0}=\frac{1}{10^3}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Aug 2010
    Posts
    4
    this,
    (1) probability that all k elements are distinct, (2) probability that all k elements are identical.
    is the part i have solved

    but i want to also find the probability that j elements out of k where j <= k, are identical
    the cases you described in (1) and (2) are for j = 1, j = k respectively
    i want to find the solution for j > 1 and j < k
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by davmt View Post
    this,
    (1) probability that all k elements are distinct, (2) probability that all k elements are identical.
    is the part i have solved

    but i want to also find the probability that j elements out of k where j <= k, are identical
    the cases you described in (1) and (2) are for j = 1, j = k respectively
    i want to find the solution for j > 1 and j < k
    Oh, I get it now.

    I'm going to use j to represent the number of distinct elements among the k chosen elements, so with that, my case (1) corresponds with j = k, and case (2) corresponds with j = 1.

    Suppose the function that gives probability is f(n,k,j). So I'm not sure of a general closed form solution, but here's how I would approach for example (n,k) = (10,5).

    The cases already covered,

    j = 1 gives f(10,5,1)=\displaystyle \frac{1}{n^{k-1}}=\frac{1}{10^4}

    j = k gives f(10,5,5)=\displaystyle \frac{n!}{(n-k)!\cdot n^k} = \frac{10!}{5!\cdot 10^5}

    And more complicated,

    j = 2 gives f(10,5,2)=\dfrac{P(10,2)\cdot(\binom{5}{1,4}\cdot\  frac{1}{1!1!}+\binom{5}{2,3}\cdot\frac{1}{1!1!})}{  10^5}.

    where \binom{5}{1,4}=\frac{5!}{1!4!} is a multinomial coefficient and here can be interpreted as the number of permutations of the multiset {1,2,2,2,2}, and where P(10,2)=\binom{10}{2}\cdot2!=\frac{10!}{(10-2)!} is the number of 2-permutations of {1,...,10}.

    For a larger example, I get

    f(10,6,3)=\dfrac{P(10,3)\cdot(\binom{6}{1,1,4}\cdo  t\frac{1}{2!1!}+\binom{6}{1,2,3}\cdot\frac{1}{1!1!  1!}+\binom{6}{2,2,2}\cdot\frac{1}{3!})}{10^6}

    Possibly I've made this more complicated than it needs to be, but for example the quantity \frac{1}{2!1!} is to account for the fact that {1,2,3,3,3,3} is the same as {2,1,3,3,3,3}.

    This seems to work in general; you just need to take the time (or write a program) to find all unordered partitions of k elements into exactly j nonzero parts. It's not hard to do this algorithmically by considering for example partitions into j=3 parts as {a,b,c} where 1 \le a \le b \le c and a+b+c = k, where we restrict a \le b \le c in order to avoid counting duplicates.

    It can be seen that j = 1 and j = k are special cases of the formula I'm suggesting... unless I've made some mistake.. (edited and hopefully now there is no mistake.)
    Last edited by undefined; August 8th 2010 at 12:27 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Aug 2010
    Posts
    4
    ok, that becomes a little less innocent that it seems in the beginning

    for j = 1 and j = k we can maybe use this

    <br />
p_{j} = \frac{n!}{(n-j)!\cdot n^{k}}<br />

    for the rest i will try to understand exactly what is happening but i get an idea for now

    thanks a lot for your help
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by davmt View Post
    ok, that becomes a little less innocent that it seems in the beginning

    for j = 1 and j = k we can maybe use this

    <br />
p_{j} = \frac{n!}{(n-j)!\cdot n^{k}}<br />
    That looks good.

    Quote Originally Posted by davmt View Post
    for the rest i will try to understand exactly what is happening but i get an idea for now

    thanks a lot for your help
    You're welcome! I find it an interesting counting problem.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. a combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 23rd 2011, 07:04 AM
  2. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 16th 2011, 03:39 PM
  3. Combinatorial problem
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: October 4th 2011, 09:05 AM
  4. combinatorial problem??
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 23rd 2009, 10:29 PM
  5. Combinatorial problem
    Posted in the Statistics Forum
    Replies: 2
    Last Post: June 13th 2008, 06:22 PM

Search Tags


/mathhelpforum @mathhelpforum