4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – najayaz Sep 22 '15 at 17:06
  • $\begingroup$ 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. $\endgroup$ – littleO Sep 22 '15 at 17:13
  • $\begingroup$ 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. $\endgroup$ – Michael Hardy Jul 20 '17 at 2:25
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Solid explanation. +1 $\endgroup$ – Mark Viola Sep 22 '15 at 17:19
  • $\begingroup$ @Nitin:Could you tell the relation between permutation and combination? $\endgroup$ – justin Dec 30 '15 at 9:44
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Nice explanation. +1 $\endgroup$ – Mark Viola Sep 22 '15 at 17:20
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Jyrki Lahtonen Jul 20 '17 at 10:34
  • $\begingroup$ @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. $\endgroup$ – Michael Hardy Jul 20 '17 at 15:31
  • $\begingroup$ 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. $\endgroup$ – Jyrki Lahtonen Jul 21 '17 at 5:31

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.