We said before that when we try to find the number of permutations we can make with a set of objects,
we have to consider position.
We think permutations or position.
But when we talk about combinations, that position no longer matters.
So we start here with this table that we built before, where we looked at these two formulas for permutations.
Now we want to look at the repeats and no repeats situation for combinations.
Remember, permutations is order matters.
Think position combinations is order does not matter.
Now, the easier formula to start with for combinations is the no repeats formula.
Let's look back at the example we are using before.
Of the three playing cards where we started with the King, the Queen and the jack, we said that in
the no repeat situation for permutations.
Let's say that we're starting with this set of three cards and we want the number of permutations when
we choose two of these cards.
Well, that's the situation where N is equal to three and K is equal to two.
And in this formula for permutations with no repeats, we said that we ended up with three factorial
divided by quantity, three minus two factorial, which was equal to three factorial divided by one
factorial or six divided by one which was six.
And that makes sense because if we choose two of these three cards, we can either choose the king and
the queen, or we could choose the king and the jack, or we could choose the queen and the jack.
These are the only three combinations of two cards that we can pick from this group.
So we have three possible arrangements here.
But when we're thinking about permutations, remember that the order matters.
So within each one of these, we have to consider the order in which we could pull these cards.
With this set of two here, we could either pull king and queen or the opposite.
We could pull the king second with the queen first so we can arrange this set two different ways.
Same thing over here with the Queen and the Jack.
We could arrange Queen Jack or we could arrange Jack Queen.
And same thing over here.
Either King Jack and then Jack King.
And so we end up with six different arrangements.
If we're starting with a set of three and choosing two and the order matters.
And that's why we end up with six permutations.
Now, as you can imagine, what happens here with combinations and no repeats is that we're looking
at the exact same thing as we did here, except that order doesn't matter, which means that this whole
second row here would disappear in the combination row.
King Queen is the same as Queen.
King King Jack is the same as Jack King, etc. So the order doesn't matter.
It's just the number of combinations, just the different distinct sets of two or pairs of two that
we can pull from this set of three.
And so what this formula ends up being over here for combinations with no repeats is actually exactly
the same as this formula permutations with no repeats.
We still have n factorial in the numerator and in the denominator we still have quantity and minus k
factorial like this and minus k factorial, but we just divide by k factorial.
And that would make sense here because we're choosing two items.
And so if we take this permutations formula, this is the set of all the permutations.
Notice here how we just divided this by two.
We took away half of the items, we divide it by two, which means we divide it by K factorial because
K is two and two, factorial is two.
And this formula holds up for any and choose K that we pick.
This formula specifically is combinations with no repeats.
Formula is so important.
We use it so often that we give it a special name, we call it the binomial coefficient and you'll see
it written many ways.
You'll often see n choose k the combinations we can make from n items when we choose K of them.
Sometimes you'll see it as c and then n k like this, which means the same thing.
We also write the binomial coefficient this way in parentheses with the n on the top, the k on the
bottom, and this means n choose k.
It's the combination made from an items when we pick K of them.
And all of this notation is referring to the same combinations.
No repeats binomial coefficient formula.
This is also the formula that lotteries often use.
For instance, it's often common in a lottery for them to choose six numbers of the numbers one through
49.
So if you think about the numbers, one through 49.
One, two, three, etc., all the way up to 49 and the lottery is going to draw six of those numbers
with repeats not allowed.
And the idea, of course, is that if your lottery ticket matches all six of the numbers drawn, then
you win the big jackpot.
But if we use this formula to calculate the number of combinations that are possible, when the lottery
can pick any numbers between one and 49.
Of course we could plug in here and find that the number of combinations is 49 factorial divided by.
If we're choosing six numbers, which we often do, we would say six factorial and then 49 minus six
factorial.
This value here, of course, simplifying to just 43 factorial.
Which means that we could rewrite this as 49 times 48, all the way down to 44, at which point the
43 factorial.
Will cancel out the rest of the factorial in the numerator.
So we have 49 all the way down to 44.
The product of those integers.
And then we have six factorial in the denominator.
And if we use a calculator to do the math here, what we find is that this comes out to a little bit
over 13.5 million, even 13.6 million, which means that if you're playing a lottery ticket, trying
to match exactly six numbers, you have a one in about 13.6, a little more, 13.6 million chance of
matching exactly those six numbers.
So that's the idea here with this lower right hand corner.
And then the last idea is combinations.
When we can repeat values, this one's probably the hardest to understand, but the easiest way to visualize
it is to think about an example.
So let's say, for instance, we'll set up a table here.
Let's say, for instance, that we are an online health food store, and as we're shipping products
out to customers, they order from us, we pack their order, we ship it out to them.
And before we send out the box, we want to include three little small samples of other products in
every shipment so that we encourage customers to try new products.
For instance, maybe we throw in a little sample protein powder, hoping that they will try that protein
powder like it, and then order a full size product from us in the future.
So let's say that in all the shipments going out this month, we have eight different samples that were
including.
So a through here represents sample A sample, B sample C, maybe A is the protein powder, B is a piece
of chocolate, maybe sample C is a small bag of healthier candies.
So we have these eight different samples here and all we want to do is include three samples and let's
say we're allowing for repeats.
We just want to grab three samples from our eight different bins here and toss three little samples
into each box going out to customers.
What we want to visualize then is that we have these eight different bins here.
If you can imagine eight bins full of these little sample size products.
And all we want to do is grab three.
So for instance, that means that we could grab, let's say two of sample A and one of sample D, we
could also do one of sample C, one of sample E and one of sample F, or we could do F, F and G, and
of course, many, many other combinations when we're allowing for repeats.
These are just examples.
The idea here is that we always have to choose exactly where we're putting each of our three Xs in this
diagram.
Once we know where we're putting each of the three Xs, then the rest is sort of determined for us.
In other words, at a basic level, once we know we're choosing two A's and a DX, we know that we don't
have anything in B, C, E, f, G, or H, And so if you think then about sort of dividers between
these buckets, So if we imagine dividers between each sample bucket like this, we have seven dividers
because we have eight different sample types.
We could really almost say that we're choosing ten things.
For instance, with this first row here, if we have ten spots, we're saying that we're choosing two
of sample A, so we're putting an X here and an X here.
Then we're putting three dividers.
So we're saying then we have three dividers.
Until we get to DX, we're putting another X once we arrive at DX and then we have four more dividers,
1 to 3 four.
That's the first example.
In this second example, if we look at the dividers here between each bin like this.
We're saying that the arrangement we're choosing here, if we put it below these lines here, is divider,
divider for these first two, and then we're choosing a sample from C and then two more dividers and
then a sample from E, and then another divider, and then a sample from F, and then two more dividers.
That is our choice.
That is our arrangement in this second example here.
So you can kind of get an idea that what this really comes down to is a choice of ten spots of how to
fill ten spots.
We need three sample spots.
We're choosing three X's, we're positioning three X's, and then the seven dividers that came from
the divisions between the eight samples.
We fill in the rest of the choices with those seven dividers.
And so instead of this idea of the binomial coefficient and choose K, like we said down here and choose
K where we're picking from end things and we're choosing K of them, this time we're picking from set
up sort of an analogy to our binomial coefficient here.
We're picking from N plus K minus one because here we had eight samples, so we had an equal to eight,
but we have to position the seven dividers.
There's always one fewer divider than the number here of buckets that we're dealing with.
So the number of dividers we have is always n minus one and the number of x's that we're placing is
K, So we're adding together and minus one and K, So you can think about this as N minus one plus K,
or we write it as n plus K minus one.
So we're picking from a set of KN plus K minus one or in other words, just replacing in this formula
N with n plus K minus one when we're still choosing K objects.
So in this notation it looks like n plus k minus one choose k.
And in our formula here instead of PN factorial, we have n plus k minus one factorial and in the denominator
we'll still have k factorial here, but we're replacing n with n plus k minus one.
So we have here instead of n minus k will replace this n with n plus k minus one.
So we get n plus k minus one instead of n right here.
And then we still have minus K, so minus K.
Well when we do that we get this positive and negative K to cancel, leaving us with just n minus one,
which means that we get n minus one factorial here in the denominator.
So this formula is exactly the same as this one.
We're just replacing N with n plus K minus one.
And we see that logic based on this bucket divider illustration where we realize, like in this example
that we had to fill ten spots, we had to fill N plus K minus one spots with K choices, we pick where
our K items are going to go.
We have K number of X's and we position those and then we fill in the rest with dividers.
So in this example here with our online health food marketplace, if we're choosing K equals three items
out of our eight samples and we're allowing repeats, then we have eight, plus three is 11, minus
one is ten.
There's our ten buckets we have to fill.
So in the numerator here we end up with ten factorial.
Let's put that up here, we get ten factorial in the denominator, we have n equals eight and minus
one is seven.
So seven factorial.
And we said that we're choosing three.
So we have three factorial times, seven factorial, three factorial times seven factorial.
Well, we know that this seven factorial will cancel with the seven factorial that's nested inside this
ten factorial, leaving us with just ten times, nine times eight in the numerator.
And so when we do that math, ten times nine times eight is 720 divided by six because three factorial
is six.
The result there is 120 combinations.
So if we have eight different samples we can pick from, we're picking three of them and we're allowing
repeats.
We have 120 combinations that we can create in that scenario.
So even though combinatorics is the study of counting, hopefully looking further into factorial and
permutations and combinations gives you a much better idea of why these counting concepts are so valuable
to us and why these come in handy for so many different real world applications.