1
00:00:00,090 --> 00:00:04,860
Now that we have a little bit of background in factorial, we want to move on to talking about permutations

2
00:00:04,860 --> 00:00:06,330
and combinations.

3
00:00:06,360 --> 00:00:09,360
We'll start here with permutations.

4
00:00:09,360 --> 00:00:12,720
And the thing to remember about permutations is the word position.

5
00:00:12,720 --> 00:00:19,170
So when you think permutations, think position or order or arrangement, in other words, order matters

6
00:00:19,170 --> 00:00:21,780
or the position of the items matters.

7
00:00:21,810 --> 00:00:27,390
Now, you might be wondering, we just talked about factorial and we said that a factorial represented

8
00:00:27,390 --> 00:00:28,260
an arrangement.

9
00:00:28,260 --> 00:00:33,870
So the question then becomes how are permutations different than factorial if factorial represent an

10
00:00:33,870 --> 00:00:34,560
arrangement?

11
00:00:34,590 --> 00:00:39,540
Well, if you remember before, when we talked about factorial, we did an example where we talked about

12
00:00:39,540 --> 00:00:40,710
the playing cards.

13
00:00:40,710 --> 00:00:44,250
We had a king, a queen and a jack.

14
00:00:44,250 --> 00:00:46,290
We had three face cards.

15
00:00:46,290 --> 00:00:50,940
And in the context of factorial, when we talk about the number of ways in which we can arrange these

16
00:00:50,940 --> 00:00:54,000
three face cards, we have two limitations.

17
00:00:54,000 --> 00:00:58,540
The first limitation is that we have to arrange all three cards in our set.

18
00:00:58,560 --> 00:01:00,030
In other words, we have three face cards.

19
00:01:00,030 --> 00:01:01,920
We have to arrange all three of them.

20
00:01:01,920 --> 00:01:07,170
We didn't address what it would mean to have three face cards, but only want to arrange two of them

21
00:01:07,170 --> 00:01:11,850
because as you can imagine, if we only want to arrange two of these, but we have three that we can

22
00:01:11,850 --> 00:01:12,570
pick from.

23
00:01:12,660 --> 00:01:16,680
We could look at all the arrangements with the King and the Queen, but we could also look at arrangements

24
00:01:16,680 --> 00:01:17,850
with the queen and the jack.

25
00:01:17,850 --> 00:01:22,470
Or we could look at arrangements with the king and the jack and the number of ways in which each of

26
00:01:22,470 --> 00:01:24,360
those subsets can be arranged.

27
00:01:24,360 --> 00:01:29,310
And when we talked about factorial, we also didn't address the possibility of repeats.

28
00:01:29,310 --> 00:01:34,860
So when we had this king, Queen and Jack, we only imagined a scenario in which we could arrange one

29
00:01:34,860 --> 00:01:36,810
king, one queen and one Jack.

30
00:01:36,810 --> 00:01:41,820
But what if we have a whole deck of playing cards and we therefore have the possibility that we could

31
00:01:41,820 --> 00:01:46,170
arrange one king, one queen and one Jack, or that we could keep repeating.

32
00:01:46,170 --> 00:01:49,740
We could have king, king, king or Queen Jack Queen.

33
00:01:49,740 --> 00:01:54,960
In other words, we can repeat a card and we still want to know the number of ways in which we can arrange

34
00:01:54,960 --> 00:02:00,370
that set when the order of that set or the order of that arrangement still matters.

35
00:02:00,390 --> 00:02:05,130
So now that we're introducing permutations, we're going to be able to address both of those things.

36
00:02:05,130 --> 00:02:09,120
And what we're going to be working toward is filling out this table right here.

37
00:02:09,120 --> 00:02:10,919
We're going to start by looking at permutations.

38
00:02:10,919 --> 00:02:13,110
So we're going to start by working on this top row.

39
00:02:13,470 --> 00:02:17,670
Then later on, we'll look at combinations and we'll fill in this bottom row.

40
00:02:17,670 --> 00:02:22,530
And within each one of these rows, when we talk about permutations, when we talk about combinations,

41
00:02:22,530 --> 00:02:27,030
we're going to talk about how to calculate the number of permutations or the number of combinations

