1 00:00:00,090 --> 00:00:05,040 We said before that when we try to find the number of permutations we can make with a set of objects, 2 00:00:05,040 --> 00:00:06,600 we have to consider position. 3 00:00:06,600 --> 00:00:08,790 We think permutations or position. 4 00:00:08,790 --> 00:00:13,640 But when we talk about combinations, that position no longer matters. 5 00:00:13,650 --> 00:00:20,130 So we start here with this table that we built before, where we looked at these two formulas for permutations. 6 00:00:20,130 --> 00:00:25,530 Now we want to look at the repeats and no repeats situation for combinations. 7 00:00:25,530 --> 00:00:28,110 Remember, permutations is order matters. 8 00:00:28,110 --> 00:00:31,820 Think position combinations is order does not matter. 9 00:00:31,830 --> 00:00:37,040 Now, the easier formula to start with for combinations is the no repeats formula. 10 00:00:37,050 --> 00:00:40,350 Let's look back at the example we are using before. 11 00:00:40,350 --> 00:00:49,140 Of the three playing cards where we started with the King, the Queen and the jack, we said that in 12 00:00:49,140 --> 00:00:52,440 the no repeat situation for permutations. 13 00:00:52,440 --> 00:00:57,720 Let's say that we're starting with this set of three cards and we want the number of permutations when 14 00:00:57,720 --> 00:00:59,730 we choose two of these cards. 15 00:00:59,730 --> 00:01:05,550 Well, that's the situation where N is equal to three and K is equal to two. 16 00:01:05,550 --> 00:01:12,450 And in this formula for permutations with no repeats, we said that we ended up with three factorial 17 00:01:12,450 --> 00:01:20,370 divided by quantity, three minus two factorial, which was equal to three factorial divided by one 18 00:01:20,370 --> 00:01:24,450 factorial or six divided by one which was six. 19 00:01:24,450 --> 00:01:31,980 And that makes sense because if we choose two of these three cards, we can either choose the king and 20 00:01:31,980 --> 00:01:41,730 the queen, or we could choose the king and the jack, or we could choose the queen and the jack. 21 00:01:41,730 --> 00:01:47,400 These are the only three combinations of two cards that we can pick from this group. 22 00:01:47,400 --> 00:01:49,950 So we have three possible arrangements here. 23 00:01:49,950 --> 00:01:54,510 But when we're thinking about permutations, remember that the order matters. 24 00:01:54,510 --> 00:01:59,730 So within each one of these, we have to consider the order in which we could pull these cards. 25 00:01:59,730 --> 00:02:05,400 With this set of two here, we could either pull king and queen or the opposite. 26 00:02:05,400 --> 00:02:13,200 We could pull the king second with the queen first so we can arrange this set two different ways. 27 00:02:13,230 --> 00:02:15,420 Same thing over here with the Queen and the Jack. 28 00:02:15,420 --> 00:02:19,500 We could arrange Queen Jack or we could arrange Jack Queen. 29 00:02:19,500 --> 00:02:20,700 And same thing over here. 30 00:02:20,700 --> 00:02:24,750 Either King Jack and then Jack King. 31 00:02:25,110 --> 00:02:28,230 And so we end up with six different arrangements. 32 00:02:28,230 --> 00:02:32,160 If we're starting with a set of three and choosing two and the order matters. 33 00:02:32,160 --> 00:02:34,890 And that's why we end up with six permutations. 34 00:02:34,890 --> 00:02:41,400 Now, as you can imagine, what happens here with combinations and no repeats is that we're looking 35 00:02:41,400 --> 00:02:48,300 at the exact same thing as we did here, except that order doesn't matter, which means that this whole 36 00:02:48,300 --> 00:02:53,340 second row here would disappear in the combination row. 37 00:02:53,370 --> 00:02:55,320 King Queen is the same as Queen. 38 00:02:55,320 --> 00:03:00,390 King King Jack is the same as Jack King, etc. So the order doesn't matter. 39 00:03:00,390 --> 00:03:06,120 It's just the number of combinations, just the different distinct sets of two or pairs of two that 40 00:03:06,120 --> 00:03:08,610 we can pull from this set of three. 41 00:03:08,610 --> 00:03:15,240 And so what this formula ends up being over here for combinations with no repeats is actually exactly 42 00:03:15,240 --> 00:03:18,570 the same as this formula permutations with no repeats. 43 00:03:18,570 --> 00:03:25,800 We still have n factorial in the numerator and in the denominator we still have quantity and minus k 44 00:03:25,800 --> 00:03:34,350 factorial like this and minus k factorial, but we just divide by k factorial. 45 00:03:34,350 --> 00:03:38,880 And that would make sense here because we're choosing two items. 46 00:03:38,880 --> 00:03:43,590 And so if we take this permutations formula, this is the set of all the permutations. 47 00:03:43,590 --> 00:03:46,560 Notice here how we just divided this by two. 48 00:03:46,590 --> 00:03:51,960 We took away half of the items, we divide it by two, which means we divide it by K factorial because 49 00:03:51,990 --> 00:03:54,360 K is two and two, factorial is two. 50 00:03:54,360 --> 00:03:59,520 And this formula holds up for any and choose K that we pick. 51 00:03:59,550 --> 00:04:03,210 This formula specifically is combinations with no repeats. 52 00:04:03,210 --> 00:04:05,910 Formula is so important. 53 00:04:05,910 --> 00:04:12,270 We use it so often that we give it a special name, we call it the binomial coefficient and you'll see 54 00:04:12,270 --> 00:04:13,650 it written many ways. 55 00:04:13,650 --> 00:04:21,810 You'll often see n choose k the combinations we can make from n items when we choose K of them. 56 00:04:21,810 --> 00:04:27,930 Sometimes you'll see it as c and then n k like this, which means the same thing. 57 00:04:28,020 --> 00:04:33,840 We also write the binomial coefficient this way in parentheses with the n on the top, the k on the 58 00:04:33,840 --> 00:04:35,780 bottom, and this means n choose k. 59 00:04:35,790 --> 00:04:39,960 It's the combination made from an items when we pick K of them. 60 00:04:39,960 --> 00:04:43,830 And all of this notation is referring to the same combinations. 61 00:04:43,830 --> 00:04:46,710 No repeats binomial coefficient formula. 62 00:04:46,710 --> 00:04:50,460 This is also the formula that lotteries often use. 63 00:04:50,460 --> 00:04:56,280 For instance, it's often common in a lottery for them to choose six numbers of the numbers one through 64 00:04:56,280 --> 00:04:56,910 49. 65 00:04:56,910 --> 00:04:59,610 So if you think about the numbers, one through 49. 66 00:04:59,660 --> 00:05:06,110 One, two, three, etc., all the way up to 49 and the lottery is going to draw six of those numbers 67 00:05:06,110 --> 00:05:08,020 with repeats not allowed. 68 00:05:08,030 --> 00:05:14,390 And the idea, of course, is that if your lottery ticket matches all six of the numbers drawn, then 69 00:05:14,390 --> 00:05:16,210 you win the big jackpot. 70 00:05:16,220 --> 00:05:22,910 But if we use this formula to calculate the number of combinations that are possible, when the lottery 71 00:05:22,910 --> 00:05:26,030 can pick any numbers between one and 49. 72 00:05:26,060 --> 00:05:33,410 Of course we could plug in here and find that the number of combinations is 49 factorial divided by. 73 00:05:33,410 --> 00:05:40,370 If we're choosing six numbers, which we often do, we would say six factorial and then 49 minus six 74 00:05:40,370 --> 00:05:41,390 factorial. 75 00:05:41,420 --> 00:05:47,450 This value here, of course, simplifying to just 43 factorial. 76 00:05:48,440 --> 00:05:59,750 Which means that we could rewrite this as 49 times 48, all the way down to 44, at which point the 77 00:05:59,750 --> 00:06:01,430 43 factorial. 78 00:06:02,660 --> 00:06:06,140 Will cancel out the rest of the factorial in the numerator. 79 00:06:06,140 --> 00:06:08,800 So we have 49 all the way down to 44. 80 00:06:08,840 --> 00:06:11,300 The product of those integers. 81 00:06:11,300 --> 00:06:15,050 And then we have six factorial in the denominator. 82 00:06:15,050 --> 00:06:21,260 And if we use a calculator to do the math here, what we find is that this comes out to a little bit 83 00:06:21,260 --> 00:06:29,120 over 13.5 million, even 13.6 million, which means that if you're playing a lottery ticket, trying 84 00:06:29,120 --> 00:06:38,150 to match exactly six numbers, you have a one in about 13.6, a little more, 13.6 million chance of 85 00:06:38,150 --> 00:06:40,670 matching exactly those six numbers. 86 00:06:40,670 --> 00:06:44,150 So that's the idea here with this lower right hand corner. 87 00:06:44,270 --> 00:06:47,030 And then the last idea is combinations. 88 00:06:47,030 --> 00:06:55,070 When we can repeat values, this one's probably the hardest to understand, but the easiest way to visualize 89 00:06:55,070 --> 00:06:57,110 it is to think about an example. 90 00:06:57,110 --> 00:07:01,610 So let's say, for instance, we'll set up a table here. 91 00:07:01,640 --> 00:07:08,000 Let's say, for instance, that we are an online health food store, and as we're shipping products 92 00:07:08,000 --> 00:07:12,620 out to customers, they order from us, we pack their order, we ship it out to them. 93 00:07:12,620 --> 00:07:19,400 And before we send out the box, we want to include three little small samples of other products in 94 00:07:19,400 --> 00:07:23,210 every shipment so that we encourage customers to try new products. 95 00:07:23,210 --> 00:07:28,670 For instance, maybe we throw in a little sample protein powder, hoping that they will try that protein 96 00:07:28,670 --> 00:07:33,050 powder like it, and then order a full size product from us in the future. 97 00:07:33,050 --> 00:07:39,710 So let's say that in all the shipments going out this month, we have eight different samples that were 98 00:07:39,710 --> 00:07:40,220 including. 99 00:07:40,220 --> 00:07:47,270 So a through here represents sample A sample, B sample C, maybe A is the protein powder, B is a piece 100 00:07:47,270 --> 00:07:51,650 of chocolate, maybe sample C is a small bag of healthier candies. 101 00:07:51,650 --> 00:07:57,410 So we have these eight different samples here and all we want to do is include three samples and let's 102 00:07:57,410 --> 00:07:59,540 say we're allowing for repeats. 103 00:07:59,540 --> 00:08:05,240 We just want to grab three samples from our eight different bins here and toss three little samples 104 00:08:05,240 --> 00:08:07,790 into each box going out to customers. 105 00:08:07,790 --> 00:08:11,870 What we want to visualize then is that we have these eight different bins here. 106 00:08:11,870 --> 00:08:15,680 If you can imagine eight bins full of these little sample size products. 107 00:08:15,680 --> 00:08:17,870 And all we want to do is grab three. 108 00:08:17,870 --> 00:08:26,690 So for instance, that means that we could grab, let's say two of sample A and one of sample D, we 109 00:08:26,690 --> 00:08:35,390 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 110 00:08:35,419 --> 00:08:40,340 of course, many, many other combinations when we're allowing for repeats. 111 00:08:40,340 --> 00:08:41,840 These are just examples. 112 00:08:41,840 --> 00:08:48,200 The idea here is that we always have to choose exactly where we're putting each of our three Xs in this 113 00:08:48,200 --> 00:08:49,130 diagram. 114 00:08:49,130 --> 00:08:54,800 Once we know where we're putting each of the three Xs, then the rest is sort of determined for us. 115 00:08:54,800 --> 00:08:59,540 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 116 00:08:59,540 --> 00:09:06,560 have anything in B, C, E, f, G, or H, And so if you think then about sort of dividers between 117 00:09:06,560 --> 00:09:16,430 these buckets, So if we imagine dividers between each sample bucket like this, we have seven dividers 118 00:09:16,430 --> 00:09:19,040 because we have eight different sample types. 119 00:09:19,040 --> 00:09:22,550 We could really almost say that we're choosing ten things. 120 00:09:22,550 --> 00:09:28,640 For instance, with this first row here, if we have ten spots, we're saying that we're choosing two 121 00:09:28,640 --> 00:09:32,060 of sample A, so we're putting an X here and an X here. 122 00:09:32,090 --> 00:09:35,000 Then we're putting three dividers. 123 00:09:35,000 --> 00:09:37,730 So we're saying then we have three dividers. 124 00:09:37,730 --> 00:09:44,810 Until we get to DX, we're putting another X once we arrive at DX and then we have four more dividers, 125 00:09:44,810 --> 00:09:46,970 1 to 3 four. 126 00:09:47,000 --> 00:09:48,770 That's the first example. 127 00:09:48,770 --> 00:09:56,390 In this second example, if we look at the dividers here between each bin like this. 128 00:09:57,300 --> 00:10:02,790 We're saying that the arrangement we're choosing here, if we put it below these lines here, is divider, 129 00:10:02,790 --> 00:10:10,680 divider for these first two, and then we're choosing a sample from C and then two more dividers and 130 00:10:10,680 --> 00:10:21,660 then a sample from E, and then another divider, and then a sample from F, and then two more dividers. 131 00:10:21,660 --> 00:10:22,920 That is our choice. 132 00:10:22,920 --> 00:10:25,860 That is our arrangement in this second example here. 133 00:10:25,860 --> 00:10:32,790 So you can kind of get an idea that what this really comes down to is a choice of ten spots of how to 134 00:10:32,790 --> 00:10:34,470 fill ten spots. 135 00:10:34,470 --> 00:10:36,540 We need three sample spots. 136 00:10:36,540 --> 00:10:42,690 We're choosing three X's, we're positioning three X's, and then the seven dividers that came from 137 00:10:42,690 --> 00:10:44,760 the divisions between the eight samples. 138 00:10:44,760 --> 00:10:48,390 We fill in the rest of the choices with those seven dividers. 139 00:10:48,390 --> 00:10:56,250 And so instead of this idea of the binomial coefficient and choose K, like we said down here and choose 140 00:10:56,250 --> 00:11:03,110 K where we're picking from end things and we're choosing K of them, this time we're picking from set 141 00:11:03,120 --> 00:11:06,210 up sort of an analogy to our binomial coefficient here. 142 00:11:06,210 --> 00:11:15,690 We're picking from N plus K minus one because here we had eight samples, so we had an equal to eight, 143 00:11:15,690 --> 00:11:18,060 but we have to position the seven dividers. 144 00:11:18,060 --> 00:11:22,710 There's always one fewer divider than the number here of buckets that we're dealing with. 145 00:11:22,710 --> 00:11:28,710 So the number of dividers we have is always n minus one and the number of x's that we're placing is 146 00:11:28,710 --> 00:11:35,550 K, So we're adding together and minus one and K, So you can think about this as N minus one plus K, 147 00:11:35,550 --> 00:11:38,100 or we write it as n plus K minus one. 148 00:11:38,100 --> 00:11:46,050 So we're picking from a set of KN plus K minus one or in other words, just replacing in this formula 149 00:11:46,050 --> 00:11:51,390 N with n plus K minus one when we're still choosing K objects. 150 00:11:51,390 --> 00:11:57,210 So in this notation it looks like n plus k minus one choose k. 151 00:11:57,450 --> 00:12:07,020 And in our formula here instead of PN factorial, we have n plus k minus one factorial and in the denominator 152 00:12:07,020 --> 00:12:14,130 we'll still have k factorial here, but we're replacing n with n plus k minus one. 153 00:12:14,130 --> 00:12:19,830 So we have here instead of n minus k will replace this n with n plus k minus one. 154 00:12:19,830 --> 00:12:24,120 So we get n plus k minus one instead of n right here. 155 00:12:24,120 --> 00:12:27,630 And then we still have minus K, so minus K. 156 00:12:27,660 --> 00:12:35,250 Well when we do that we get this positive and negative K to cancel, leaving us with just n minus one, 157 00:12:35,550 --> 00:12:40,620 which means that we get n minus one factorial here in the denominator. 158 00:12:40,620 --> 00:12:43,830 So this formula is exactly the same as this one. 159 00:12:43,830 --> 00:12:47,400 We're just replacing N with n plus K minus one. 160 00:12:47,400 --> 00:12:55,590 And we see that logic based on this bucket divider illustration where we realize, like in this example 161 00:12:55,590 --> 00:13:03,960 that we had to fill ten spots, we had to fill N plus K minus one spots with K choices, we pick where 162 00:13:03,960 --> 00:13:06,180 our K items are going to go. 163 00:13:06,210 --> 00:13:10,860 We have K number of X's and we position those and then we fill in the rest with dividers. 164 00:13:10,860 --> 00:13:18,270 So in this example here with our online health food marketplace, if we're choosing K equals three items 165 00:13:18,270 --> 00:13:24,690 out of our eight samples and we're allowing repeats, then we have eight, plus three is 11, minus 166 00:13:24,690 --> 00:13:26,070 one is ten. 167 00:13:26,100 --> 00:13:28,710 There's our ten buckets we have to fill. 168 00:13:28,710 --> 00:13:32,130 So in the numerator here we end up with ten factorial. 169 00:13:32,130 --> 00:13:39,180 Let's put that up here, we get ten factorial in the denominator, we have n equals eight and minus 170 00:13:39,180 --> 00:13:39,840 one is seven. 171 00:13:39,840 --> 00:13:41,220 So seven factorial. 172 00:13:41,220 --> 00:13:42,870 And we said that we're choosing three. 173 00:13:42,870 --> 00:13:49,770 So we have three factorial times, seven factorial, three factorial times seven factorial. 174 00:13:50,010 --> 00:13:56,670 Well, we know that this seven factorial will cancel with the seven factorial that's nested inside this 175 00:13:56,670 --> 00:14:02,850 ten factorial, leaving us with just ten times, nine times eight in the numerator. 176 00:14:02,850 --> 00:14:09,810 And so when we do that math, ten times nine times eight is 720 divided by six because three factorial 177 00:14:09,810 --> 00:14:11,010 is six. 178 00:14:11,010 --> 00:14:15,240 The result there is 120 combinations. 179 00:14:15,240 --> 00:14:21,120 So if we have eight different samples we can pick from, we're picking three of them and we're allowing 180 00:14:21,120 --> 00:14:21,930 repeats. 181 00:14:21,930 --> 00:14:27,120 We have 120 combinations that we can create in that scenario. 182 00:14:27,120 --> 00:14:33,780 So even though combinatorics is the study of counting, hopefully looking further into factorial and 183 00:14:33,780 --> 00:14:40,980 permutations and combinations gives you a much better idea of why these counting concepts are so valuable 184 00:14:40,980 --> 00:14:46,770 to us and why these come in handy for so many different real world applications.