How to understand the combination formula?

The explanation of the formula is quite nice, I think. First, it says that there are $n!$ different reorderings of the row of $n$ people. Now, say I want to choose a set of $k$ people out of the $n$ people. I choose it by choosing the first $k$ people in the row.

Now, take one particular set of $k$ people. Let's call the people in the set chosen and the others unchosen. How many different reorderings of the row caused this exact set of chosen people to be selected? I know that if they are selected, all these $k$ people were in the first $k$ places, and all the rest were in the remaining $n-k$.

Well, there are $k!$ possible reorderings of the people on the first $k$ places, so for each ordering of the unchosen people in the $n-k$ unchosen places, there are $k!$ reorderings of the chosen people in which all the chosen occupy the first $k$ places. But there are $(n-k)!$ reorderings of the unchosen people, and for each of them, $k!$ reorderings of the chosen ones, so all together $k! (n-k)!$ such orderings in which the chosen ones get selected.

So, out of all $n!$ reorderings of all people, one particular set of size gets chosen $k!(n-k)!$ times. Since in each choosing, I choose one set, there must therefore be $\frac{n!}{k!(n-k)!}$ different sets of size $k$.

Tags:

Combinatorics

Related

volume of a cube and a ball in n-dimensions? If every element of $H$ and $G/H$ is a square, then prove that so is every element of $G$. Logic behind dividing negative numbers Number of elements of order $2$ in $S_n$ Conversion of rotation matrix to quaternion Integral $\int^1_0\frac{\ln{x} \ \mathrm{Li}_2(x)}{1-x}dx$ How to express “b is a power of 10” – Typographical Number Theory in Gödel Escher Bach Are there finitely many Pythagorean triples whose smallest two numbers differ by 1? Inequality of integrals $\int_0^1(f(x))^2 dx \geq 4$ if $\int_0^1xf(x) dx=\int_0^1f(x) dx = 1$ Why we consider log likelihood instead of Likelihood in Gaussian Distribution Integral of $\int_0^\infty\frac{1}{e^{x}-x} dx$ "Nice proof" that the unit of the left Kan extension of $F$ is an isomorphism, if $F$ is fully faithful

Recent Posts