Recap

The Blade Dancer

Can I get a recap of why we divide by 3 factorial? Thanks.

Nate

@The-Blade-Dancer Let's start with talking about what factorial means, as a quick refresher.
$$n! = n(n-1)(n-2)...(3)(2)(1)$$

But that's just the mathematical definition. What does a factorial represent? A common description is the number of rearrangements of $n$ objects. The formal way of stating this is "the number of permutations of a set of $n$ elements," but it really just means that if we have $n$ things, we can arrange them $n!$ unique ways. The motivation for this is pretty simple: if we're ordering our $n$ objects, we have $n$ choices for the first object, $n - 1$ for the second, and so on.

So how does this play into how we choose three of our nine dots? If we choose the top right dot, the bottom right dot, and the bottom left dot, we form the same triangle as when we choose the bottom right dot, the bottom left dot, and the top right dot. In other words, the order in which we choose the dots does not matter.

If we calculate without taking this into account, we have 9 choices for the first dot, 8 choices for the second dot, and 7 choices for the third dot. But this implies that the order of the dots matters. How do we account for this? Well, for any given selection of three distinct dots, how many different orderings for them exist? That's exactly what factorial describes! Each unique selection of 3 dots has 3! possible orderings. So to go from our calculation where order matters, we divide out all of the possible rearrangements of our three dots, giving us the following final answer for how many possible ways to select three distinct dots from a group of nine there are:
$$\frac{9 \cdot 8 \cdot7}{3!} = \frac{9 \cdot 8 \cdot7}{6} = 84$$

Then as Professor Loh points out, you have to subtract out some of those groups of three dots. But that's how we get the total number of dots to start!

The Blade Dancer

But what if the bottom factorial exceeds the value of the product at the top? That happens a lot and I don't know what to do.

Nate

Good question! The short answer is that if you're using the binomial formula, the factorial will never exceed the value of the product on the top. For the sake of still having concrete numbers to work with, let's keep talking about trying to select 3 items from a group of size $n$, where the order in which we choose the items doesn't matter, but keep in mind that the logic we're using here also works for selecting $k$ items from a group of size $n$, where $k$ and $n$ are any non-negative integer.

First off, if $n < 3$, then our expression doesn't make any sense. We can't select 3 distinct items from a group of size 2. Whenever $n < k$, we say that $n$ choose $k$, typically written $\binom{n}{k}$, is 0.

What about when $n \geq k$? Can we state confidently that $\binom{n}{k}$ will always be a whole number?

There's two ways to answer this question. The first is to say that $\binom{n}{k}$ represents something, the number of ways to choose $k$ things from a group of size $n$, and that there's always a positive integer number of ways to do that. But to me, that's not really a satisfying answer. It doesn't go into the math of why the formula always works out to be a nice number.

Let's go back to selecting groups of size three out of a larger group. What's the smallest $n$ for which there's a nonzero number of ways to do this? $n = 3$, we need at least three objects to be able to select three of them. How many ways can we select three? Well, we have 3 options for the first selection, 2 for the second, 1 for the third, and then we need to divide out the different orders:
$$\binom{3}{3} = \frac{3 \cdot 2 \cdot 1}{3!} = 1$$
And that makes sense! The only way to choose three elements from a set of size three is to choose the whole set.

Then as we increase the size of the set we select from, this number will only go up. If we increase $n$ by one, what happens?
$$\binom{4}{3} = \frac{4 \cdot 3 \cdot 2}{3!} = 4 \binom{3}{3}$$
Each time we increase the size of the set we select from, without changing the number of elements we selecting from it, the number of ways to do so increases. This should make sense - more elements means more possible selections.

So we've seen that for a non-negative integer $n$ and $k \leq n$, $\binom{n}{k} \geq 1$. But we haven't talked about why we know $\binom{n}{k}$ must be an integer, mathematically speaking. This is a little complicated, but here's a rough intuitive sense that helped me when I first encountered this: if you have $k!$ on the bottom if your expression, you're multiplying $k$ consecutive positive integers together on the top: $n, n-1, \ldots, n-k+1 $. Then you get a rough intuitive sense that for whatever values you have in $k!$, they will also exist in the product of the $k$ consecutive integers. For example, if $k = 7$, you can see that any set of 7 consecutive positive integers must have one integer with a factor of 7.

I hope this helps, and if any part of this is unclear, let me know and I'll try to explain it better.