Why do we divide Permutations to get to Combinations?

Question

I'm having a hard time reasoning through the formula for combinations $\frac{n!}{k!\left(n-k\right)!}$. I understand the reason for the permutations formula and I know that for the combinations we divide by $k!$ to adjust for the repeated cases, since order does not matter. But what exactly happens when we divide the set of permutations by $k!$ ?

I know this may seem like a silly question... I just can't take this for granted, lest I miss a chance to apply it correctly. Can you describe what's happening here step by step, sort like debugging a script?

Answer 1

Let $X$ be a finite set of size $n$. Suppose we want to know the number of combinations of size $k$. First a definition:

A combination is a subset of $X$

So let us instead ask: How can we construct a combination? I suggest that we do this by constructing a permutation. Let’s use this definition:

A subpermutation of $X$ is some subset of $X$ with some ordering attached.

There are two ways two proceed. This one is called forwards:

How do we construct a subpermutation? Well it has to be ordered so let’s choose the first element. There are $n$ choices and we can partition the set of permutations by the choice of first element, so we haven’t missed anything yet with this choice and we haven’t double counted anything. So we carry on and eventually we stop after $k$ elements and conclude that there are $\frac{n!}{(n-k)!}=n(n-1)\cdots(n-k+1)$ subpermutations of size $k.$

Given a subpermutation we can forget the order to get a combination. However as there are multiple subpermutations with the same set and different orders, we have counted the same combination multiple times by getting to it in different ways. If we divide by the number of ways of getting to each combination, we will not be counting things multiple times. So how many ways to get to a combination? Well that’s the number of ways to have a different order on a subpermutation without changing the set. How many of those? Well there’s $k$ choices for the first, $k-1$ for the second, and so on, so $k!$ total, hence we divide by $k!.$

---

This is the backwards way:

Suppose we know there are $C$ combinations of size $k$ and we want to compute $P,$ the number of subpermutations of size $k$. Here is an algorithm:

1. Choose a combination of size $k$
2. Choose some ordering on that combination

And there are $C$ ways of doing part 1, and $k!$ ways to do part 2, so there are $Ck!$ ways to make a subpermutation of size $k.$ We haven’t double counted because we don’t double count in step 1 or 2 and two subpermutations need the same set and the same order to be equal. Therefore $P=Ck!$, but we happen to know $P$ and not $C$ so we can deduce $C=\frac P{k!}$

Answer 2

Maybe, looking at an example clarifies this best :

You have $20$ objects and have to choose $5$ of them. How many possibilities are there ?

You have $20,19,18,17,16$ choices explaining how $\frac{20!}{15!}$ comes into the play.

Now each combination can appear in $5!$ possible orders which correspond to the same combination. Therefore we have to divide by $5!$ to find the number of combinations.

This can be generalized to arbitary numbers explaining how the binomial coefficient emerges.

Answer 3

Let's bunch together permutations that have the same content. Each resulting equivalence class has $k!$ members. Therefore, the number of such classes is $k!$ times smaller than the number of permutations. A combination is just an equivalence class or, if you prefer, one nominated element thereof.

Answer 4

Imagine you have $5$ sports cars that are to be displayed in an event, but there are only 3 spots avaiable. Lamborghini, Mercedez, Ferrari, Porsche, and Bugatti.

Let's say you choose a Mercedez, a Ferrari, and a Lamborghini. There are $5 \times 4 \times 3 = 5!/2!$ ways to arrange these cars

Notice, however, that the display (Lamborghini, Mercedez, Ferrari) is the same display as (Mercedez, Ferrari, Lamborghini) because you have the same selection of cars. You can arrange $3$ objects in $3!$ ways and still have the same collection of objects.

Therefore you must divide the $5 \times 4 \times 3 = 5!/2!$ by $3!$, leading to $$ \frac{5!}{3!2!}$$.

Answer 5

This is the formula for selecting from a distinct list of items. Lets say we pick from 100 songs on a top song list. We only care to pick the top 5 songs. Okay, there are 100! ways to arrange the songs on the original list. Once we take off the top 5, two things happen. The order of the remaining 95 don't matter they aren't the top 5, dividing by 95! cuts that away. We don't care what order the Top 5 are played in, so we divide out the possible orders those top 5 could have, 5! in total number. This arrives us at: $$\frac{100!}{(95!)(5!)}$$

