Welcome everyone to this section of the course on combinatorics, where we're going to discuss factorial
permutations and combinations.
Now combinatorics is often referred to as a study of counting, and you may be wondering, study counting,
That's easy.
One, two, three, four, five, six, etc..
Problem solved.
What is there to actually study?
I thought counting was a given.
Well, not quite.
Combinatorics helps us count things when the results may not be immediately clear.
In fact, many real life business challenges and data science decisions are directly related to the
ability to count possible combinations or permutations of an object or set of objects.
Now we can use combinatorics to address real business questions, for example.
Imagine you're running a subscription box company such as something like Stitch Fix, where you actually
combine different clothing items and send them to a user or something like Chewy, where you had a dog
toys or cat toys, you put them in a box and deliver them to the user.
Some questions that could come up are how many possible combinations of products are there that can
be delivered to a customer?
Or imagine you're running a feedback survey company.
How many different feedback scores are possible for a given number of questions with each reporting
1 to 5 star ratings?
That is to say, if you have five survey questions where each question asks the user to rate between
one and five stars, how many actual different possible feedback scores are there?
Or if you're running an online marketplace such as Amazon, how many combinations of products are possible
within a customer's budget?
Or maybe even for a food delivery business.
How many different possible order combinations can be created given a certain subset of possible food
items from the menu?
These aren't going to be immediately clear, which is why we need combinatorics to answer these questions.
Using the power of factorial permutations and combinations, we can actually directly find answers to
these questions.
So in this section, of course, we're going to be exploring three key ideas and combinatorics that
can have direct applications to business situations like factorial permutations and combinations.
So I want to quickly explore these three concepts before we dive deeper into the details and get some
practice with them.
Let's begin with the factorial, which will serve as our foundation when we begin to learn about permutations
and combinations in mathematics.
The factorial is an operation on a non negative integer n denoted by an exclamation point, and it's
actually equal to the product of all positive integers, less than or equal to n.
Now that's a pretty wordy way of describing what a factorial is, so it's probably better to just go
through an example.
Simply put, the factorial is the product of all positive integers, less than or equal to n.
So if I have any factorial noted as an exclamation mark that's actually equal to n multiplied by n minus
one multiplied by n minus two multiplied by n minus three, and so on and so on until you get to the
last positive integer, which is one in this case.
So three times, two times one.
Let's plug in a real number so we understand what we're actually trying to convey here.
If I have ten factorial, then what I'm asking for is ten times, nine times, eight times, seven times
six, all the way down to one.
Which, if you're wondering, is actually equal to 3,628,800.
So you can see even relatively small numbers once you put in the factorial become really large numbers
because it's a giant product.
So if we actually think of factorial, there's this really interesting property that shows up.
So if we have ten factorial notice, it's ten times nine times, eight times seven and so on.
But we could grab everything past ten and realize that's actually it's own factorial.
So everything there is actually equal to nine factorial.
So that means ten factorial is simply equal to ten times nine factorial.
Or if we were to generalize this, it would be that RN factorial is equal to DN times RN minus one factorial.
This is a really convenient property of factorial is when we begin working with them inside a fractions.
For example, if you have MN factorial divided by MN minus one factorial, you could split this up at
the numerator and say MN factorial is actually equal to MN times and minus one factorial.
And due to the numerator section on top that is proportion of MN minus one factorial being equal to
a part of the denominator and minus one factorial.
These cancel out, which means you're just left with MN, and this sort of property is very useful in
permutations and combinations.
So understanding the mathematics of factorial allow us to calculate permutations and combinations which
directly allow us to answer some of those business challenge decisions at the very start of this lecture.
Let's begin by exploring permutations in more detail.
A permutation of a set of objects is an arrangement of the objects in a certain order.
The key words here are arrangement and certain order.
This means we can calculate all the possible arrangements or in other words, permutations of a set
of objects.
For example, imagine you're ordering three items from Amazon that will be delivered on separate days,
so each item has to be delivered on a separate day.
How many permutations are there of the order of their arrivals?
So if you have three items and you know they all have to be delivered on separate days, how many different
permutations or arrangements could those packages arrive in?
Well, let's imagine the items are A, B, and C.
You could have item A arrive first, followed by B, then followed by C, or you could have item B arrived
first, followed by A, followed by C.
And you can actually write out all these possible permutations of the order of their arrival, a ABC
cab, BCA, etc. That's easy to do with just three items.
But what if you have ten items or 15 items?
How do you actually calculate the permutations?
Well, for simple examples like this one, the number of possible permutations is simply n factorial.
Thus, the order of delivery of three items can be delivered in six different permutations, which is
equal to three factorial.
So three factorial.
If we were to apply that formula and factorial, we have three items, which means it's going to be
three times two times one, which is six different permutations.
So permutations in a simple example like this one is just equal to n factorial.
That's the number of ways you can arrange or order a set of objects.
Now, keep in mind, there are other considerations for permutations, such as the number of permutations
possible for a subset of items or permutations that allow for repetition, such as license plates.
But we'll talk about those in more detail later on.
The last thing I want to point out here is combinatorics, such as permutation.
Calculations are even used in high stakes situations.
They were used as part of a solution during World War Two by the allies to estimate the number of tanks
being manufactured by Germany simply based on the sampling of the serial part numbers of different tank
parts.
Now let's move on to talking about combinations.
A combination is an unordered selection of objects.
Remember, permutations, arrangement and ordering mattered for combinations.
It won't matter.
So, for example, a group of people chosen from a larger pool or a group of people for a baseball team,
as if you're picking teams for different soccer teams or baseball teams back in school, maybe you have
a giant group of people and you start splitting them up into different combinations of teams.
You could also have combinations that allow for repetition.
For example, trying to figure out the different combinations that you could use based off pizza toppings
to create your pizza, you could technically order double pepperoni.
So there's different calculations depending on the situation.
The main thing to notice here is how unlike permutations, ordering or arrangement doesn't matter here.
So, for example, if you have a soccer team with players A, B and C, it doesn't really matter what
order those players are standing in.
You still have the same soccer team or football team such as CBA versus ABC.
Those are the same combination.
Now if you're dealing with something where ordering does matter, like the delivery ordering of packages,
that's a permutation.
So the permutation ABC is not the same as the permutation CBA.
This can be a little confusing when you first encounter it because sometimes it's not clear whether
the question is asking for a combination or a permutation.
It just takes a little bit of practice to understand what is the correct combinatorial solution to apply.
But just keep in mind, combinations order doesn't matter.
So ABC is the same combination as CBA permutation.
Arrangement ordering does matter.
That means ABC is not the same permutation as CBA.
Now let's actually show you how to calculate combinations.
Calculating combinations also makes use of factorial and has its own notation.
So formally speaking, if we want the count for the number of combinations from a set of N objects taken
K at a time.
So for example, NN could be 100 people and we want to figure out how many combinations of ten person
baseball teams can we make.
That means K is equal to ten.
We can plug it in to the combination formula.
That looks like this.
And keep in mind, they're sometimes different ways to actually notate this.
But some people like to use the left handed way where it's a giant C for combination and then NW objects
on top K at a time or some people like this brackets or brace notation and on top and k but if you look
over on the right hand side, that's probably the most important way because that's the actual formula
for solving the count for the number of combinations.
It simply n factorial divided by k factorial multiplied by n minus k factorial.
For example, imagine a consumer dog toy box company that delivers boxes with five dog toys out of their
selection of 20 dog toys in their warehouse.
And maybe we want to figure out how many different possible combinations of boxes are there.
Well, I know I want five possible toys in my combination.
That's going to be k.
The number of objects I have to select from is 20 so and is equal to 20 K is equal to five.
And if I just plug in those numbers and begin crunching this out.
I can actually use the property of NW factorial being equal to NW times and minus one factorial and
begin to realize I can cancel out the 15 factorial as showing up in both the numerator and the denominator.
And then I simply solve this to get 15,504 different combinations of five dog toys in a box out of the
selection of 20 dog toys.
I should point out that for this particular formula of combinations, we weren't considering the fact
that I could repeat dog toys.
I was assuming that each dog toy had to be different in the box.
If I allowed for repeat dog toys, that would actually be a different formula.
But we'll cover combinations with repetition later on.
So understanding factorial permutations and combinations has become a key part of creating robust logistics
frameworks since clearly understanding package ordering and combinations can help create efficiencies
for customers.
There are other ideas around permutations and combinations that we haven't discussed yet.
For example, I mentioned the fact that you could use repetition.
What if you allow the same dog toys to be selected twice for a single delivery package?
In the previous example, we'll have to think a little bit harder about that because it's not the same
formula as if you weren't allowing for a repetition.
This again was combination with repetition, which follows a different formula.
And in the previous example, we did not allow for repetition.
In the next few lectures, we're going to dive deeper into the understanding of factorial permutations
and combinations.
Who knew there could be so much to just counting?
We'll see you at the next lecture.