42
00:02:27,030 --> 00:02:33,060
when we can repeat items in the set versus when we can't repeat or when repeats aren't allowed.

43
00:02:33,060 --> 00:02:38,730
So to start building out this table, let's go back to our King Queen Jack example from the Factorial

44
00:02:38,730 --> 00:02:39,360
Lecture.

45
00:02:39,360 --> 00:02:45,540
If you remember when we had three face cards and we wanted to arrange all three of them, we said that

46
00:02:45,540 --> 00:02:50,610
the number of possible arrangements was going to be equal to three factorial because we had three items

47
00:02:50,610 --> 00:02:51,450
in the set.

48
00:02:51,450 --> 00:02:57,240
So in other words, given an items, the number of arrangements was in factorial.

49
00:02:57,240 --> 00:03:01,770
And if you remember when we did that calculation, we said that the order mattered.

50
00:03:01,770 --> 00:03:06,660
We said that the arrangement King Queen Jack, for example, was different than the arrangement.

51
00:03:06,660 --> 00:03:07,530
KING Jack.

52
00:03:07,530 --> 00:03:13,680
QUEEN So because the order mattered, when we calculated that in factorial value, we were actually

53
00:03:13,680 --> 00:03:15,540
calculating a permutation.

54
00:03:15,540 --> 00:03:20,370
In other words, in the last lecture, instead of saying that we were talking about factorial, we could

55
00:03:20,370 --> 00:03:22,980
have said that we were talking about permutations.

56
00:03:22,980 --> 00:03:29,940
We were just forcing the arrangement of the entire set instead of allowing for subsets of the arrangement.

57
00:03:29,940 --> 00:03:36,420
When we allow for subsets, we use a different formula, and that formula is the one that we'll put

58
00:03:36,420 --> 00:03:36,930
here.

59
00:03:36,930 --> 00:03:43,620
It's n factorial divided by quantity, n minus k factorial.

60
00:03:43,710 --> 00:03:52,110
And the idea here is that we have n number of items in our set and we're choosing K of them to make

61
00:03:52,110 --> 00:03:53,220
permutations.

62
00:03:53,220 --> 00:03:58,860
So for instance, if we start with one king, one queen, one Jack, we have this set of three items,

63
00:03:58,860 --> 00:04:01,590
then in this case an equals three.

64
00:04:01,590 --> 00:04:07,530
And let's say we want to determine the number of ways in which we can arrange just two of these cards

65
00:04:07,530 --> 00:04:08,610
in that case.

66
00:04:09,360 --> 00:04:10,490
K equals two.

67
00:04:10,500 --> 00:04:13,290
So what we're doing is we're starting with this set of three.

68
00:04:13,470 --> 00:04:18,140
We're picking just two of these three items so we could pick the king in the queen.

69
00:04:18,149 --> 00:04:22,079
We could pick the queen in the jack or we could pick the king in the jack.

70
00:04:22,110 --> 00:04:28,470
So we're picking two first, and then once we have our set of two, we're calculating the number of

71
00:04:28,470 --> 00:04:32,220
permutations, the number of ways in which we can arrange that set of two.

72
00:04:32,250 --> 00:04:37,350
So, for instance, if we picked the king and the queen, we know we could arrange that as king, then

73
00:04:37,350 --> 00:04:40,350
queen or as queen, then king.

74
00:04:40,530 --> 00:04:47,340
So of course, if we plug that into this formula here, we're going to get an equals three factorial

75
00:04:47,340 --> 00:04:50,380
divided by RN, minus K or three minus two.

76
00:04:50,400 --> 00:04:53,460
So three minus two factorial.

77
00:04:53,460 --> 00:05:01,410
And the result here is three factorial over one factorial or three times two times one in the numerator

78
00:05:01,410 --> 00:05:02,160
is six.

79
00:05:02,160 --> 00:05:04,200
One factorial, of course is just one.

80
00:05:04,200 --> 00:05:06,750
So we get six over one or six.

81
00:05:06,780 --> 00:05:09,490
Now what happens if we start with this same set of three?

82
00:05:09,510 --> 00:05:10,620
King, Queen and Jack.

83
00:05:10,620 --> 00:05:13,050
But we only want to choose one of the cards.

