5

Regarding the formula for binomial coefficients:

$$\binom{n}{k}=\frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}$$

the professor described the formula as first choosing the $k$ objects from a group of $n$, where order matters, and then dividing by $k!$ to adjust for overcounting.

I understand the reasoning behind the numerator but don't understand why dividing by $k!$ is what's needed to adjust for overcounting. Can someone please help me understand how one arrives at $k!$? Thanks.

Michael Hardy
  • 1
Mark
  • 161
  • The binomial coefficient is supposed to only count selections and not arrangements, so to do that you first do arrangements and then consider all the $k$ objects to be identical so there is no longer any way to arrange them. That gives us the denominator. – najayaz Sep 22 '15 at 17:06
  • I like to think of it as "number of ordered $k$-tuples = number of subsets of size $k$ $\times$ number of ways to order a subset of size $k$." In other words, for each subset of size $k$ we have $k!$ ordered $k$-tuples. – littleO Sep 22 '15 at 17:13
  • I very much favor an approach to thinking about many things in mathematics in a way that I think of as "concrete but theoretical". At some point I may try to formulate a precise definition. The answer I've posted below is an example of that. – Michael Hardy Jul 20 '17 at 02:25

3 Answers3

4

Suppose you had 5 books on a shelf and wanted to pick 3. If order mattered (permutations), there would be $5 \cdot 4 \cdot 3$ ways of doing so. If order did not matter (combinations), you would discount the extra permutations. That is, "ABC" would be the single representative of all of its $3!$ permutations. The total number ways of selecting the books is $\frac{5\cdot4\cdot3}{3!}$. For the general case, replace the 5 with $n$ and 3 with $k$.

user217285
  • 5,735
2

Suppose you want to plant three identical red flowers in a row. In how many ways can you do it? First you plant all three red flowers in a row. Suppose you swap the first flower with the second one. Did anything change? You still have three red flowers in a row. Try swapping the first flower with the third one. Do you see any difference? I can't. They are still the same three red flowers planted in a row. Basically, no matter how your permute these flowers, you have only one outcome, namely a row of three identical red flowers.

So, there are $3!$ ways to plant these flowers in a row, but since every row looks exactly like the other row, we divide out the redundant ones. There are $3!$ redundant rows. Then $\frac {3!}{3!} = 1$ way to plant three identical red flowers.

user273143
  • 91
0

Let's try it with $\dbinom 5 3:$ \begin{align} P(5,2) = {} & (\text{number of permutations of 3 things in a set of 5}) \\[10pt] = {} & \frac{5!}{(5-2)!} = 20. \\[10pt] & \text{These permutations are:} \\[10pt] & ab,\ ba\qquad \longleftarrow \text{$2!=2$ permutations, both the same combination.} \\ & ac,\ ca\qquad \longleftarrow \text{$2!=2$ permutations, both the same combination.} \\ & ad,\ da\qquad \longleftarrow \text{$2!=2$ permutations, both the same combination.} \\ & ae,\ ea\qquad \longleftarrow \text{etc.} \\ & bc,\ cb \\ & bd,\ db \\ & be,\ eb \\ & cd,\ dc \\ & ce,\ ec \\ & de,\ ed \end{align} For each combination, there are $2!=2$ permutations. So you divide the number of permutations by $2!=2$ to get the number of combinations.

Michael Hardy
  • 1
  • The system raised an automatic flag, because this answer is identical to another one you posted earlier. I guess it is trying to tell you that one of the answers has to go. Do you want me to flip a coin? – Jyrki Lahtonen Jul 20 '17 at 10:34
  • @JyrkiLahtonen : I pasted it here because the question under which I posted it before was flagged as a duplicate. I've done that several times before and never heard of such a flag. If the other question is closed as a duplicate, the perhaps I should put a comment under it, linking to this answer. – Michael Hardy Jul 20 '17 at 15:31
  • The flag is automatic. I know some users try "to get paid twice for the same work" (in terms of rep points), but I find the practice unethical. Not unlike self-plagiarizing. – Jyrki Lahtonen Jul 21 '17 at 05:31