6
$\begingroup$

I have been looking at this problem for a long time. Can anyone prove the combination formula using factorials N choose K?

In case anyone does not know how to list all combinations in a set, you start with a permutation tree (for example)
1 2 3 4
234 134 124 123

You then delete all connected groups in the second row that are less than the previous row (or experience an inversion) which are in bold above.

$\endgroup$
5
  • $\begingroup$ You want to prove that the number of $k$-subsets of an $n$-set is $\binom nk=\frac{n!}{k!(n-k)!}$? $\endgroup$
    – Pedro
    Dec 27, 2015 at 18:54
  • $\begingroup$ yes, that would be very helpful $\endgroup$
    – W. G.
    Dec 27, 2015 at 19:03
  • 1
    $\begingroup$ if you don't like the argument in the answer(which is perfectly fine) then you can also prove this by induction in k $\endgroup$
    – math635
    Dec 27, 2015 at 19:18
  • $\begingroup$ I guess I was wanting a more in depth proof. Possibly by using factorials, nodes, cycles, whatever it takes to arrive at the n choose k formula. $\endgroup$
    – W. G.
    Dec 27, 2015 at 19:53
  • $\begingroup$ Just a link iam posting so to visualise the n choose k mathsisfun.com/combinatorics/combinations-permutations.html $\endgroup$ May 6, 2020 at 15:26

4 Answers 4

10
$\begingroup$

First choose $k$ elements among the $n$ elements in some order, which can be done in $n\cdot(n-1)\cdots (n-k+1)$ ways.

In this count, any group of $k$ elements have been counted $k!$ times, which you have to compensate for, giving

$$\frac{n\cdot(n-1)\cdots (n-k+1)}{k!} = \frac{n!}{k!(n-k)!}.$$

$\endgroup$
10
  • $\begingroup$ I know that. I just want to see how that formula can be proved. In a lot more detail. $\endgroup$
    – W. G.
    Dec 27, 2015 at 19:26
  • 3
    $\begingroup$ @W.G. If you tell us exactly what is wrong with this proof, we might be more able to help you. $\endgroup$
    – Mankind
    Dec 27, 2015 at 22:02
  • $\begingroup$ Why any group of k elements can be counted k! times? It seems like a broad statement to make with no reasoning behind it. You can prove it inductively like the site below, but there has got to be a better reason for it.{google.com/…} $\endgroup$
    – W. G.
    Dec 28, 2015 at 0:03
  • $\begingroup$ @W.G. The factor of $k!$ represents the number of orders in which the $k$ objects can be selected. Since the order of selection is irrelevant, we must divide by the $k!$ orders in which the same elements can be selected. $\endgroup$ Dec 28, 2015 at 1:47
  • $\begingroup$ Yes, but I'm looking a little deeper. I'm looking for something a little more concrete. $\endgroup$
    – W. G.
    Dec 28, 2015 at 3:33
4
$\begingroup$

I copied my answer from Quora which I wrote on the same day as I saw this.

Let’s take the numbers 1 2 3 4 5 6 7 8 9 10 11 and call it set A

Ask yourself: how many ways can I make triplets from A (e.g. 1 2 3 or 10 11 6), where triplets with exactly the same numbers count as one (e.g. 1 2 3 and 3 2 1)

Let’s start off by considering the number of different ways of ordering three numbers (permutations) from set A.

We start off with 11 options, followed by 10 left and then we are left with 9. So 11 * 10 * 9 = 990

Let’s define a set B, which contains all of the different orderings of triplets from A.

Consider ANY element in set B. Let’s call the numbers x y z. Because set B is a set of permutations, it’ll also contain values:

  1. x z y
  2. y x z
  3. y z x
  4. z x y
  5. z y x

So our goal, is to remove all extra five elements from set B for all triplets x y z. Well we can do this.

We know there are 990 permutations in total. For each permutation, there are five others which contain exactly the same numbers. So let p be a single triplet. There will be 6p of these in B (ignoring their order). We know 6p = 990. Hence p = 165. So there are 165 unique triplets in B, which answers our first question.

There is one issue I didn’t raise: how did I know how many different ways there were of ordering x y and z? Well the simple answer is that it was fairly trivial to think up the different orderings, since there were only three numbers per ordering.

If there were more numbers (let’s call this number r), then the best way to calculate the number of different orderings would be r(r-1)(r-2)…1, which is r!. (Each time we have one less choice until there’s only 1 left)

So we can say: the number of different triplet combinations from the set A is $\frac{11*10*9}{3!}$

OK, from this, we can think of a more general formula.

If there are n items in a set, the number of ways we can group r items is $\frac{n(n-1)(n-2)...(n-r+1)}{r!}$