84
00:05:13,050 --> 00:05:15,840
In that case, N equals three and K equals one.

85
00:05:15,840 --> 00:05:24,390
And so we would end up with three factorial divided by quantity, three minus one factorial or three

86
00:05:24,390 --> 00:05:32,240
factorial over two factorial, in which case we get six divided by two or three.

87
00:05:32,250 --> 00:05:37,710
And that should make sense because if we're only choosing one card from the set to a range at a time,

88
00:05:37,710 --> 00:05:42,630
then we're either choosing the king and there's only one way to arrange that we're choosing the Queen,

89
00:05:42,630 --> 00:05:47,190
and there's only one way to arrange just the single queen, or we're choosing the jack.

90
00:05:47,190 --> 00:05:50,340
And there's only one way to arrange just that single jack.

91
00:05:50,340 --> 00:05:52,530
So there's three ways to arrange.

92
00:05:52,530 --> 00:05:54,150
There are three permutations.

93
00:05:54,150 --> 00:05:59,130
If we start with a set of three and we just pick one item at a time or to pick an entirely different

94
00:05:59,130 --> 00:06:03,870
example, if we're trying to figure out the number of ways in which we can seat five people around a

95
00:06:03,870 --> 00:06:07,230
table, and in this case, maybe order really does matter to us.

96
00:06:07,230 --> 00:06:11,970
Maybe we really do want the permutation because we care who sits next to who.

97
00:06:12,000 --> 00:06:17,610
Well, look what happens if we arrange all five people using this formula because we want the number

98
00:06:17,610 --> 00:06:18,450
of permutations.

99
00:06:18,450 --> 00:06:19,560
Order matters to us.

100
00:06:19,560 --> 00:06:21,240
We care who sits next to who.

101
00:06:21,240 --> 00:06:24,450
But of course, we're dealing with people here so we can't repeat them.

102
00:06:24,450 --> 00:06:27,360
We can't have the same person sitting in two different seats.

103
00:06:27,360 --> 00:06:30,780
So we're looking at the number of permutations with no repeats.

104
00:06:30,780 --> 00:06:32,070
We can use this formula.

105
00:06:32,280 --> 00:06:38,190
If we want to arrange all five people around the table, then both N equals five and K equals five.

106
00:06:38,190 --> 00:06:46,230
We have an equal to K and we would set that up as five factorial divided by quantity, five minus five

107
00:06:46,230 --> 00:06:51,600
factorial or five factorial over zero factorial.

108
00:06:51,600 --> 00:06:57,810
That denominator always goes to zero factorial when n is equal to K, we know that zero factorial is

109
00:06:57,810 --> 00:07:02,810
equal to one, which means this simplifies to just five factorial.

110
00:07:02,820 --> 00:07:05,400
And remember we said we had n equals five people.

111
00:07:05,400 --> 00:07:07,710
So this is really just n factorial.

112
00:07:07,710 --> 00:07:10,470
And we're back to this factorial idea.

113
00:07:10,470 --> 00:07:16,380
Remember earlier we said that factorial were just like a permutation, except that we always used the

114
00:07:16,380 --> 00:07:17,460
entire set.

115
00:07:17,460 --> 00:07:19,110
Well here, that's just what we did.

116
00:07:19,110 --> 00:07:25,620
We had five people and we wanted to arrange the entire set of all five of them instead of some subset,

117
00:07:25,620 --> 00:07:27,780
like just three of the five people.

118
00:07:27,780 --> 00:07:31,920
So with five people when we want to arrange all of them, but order matters.

119
00:07:31,920 --> 00:07:33,420
So we're finding a permutation.

120
00:07:33,420 --> 00:07:38,610
This denominator always simplifies to zero factorial we always get and factorial.

121
00:07:38,610 --> 00:07:44,280
So when you think about five people and you want to arrange all of them, that's this formula here.

122
00:07:44,280 --> 00:07:47,310
But you know, that's just going to simplify to RN factorial.

123
00:07:47,310 --> 00:07:51,060
So in this case, we know five factorial is 120.

124
00:07:51,210 --> 00:07:55,470
There are 120 ways to arrange five people around a table.

125
00:07:55,470 --> 00:08:00,720
So that's how the idea of permutations and factorial are related to one another.

