3
$\begingroup$

Disclaimer: I'm new to combinations and permutations.

Observation: If it's $\frac {permutations} {ways}$, each way is $\frac {permutations} {ways}$ permutations.

Problem: Given $n \choose k$, I more or less intuitively understand the binomial coefficient: $\frac {n!} {k! (n-k)!}$ thanks to Khan Academy's intuition video on Combination formula. But, why are we dividing ways instead of subtracting the "repeats" (i.e., the ways to arrange k that were already counted as combinations)?

Question: Rephrasing my question: how could you calculate what to subtract without already knowing the answer to $n \choose k$? For example, in $${4 \choose 3}=4$$ you know that $4! = 24$, so $$24-x=4$$ $$x=20$$ where x represents "repeats." But I had to know the answer was 4 to calculate x. Simply put then, is it possible to calculate 20 without knowing 4?

$\endgroup$

2 Answers 2

2
$\begingroup$

Your attempt to work with units is a good start.

You divide rather than subtract because the number of repeats per permutation is constant. So for three element subsets of a $10$ element set there are $10\times 9 \times 8$ ways to choose the three elements in order, but that finds each subset $3!$ times.

To subtract instead of dividing you'd have to know how many subsets there were (and multiply that by $3!$) but finding the number of sets is the whole problem.

$\endgroup$
1
$\begingroup$

To give a conceptual answer: It's ugly to look at X's in a particular order, going one by one, saying "this is the first one with this property, any after this one I'll disregard" and then counting how many "firsts" you got. In contrast, it's simple and clean to treat all X's on an equal footing without distinguishing any particular ones, form groups of the X's according to whether they have some property, and then count the groups.

(Here, X's are arrangements of $k$ out of $n$ objects.)

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