1 00:00:05,580 --> 00:00:10,470 Welcome everyone to this section of the course on combinatorics, where we're going to discuss factorial 2 00:00:10,500 --> 00:00:12,450 permutations and combinations. 3 00:00:13,500 --> 00:00:19,860 Now combinatorics is often referred to as a study of counting, and you may be wondering, study counting, 4 00:00:19,860 --> 00:00:20,460 That's easy. 5 00:00:20,460 --> 00:00:22,630 One, two, three, four, five, six, etc.. 6 00:00:22,650 --> 00:00:23,510 Problem solved. 7 00:00:23,520 --> 00:00:24,960 What is there to actually study? 8 00:00:24,990 --> 00:00:26,520 I thought counting was a given. 9 00:00:26,730 --> 00:00:28,140 Well, not quite. 10 00:00:28,380 --> 00:00:33,030 Combinatorics helps us count things when the results may not be immediately clear. 11 00:00:33,180 --> 00:00:38,070 In fact, many real life business challenges and data science decisions are directly related to the 12 00:00:38,070 --> 00:00:43,710 ability to count possible combinations or permutations of an object or set of objects. 13 00:00:44,890 --> 00:00:49,420 Now we can use combinatorics to address real business questions, for example. 14 00:00:50,140 --> 00:00:55,270 Imagine you're running a subscription box company such as something like Stitch Fix, where you actually 15 00:00:55,270 --> 00:01:00,760 combine different clothing items and send them to a user or something like Chewy, where you had a dog 16 00:01:00,760 --> 00:01:04,440 toys or cat toys, you put them in a box and deliver them to the user. 17 00:01:04,450 --> 00:01:09,700 Some questions that could come up are how many possible combinations of products are there that can 18 00:01:09,700 --> 00:01:11,230 be delivered to a customer? 19 00:01:12,520 --> 00:01:15,260 Or imagine you're running a feedback survey company. 20 00:01:15,280 --> 00:01:19,720 How many different feedback scores are possible for a given number of questions with each reporting 21 00:01:19,720 --> 00:01:21,150 1 to 5 star ratings? 22 00:01:21,160 --> 00:01:26,230 That is to say, if you have five survey questions where each question asks the user to rate between 23 00:01:26,230 --> 00:01:30,430 one and five stars, how many actual different possible feedback scores are there? 24 00:01:31,860 --> 00:01:37,500 Or if you're running an online marketplace such as Amazon, how many combinations of products are possible 25 00:01:37,500 --> 00:01:39,300 within a customer's budget? 26 00:01:41,080 --> 00:01:43,330 Or maybe even for a food delivery business. 27 00:01:43,330 --> 00:01:48,010 How many different possible order combinations can be created given a certain subset of possible food 28 00:01:48,010 --> 00:01:49,450 items from the menu? 29 00:01:49,510 --> 00:01:54,700 These aren't going to be immediately clear, which is why we need combinatorics to answer these questions. 30 00:01:56,080 --> 00:02:01,270 Using the power of factorial permutations and combinations, we can actually directly find answers to 31 00:02:01,270 --> 00:02:02,170 these questions. 32 00:02:03,220 --> 00:02:07,570 So in this section, of course, we're going to be exploring three key ideas and combinatorics that 33 00:02:07,570 --> 00:02:13,030 can have direct applications to business situations like factorial permutations and combinations. 34 00:02:14,000 --> 00:02:19,220 So I want to quickly explore these three concepts before we dive deeper into the details and get some 35 00:02:19,220 --> 00:02:20,180 practice with them. 36 00:02:21,520 --> 00:02:26,650 Let's begin with the factorial, which will serve as our foundation when we begin to learn about permutations 37 00:02:26,650 --> 00:02:29,110 and combinations in mathematics. 38 00:02:29,110 --> 00:02:35,890 The factorial is an operation on a non negative integer n denoted by an exclamation point, and it's 39 00:02:35,890 --> 00:02:40,450 actually equal to the product of all positive integers, less than or equal to n. 40 00:02:40,660 --> 00:02:45,520 Now that's a pretty wordy way of describing what a factorial is, so it's probably better to just go 41 00:02:45,520 --> 00:02:46,450 through an example. 42 00:02:47,620 --> 00:02:52,720 Simply put, the factorial is the product of all positive integers, less than or equal to n. 43 00:02:53,330 --> 00:03:01,370 So if I have any factorial noted as an exclamation mark that's actually equal to n multiplied by n minus 44 00:03:01,370 --> 00:03:08,690 one multiplied by n minus two multiplied by n minus three, and so on and so on until you get to the 45 00:03:08,690 --> 00:03:11,180 last positive integer, which is one in this case. 46 00:03:11,180 --> 00:03:12,860 So three times, two times one. 47 00:03:13,190 --> 00:03:17,030 Let's plug in a real number so we understand what we're actually trying to convey here. 48 00:03:17,480 --> 00:03:23,570 If I have ten factorial, then what I'm asking for is ten times, nine times, eight times, seven times 49 00:03:23,570 --> 00:03:25,550 six, all the way down to one. 50 00:03:26,910 --> 00:03:32,200 Which, if you're wondering, is actually equal to 3,628,800. 51 00:03:32,220 --> 00:03:37,770 So you can see even relatively small numbers once you put in the factorial become really large numbers 52 00:03:37,770 --> 00:03:39,330 because it's a giant product. 53 00:03:41,100 --> 00:03:45,830 So if we actually think of factorial, there's this really interesting property that shows up. 54 00:03:45,840 --> 00:03:50,340 So if we have ten factorial notice, it's ten times nine times, eight times seven and so on. 55 00:03:50,730 --> 00:03:55,440 But we could grab everything past ten and realize that's actually it's own factorial. 56 00:03:55,800 --> 00:03:58,820 So everything there is actually equal to nine factorial. 57 00:03:58,830 --> 00:04:03,770 So that means ten factorial is simply equal to ten times nine factorial. 58 00:04:03,780 --> 00:04:11,430 Or if we were to generalize this, it would be that RN factorial is equal to DN times RN minus one factorial. 59 00:04:11,520 --> 00:04:17,610 This is a really convenient property of factorial is when we begin working with them inside a fractions. 60 00:04:18,790 --> 00:04:26,890 For example, if you have MN factorial divided by MN minus one factorial, you could split this up at 61 00:04:26,890 --> 00:04:32,440 the numerator and say MN factorial is actually equal to MN times and minus one factorial. 62 00:04:32,500 --> 00:04:38,680 And due to the numerator section on top that is proportion of MN minus one factorial being equal to 63 00:04:38,680 --> 00:04:41,140 a part of the denominator and minus one factorial. 64 00:04:41,170 --> 00:04:46,930 These cancel out, which means you're just left with MN, and this sort of property is very useful in 65 00:04:46,930 --> 00:04:48,760 permutations and combinations. 66 00:04:50,400 --> 00:04:55,830 So understanding the mathematics of factorial allow us to calculate permutations and combinations which 67 00:04:55,830 --> 00:05:00,930 directly allow us to answer some of those business challenge decisions at the very start of this lecture. 68 00:05:01,020 --> 00:05:04,230 Let's begin by exploring permutations in more detail. 69 00:05:05,660 --> 00:05:11,240 A permutation of a set of objects is an arrangement of the objects in a certain order. 70 00:05:11,270 --> 00:05:15,110 The key words here are arrangement and certain order. 71 00:05:15,350 --> 00:05:20,720 This means we can calculate all the possible arrangements or in other words, permutations of a set 72 00:05:20,720 --> 00:05:21,650 of objects. 73 00:05:22,550 --> 00:05:28,400 For example, imagine you're ordering three items from Amazon that will be delivered on separate days, 74 00:05:28,400 --> 00:05:31,430 so each item has to be delivered on a separate day. 75 00:05:31,670 --> 00:05:35,840 How many permutations are there of the order of their arrivals? 76 00:05:35,840 --> 00:05:40,550 So if you have three items and you know they all have to be delivered on separate days, how many different 77 00:05:40,550 --> 00:05:44,600 permutations or arrangements could those packages arrive in? 78 00:05:45,710 --> 00:05:49,220 Well, let's imagine the items are A, B, and C. 79 00:05:49,850 --> 00:05:56,840 You could have item A arrive first, followed by B, then followed by C, or you could have item B arrived 80 00:05:56,840 --> 00:05:59,330 first, followed by A, followed by C. 81 00:05:59,450 --> 00:06:05,360 And you can actually write out all these possible permutations of the order of their arrival, a ABC 82 00:06:05,390 --> 00:06:09,980 cab, BCA, etc. That's easy to do with just three items. 83 00:06:09,980 --> 00:06:12,650 But what if you have ten items or 15 items? 84 00:06:12,650 --> 00:06:14,810 How do you actually calculate the permutations? 85 00:06:15,560 --> 00:06:21,080 Well, for simple examples like this one, the number of possible permutations is simply n factorial. 86 00:06:21,110 --> 00:06:26,300 Thus, the order of delivery of three items can be delivered in six different permutations, which is 87 00:06:26,300 --> 00:06:27,910 equal to three factorial. 88 00:06:27,950 --> 00:06:29,720 So three factorial. 89 00:06:29,720 --> 00:06:34,550 If we were to apply that formula and factorial, we have three items, which means it's going to be 90 00:06:34,550 --> 00:06:38,090 three times two times one, which is six different permutations. 91 00:06:38,090 --> 00:06:42,660 So permutations in a simple example like this one is just equal to n factorial. 92 00:06:42,680 --> 00:06:46,220 That's the number of ways you can arrange or order a set of objects. 93 00:06:48,030 --> 00:06:52,800 Now, keep in mind, there are other considerations for permutations, such as the number of permutations 94 00:06:52,800 --> 00:06:58,960 possible for a subset of items or permutations that allow for repetition, such as license plates. 95 00:06:58,980 --> 00:07:01,620 But we'll talk about those in more detail later on. 96 00:07:01,920 --> 00:07:06,120 The last thing I want to point out here is combinatorics, such as permutation. 97 00:07:06,120 --> 00:07:09,530 Calculations are even used in high stakes situations. 98 00:07:09,540 --> 00:07:14,570 They were used as part of a solution during World War Two by the allies to estimate the number of tanks 99 00:07:14,580 --> 00:07:20,970 being manufactured by Germany simply based on the sampling of the serial part numbers of different tank 100 00:07:20,970 --> 00:07:21,660 parts. 101 00:07:23,340 --> 00:07:26,220 Now let's move on to talking about combinations. 102 00:07:26,430 --> 00:07:30,150 A combination is an unordered selection of objects. 103 00:07:30,150 --> 00:07:34,350 Remember, permutations, arrangement and ordering mattered for combinations. 104 00:07:34,350 --> 00:07:35,160 It won't matter. 105 00:07:35,190 --> 00:07:41,190 So, for example, a group of people chosen from a larger pool or a group of people for a baseball team, 106 00:07:41,280 --> 00:07:46,830 as if you're picking teams for different soccer teams or baseball teams back in school, maybe you have 107 00:07:46,830 --> 00:07:51,420 a giant group of people and you start splitting them up into different combinations of teams. 108 00:07:51,750 --> 00:07:54,630 You could also have combinations that allow for repetition. 109 00:07:54,630 --> 00:07:59,610 For example, trying to figure out the different combinations that you could use based off pizza toppings 110 00:07:59,610 --> 00:08:03,040 to create your pizza, you could technically order double pepperoni. 111 00:08:03,060 --> 00:08:05,760 So there's different calculations depending on the situation. 112 00:08:06,490 --> 00:08:13,160 The main thing to notice here is how unlike permutations, ordering or arrangement doesn't matter here. 113 00:08:13,180 --> 00:08:20,650 So, for example, if you have a soccer team with players A, B and C, it doesn't really matter what 114 00:08:20,650 --> 00:08:22,550 order those players are standing in. 115 00:08:22,570 --> 00:08:28,610 You still have the same soccer team or football team such as CBA versus ABC. 116 00:08:28,630 --> 00:08:30,640 Those are the same combination. 117 00:08:30,820 --> 00:08:36,700 Now if you're dealing with something where ordering does matter, like the delivery ordering of packages, 118 00:08:36,700 --> 00:08:38,049 that's a permutation. 119 00:08:38,049 --> 00:08:42,789 So the permutation ABC is not the same as the permutation CBA. 120 00:08:42,820 --> 00:08:47,800 This can be a little confusing when you first encounter it because sometimes it's not clear whether 121 00:08:47,800 --> 00:08:51,230 the question is asking for a combination or a permutation. 122 00:08:51,250 --> 00:08:56,820 It just takes a little bit of practice to understand what is the correct combinatorial solution to apply. 123 00:08:56,830 --> 00:09:00,400 But just keep in mind, combinations order doesn't matter. 124 00:09:00,400 --> 00:09:04,330 So ABC is the same combination as CBA permutation. 125 00:09:04,330 --> 00:09:06,190 Arrangement ordering does matter. 126 00:09:06,190 --> 00:09:09,610 That means ABC is not the same permutation as CBA. 127 00:09:10,700 --> 00:09:13,490 Now let's actually show you how to calculate combinations. 128 00:09:13,700 --> 00:09:18,050 Calculating combinations also makes use of factorial and has its own notation. 129 00:09:19,270 --> 00:09:26,140 So formally speaking, if we want the count for the number of combinations from a set of N objects taken 130 00:09:26,140 --> 00:09:27,310 K at a time. 131 00:09:27,310 --> 00:09:33,910 So for example, NN could be 100 people and we want to figure out how many combinations of ten person 132 00:09:33,910 --> 00:09:35,400 baseball teams can we make. 133 00:09:35,410 --> 00:09:36,810 That means K is equal to ten. 134 00:09:36,820 --> 00:09:39,100 We can plug it in to the combination formula. 135 00:09:40,040 --> 00:09:41,510 That looks like this. 136 00:09:41,510 --> 00:09:44,840 And keep in mind, they're sometimes different ways to actually notate this. 137 00:09:44,840 --> 00:09:50,060 But some people like to use the left handed way where it's a giant C for combination and then NW objects 138 00:09:50,060 --> 00:09:57,170 on top K at a time or some people like this brackets or brace notation and on top and k but if you look 139 00:09:57,170 --> 00:10:01,490 over on the right hand side, that's probably the most important way because that's the actual formula 140 00:10:01,490 --> 00:10:04,340 for solving the count for the number of combinations. 141 00:10:04,340 --> 00:10:10,010 It simply n factorial divided by k factorial multiplied by n minus k factorial. 142 00:10:11,320 --> 00:10:18,460 For example, imagine a consumer dog toy box company that delivers boxes with five dog toys out of their 143 00:10:18,460 --> 00:10:21,540 selection of 20 dog toys in their warehouse. 144 00:10:21,550 --> 00:10:25,930 And maybe we want to figure out how many different possible combinations of boxes are there. 145 00:10:26,740 --> 00:10:31,150 Well, I know I want five possible toys in my combination. 146 00:10:31,150 --> 00:10:32,230 That's going to be k. 147 00:10:32,440 --> 00:10:39,700 The number of objects I have to select from is 20 so and is equal to 20 K is equal to five. 148 00:10:39,940 --> 00:10:43,420 And if I just plug in those numbers and begin crunching this out. 149 00:10:44,070 --> 00:10:50,400 I can actually use the property of NW factorial being equal to NW times and minus one factorial and 150 00:10:50,400 --> 00:10:56,370 begin to realize I can cancel out the 15 factorial as showing up in both the numerator and the denominator. 151 00:10:56,820 --> 00:11:06,090 And then I simply solve this to get 15,504 different combinations of five dog toys in a box out of the 152 00:11:06,090 --> 00:11:08,100 selection of 20 dog toys. 153 00:11:08,130 --> 00:11:13,260 I should point out that for this particular formula of combinations, we weren't considering the fact 154 00:11:13,260 --> 00:11:15,200 that I could repeat dog toys. 155 00:11:15,210 --> 00:11:18,830 I was assuming that each dog toy had to be different in the box. 156 00:11:18,840 --> 00:11:22,530 If I allowed for repeat dog toys, that would actually be a different formula. 157 00:11:22,530 --> 00:11:25,890 But we'll cover combinations with repetition later on. 158 00:11:27,660 --> 00:11:34,140 So understanding factorial permutations and combinations has become a key part of creating robust logistics 159 00:11:34,140 --> 00:11:39,270 frameworks since clearly understanding package ordering and combinations can help create efficiencies 160 00:11:39,270 --> 00:11:40,260 for customers. 161 00:11:41,440 --> 00:11:45,610 There are other ideas around permutations and combinations that we haven't discussed yet. 162 00:11:45,640 --> 00:11:48,720 For example, I mentioned the fact that you could use repetition. 163 00:11:48,730 --> 00:11:52,840 What if you allow the same dog toys to be selected twice for a single delivery package? 164 00:11:52,870 --> 00:11:57,340 In the previous example, we'll have to think a little bit harder about that because it's not the same 165 00:11:57,340 --> 00:12:00,490 formula as if you weren't allowing for a repetition. 166 00:12:00,790 --> 00:12:04,570 This again was combination with repetition, which follows a different formula. 167 00:12:04,570 --> 00:12:07,660 And in the previous example, we did not allow for repetition. 168 00:12:09,120 --> 00:12:13,860 In the next few lectures, we're going to dive deeper into the understanding of factorial permutations 169 00:12:13,860 --> 00:12:14,920 and combinations. 170 00:12:14,940 --> 00:12:17,280 Who knew there could be so much to just counting? 171 00:12:17,370 --> 00:12:18,870 We'll see you at the next lecture.