# Probabilities: k out of n

I have 10 numbers. each of them represents a coordinate.

I think that by combining these ten numbers, 100 points can be generated:

$$10^2=100$$

Then by choosing k points out of those 100, there can be: $$\frac{100!}{k!(100-k)!}$$ different combinations of k points.

Is this right?
For the different values of k $$1<k<11$$ how many combinations can be generated?

-
Yes, you're right. –  markovchain Jun 25 '13 at 12:25

You have a set of ten numbers. When you "combine" them to form coordinates, there are $10$ ways to choose the first coordinate and $10$ ways to choose the second coordinate. Thus, there are $10\times10=100$ possible coordinates.

To select $k$ points, we use the binomial coefficient, with $n = 100$: $$\text{Ways for k points} = \binom{n}{k} = \binom{100}{k} = \frac{100!}{k!(100-k!)}$$

-
I think you have to go even further, it works for coordinates, but in a set of 10 numbers there are actually $2^{10}=1024$ different subsets of 10 numbers. –  Salieri Jun 25 '13 at 12:37
Why do you care about subsets, @Cardonai ? –  Thomas Andrews Jun 25 '13 at 12:50
@Cardonai You're right: a set of $10$ numbers has a power set of size $2^{10}$. But, I don't see the bearing this has on my answer... –  apnorton Jun 25 '13 at 12:51

Yes.

First, I think I'll clearly define your question. Say you mean you have a set $X_1$ with 10 distinct elements, and an equal set $X_2$ with exactly the same elements.

You can then have a third set $X_3$ which is made up of the combination of elements in the set $X_1$ and $X_2$ in that order. So if your set was $X_1$ = {a,b,c,d,e,f,g,h,i,j} which is the same as $X_2$, then $X_3$ = {aa,ab,ac,ad,ae,...jh,ji,jj}

I did that because you said "coordinates" which imply a spatial nature, which is continuous. Anyways, that doesn't really affect the answer to the question. But it does give a more defined basis.

So the size of $X_3$ is 100. If we wanted to take $k$ things from $X_3$, say $k=3$, we can take {aa,ab,ac}. Or we can take {ab,ac,ad}. Or we can take {ac,ad,ae}.

But if we take {ab,ac,aa} or {aa,ac,ab} or {ab,aa,ac} or {ac,aa,ab} or {ac,ab,aa}, that's the same as the first one we already picked, but jumbled around in a different order. The same goes for the other sets. In this case, there are 6 ways to choose the same set.

Let's try going for $k=4$. Let's pick something easy, like {aa,bb,cc,dd}.

I can pick the following sets and choose exactly the same set as above:

{aa,bb,dd,cc} {aa,cc,bb,dd} {aa,cc,dd,bb} {aa,dd,bb,cc} {aa,dd,cc,bb}

{bb,aa,cc,dd} {bb,aa,dd,cc} {cc,aa,bb,dd} {cc,aa,dd,bb} {dd,aa,bb,cc} {dd,aa,cc,bb}

{bb,cc,aa,dd} {bb,dd,aa,cc} {cc,bb,aa,dd} {cc,dd,aa,bb} {dd,bb,aa,cc} {dd,cc,aa,bb}

{bb,cc,dd,aa} {bb,dd,cc,aa} {cc,bb,dd,aa} {cc,dd,bb,aa} {dd,bb,cc,aa} {dd,cc,bb,aa}

If you count them all, that's a total of 24 sets that have the same elements, but the elements have been jumbled up in a different order.

If I chose $k=5$, there would be 120 ways to pick the same set. Therefore, I won't list all of those down.

But if I chose only $k=2$, I would have only two ways to pick them out. If I chose {aa,bb}, the only other set the same as that is {bb,aa}. And if $k=1$, there's only 1 way to choose one element from that set.

So notice that when I pick $k$ things, there are a $k$! number of ways to choose the same set I chose. If I picked $k=1$, $k$!=1, and $k=2$, $k$!=2, and $k=3$, $k$!=6, and $k=4$, $k$!=24, and $k=5$, $k$!=120, and so on.

This is why your fraction is $\frac {100!}{k!(100-k)!}$. That $k$! is there in the bottom because you're removing all the other ways that you can choose essentially the same set.

This is called a combination, which you did mention. But this is the logic behind the combinations.

There is $\frac{100!}{(100-k)!}$ though, because of permutations. But as the question only wants combinations, I should probably stop here. :) It's also a good exercise for yourself to figure out why permutations work that way.

## Edit:

For your follow up question, you only need to use a calculator to find out the answer yourself :)

-
OK! Many thanks!!! I am not sure that I can use a calculator because I want to use different values than 100. I mean that I want to study this function $$\frac{n!}{k!(n-k)!}$$ –  Herc11 Jun 25 '13 at 12:59
As far as that goes, you can study it by observing a graph. But I recommend you study it by learning the logic of how that formula came to be. On a calculator, you can just use ${_n}C_r$. You can even do this on the internet. Go to wolframalpha.com and play with your numbers. –  markovchain Jun 25 '13 at 13:28
Yes. I used Matlab. I saw that when k>50 the number of combinations is smaller than k=50. Is the same graph as binomial's distribution? –  Herc11 Jun 25 '13 at 13:32
Almost the same. In fact, the binomial distribution is $$\frac{n!}{k!(n-k)!}p^k(1-p)^{n-k}$$ –  markovchain Jun 25 '13 at 13:36
The reason it peaks at k=50 is because $\frac{100!}{k!(100-k)!}$ when k=1 is the same as when k=99. And it is the same when k=2 and k=98. And so on, up to k=49 and k=51. Generally, ${_n}C_r$ (the combination) is equal when r=k and when r=n-k. Can you see why? –  markovchain Jun 25 '13 at 13:39