126
00:08:00,720 --> 00:08:06,060
Let's just fill out this one last box here permutations where we allow for repeats.

127
00:08:06,060 --> 00:08:11,220
So an easy example or an easy way to think about this is with phone numbers.

128
00:08:11,220 --> 00:08:15,510
So let's say we want to figure out how many seven digit phone numbers we can make.

129
00:08:15,510 --> 00:08:18,450
Well, if we use all the digits zero through nine.

130
00:08:18,450 --> 00:08:23,430
So zero one, two, three, all the way up through nine, that's ten digits.

131
00:08:23,430 --> 00:08:26,340
If we had started with one, we would have had nine digits.

132
00:08:26,340 --> 00:08:27,210
One, two, three, four.

133
00:08:27,240 --> 00:08:28,770
All the way up to nine is nine digits.

134
00:08:28,770 --> 00:08:32,580
But when we add in the zero as a digit, this is ten digits.

135
00:08:32,580 --> 00:08:37,799
And if we're allowing repeats and making a phone number with seven different digits, then think about

136
00:08:37,799 --> 00:08:38,520
it this way.

137
00:08:38,520 --> 00:08:43,740
When we pick the first digit, we can pick any one of these ten digits.

138
00:08:43,740 --> 00:08:48,480
So we have ten possibilities for the first digit of the seven digit phone number.

139
00:08:48,480 --> 00:08:55,740
So if we say one, two, three and then four, five, six, seven for our seven digit phone number,

140
00:08:55,740 --> 00:08:57,510
we have ten possibilities here.

141
00:08:57,510 --> 00:09:01,140
When we go to pick the second digit, of course, we're allowing repeats.

142
00:09:01,140 --> 00:09:04,110
We can use the same digit again in the phone number.

143
00:09:04,110 --> 00:09:07,860
So we again have ten possibilities and this is always the case.

144
00:09:07,860 --> 00:09:08,730
We'll have ten possible.

145
00:09:08,750 --> 00:09:16,340
Abilities for every digit in our seven digit phone number, which means that when we allow repeats,

146
00:09:16,340 --> 00:09:24,500
the calculation we use is simply nn to the power of K, where n is the number of things we have to pick

147
00:09:24,500 --> 00:09:26,540
from, in this case ten digits.

148
00:09:26,540 --> 00:09:30,500
And K is the number of times that we're making that pick here.

149
00:09:30,500 --> 00:09:34,880
We picked seven times because we had seven spots to fill to make a phone number.

150
00:09:35,090 --> 00:09:36,680
So we're picking from ten things.

151
00:09:36,680 --> 00:09:42,380
We're picking seven times, which means that in this phone number example, the number of phone numbers

152
00:09:42,380 --> 00:09:48,500
we can build is given by ten to the seven, which is equal to 10 million.

153
00:09:48,650 --> 00:09:54,740
So there are 10,000,007 digit phone numbers that we can make if we allow ourselves to use all ten digits,

154
00:09:54,740 --> 00:09:58,460
zero through nine, and repeat them as many times as we want.

155
00:09:58,490 --> 00:10:08,150
Meaning we can start with the phone number, 0000000 and go all the way up to the phone number 9999999.

156
00:10:08,150 --> 00:10:16,550
But the order of the digits matters, which of course makes sense because the phone number, 1000000

157
00:10:16,550 --> 00:10:21,140
is not the same as the phone number, 0100000.

158
00:10:21,170 --> 00:10:23,960
The place where we put the one changes the phone number.

159
00:10:23,960 --> 00:10:25,280
So order matters.

160
00:10:25,280 --> 00:10:26,990
We're dealing with a permutation.

161
00:10:26,990 --> 00:10:31,100
We have ten digits to pick from every time and we can make seven picks.

162
00:10:31,100 --> 00:10:38,390
That calculation permutations with repeats aloud is end to the K where we pick from n items K number

163
00:10:38,390 --> 00:10:39,050
of times.

164
00:10:39,050 --> 00:10:41,390
So that's how we calculate permutations.

165
00:10:41,390 --> 00:10:47,600
And in the next lecture we'll compare this to combinations and learn how to calculate combinations with

166
00:10:47,600 --> 00:10:50,420
both repeats and no repeats.