OK, we still haven’t derived the general combinations formula, but we’re getting closer.

There is one other concept we’ve yet to raise: If I take r items from a group of n items, then there will be n-r unique group of items left over from the items I didn’t take.

For example, with set A, if I take a unique triplet (ignoring any permutations) 1 2 3, then I also have a unique set of 9 numbers 4 5 6 7 8 9 10 11. Or if I took the numbers 4 8 11, I’d also end up with the numbers 1 2 3 5 6 7 9 10.

Therefore: The number of ways of taking r items from a group of n items, is the same as the number of ways of taking n-r items from a group of n items.

So let’s go back to that general formula, and let’s call it x: $\frac{n(n-1)(n-2)...(n-r+1)}{r!} = x$

By the above rule, this also means the number of ways of taking n-r items is also x. So

$\frac{n(n-1)(n-2)...(r+1)}{(n-r)!} = x$

If we add this together we get: $2x = \frac{n(n-1)(n-2)...(r+1)}{(n-r)!} + \frac{n(n-1)(n-2)...(n-r+1)}{r!} $ [Note: original answer had an (n-1) denominator in first addend] Now via simple adding of fractions we can do: $2x = \frac{r![n(n-1)(n-2)...(r+1)]}{r!(n-r)!} + \frac{(n-r)![n(n-1)(n-2)...(n-r+1)]}{r!(n-r)!} $

But wait. Let’s take a closer look at our numerators:

1. r![n(n-1)(n-2)...(r+1)]

2. (n-r)![n(n-1)(n-2)...(n-r+1)]

Number 1 implies 1234…*r (r!), multiplied by (r+1)(r+2)…(n-2)(n-1)n. S0 isn’t this just another way of writing out n! ?

Number two implies 1234…(n-r) ( (n-r)! ) multiplies by (n-r+1)(n-r+2)…(n-2)(n-1)n. Isn’t this also n! ?

Therefore, we can simplify this and say

$2x = \frac{n!}{(n-r)!r!} + \frac{n!}{r!(n-r)!} $ so $2x = \frac{2n!}{r!(n-r)!} $

Therefore x = $\frac{2n!}{2r!(n-r)!} $ = $\frac{n!}{r!(n-r)!} $

That's one way of proving the formula.

$\endgroup$
4
$\begingroup$

This is how I see it.

Say I have 10 slots and 10 digits that I want to know how many permutations the digits that I can form, the slots look like _ _ _ _ _ _ _ _ _ _

on the first slot, i have 10 options to choose from, so [10] _ _ _ _ _ _ _ _ _

since the first slot is already occupied, i am left with having 9 options [10] [9] _ _ _ _ _ _ _ _

and the third slot will only have 8 left and so on, giving [10] [9] [8] [7] [6] [5] [4] [3] [2] [1]...So the number of 10-digit numbers I can make is 10x9x8x7x6x5x4x3x2x1, which is the definition of 10!

However if i have the same 10 digits but i only have 3 slots then [10] [9] [8] = 10x9x8, which is 10!/7! or 10!/(10-3)! which in general form would become the familiar nPr = n!/(n−r)!

now, among the permutations for [10] [9] [8], the 3 slots themselves can also be rearranged 3! times. to make it easier, let's name the 3 slots, A, B and C [10]-->slot A [9]--> slot B [8]--> slot C

ABC, ACB, BAC, BCA, CAB, CBA are all considered the same when what you want is a combination. so to remove the redundancy, we divide the number of permutations of the digits by the number of redundancies, that is to say, the number of permutations of the slots.

for which you get nCr = (permutation of digits)/(permutation of slots) note that permutation of slots is always rPr, which is r!

and thus you get nCr = nPr /r! = n!/[(n-r)!r!]

$\endgroup$
1
1
$\begingroup$

According to Sheldon Ross' A First Course In Probability, $n(n − 1) · · · (n − k + 1)$ represents the number of ways in which $k$ items can be selected from $n$ items when we care about the order of selection. Notice then that each group of $k$ items is counted $k!$ times. Then the number of different groups of $k$ items that can be made from a set of $n$ items is: $$ \frac{n(n-1)(n-2)...(n-k+1)}{k!} $$

Now, note also that $n!$ can be expressed as $n(n-1)(n-2)...(n-k+1)\times(n-k)!$ Given this information, we can derive the combination formula by multiplying this equation by $1=\frac{(n-k)!}{(n-k)!}$, which gives: $$ \frac{n(n-1)(n-2)...(n-k+1)}{k!}\times\frac{(n-k)!}{(n-k)!} = \frac{n!}{k!(n-k)!} = {n \choose k} $$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.