EDIT: To show why distinctness matters, Here's a case, where it won't give you the number of distinguishable states chessboard positions (legal or not, with all 32 pieces). Why because you have 2 each of indistinguishable rooks,knights,and bishops on each side, as well as 8 indistinguishable pawns on each. This means there are 2×2×2×2×2×2×40,320×40,320=104,044,953,600 times as many positions if you distinguish between indistinguisable pieces swapping places.

Edited chess example due to calculation error.

Answer 6

Assume that you want to know the number of combinations of $k$ elements out of $n$ elements. One way to pick such a combination is the arrange all $n$ elements in any arbitrary order (there are $n!$ ways to do so) and pick the first $k$ of them as "your selection". As the remaining $n-k$ elements can be arranged in any order, each ordered selection of the first $k$ elements appears $(n-k)!$ times in the set of all permutations of the $n$ elements, so you have to divide $n!$ by $(n-k)!$ to count the different (ordered) "selections" of $k$ elements. Now, as you are not interested in the order of the $k$ elements, all $k!$ permutations of a "selection" represent the same combination, so you still have to divide the number by $k!$, which makes a total of $\frac{n!}{k!(n-k)!}$ combinations. So, in short, this dividing "removes the order" when counting (here: the order of the first $k$ elements and the order of the remaining $n-k$ elements).

Answer 7

My favorite way of explaining this to myself actually would be something in this vein.

Suppose we have a set of $n$ objects, and we want to find the number of unique $k$-arrangements of them - that is, take $k$ objects from the $n$, and each unique arrangement counts as a single one. The term "arrangement" is important - that means order matters. We know this to be given by

$$P(n,k) = \frac{n!}{(n-k)!}$$

You can rationalize this by thinking of your $k$-arrangement having "slots", and filling them in order. The first slot can be filled by $n$ potential items, the second by $n-1$, and in general the $i^{th}$ by $n-(i+1)$. This gives

$$P(n,k) = n(n-1)(n-2)...(n-k+1)$$

It is a trivial exercise in algebra to show both expressions are equal.

---

This becomes relevant when we consider the selection argument. In this case we want the number of $k$-selections - the number of ways to take $k$ objects from the $n$, but this time order doesn't matter.

This is my favorite way to think of it because I didn't realize this until a few weeks ago - I had just been blindly using the known formulas until an "aha!" moment.

Consider a particular $k$-arrangement from our permutation argument. Let it be the permutation

$$(x_1,x_2,x_3,...,x_k)$$

where each $x_i$ is one of the $n$ objects. We know that, no matter which way we arrange this, however, it will be considered the same selection, because in selections/combinations, order does not matter. I could swap $x_1$ and $x_2$, or I could reverse the order, or I could order them "even-odd-even-odd" -- it doesn't matter, they're all the same one.

Which then brings up the question - how many ways are there to rearrange $k$ objects? We know this to be $P(k,k) = k!$. This means that, for every particular arrangement, it is in a sort of "class" of arrangements that are indistinct as selections. For every arrangement of $k$ objects, only one of those $k!$ arrangements is distinct - and that is for every arrangement.

That allows us to conclude that the number of selections/combinations is given by

$$C(n,k) = \frac{P(n,k)}{k!}$$

Explicitly using the formula for $P(n,k)$, then,

$$C(n,k) = \frac{P(n,k)}{k!} = \frac{1}{k!} P(n,k) = \frac{1}{k!} \cdot \frac{n!}{(n-k)!} = \frac{n!}{k!(n-k)!}$$

Answer 8

Instead of trying to figure out directly why we should divide the permutations by $k!$, let's try thinking of it from the other direction:

Given $n$ distinct objects, there is some number of ways of choosing a combination of $k$ of those objects where the order of objects in the final list of $k$ doesn't matter. Let's not worry about exactly how to calculate that number yet; it's enough to know that it exists. (We could, for example, just list all the combinations by brute force with careful checking for duplicates.) For any $n$ and any $k,$ let $C(n,k)$ represent the number of combinations.

