Math Help - Combinatorial Problem

1. 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

2. Originally Posted by davmt
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.

Originally Posted by davmt
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.

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

Originally Posted by davmt
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..

3. 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

4. Originally Posted by davmt
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}$

5. 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

6. Originally Posted by davmt
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).

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

7. ok, that becomes a little less innocent that it seems in the beginning

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

$
p_{j} = \frac{n!}{(n-j)!\cdot n^{k}}
$

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

8. Originally Posted by davmt
ok, that becomes a little less innocent that it seems in the beginning

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

$
p_{j} = \frac{n!}{(n-j)!\cdot n^{k}}
$
That looks good.

Originally Posted by davmt
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.