Now consider one of those combinations of $k$ items. If we want to count permutations (where order matters), this single combination can be arranged in $k!$ distinct permutations. None of those permutations is the same as any permutation derived from any other combination of $k$ items. So if we go through the combinations one by one, each adds $k!$ new permutations to the total. But there are $C(n,k)$ combinations. So $P(n,k),$ defined as the total number of permutations of $k$ items selected from $n$ distinct items, obeys the equation $$ P(n, k) = C(n, k) \times k!.$$

Now it is a simple arithmetic operation to divide by $k!$ on both sides, with the result $$ C(n, k) = \frac{P(n, k)}{k!}.$$

And that's why we divide the number of permutations by $k!.$

Answer 9

You divide by k! since that's the number of permutations for the k objects that you've taken. All the permutations/orders of each set of k objects is equivalent since you're dealing with combinations, so you have to divide that out.

Answer 10

This is my favourite way visualise the link between permutations and combinations which I think answers the OP's question. The answer does not add anything to the maths but is a way that I remember how to calculate permutations and combinations - I read it online years ago and I still remember it (but apologies to the original author for not remembering the citation).

Consider having a group of 20 people ($n$) and working out how many unique queues of 5 people ($k$) we can create. This represents permutations and can be calculated in two ways. The first way of calculating permutations is described in previous answers:

$$P = \frac {n!}{(n-k)!}$$

The second way of calculating the same thing would be to take every possible group of 5 people ($k$) (this would actually represent the combinations i.e. order not important) and then, for each group, calculate how many unique queues could be formed; as there are only $k$ people in each group, the number of unique queues is calculated as $k!$. So, in this second method, the number of permutations would be calculated as:

$$P = C \times k!$$

From this, it's easy to see that:

$$C \times k! = \frac {n!}{(n-k)!}$$

and therefore $$C = \frac{n!}{k!(n-k)!}$$

Answer 11

Let $P(n,k)$ denote the number of permutations on $n$ objects taken $k$ at a time.

Order in this case is important---change the order and you have a different permutation. For example, 1,2,3 and 3,2,1 are but two of the $3!$ ways to arrange (permute) the elements of the set $\lbrace 1, 2, 3 \rbrace$. Moreover, since there are in general $k!$ ways to permute a set of $k$ objects, the way to obtain a formula for the number of combinations on $n$ objects taken $k$ at a time is to divide $P(n,k) = \frac{n!}{(n-k)!}$ by $k!$.

This yields

$$C(n,k) = \frac{P(n,k)}{k!} = \frac{n!}{(n-k)!k!}.$$

Answer 12

A tree showing permutations for a set of {n} = 5 and selecting subset of {n} = 3

Adding to the above answers, I would like to add in the intuition for as to why we divide by the number of ways of getting the permutations which are same to us.

In the image you can see the set of permutations, imagine it to be a bag full of things of our interests. These "things" can be divided into groups. For example, if for some reason, to us there is no difference if subsets start with 1, 2, 3, 4 or 5 as far as combinations are concerned, then the total combinations relevant to us will be $\frac{^5P_3}{3}$, that is, $\frac{1}{3}$rd of the total permutations. In other words there are 3 ways to get permutations which either start with 1, 2, 3, 4 or 5, which are, place one of the remaining 3 numbers at the first spot after you fill the last two spots. This means we have 3 groups which are identical to each other, each having 20 members.

(Refer to second image for better understanding) 3 identical groups of 5P3/3

Going further. For a set $Z$ with $ n\{Z\}=N$, where all numbers are unique, if we want all the subsets $X$ with $n\{X\}=k$, meaning that ordering of numbers in subsets is not important for us, we'll have $$p = \text{ } ^NP_k \text{} \text{ ,where } p \text{ is the Total permutations }$$ Now these permutations $p$ will have $k!$ groups, each group representing a way of permutation. Each group contains our desired combinations ordered in the particular way which the given group represents. The differentiating factor between the members of a group with members of another group is the order/permutation which makes no difference for us, meaning $$\frac{p}{k!}=c \text{} \text{ , where } c \text{ is the Total combinations}$$

This is nothing but $$C(n,k)=\frac{N!}{(N-k)!\times(k!)}=\frac{P(n,k)}{k!}$$