1
00:00:00,499 --> 00:00:02,830
The following content is
provided under a Creative
2
00:00:02,830 --> 00:00:04,350
Commons license.
3
00:00:04,350 --> 00:00:06,680
Your support will help
MIT OpenCourseWare
4
00:00:06,680 --> 00:00:11,050
continue to offer high quality
educational resources for free.
5
00:00:11,050 --> 00:00:13,670
To make a donation or
view additional materials
6
00:00:13,670 --> 00:00:17,566
from hundreds of MIT courses,
visit MIT OpenCourseWare
7
00:00:17,566 --> 00:00:18,191
at ocw.mit.edu.
8
00:00:22,800 --> 00:00:27,050
PROFESSOR: So this week we are
going to talk about counting.
9
00:00:27,050 --> 00:00:32,009
Tonight is a problem
set eight due.
10
00:00:32,009 --> 00:00:34,910
For this week, we will post
a new problem set tonight
11
00:00:34,910 --> 00:00:36,940
as well.
12
00:00:36,940 --> 00:00:39,190
Counting is very important.
13
00:00:39,190 --> 00:00:41,130
The rest of the semester
after this week,
14
00:00:41,130 --> 00:00:44,499
we will actually explain
probability theory.
15
00:00:44,499 --> 00:00:45,790
And it's all based on counting.
16
00:00:48,440 --> 00:00:51,710
So I'm going to
teach you this week
17
00:00:51,710 --> 00:00:54,690
a whole toolkit of all
kinds of ways how to count.
18
00:00:54,690 --> 00:00:56,960
And as you can see,
we're going to talk
19
00:00:56,960 --> 00:00:59,020
about a lot of different
kinds of rules.
20
00:00:59,020 --> 00:01:03,100
A mapping rule we'll
talk about, the pigeon
21
00:01:03,100 --> 00:01:05,300
hole principle, another
rule, the product rule
22
00:01:05,300 --> 00:01:06,620
and the sum rule.
23
00:01:06,620 --> 00:01:10,100
And these are all ways
to count one thing
24
00:01:10,100 --> 00:01:11,332
by counting another thing.
25
00:01:11,332 --> 00:01:13,040
Actually, what we are
going to talk about
26
00:01:13,040 --> 00:01:19,080
is how to count a
difficult set the objects.
27
00:01:19,080 --> 00:01:21,130
And we will map those
objects to something
28
00:01:21,130 --> 00:01:24,930
that we can count in
a much easier way.
29
00:01:24,930 --> 00:01:25,430
OK.
30
00:01:25,430 --> 00:01:28,780
So let's start with a lot
of definitions actually.
31
00:01:28,780 --> 00:01:33,980
So we have to talk about sets,
sequences, and permutations
32
00:01:33,980 --> 00:01:35,960
to start off with.
33
00:01:35,960 --> 00:01:42,640
So the definition of
a set is as follows.
34
00:01:42,640 --> 00:01:51,450
A set is actually an
unordered collection
35
00:01:51,450 --> 00:01:52,835
of distinct elements.
36
00:02:01,180 --> 00:02:05,970
So as an example,
we may have, say,
37
00:02:05,970 --> 00:02:11,120
a set that contains the
elements a, b, and c.
38
00:02:11,120 --> 00:02:12,649
Well, if you reorder
these elements,
39
00:02:12,649 --> 00:02:13,690
it doesn't really matter.
40
00:02:13,690 --> 00:02:14,980
It's still the same set.
41
00:02:14,980 --> 00:02:19,640
We can also write it
as the set c, a, b.
42
00:02:19,640 --> 00:02:22,820
On the other hand if you
have a collection in which
43
00:02:22,820 --> 00:02:26,650
say the elements
a appears twice,
44
00:02:26,650 --> 00:02:28,970
well, these two
are not distinct.
45
00:02:28,970 --> 00:02:31,270
So this is not a set.
46
00:02:31,270 --> 00:02:32,500
So this is not a set.
47
00:02:32,500 --> 00:02:34,801
But it is a collection.
48
00:02:34,801 --> 00:02:36,175
And you may call
this a multiset.
49
00:02:36,175 --> 00:02:38,350
But we'll not go into that.
50
00:02:38,350 --> 00:02:40,550
So we will be
talking about sets.
51
00:02:40,550 --> 00:02:43,930
And your interested usually
in the cardinality of a set.
52
00:02:43,930 --> 00:02:45,860
So what's that?
53
00:02:45,860 --> 00:02:52,410
The cardinality or size
is defined as follows.
54
00:02:55,000 --> 00:03:04,470
Cardinality is just
a number of elements
55
00:03:04,470 --> 00:03:06,590
that the set S really has.
56
00:03:06,590 --> 00:03:16,020
So it's a number
of elements in S.
57
00:03:16,020 --> 00:03:22,550
And how do we denote this/ This
is denoted by two vertical bars
58
00:03:22,550 --> 00:03:27,740
around the letter that
represents the set.
59
00:03:27,740 --> 00:03:30,520
So we denote this as follows.
60
00:03:30,520 --> 00:03:33,260
Now, when we talk
about sets, we may also
61
00:03:33,260 --> 00:03:37,940
be interested in ordered
collection of elements.
62
00:03:37,940 --> 00:03:40,820
And that's what we
call a sequence.
63
00:03:40,820 --> 00:03:44,440
So a sequence is
defined as follows.
64
00:03:44,440 --> 00:04:00,170
A sequence is an ordered
collection of elements.
65
00:04:00,170 --> 00:04:04,570
And we also call these
elements components or terms.
66
00:04:12,810 --> 00:04:16,839
And these elements
do not necessarily
67
00:04:16,839 --> 00:04:27,360
have to be distinct-- so
not necessarily distinct.
68
00:04:27,360 --> 00:04:29,400
Now as an example, so
how do we denote this?
69
00:04:29,400 --> 00:04:36,520
For sets, we use this type
of notation like this symbol.
70
00:04:36,520 --> 00:04:40,270
For sequences, we just have a
very simple type of bracket,
71
00:04:40,270 --> 00:04:42,630
just a round bracket.
72
00:04:42,630 --> 00:04:49,240
So an example could be, well,
the elements a, b, and c.
73
00:04:49,240 --> 00:04:51,280
The first entry
or the first term
74
00:04:51,280 --> 00:04:53,760
of the sequence-- depending
on whether you look
75
00:04:53,760 --> 00:04:57,040
at it from the left or
the right, it may differ--
76
00:04:57,040 --> 00:05:01,140
is here a, b, and then c.
77
00:05:01,140 --> 00:05:03,810
Another one could
be a, b, and a.
78
00:05:03,810 --> 00:05:06,840
And as you can see, the element
a occurs twice in the sequence.
79
00:05:10,700 --> 00:05:13,980
So we're going to relate
sets and sequences.
80
00:05:13,980 --> 00:05:18,080
And let's talk about
the permutation.
81
00:05:18,080 --> 00:05:21,450
So a permutation of a set
is defined as follows.
82
00:05:28,500 --> 00:05:36,080
A permutation of a
set S is actually
83
00:05:36,080 --> 00:05:44,150
a sequence that contains every
element in S exactly once.
84
00:05:55,250 --> 00:05:58,515
So every element in S
occurs exactly once.
85
00:06:03,280 --> 00:06:08,260
And as an example, we may
look at the set that we have
86
00:06:08,260 --> 00:06:11,930
described over here,
the set a,b, and c.
87
00:06:11,930 --> 00:06:16,530
And how many
permutations are there?
88
00:06:16,530 --> 00:06:22,736
So the first one I may just
order the elements in a, b,
89
00:06:22,736 --> 00:06:23,430
and c.
90
00:06:23,430 --> 00:06:28,020
So I have, say, the sequence
a and then b, and then c.
91
00:06:28,020 --> 00:06:29,330
There are many more.
92
00:06:29,330 --> 00:06:33,990
I can, for example,
start with b, and then c,
93
00:06:33,990 --> 00:06:36,530
and then may cycle through to a.
94
00:06:36,530 --> 00:06:40,844
That's another permutation
of these three elements.
95
00:06:40,844 --> 00:06:42,010
And I can do this once more.
96
00:06:42,010 --> 00:06:49,760
I can, for example, start with
c, and then a, and then b.
97
00:06:49,760 --> 00:06:53,150
And it turns out that
we can do a few more.
98
00:06:53,150 --> 00:06:56,140
You can also start to c,
and then b, and then a.
99
00:06:56,140 --> 00:07:00,140
We sort of reversed
the order that we
100
00:07:00,140 --> 00:07:05,070
had over here into its opposite,
so first c, then b, then a.
101
00:07:05,070 --> 00:07:07,390
And we can look at
this cycle there.
102
00:07:07,390 --> 00:07:08,480
There's shifts.
103
00:07:08,480 --> 00:07:11,260
And we start with b, a,
and then we rotate through
104
00:07:11,260 --> 00:07:14,060
to c, which is what
we did over here
105
00:07:14,060 --> 00:07:17,050
when you went from this
permutation to this one.
106
00:07:17,050 --> 00:07:19,700
So we have to b, a, and then c.
107
00:07:19,700 --> 00:07:25,410
And then we may start with
a, and we have a, c, and b.
108
00:07:25,410 --> 00:07:28,910
It turns out that
this is actually
109
00:07:28,910 --> 00:07:32,100
all the possible
permutations of this set.
110
00:07:32,100 --> 00:07:36,202
So there's six of these.
111
00:07:36,202 --> 00:07:39,950
And in general, how
many permutations
112
00:07:39,950 --> 00:07:42,760
are there of a
set of n elements?
113
00:07:42,760 --> 00:07:46,340
So let's have a look
here what we did.
114
00:07:46,340 --> 00:07:50,020
So if I want to create
a permutation of a set,
115
00:07:50,020 --> 00:07:56,110
I may start off by selecting for
the first term a, and b, or c.
116
00:07:56,110 --> 00:07:58,800
So I have actually
three choices.
117
00:07:58,800 --> 00:08:06,015
So the first term
has three choices.
118
00:08:09,200 --> 00:08:12,010
The second term over
here, well, for example,
119
00:08:12,010 --> 00:08:14,910
suppose my first term was b.
120
00:08:14,910 --> 00:08:17,940
Then the second
term, well, must be
121
00:08:17,940 --> 00:08:21,880
an element that is different
from b, as yet part of S.
122
00:08:21,880 --> 00:08:27,450
So I have only two choices for
the second term, either c or a.
123
00:08:27,450 --> 00:08:32,400
So the second term
has two choices.
124
00:08:32,400 --> 00:08:35,309
And once I have chosen
the second one, well,
125
00:08:35,309 --> 00:08:37,960
if I've already chosen
b and c, there's
126
00:08:37,960 --> 00:08:42,150
only one element left in
the set over here, only a.
127
00:08:42,150 --> 00:08:44,480
So I have only one choice left.
128
00:08:44,480 --> 00:08:48,740
So in this way, we may count
the total number of permutations
129
00:08:48,740 --> 00:08:50,820
of this set as the
number of choices
130
00:08:50,820 --> 00:08:54,270
that I have for the first term
times the number of choices
131
00:08:54,270 --> 00:08:57,350
for the second term,
3 times 2 times
132
00:08:57,350 --> 00:09:00,520
the number of choices for the
third term, which is only one.
133
00:09:00,520 --> 00:09:10,540
So the third term
has only one choice.
134
00:09:10,540 --> 00:09:14,520
Now in general, we can do
this for any permutation.
135
00:09:14,520 --> 00:09:21,860
And if you want to count
the number of permutations,
136
00:09:21,860 --> 00:09:31,020
of a set with n
elements, well, it
137
00:09:31,020 --> 00:09:34,920
turns out that it's equal to n
times n minus 1 just like here.
138
00:09:34,920 --> 00:09:38,120
We have three elements,
3 times 3 minus 1
139
00:09:38,120 --> 00:09:41,380
and so on, n times n
minus 1 times n minus 2,
140
00:09:41,380 --> 00:09:47,620
et cetera all the way up to one.
141
00:09:47,620 --> 00:09:49,550
And this is n factorial.
142
00:09:49,550 --> 00:09:51,290
And you've seen
this already when
143
00:09:51,290 --> 00:09:53,180
we talked about
Stirling's formula
144
00:09:53,180 --> 00:09:55,731
and how to approximate this.
145
00:09:55,731 --> 00:09:57,620
Now, this type of
reasoning we will
146
00:09:57,620 --> 00:10:01,600
generalize later on when we
come to the Generalized Product
147
00:10:01,600 --> 00:10:02,770
rule.
148
00:10:02,770 --> 00:10:05,590
And But this is
already a first example
149
00:10:05,590 --> 00:10:08,350
of how we go about this.
150
00:10:08,350 --> 00:10:13,470
So permutations relates
sets and sequences.
151
00:10:13,470 --> 00:10:16,970
So now we go on to define
more special functions.
152
00:10:16,970 --> 00:10:19,640
So permutations is
one kind of mapping.
153
00:10:19,640 --> 00:10:22,770
So let's now define functions.
154
00:10:22,770 --> 00:10:29,440
And then we will talk about a
few different flavors of those.
155
00:10:29,440 --> 00:10:32,070
We talk about surjective
functions, injective functions,
156
00:10:32,070 --> 00:10:33,920
and bijective functions.
157
00:10:33,920 --> 00:10:39,360
And the whole idea is is that
if I can use a mapping from one
158
00:10:39,360 --> 00:10:43,500
set to another set
that satisfies some
159
00:10:43,500 --> 00:10:45,600
of those properties,
it can say something
160
00:10:45,600 --> 00:10:48,630
about how their
cardinalities are related.
161
00:10:48,630 --> 00:10:49,680
And that's what we want.
162
00:10:49,680 --> 00:10:51,440
We want to count.
163
00:10:51,440 --> 00:10:56,035
OK So the definition of
a function is as follows.
164
00:11:00,220 --> 00:11:06,050
So a function f from
x to y is actually
165
00:11:06,050 --> 00:11:18,730
a relation between
the sets X and Y.
166
00:11:18,730 --> 00:11:24,190
And we say that--
oh-- with the property
167
00:11:24,190 --> 00:11:31,890
that every single element,
every element, of X
168
00:11:31,890 --> 00:11:50,070
is actually related to
exactly one element of Y.
169
00:11:50,070 --> 00:11:59,920
And we will call x to be the
domain of the function f.
170
00:11:59,920 --> 00:12:06,860
And Y we will call the range
or image of the function f.
171
00:12:06,860 --> 00:12:08,670
So let's give an example.
172
00:12:08,670 --> 00:12:13,400
And to see a couple of
examples of, first of all,
173
00:12:13,400 --> 00:12:16,765
a function and then
relations to that
174
00:12:16,765 --> 00:12:18,680
are actually not functions.
175
00:12:18,680 --> 00:12:22,980
So suppose you have a mapping
from x which just contains
176
00:12:22,980 --> 00:12:25,130
the elements a, b,
and c, just in line
177
00:12:25,130 --> 00:12:26,795
with this example over here.
178
00:12:26,795 --> 00:12:34,410
And we have a mapping f
that maps to the set y.
179
00:12:34,410 --> 00:12:37,840
And the y is just the
numbers 1, 2, and 3.
180
00:12:37,840 --> 00:12:46,050
Well, i could map, for example,
a to 1, b to 3, and c to 3.
181
00:12:46,050 --> 00:12:47,660
Now this is a function.
182
00:12:47,660 --> 00:12:52,450
Because every element of x
is met to exactly one element
183
00:12:52,450 --> 00:12:55,360
of y. a is just mapped to 1.
184
00:12:55,360 --> 00:12:58,120
b is also mapped to
an element, only 3.
185
00:12:58,120 --> 00:13:00,930
c is mapped to 3 as well.
186
00:13:00,930 --> 00:13:07,730
And they usually write this as
f evaluated in a is equal to 1.
187
00:13:07,730 --> 00:13:11,090
And f b is equal to 3.
188
00:13:11,090 --> 00:13:14,960
And f of c is
equal to 3 as well.
189
00:13:14,960 --> 00:13:16,643
Now what is not a
function-- oh, I
190
00:13:16,643 --> 00:13:20,205
could, for example, add another
edge over here if I wanted to.
191
00:13:20,205 --> 00:13:21,330
But this is not a function.
192
00:13:21,330 --> 00:13:25,440
Because b is now mapped
to two elements, 2 and 3.
193
00:13:25,440 --> 00:13:27,610
And that's not what's
covered by this definition.
194
00:13:27,610 --> 00:13:30,050
So this is not a function.
195
00:13:30,050 --> 00:13:32,670
I can also remove, say, an edge.
196
00:13:32,670 --> 00:13:35,380
Well, in this case, b is not
mapped to anything at all.
197
00:13:35,380 --> 00:13:37,050
And that's not a
function either.
198
00:13:37,050 --> 00:13:40,180
So we really have the
property for functions
199
00:13:40,180 --> 00:13:42,520
that there is six exactly
one outgoing arrow,
200
00:13:42,520 --> 00:13:47,740
if you want to think
about it as being a graph,
201
00:13:47,740 --> 00:13:54,680
from each element in x to
exactly one element in y.
202
00:13:54,680 --> 00:13:57,455
So now we can talk
about a few definitions.
203
00:14:01,580 --> 00:14:05,400
So we will talk about these
few properties, surjective,
204
00:14:05,400 --> 00:14:07,280
injective, and bijective.
205
00:14:07,280 --> 00:14:12,770
And then we can start to do
a few interesting examples.
206
00:14:12,770 --> 00:14:17,505
So a function f that goes from
x to y is called surjective.
207
00:14:21,640 --> 00:14:45,190
if every single element of y
is mapped to at least once.
208
00:14:45,190 --> 00:14:47,840
So what does that mean?
209
00:14:47,840 --> 00:14:49,250
To at least once.
210
00:14:53,170 --> 00:14:59,380
So every element of y, so
say 1 for example here,
211
00:14:59,380 --> 00:15:01,340
is mapped to at least once.
212
00:15:01,340 --> 00:15:05,790
Well, to the element
1 we have mapped a.
213
00:15:05,790 --> 00:15:06,520
So that's great.
214
00:15:06,520 --> 00:15:10,710
But for example element 2
is not mapped to at all.
215
00:15:10,710 --> 00:15:13,070
So this particular
example is not surjective.
216
00:15:13,070 --> 00:15:15,240
But we will come to a
few examples that are.
217
00:15:15,240 --> 00:15:18,790
So here we have the distinction
that every element of y,
218
00:15:18,790 --> 00:15:23,920
so every single element of y,
is mapped to at least once.
219
00:15:23,920 --> 00:15:30,160
The injective is defined
in a similar fashion.
220
00:15:30,160 --> 00:15:33,220
But now, every element
of y is not mapped to
221
00:15:33,220 --> 00:15:35,850
at least once, but at most once.
222
00:15:40,110 --> 00:15:41,535
So let's have look over here.
223
00:15:41,535 --> 00:15:43,660
And that's also not true
for this example actually.
224
00:15:43,660 --> 00:15:48,120
Because three is
mapped to two times.
225
00:15:48,120 --> 00:15:50,250
So it's not mapped
to at most once.
226
00:15:50,250 --> 00:15:53,510
So this example is
also not injective.
227
00:15:53,510 --> 00:15:55,620
Because if the
function is injective,
228
00:15:55,620 --> 00:16:00,350
every element of y of the range
is mapped to at most once.
229
00:16:00,350 --> 00:16:09,545
Bijective is if every element
of y is mapped to exactly once.
230
00:16:14,110 --> 00:16:18,910
And we can see that the
function is bijective if
231
00:16:18,910 --> 00:16:22,070
and only if it is both
surjective and injective.
232
00:16:22,070 --> 00:16:28,920
So bijective if and only if
we have both the properties
233
00:16:28,920 --> 00:16:34,550
surjectvie as well as injective.
234
00:16:34,550 --> 00:16:36,495
So let's give a
couple of examples.
235
00:16:44,510 --> 00:16:49,090
So as the first example, we
may have the set x and y.
236
00:16:49,090 --> 00:16:54,780
We have 1, 2, and 3, and set it
to elements a and b over here.
237
00:16:54,780 --> 00:17:00,330
1 is mapped to a, 2 is mapped
to a, and 3 is mapped to b.
238
00:17:00,330 --> 00:17:03,020
And now we can see
that every element in y
239
00:17:03,020 --> 00:17:04,440
is mapped to at least once.
240
00:17:04,440 --> 00:17:05,800
This one is mapped to two times.
241
00:17:05,800 --> 00:17:07,750
This one is mapped to once.
242
00:17:07,750 --> 00:17:10,490
So this one is
actually surjective.
243
00:17:10,490 --> 00:17:12,760
So that's great.
244
00:17:12,760 --> 00:17:16,380
Another example of
something this is injective
245
00:17:16,380 --> 00:17:22,148
is if you have, say, 1, 2,
and 3, and a, b, c, and d.
246
00:17:22,148 --> 00:17:25,020
1 is mapped, say, to a.
247
00:17:25,020 --> 00:17:27,420
2 to b, 3 to d.
248
00:17:27,420 --> 00:17:30,320
Well, in this case we
have that it's injective.
249
00:17:30,320 --> 00:17:34,614
Because every element of y
is mapped to at most once,
250
00:17:34,614 --> 00:17:37,140
once, once, zero
times, and once.
251
00:17:37,140 --> 00:17:39,340
So this one is injective.
252
00:17:39,340 --> 00:17:41,300
And this one is not
injective, right?
253
00:17:41,300 --> 00:17:43,380
Because this one is
mapped to 2 times.
254
00:17:43,380 --> 00:17:44,926
This one is not surjective.
255
00:17:44,926 --> 00:17:46,550
Because this one is
not covered at all.
256
00:17:46,550 --> 00:17:49,081
It's only mapped to once.
257
00:17:49,081 --> 00:17:49,580
OK.
258
00:17:49,580 --> 00:17:54,980
So let us talk again
about permutations.
259
00:17:54,980 --> 00:17:57,230
So let me talk
about permutations.
260
00:17:57,230 --> 00:18:01,040
We can define a mapping
using a permutation that
261
00:18:01,040 --> 00:18:03,640
is an example of a bijection.
262
00:18:03,640 --> 00:18:06,290
So let's do that.
263
00:18:06,290 --> 00:18:09,589
And then we can come
to the mapping rule.
264
00:18:09,589 --> 00:18:11,130
And we can start to
do some counting.
265
00:18:14,240 --> 00:18:24,900
So for example if we have a
permutation, a 1 up to a n, so
266
00:18:24,900 --> 00:18:31,270
let this be a
permutation of the set
267
00:18:31,270 --> 00:18:37,130
S that contains all the
elements a 1, up to a n.
268
00:18:37,130 --> 00:18:39,930
So this is just one
example of a permutation.
269
00:18:39,930 --> 00:18:42,860
And now we may define
the following function.
270
00:18:42,860 --> 00:18:52,630
We say that pi evaluated
in a i give us output i.
271
00:18:52,630 --> 00:18:56,080
Actually, what I mean
here is that if you
272
00:18:56,080 --> 00:19:00,340
take an element in
S, then this one
273
00:19:00,340 --> 00:19:07,610
is mapped to under this
function to i if and only
274
00:19:07,610 --> 00:19:12,000
if a is in the i-th position
in this permutation.
275
00:19:12,000 --> 00:19:24,450
So if and only if today is in
i-th term in the permutation.
276
00:19:30,530 --> 00:19:35,600
So in this case, we know
that pi is bijective.
277
00:19:35,600 --> 00:19:36,930
And why is this?
278
00:19:36,930 --> 00:19:42,300
Well, we know from the
definition of a permutation
279
00:19:42,300 --> 00:19:45,650
that any permutation is a
sequence in which every element
280
00:19:45,650 --> 00:19:48,430
of S occurs exactly once.
281
00:19:48,430 --> 00:19:53,540
So that means that every
position is covered exactly
282
00:19:53,540 --> 00:19:56,790
once by an element of
S. And that is exactly
283
00:19:56,790 --> 00:19:59,190
the definition over
here which says
284
00:19:59,190 --> 00:20:05,190
that every element in the
range is mapped to exactly
285
00:20:05,190 --> 00:20:07,960
once by an element in a domain.
286
00:20:07,960 --> 00:20:10,195
So this is an example
of a bijection.
287
00:20:13,340 --> 00:20:13,840
OK.
288
00:20:13,840 --> 00:20:16,570
So now that we have
defined functions
289
00:20:16,570 --> 00:20:18,540
and the special
properties, let's
290
00:20:18,540 --> 00:20:24,830
talk about the mapping rule,
which we'll do over here.
291
00:20:28,600 --> 00:20:33,340
And now for the
first time we start
292
00:20:33,340 --> 00:20:36,055
to talk about the
cardinalities of sets
293
00:20:36,055 --> 00:20:37,680
and how they're
related to one another.
294
00:20:40,440 --> 00:20:43,610
So the mapping
rule is that first
295
00:20:43,610 --> 00:20:48,610
of all, if f is a
function from x to y
296
00:20:48,610 --> 00:20:53,900
and if f is actually surjective,
well, what do we know?
297
00:20:53,900 --> 00:20:56,360
We actually know
that the cardinality
298
00:20:56,360 --> 00:20:59,140
of the number of
elements in the domain
299
00:20:59,140 --> 00:21:02,114
is at least the number
of elements in the range.
300
00:21:02,114 --> 00:21:02,780
And why is that?
301
00:21:02,780 --> 00:21:05,950
If you look at a
definition of surjectivity,
302
00:21:05,950 --> 00:21:08,810
we know that every
element of y is
303
00:21:08,810 --> 00:21:11,820
covered by some element
in x at least once.
304
00:21:11,820 --> 00:21:19,350
And all the elements in x
and mapped to exactly one
305
00:21:19,350 --> 00:21:20,630
element in y.
306
00:21:20,630 --> 00:21:24,780
So we know that the
cardinality of x is at least y.
307
00:21:24,780 --> 00:21:26,680
Because every element
in y is mapped
308
00:21:26,680 --> 00:21:30,810
by some unique
distinct element in x.
309
00:21:30,810 --> 00:21:38,910
And if a function f is
injective, well, in that case
310
00:21:38,910 --> 00:21:43,990
we know that the
reverse relation holds,
311
00:21:43,990 --> 00:21:46,940
so inequality holds.
312
00:21:46,940 --> 00:21:51,660
The cardinality of x is at
most the cardinality of y.
313
00:21:51,660 --> 00:21:52,470
So why is that?
314
00:21:52,470 --> 00:21:56,800
Well, every element in an
injective function, right?
315
00:21:56,800 --> 00:22:00,045
Every element is mapped
to at most one element.
316
00:22:03,700 --> 00:22:08,430
So every element in y is mapped
by at most one element in x.
317
00:22:08,430 --> 00:22:11,047
So we know that all
the elements in x
318
00:22:11,047 --> 00:22:14,540
are mapped to some element in y.
319
00:22:14,540 --> 00:22:20,320
But every element in y cannot
map to by more than two times
320
00:22:20,320 --> 00:22:21,970
by something in the domain.
321
00:22:21,970 --> 00:22:25,380
So we know that this
inequality holds.
322
00:22:25,380 --> 00:22:25,880
OK.
323
00:22:25,880 --> 00:22:30,001
For a bijective function, we
have that both these properties
324
00:22:30,001 --> 00:22:30,500
hold.
325
00:22:30,500 --> 00:22:34,570
And we will have an
equality over here.
326
00:22:34,570 --> 00:22:44,070
So if this one is bijective,
we have that the cardinalities
327
00:22:44,070 --> 00:22:45,730
are equal to one another.
328
00:22:45,730 --> 00:22:48,630
And this is also called
the bijection rule.
329
00:22:53,640 --> 00:22:56,340
So let's give an
example where we
330
00:22:56,340 --> 00:23:03,790
want to find out how many
ways there are to select
331
00:23:03,790 --> 00:23:07,110
12 doughnuts from 5 varieties.
332
00:23:07,110 --> 00:23:08,817
So let's see how
that would work.
333
00:23:08,817 --> 00:23:10,400
And the whole idea
is that we're going
334
00:23:10,400 --> 00:23:14,320
to define the set that
we want to count, which
335
00:23:14,320 --> 00:23:17,480
is all these possible
configurations of doughnuts
336
00:23:17,480 --> 00:23:19,455
over five varieties of flavors.
337
00:23:23,760 --> 00:23:27,390
And then we're going to map
these to another structure
338
00:23:27,390 --> 00:23:29,870
that we can understand
a little be better.
339
00:23:29,870 --> 00:23:30,830
So let's do this.
340
00:23:34,280 --> 00:23:49,660
So as an example, let x be all
the ways to select, say, 12
341
00:23:49,660 --> 00:23:55,719
doughnuts from 5 varieties.
342
00:23:55,719 --> 00:23:56,760
So let's give an example.
343
00:24:00,780 --> 00:24:04,000
For example, we may
have 2 doughnuts.
344
00:24:04,000 --> 00:24:08,195
And they are in the
chocolate flavored basket.
345
00:24:08,195 --> 00:24:09,070
So we have chocolate.
346
00:24:13,060 --> 00:24:19,537
And suppose we have no doughnuts
in the lemon filled version
347
00:24:19,537 --> 00:24:20,120
of a doughnut.
348
00:24:23,140 --> 00:24:27,000
Suppose he have a whole
bunch of doughnuts,
349
00:24:27,000 --> 00:24:32,590
say 6 of those,
that are with sugar.
350
00:24:32,590 --> 00:24:34,680
We have some that
are glazed, say 2.
351
00:24:38,050 --> 00:24:44,120
And finally, we have just a
couple of plain doughnuts.
352
00:24:44,120 --> 00:24:47,190
So this would be a
configuration that is in x.
353
00:24:47,190 --> 00:24:50,490
Because we have 1, 2,
3, 4, 5, varieties.
354
00:24:50,490 --> 00:24:57,100
And we have 12 doughnuts, 2 over
here, 6 here, 2, and another 2,
355
00:24:57,100 --> 00:25:02,180
12 doughnuts, that are selected
from these 5 varieties.
356
00:25:02,180 --> 00:25:08,320
Now, if you are going to try to
represent such a configuration,
357
00:25:08,320 --> 00:25:11,110
that's usually how we
think about counting,
358
00:25:11,110 --> 00:25:14,460
then we may map this
to a 01 sequence.
359
00:25:14,460 --> 00:25:16,040
So how do we do this?
360
00:25:16,040 --> 00:25:19,700
We can just map the
doughnuts two 0s, the divider
361
00:25:19,700 --> 00:25:23,240
between the two baskets as a 1.
362
00:25:23,240 --> 00:25:24,160
So this is a 1.
363
00:25:24,160 --> 00:25:29,030
Then we have no 0
between these two ones,
364
00:25:29,030 --> 00:25:31,540
because there are no doughnuts
in the lemon filled basket.
365
00:25:31,540 --> 00:25:36,510
So we have one that is the
mapping from this divider
366
00:25:36,510 --> 00:25:38,260
field over here.
367
00:25:38,260 --> 00:25:39,250
We've got 6 0s.
368
00:25:41,872 --> 00:25:45,630
We have another one that
is this divider, two 0s,
369
00:25:45,630 --> 00:25:50,250
two doughnuts in the
glazed version, and so on.
370
00:25:50,250 --> 00:25:51,800
So what do we see here?
371
00:25:51,800 --> 00:25:59,790
We have a 01 sequence where we
have 12 zeros and we have 1, 2,
372
00:25:59,790 --> 00:26:03,950
3, 4 1s.
373
00:26:03,950 --> 00:26:07,190
And we can see that this
mapping is actually bijective.
374
00:26:07,190 --> 00:26:13,320
Because if I have two 0s, I
can map them back to doughnuts.
375
00:26:13,320 --> 00:26:17,710
The 1 I can map back to the
divider between two baskets.
376
00:26:17,710 --> 00:26:27,390
So let y be the set of all
kinds of configurations of 12,
377
00:26:27,390 --> 00:26:29,100
all kinds of sequences.
378
00:26:29,100 --> 00:26:32,815
Oops, maybe I will
not take this one out.
379
00:26:32,815 --> 00:26:34,030
Let's do this one.
380
00:26:36,840 --> 00:26:47,530
So if you are going
to define y as the set
381
00:26:47,530 --> 00:27:02,280
of all 16-bit sequences
with exactly four 1s,
382
00:27:02,280 --> 00:27:05,200
then we know that by
the bijection rule,
383
00:27:05,200 --> 00:27:08,280
we have created this
bijection over here,
384
00:27:08,280 --> 00:27:12,220
that the cardinalities of
x and y are exactly equal.
385
00:27:12,220 --> 00:27:15,530
So now we know that
by the bijection rule,
386
00:27:15,530 --> 00:27:19,050
we have been able to count
the number of elements
387
00:27:19,050 --> 00:27:22,600
in x by counting something else,
which is really how we proceed
388
00:27:22,600 --> 00:27:24,390
in these types of proofs.
389
00:27:24,390 --> 00:27:30,150
So we are now able to just
count these types of objects.
390
00:27:30,150 --> 00:27:33,740
And later on next lecture,
we'll actually figure out
391
00:27:33,740 --> 00:27:37,110
a formula for this one.
392
00:27:37,110 --> 00:27:39,710
So this is an example of how
we can use the bijection rule.
393
00:27:42,460 --> 00:27:47,220
Another example is one in which
we are going to count subsets.
394
00:27:52,510 --> 00:27:56,140
So we'll give a lot of examples
through these two lectures.
395
00:27:56,140 --> 00:27:58,040
And also the problem
set, as you will see,
396
00:27:58,040 --> 00:28:02,860
will have a lot of small
little parts with all kinds
397
00:28:02,860 --> 00:28:05,740
of countings that you will need
to do applying different rules.
398
00:28:08,680 --> 00:28:15,860
So let's talk about how to
count subsets of a set x.
399
00:28:15,860 --> 00:28:25,630
So what we want is a
bijection from subsets
400
00:28:25,630 --> 00:28:29,130
of a set x containing
of, say, 1 up
401
00:28:29,130 --> 00:28:37,130
to n, so the integers 1 up
to n, to n-bit sequences.
402
00:28:37,130 --> 00:28:39,640
We know that we
can do this if you
403
00:28:39,640 --> 00:28:41,050
define a bijection as follows.
404
00:28:43,800 --> 00:28:50,880
So we map a subset
S under a mapping
405
00:28:50,880 --> 00:28:58,960
f to a bit sequence, b1,
b1, all the way to bn.
406
00:28:58,960 --> 00:29:02,880
If I add the
following relation, bi
407
00:29:02,880 --> 00:29:07,770
is computed as either a 1
or a 0, it's computed as a 1
408
00:29:07,770 --> 00:29:16,320
if i is in S. And it's
a 0 if i is not in S.
409
00:29:16,320 --> 00:29:18,680
Now, we know that
this is a bijection.
410
00:29:18,680 --> 00:29:21,330
So if we have a bit
sequence, then we
411
00:29:21,330 --> 00:29:25,880
can construct from this mapping
the corresponding subset.
412
00:29:25,880 --> 00:29:28,620
If you have a subset,
we can use this mapping
413
00:29:28,620 --> 00:29:32,040
to construct the
corresponding bit sequence.
414
00:29:38,840 --> 00:29:43,890
So how many n-bit
sequences are there?
415
00:29:48,190 --> 00:29:52,790
Well, there are 2 to the
power n n-bit sequences.
416
00:29:52,790 --> 00:29:53,570
Why is that?
417
00:29:53,570 --> 00:29:57,100
Well, we have two choices
for b1, a 0 or a 1,
418
00:29:57,100 --> 00:30:00,300
two choices for b2,
0 or a 1, and so on.
419
00:30:00,300 --> 00:30:07,050
So we have 2 times 2
times 2 choices over here.
420
00:30:07,050 --> 00:30:12,710
So we have 2 to the power n
choices for a bit sequence.
421
00:30:12,710 --> 00:30:16,150
So there are 2 to the power
of n number of bit sequences.
422
00:30:16,150 --> 00:30:18,370
And this is actually equal.
423
00:30:18,370 --> 00:30:21,640
Because of this bijection rule
that we have described over
424
00:30:21,640 --> 00:30:26,160
here, this is equal to the
total number of possible ways
425
00:30:26,160 --> 00:30:28,360
to select subsets of x.
426
00:30:28,360 --> 00:30:42,790
So this is the number of
subsets of an n element set.
427
00:30:42,790 --> 00:30:47,790
So this is a very nice
way to demonstrate
428
00:30:47,790 --> 00:30:50,880
how we can use a bijection
rule to count something
429
00:30:50,880 --> 00:30:52,800
that appears to be
much more harder
430
00:30:52,800 --> 00:30:54,779
to think about, to grasp.
431
00:30:54,779 --> 00:30:56,320
At least for me it's
harder to grasp.
432
00:30:56,320 --> 00:31:00,100
So I have a subset
that can be any size
433
00:31:00,100 --> 00:31:02,750
in a set of n elements.
434
00:31:02,750 --> 00:31:04,960
And now I can find
this really easy
435
00:31:04,960 --> 00:31:07,140
going mapping that I
can show to be bijective
436
00:31:07,140 --> 00:31:09,930
and all of a sudden, I
know how to count it.
437
00:31:09,930 --> 00:31:13,430
Because I can just
look at the image
438
00:31:13,430 --> 00:31:16,930
and count those types of
objects, in this case n-bit
439
00:31:16,930 --> 00:31:17,820
sequences.
440
00:31:17,820 --> 00:31:19,780
I get a really
easygoing number that I
441
00:31:19,780 --> 00:31:21,730
can compute fairly easily.
442
00:31:21,730 --> 00:31:25,800
And now I have counted
something much more complex.
443
00:31:25,800 --> 00:31:30,340
So this is how we generally
will think about these things.
444
00:31:30,340 --> 00:31:30,840
OK.
445
00:31:30,840 --> 00:31:35,910
So let's talk now about
the generalized pigeon hole
446
00:31:35,910 --> 00:31:36,410
principal.
447
00:31:36,410 --> 00:31:42,100
So we have covered quite a
lot of definitions right now.
448
00:31:42,100 --> 00:31:44,820
So we explained the
functions mapping rule.
449
00:31:44,820 --> 00:31:47,750
So now we come to generalized
pigeon hole principle
450
00:31:47,750 --> 00:31:50,775
and a few other rules.
451
00:31:50,775 --> 00:31:51,275
OK.
452
00:32:04,597 --> 00:32:06,680
So what about a generalized
pigeon hole principal?
453
00:32:17,940 --> 00:32:24,210
This is actually the
following counting argument.
454
00:32:24,210 --> 00:32:29,160
If I know that the
cardinality of a set x
455
00:32:29,160 --> 00:32:34,550
is more than k times the
cardinality of a set y,
456
00:32:34,550 --> 00:32:35,670
what do I know?
457
00:32:35,670 --> 00:32:38,990
Well, I know that
for all functions f
458
00:32:38,990 --> 00:32:43,880
that have domain
x and range y, I
459
00:32:43,880 --> 00:33:01,610
know that there must exist k
plus 1 different elements of x
460
00:33:01,610 --> 00:33:05,440
that are mapped to
the same element in y.
461
00:33:15,850 --> 00:33:21,642
And if we take a
specific case k=1,
462
00:33:21,642 --> 00:33:23,850
we will actually call this
the pigeon hole principle.
463
00:33:27,930 --> 00:33:31,970
And let me just demonstrate
it by the famous example
464
00:33:31,970 --> 00:33:32,535
of pigeons.
465
00:33:35,270 --> 00:33:39,620
Well, if I have more pigeons
that the number of holes
466
00:33:39,620 --> 00:33:45,120
than they can fly into, I know
for sure there exists a hole
467
00:33:45,120 --> 00:33:48,510
that two pigeons will fit in.
468
00:33:48,510 --> 00:33:53,050
So that's where the
name comes from.
469
00:33:53,050 --> 00:33:55,290
So let me write it out.
470
00:33:55,290 --> 00:34:04,230
So an example is if I
have more than n pigeons,
471
00:34:04,230 --> 00:34:14,159
so the pigeons from the set x,
and say they fly into n holes,
472
00:34:14,159 --> 00:34:17,929
and the holes is my
set y, well, then
473
00:34:17,929 --> 00:34:21,520
I know the cardinality of x is
more than the cardinality of y.
474
00:34:21,520 --> 00:34:24,460
I have more pigeons
than there are holes.
475
00:34:24,460 --> 00:34:33,139
So I know that at
least two pigeons
476
00:34:33,139 --> 00:34:34,870
will fly into the same hole.
477
00:34:41,239 --> 00:34:43,969
So for a generalized
case, how can we
478
00:34:43,969 --> 00:34:45,730
prove something like that?
479
00:34:45,730 --> 00:34:49,350
Well, we could use, for example,
something like a contradiction.
480
00:34:49,350 --> 00:35:00,250
For example, suppose
that for all k plus 1--
481
00:35:00,250 --> 00:35:03,120
as opposed to the
negation is true.
482
00:35:03,120 --> 00:35:04,660
So how do we prove this usually?
483
00:35:04,660 --> 00:35:06,350
So assume we have this.
484
00:35:06,350 --> 00:35:07,430
We want to prove this.
485
00:35:07,430 --> 00:35:08,680
Well, suppose that's not true.
486
00:35:08,680 --> 00:35:10,900
So suppose there's a mapping f.
487
00:35:10,900 --> 00:35:14,400
So a set for all k plus 1
different elements of x,
488
00:35:14,400 --> 00:35:18,880
well, they are not mapped
to the same elements in y.
489
00:35:18,880 --> 00:35:22,710
But what I really know then
is that every element in y
490
00:35:22,710 --> 00:35:27,810
is mapped to at most by
k distinct elements of x.
491
00:35:27,810 --> 00:35:33,170
So that means that the total
number of elements of x
492
00:35:33,170 --> 00:35:35,320
must be at most k times y.
493
00:35:35,320 --> 00:35:36,240
And that's not true.
494
00:35:36,240 --> 00:35:38,050
It's larger by assumption.
495
00:35:38,050 --> 00:35:39,690
So it's a contradiction.
496
00:35:39,690 --> 00:35:42,570
So this is a very
general principle though.
497
00:35:42,570 --> 00:35:44,370
And it's worth
writing it all out.
498
00:35:44,370 --> 00:35:50,350
Because this is a famous rule
that we will use in counting.
499
00:35:50,350 --> 00:35:53,661
And it leads to
interestingly results.
500
00:35:53,661 --> 00:35:54,160
OK.
501
00:35:54,160 --> 00:35:58,840
So let's give another example.
502
00:35:58,840 --> 00:36:00,700
Let's think about Boston.
503
00:36:00,700 --> 00:36:05,350
In Boston, we have say a half
a million non-bald people.
504
00:36:05,350 --> 00:36:12,450
It turns out that there
are at least 3 people that
505
00:36:12,450 --> 00:36:15,485
have the exact same number
or hairs on the head.
506
00:36:15,485 --> 00:36:16,560
So that's kind of weird.
507
00:36:16,560 --> 00:36:17,960
How do we know that?
508
00:36:17,960 --> 00:36:22,180
I cannot point out any three
in Boston that have the same
509
00:36:22,180 --> 00:36:23,520
number of hairs.
510
00:36:23,520 --> 00:36:24,690
I have no idea.
511
00:36:24,690 --> 00:36:27,730
But somehow I can count
and use this principle
512
00:36:27,730 --> 00:36:30,060
and tell you that
it must be true
513
00:36:30,060 --> 00:36:34,110
that in Boston with
500,000 people,
514
00:36:34,110 --> 00:36:36,990
there are 3 of them
that are not bald.
515
00:36:36,990 --> 00:36:38,370
So we exclude the bald people.
516
00:36:38,370 --> 00:36:39,494
Because that would be easy.
517
00:36:39,494 --> 00:36:40,470
They all have 0 hairs.
518
00:36:40,470 --> 00:36:44,970
But say non-bald
people that actually
519
00:36:44,970 --> 00:36:46,520
have the same number of hairs.
520
00:36:46,520 --> 00:36:49,170
So how do we do that?
521
00:36:49,170 --> 00:36:52,180
How can we make such
types of conclusions?
522
00:36:52,180 --> 00:37:01,860
So say Boston has about
500,000 and non-bald people.
523
00:37:01,860 --> 00:37:06,050
And let's call this set x.
524
00:37:06,050 --> 00:37:09,550
Because we're going to use
the pigeon hole principle.
525
00:37:09,550 --> 00:37:21,210
So our claim is that there
exists 3 people in Boston such
526
00:37:21,210 --> 00:37:30,420
that they have the same
number of hairs on their head.
527
00:37:36,030 --> 00:37:39,630
So how do we do this?
528
00:37:39,630 --> 00:37:44,830
Well, we know that
we may generally
529
00:37:44,830 --> 00:37:47,160
assume that any
person has at most
530
00:37:47,160 --> 00:37:50,750
200,000 hairs on their head.
531
00:37:50,750 --> 00:38:06,630
So the number of hairs on
a head is at most 200,000.
532
00:38:06,630 --> 00:38:09,780
So how should I define
my set y in order
533
00:38:09,780 --> 00:38:12,080
to apply this pigeon
hole principle?
534
00:38:12,080 --> 00:38:15,210
So what do we do?
535
00:38:15,210 --> 00:38:18,670
So I want to have
mapping, right,
536
00:38:18,670 --> 00:38:29,030
from all the people the set
x to the number of hairs.
537
00:38:29,030 --> 00:38:36,440
So the number of hairs on one's
head is going to be the set y.
538
00:38:36,440 --> 00:38:38,950
And what do we know?
539
00:38:38,950 --> 00:38:43,270
We know that the cardinality
of y is at most 200,000.
540
00:38:43,270 --> 00:38:48,350
Actually, the way we defined
it it's exactly 200,000.
541
00:38:48,350 --> 00:38:54,950
And the set x has a
cardinality of about 500,000.
542
00:38:54,950 --> 00:38:57,190
So what do we know?
543
00:38:57,190 --> 00:39:00,060
We can apply our generalized
pigeon hole principle.
544
00:39:00,060 --> 00:39:05,880
It's very surprising, because we
notice that x is more than two
545
00:39:05,880 --> 00:39:09,530
times the cardinality of y.
546
00:39:09,530 --> 00:39:13,080
2 times 200,000 is
less than 500,000.
547
00:39:13,080 --> 00:39:18,470
So I know that by this
particular principle,
548
00:39:18,470 --> 00:39:21,790
this particular mapping must
have the property, because this
549
00:39:21,790 --> 00:39:26,020
holds for all mappings, that
there are at least k plus 1, 2
550
00:39:26,020 --> 00:39:32,450
plus 1, 3 different people
in Boston out of the set
551
00:39:32,450 --> 00:39:36,262
x that are mapped to
the same element in y.
552
00:39:36,262 --> 00:39:37,970
That means that they
have the same number
553
00:39:37,970 --> 00:39:39,669
of hairs on their head.
554
00:39:39,669 --> 00:39:41,210
So this is kind of
really surprising.
555
00:39:41,210 --> 00:39:45,080
We can make a statement
without really inspecting
556
00:39:45,080 --> 00:39:47,490
every single person's head.
557
00:39:47,490 --> 00:39:52,170
But we can still make a
statement about the fact
558
00:39:52,170 --> 00:39:54,812
that there are 3 different
people in Boston that have
559
00:39:54,812 --> 00:39:58,020
the exact same number of hairs.
560
00:39:58,020 --> 00:40:01,770
So this is an example of
a non-constructive proof.
561
00:40:01,770 --> 00:40:03,450
And I will give another one.
562
00:40:03,450 --> 00:40:07,250
And it's a very
important principle.
563
00:40:07,250 --> 00:40:10,400
There's actually a new technique
that you haven't seen before.
564
00:40:10,400 --> 00:40:14,340
So far we have been
constructively proofing
565
00:40:14,340 --> 00:40:16,860
all kinds of properties
using induction mainly.
566
00:40:20,120 --> 00:40:22,460
And this is what is called
a non-constructive proof.
567
00:40:22,460 --> 00:40:26,790
Because I cannot give a specific
example that demonstrates that
568
00:40:26,790 --> 00:40:29,230
this claim is true.
569
00:40:29,230 --> 00:40:31,860
But yet, I've shown
that it is true,
570
00:40:31,860 --> 00:40:36,210
but in a non-constructive
way without an example.
571
00:40:36,210 --> 00:40:36,710
OK.
572
00:40:36,710 --> 00:40:39,510
So what about another one?
573
00:40:44,590 --> 00:40:50,200
For example, we may pick 10
arbitrary two-digit numbers.
574
00:40:50,200 --> 00:40:58,695
So pick 10 arbitrary
double-digit numbers.
575
00:41:02,750 --> 00:41:07,805
And we can pick any
sequence of numbers.
576
00:41:07,805 --> 00:41:09,740
I'm just picking a few.
577
00:41:09,740 --> 00:41:11,840
You may add a few, too.
578
00:41:11,840 --> 00:41:23,470
i don't know, 2, 7, 14, I don't
know, 31, 25, 60, 92, and so
579
00:41:23,470 --> 00:41:24,230
on.
580
00:41:24,230 --> 00:41:30,510
So I have 1, 2,
3, 4, 5, 6, 7, 8,
581
00:41:30,510 --> 00:41:37,720
I don't know 9, and another one,
say, 91 or something like that.
582
00:41:37,720 --> 00:41:41,450
And so I have 10
double-digit numbers.
583
00:41:41,450 --> 00:41:43,920
It turns out that I can
show to you that there
584
00:41:43,920 --> 00:41:50,560
are two subsets that if I look
at the sum of their elements,
585
00:41:50,560 --> 00:41:53,550
so I look at sum of the
elements of the first subset
586
00:41:53,550 --> 00:41:57,810
and I look at the sum of the
elements of the second subset,
587
00:41:57,810 --> 00:42:02,080
that I can find two subsets
that have an equal sum.
588
00:42:02,080 --> 00:42:03,930
Now if you just look
at those numbers,
589
00:42:03,930 --> 00:42:07,642
and I've now picked 10
arbitrary double-digit numbers,
590
00:42:07,642 --> 00:42:10,100
well, usually it's pretty hard
to figure out whether that's
591
00:42:10,100 --> 00:42:11,040
really true or not.
592
00:42:11,040 --> 00:42:13,970
Maybe I have been selecting
the numbers in such a way
593
00:42:13,970 --> 00:42:16,460
that it's easy to see.
594
00:42:16,460 --> 00:42:19,480
I mean, we can still try
to wrap our minds around it
595
00:42:19,480 --> 00:42:21,810
and try to really solve
this constructively
596
00:42:21,810 --> 00:42:23,880
by giving an example.
597
00:42:23,880 --> 00:42:26,380
It turns out that we can
prove this statement.
598
00:42:26,380 --> 00:42:29,880
And we will use the
pigeon hole principle.
599
00:42:29,880 --> 00:42:32,550
And we do not even have
to actually-- oh, you
600
00:42:32,550 --> 00:42:33,731
have a question?
601
00:42:33,731 --> 00:42:36,320
AUDIENCE: [INAUDIBLE].
602
00:42:36,320 --> 00:42:37,170
PROFESSOR: Oh, sure.
603
00:42:37,170 --> 00:42:39,110
We can make it double-digits.
604
00:42:39,110 --> 00:42:40,900
So I could put this here.
605
00:42:40,900 --> 00:42:44,020
It'll be 4, 2 of I want to.
606
00:42:44,020 --> 00:42:46,469
But yeah, just select
something else.
607
00:42:46,469 --> 00:42:47,510
It doesn't really matter.
608
00:42:51,931 --> 00:42:52,430
Yeah.
609
00:42:52,430 --> 00:42:55,160
So what we are going to show now
is that through the pigeon hole
610
00:42:55,160 --> 00:42:59,240
principle, we can prove that
there are two subsets that
611
00:42:59,240 --> 00:43:00,830
have the same sum.
612
00:43:00,830 --> 00:43:05,420
And just by inspection it's
a very hard problem to solve.
613
00:43:05,420 --> 00:43:08,380
So I did not even
give you an example.
614
00:43:08,380 --> 00:43:10,600
But we can still show this.
615
00:43:10,600 --> 00:43:12,970
So how can we go
ahead with this?
616
00:43:12,970 --> 00:43:16,740
So let's think together
about this problem.
617
00:43:16,740 --> 00:43:22,060
So I want to choose
two sets x and y.
618
00:43:22,060 --> 00:43:26,580
And somehow, I want to
have a mapping, right,
619
00:43:26,580 --> 00:43:34,840
from any double-digit
set of numbers.
620
00:43:34,840 --> 00:43:38,020
Somehow I want to
map that to sums.
621
00:43:38,020 --> 00:43:39,680
Because that's what
I'm interested in.
622
00:43:39,680 --> 00:43:40,820
I'm interested in sums.
623
00:43:40,820 --> 00:43:50,990
And I want to show
something about subsets
624
00:43:50,990 --> 00:43:52,770
of these double-digit numbers.
625
00:43:52,770 --> 00:43:54,790
So what do I do?
626
00:43:54,790 --> 00:44:06,830
I take x as the collection
of subsets of these numbers.
627
00:44:10,370 --> 00:44:14,040
And I want to that there are
at least two subsets that
628
00:44:14,040 --> 00:44:15,880
map to the same sum.
629
00:44:15,880 --> 00:44:18,890
So let's first count
how many we have here.
630
00:44:18,890 --> 00:44:19,790
We already did this.
631
00:44:19,790 --> 00:44:26,240
We made a mapping from subsets
to two binary sequences,
632
00:44:26,240 --> 00:44:27,660
bit sequences.
633
00:44:27,660 --> 00:44:31,160
In this case, we
have 10 numbers.
634
00:44:31,160 --> 00:44:37,660
So we have 2 to the power
10 possible subsets.
635
00:44:37,660 --> 00:44:41,870
So this is equal to 1,024.
636
00:44:41,870 --> 00:44:46,890
Now y is going to be
the sum of a subset.
637
00:44:46,890 --> 00:44:51,520
So what do I know?
638
00:44:51,520 --> 00:44:55,570
I know that the
possible sums range
639
00:44:55,570 --> 00:45:00,300
from 0 all the way to,
well, what's the maximum?
640
00:45:00,300 --> 00:45:05,990
sum that I can have
out of a subset of 10
641
00:45:05,990 --> 00:45:07,000
double-digit numbers?
642
00:45:07,000 --> 00:45:13,110
So I can select all the
10 elements in this set.
643
00:45:13,110 --> 00:45:14,320
And they are double digit.
644
00:45:14,320 --> 00:45:18,410
So at most, they are 99.
645
00:45:18,410 --> 00:45:23,650
So I know that
this set is really
646
00:45:23,650 --> 00:45:28,070
the set of all possible sums.
647
00:45:31,630 --> 00:45:36,250
Now we know that 1,024
is more than 990.
648
00:45:36,250 --> 00:45:40,980
So the cardinality of x is
more than the cardinality of y.
649
00:45:40,980 --> 00:45:42,460
So by the pigeon
hole principle, we
650
00:45:42,460 --> 00:45:46,960
know that there exists at least
two different elements of x.
651
00:45:46,960 --> 00:45:50,710
In our case, there exists
two different subsets
652
00:45:50,710 --> 00:45:56,600
that map to the same
elements in y, the same sum.
653
00:45:56,600 --> 00:46:03,050
So now we have shown that
even though we have not
654
00:46:03,050 --> 00:46:05,760
shown any particular
example that demonstrates
655
00:46:05,760 --> 00:46:08,620
this claim that there are
two different subsets that
656
00:46:08,620 --> 00:46:12,010
have the same sum, we
still got a proof using
657
00:46:12,010 --> 00:46:14,460
counting that this is true.
658
00:46:14,460 --> 00:46:17,500
So this is called a
non-constructive proof.
659
00:46:17,500 --> 00:46:18,545
Let me write it down.
660
00:46:25,980 --> 00:46:32,540
And this is a great way
of proofing properties.
661
00:46:36,720 --> 00:46:45,280
So now we can continue
with another definition
662
00:46:45,280 --> 00:46:48,610
where we look at
another property.
663
00:46:48,610 --> 00:46:51,490
Over here, we talks about
surjectivity, injectivity,
664
00:46:51,490 --> 00:46:54,670
and bijectivity.
665
00:46:54,670 --> 00:47:02,630
And now we will talk about
the following property.
666
00:47:02,630 --> 00:47:15,560
We say that a k
to 1 function is f
667
00:47:15,560 --> 00:47:33,795
from x to y actually maps
actually k elements of x
668
00:47:33,795 --> 00:47:42,190
to every element of y.
669
00:47:42,190 --> 00:47:45,890
So what do we know?
670
00:47:45,890 --> 00:47:49,770
Well, we can have the
following counting rule
671
00:47:49,770 --> 00:47:52,200
that we call the division rule.
672
00:47:52,200 --> 00:47:57,020
And it says that if f
such a type of function,
673
00:47:57,020 --> 00:48:05,940
so if f is k to 1,
well then we know
674
00:48:05,940 --> 00:48:09,340
that the cardinality
of the domain
675
00:48:09,340 --> 00:48:16,170
is equal to k times
the cardinality y.
676
00:48:16,170 --> 00:48:16,920
And why is that?
677
00:48:16,920 --> 00:48:21,160
Well, exactly k elements of
x map to each element of y.
678
00:48:21,160 --> 00:48:23,240
So the first element
of y, we have
679
00:48:23,240 --> 00:48:25,460
k elements of x mapped to it.
680
00:48:25,460 --> 00:48:28,680
The second element of y, k
elements mapped to that one.
681
00:48:28,680 --> 00:48:31,030
So we know that the
domain is exactly
682
00:48:31,030 --> 00:48:35,930
k times the range, k times
the size of the range.
683
00:48:35,930 --> 00:48:41,830
Now this division rule
actually generalizes
684
00:48:41,830 --> 00:48:46,020
the bijection rule,
which I've put
685
00:48:46,020 --> 00:48:48,010
over there, the bijection rule.
686
00:48:50,570 --> 00:48:53,030
And why is that?
687
00:48:53,030 --> 00:48:59,520
Well, that's because a function
is a bijection if and only
688
00:48:59,520 --> 00:49:05,720
if it is actually 1 to 1.
689
00:49:05,720 --> 00:49:11,340
So if you replace k by 1, we
have that exactly one element
690
00:49:11,340 --> 00:49:13,510
of x is mapped to
every element in y.
691
00:49:13,510 --> 00:49:17,080
And that's the definition
of a bijection.
692
00:49:17,080 --> 00:49:20,180
And the bijection rule says
that if you have a bijection,
693
00:49:20,180 --> 00:49:23,000
then the cardinality
of the domain
694
00:49:23,000 --> 00:49:26,140
is equal to the cardinality
of the range, so for k
695
00:49:26,140 --> 00:49:29,350
equals 1 here.
696
00:49:29,350 --> 00:49:33,890
So let's give an example
on how this works.
697
00:49:33,890 --> 00:49:38,993
I think we can take
this out actually.
698
00:49:42,240 --> 00:49:46,430
So let's give an example
using a chessboard,
699
00:49:46,430 --> 00:49:51,860
where we have 2 identical rooks
and we want to count the number
700
00:49:51,860 --> 00:49:57,060
of ways we can put them on the
chessboard in such a way that
701
00:49:57,060 --> 00:50:01,640
the 2 rooks cannot
see one another,
702
00:50:01,640 --> 00:50:06,040
meaning that the rooks are on
different rows and on different
703
00:50:06,040 --> 00:50:08,140
columns.
704
00:50:08,140 --> 00:50:10,500
So let's give an example.
705
00:50:10,500 --> 00:50:11,700
So the example is like this.
706
00:50:11,700 --> 00:50:32,160
So how many ways do we have
to place 2 identical rooks
707
00:50:32,160 --> 00:50:45,735
on a chessboard in such a
way that no row or column
708
00:50:45,735 --> 00:50:46,235
is shared?
709
00:50:50,820 --> 00:50:54,270
So how can we do this?
710
00:50:54,270 --> 00:50:59,750
Well, for example, let's
look at a chessboard.
711
00:51:04,190 --> 00:51:09,980
And suppose we have a rook
over here and a rook over here.
712
00:51:09,980 --> 00:51:18,250
And say the first rook is
on row 1 and on column 1.
713
00:51:18,250 --> 00:51:25,050
And the second rook is
on row 2, R2, on row R2,
714
00:51:25,050 --> 00:51:31,280
and on the column
that is indexed by C2.
715
00:51:31,280 --> 00:51:35,270
So how can we describe
such configurations?
716
00:51:35,270 --> 00:51:40,230
Well, I could describe this
by using a sequence in which I
717
00:51:40,230 --> 00:51:42,230
look at the placement
of the first rook,
718
00:51:42,230 --> 00:51:44,570
and then describe the
placement of the second rook.
719
00:51:44,570 --> 00:51:51,400
So I may have r1, c1,
and then r2 and c2.
720
00:51:51,400 --> 00:51:54,680
So this could be
a way to describe
721
00:51:54,680 --> 00:51:57,830
the positioning of these rooks.
722
00:51:57,830 --> 00:52:03,470
And I could create a mapping
f that is doing this for me.
723
00:52:03,470 --> 00:52:11,210
And so if I call this
an example of a valid.
724
00:52:14,020 --> 00:52:17,200
So let y be the set of
valid rook configuration.
725
00:52:17,200 --> 00:52:18,640
And this is one example of it.
726
00:52:18,640 --> 00:52:20,646
So this is part of this set.
727
00:52:30,380 --> 00:52:44,510
And if I define x
as all the sequences
728
00:52:44,510 --> 00:52:53,160
r1, c1, r2, and c2 such that,
well, the rook over here
729
00:52:53,160 --> 00:52:55,670
does not share a row
with the rook that
730
00:52:55,670 --> 00:52:57,280
is described by this position.
731
00:52:57,280 --> 00:53:00,800
So r1 is not equal to r2.
732
00:53:00,800 --> 00:53:02,710
And they also do
not share a column.
733
00:53:02,710 --> 00:53:07,790
So the first rook has column c1.
734
00:53:07,790 --> 00:53:10,860
The second one is on column c2.
735
00:53:10,860 --> 00:53:13,555
So also c1 and c2
should be different.
736
00:53:16,080 --> 00:53:19,080
So these sequences are
really placements, right?
737
00:53:19,080 --> 00:53:23,040
So this describes rook 1.
738
00:53:23,040 --> 00:53:26,680
This describes the rook 2.
739
00:53:26,680 --> 00:53:31,605
And the whole combination
is really a placement.
740
00:53:36,950 --> 00:53:38,690
So now I have
described the function
741
00:53:38,690 --> 00:53:41,820
f that maps a sequence
that describes
742
00:53:41,820 --> 00:53:45,710
the position of the first
and the second rook,
743
00:53:45,710 --> 00:53:49,450
maps such a sequence
to an element in y,
744
00:53:49,450 --> 00:53:52,830
which is a valid
rook configuration.
745
00:53:52,830 --> 00:53:56,470
So now let's have a look at how
we can apply the division rule.
746
00:53:56,470 --> 00:54:02,380
So is this function bijective?
747
00:54:02,380 --> 00:54:02,940
Is that true?
748
00:54:06,770 --> 00:54:11,300
So is it true that every--
so I have a mapping that
749
00:54:11,300 --> 00:54:13,530
goes from here to here.
750
00:54:13,530 --> 00:54:18,510
But is it true that every
valid rook configuration
751
00:54:18,510 --> 00:54:22,120
is mapped to exactly once?
752
00:54:22,120 --> 00:54:23,870
Is that true?
753
00:54:23,870 --> 00:54:33,960
Is this the only sequence that
will map using this function f
754
00:54:33,960 --> 00:54:35,285
into a valid configuration?
755
00:54:38,170 --> 00:54:38,670
Yup.
756
00:54:38,670 --> 00:54:40,090
It's true.
757
00:54:40,090 --> 00:54:45,140
So you can switch
rook 1 and rook 2.
758
00:54:45,140 --> 00:54:46,910
And it will still look the same.
759
00:54:46,910 --> 00:54:48,190
The 2 rooks are identical.
760
00:54:48,190 --> 00:54:49,450
They look exactly the same.
761
00:54:49,450 --> 00:54:53,520
So we have, again, the
exact same configuration.
762
00:54:53,520 --> 00:55:02,150
And we can see that this
particular sequence also
763
00:55:02,150 --> 00:55:03,320
maps to the same.
764
00:55:03,320 --> 00:55:06,840
It just swap the positions.
765
00:55:06,840 --> 00:55:11,550
So we have r2, c2,
r1, and c1 also maps
766
00:55:11,550 --> 00:55:14,770
under f to the
same configuration.
767
00:55:14,770 --> 00:55:18,960
And those are the
exact 2 possibilities
768
00:55:18,960 --> 00:55:24,230
that can happen that map
to this configuration.
769
00:55:24,230 --> 00:55:28,290
Every valid configuration is
mapped to exactly 2 times.
770
00:55:28,290 --> 00:55:30,780
So now we can use
the division rule.
771
00:55:30,780 --> 00:55:32,570
Because f is 2 to 1.
772
00:55:32,570 --> 00:55:39,240
So f is 2 to 1.
773
00:55:39,240 --> 00:55:41,720
What does that mean if you
apply the division rule?
774
00:55:41,720 --> 00:55:47,220
It means that the cardinality
of all those sequences
775
00:55:47,220 --> 00:55:49,500
is equal to 2 times
the cardinality
776
00:55:49,500 --> 00:55:52,420
of valid configurations.
777
00:55:52,420 --> 00:55:56,480
Or in other words,
the cardinality
778
00:55:56,480 --> 00:55:59,140
for all the valid configurations
is the cardinality
779
00:55:59,140 --> 00:56:03,840
of all those possible
sequences divided by 2.
780
00:56:03,840 --> 00:56:07,720
So now we can start
counting x over here.
781
00:56:07,720 --> 00:56:08,881
So how do we do that?
782
00:56:08,881 --> 00:56:11,380
Well, I'm going to use something
similar as what we did when
783
00:56:11,380 --> 00:56:13,640
we were counting permutations.
784
00:56:13,640 --> 00:56:17,410
And we'll generalize
it in a moment.
785
00:56:17,410 --> 00:56:18,880
So how do we go about this?
786
00:56:18,880 --> 00:56:20,320
Well, let's have a look.
787
00:56:20,320 --> 00:56:32,410
If I have r1, c1, and r2, and
c2, so this is a sequence.
788
00:56:32,410 --> 00:56:35,450
So how many choices do I have?
789
00:56:35,450 --> 00:56:38,130
Well, a chessboard has 8 rows.
790
00:56:38,130 --> 00:56:46,620
So I can choose 8 possible
rows for the first rook.
791
00:56:46,620 --> 00:56:47,860
It also has 8 columns.
792
00:56:47,860 --> 00:56:52,190
So I have 8 possible
choices for the column.
793
00:56:52,190 --> 00:56:54,180
But what about the second rook?
794
00:56:54,180 --> 00:56:58,690
Well, the second rook can
be on any row except the one
795
00:56:58,690 --> 00:57:01,590
that I've already
selected for the first.
796
00:57:01,590 --> 00:57:07,790
So this 8 minus 1, we have
7 possible choices to select
797
00:57:07,790 --> 00:57:09,530
the row for the second rook.
798
00:57:09,530 --> 00:57:12,600
It must be different from the
one that was already selected.
799
00:57:12,600 --> 00:57:14,620
And I have 7 possible choices.
800
00:57:14,620 --> 00:57:17,650
And similarly for
this particular column
801
00:57:17,650 --> 00:57:19,990
as well, the column
has to be different.
802
00:57:19,990 --> 00:57:22,080
So how many choices do I have?
803
00:57:22,080 --> 00:57:23,310
Well, it's not 8.
804
00:57:23,310 --> 00:57:25,440
It's one less, because
I've already selected
805
00:57:25,440 --> 00:57:27,830
the one for the first rook.
806
00:57:27,830 --> 00:57:31,100
So I have 7 choices.
807
00:57:31,100 --> 00:57:36,200
So the cardinality of x is
actually equal to 8 times
808
00:57:36,200 --> 00:57:38,220
8 times 7 times 7.
809
00:57:38,220 --> 00:57:43,520
So it's 8 times 7
squared divided by 2.
810
00:57:43,520 --> 00:57:46,670
So now we have to counted,
by using the division rule,
811
00:57:46,670 --> 00:57:49,065
we have to the divide this by 2.
812
00:57:49,065 --> 00:57:51,440
We have counted the total
number of valid configurations.
813
00:57:55,460 --> 00:57:58,560
So now we are going to
generalize this principle
814
00:57:58,560 --> 00:58:00,580
that we have talked about here.
815
00:58:00,580 --> 00:58:05,980
And we will do that
over here I think.
816
00:58:05,980 --> 00:58:07,870
Yup.
817
00:58:07,870 --> 00:58:11,494
And that's the
generalized product rule.
818
00:58:15,210 --> 00:58:21,460
So the generalized product
rule is as follows.
819
00:58:21,460 --> 00:58:25,200
It's essentially
saying that if we
820
00:58:25,200 --> 00:58:30,950
have a set of sequences
of length k, then
821
00:58:30,950 --> 00:58:32,320
how can we count those?
822
00:58:32,320 --> 00:58:36,055
Well, if we know the
following properties-- well,
823
00:58:36,055 --> 00:58:45,486
let me first write out
the generalized product
824
00:58:45,486 --> 00:58:53,050
rule is as follows.
825
00:58:53,050 --> 00:59:03,380
Let S be a set of
length k sequences.
826
00:59:07,300 --> 00:59:26,940
Then I know that if there
are n1 possible first entries
827
00:59:26,940 --> 00:59:30,970
and if I know that once I've
selected my first entry,
828
00:59:30,970 --> 00:59:43,567
there are n2 possible second
entries for each first entry.
829
00:59:55,020 --> 00:59:57,640
And if I continue
like this, my choice
830
00:59:57,640 --> 01:00:00,710
for the third term
in the sequence
831
01:00:00,710 --> 01:00:07,930
is I've always n3
possible choices
832
01:00:07,930 --> 01:00:11,990
given my selection for
the first 2 entries.
833
01:00:11,990 --> 01:00:14,950
So if I have that property
that continues in that way,
834
01:00:14,950 --> 01:00:16,080
so let me write it out.
835
01:00:16,080 --> 01:00:26,458
So we have n3
possible third entries
836
01:00:26,458 --> 01:00:39,210
for each combination
in this case of first
837
01:00:39,210 --> 01:00:45,370
together with second entries.
838
01:00:45,370 --> 01:00:49,890
And if I continue this
all the way to nk,
839
01:00:49,890 --> 01:00:54,810
so nk possible kth entries
for each combination of all
840
01:00:54,810 --> 01:01:02,070
the previous
entries, then I know
841
01:01:02,070 --> 01:01:06,430
that the set S
can be counted as,
842
01:01:06,430 --> 01:01:09,560
well, I've n1 possible
choices for the first entry.
843
01:01:09,560 --> 01:01:11,350
Once I've chosen
to fix that one,
844
01:01:11,350 --> 01:01:15,010
I have n2 possible choices
for the second, then
845
01:01:15,010 --> 01:01:16,830
n3 possible choice
for the third.
846
01:01:16,830 --> 01:01:21,520
And I go all the way to nk.
847
01:01:21,520 --> 01:01:23,780
Well, let's first talk about
it from the perspective
848
01:01:23,780 --> 01:01:25,980
of the chess problem here.
849
01:01:25,980 --> 01:01:29,960
I got 8 possible choices for r1.
850
01:01:29,960 --> 01:01:32,130
Given r1, I don't care.
851
01:01:32,130 --> 01:01:35,290
I still have 8 possible
choices for the column here.
852
01:01:35,290 --> 01:01:37,270
So I have 8 choices here.
853
01:01:37,270 --> 01:01:42,220
But for the third one, once
I have selected r1 and c1,
854
01:01:42,220 --> 01:01:48,160
I only have 7 choices left for
r2 and 7 choices left for c2.
855
01:01:48,160 --> 01:01:50,800
So that's an
example where we use
856
01:01:50,800 --> 01:01:54,160
this particular
generalized product rule.
857
01:01:54,160 --> 01:01:59,210
Also when we were counting
the number of permutations,
858
01:01:59,210 --> 01:02:02,390
we were saying we can
fix the first entry
859
01:02:02,390 --> 01:02:04,740
of a permutation
in n ways if I have
860
01:02:04,740 --> 01:02:07,160
a permutation for n elements.
861
01:02:07,160 --> 01:02:13,640
And then I have the second
entry, the second term,
862
01:02:13,640 --> 01:02:16,410
of a permutation has
only n minus 1 choices.
863
01:02:16,410 --> 01:02:18,770
Because I've already chosen one.
864
01:02:18,770 --> 01:02:20,850
And the next one has
n minus 3 choices.
865
01:02:20,850 --> 01:02:23,020
Because I've already
selected 2 of them.
866
01:02:23,020 --> 01:02:25,350
So I have only n
minus 2 choices left.
867
01:02:25,350 --> 01:02:26,830
Then I have n minus 3 choices.
868
01:02:26,830 --> 01:02:29,430
Because I've already
selected 3 and so on.
869
01:02:29,430 --> 01:02:31,870
And I get n factorial.
870
01:02:31,870 --> 01:02:36,070
So that's the same kind of
principle that we have here.
871
01:02:36,070 --> 01:02:42,170
So let me give an example where
we can see how this works.
872
01:02:57,550 --> 01:02:59,700
So what do we do?
873
01:02:59,700 --> 01:03:03,920
In this example, we want to
count the number of committees.
874
01:03:03,920 --> 01:03:05,635
So it's the exact
same kind of principle
875
01:03:05,635 --> 01:03:08,170
that we are going to talk about.
876
01:03:08,170 --> 01:03:13,390
So we are going to count the
number of communities described
877
01:03:13,390 --> 01:03:18,370
by sequence x, y, z, where
x the first one is, say,
878
01:03:18,370 --> 01:03:21,560
the leader of the committee.
879
01:03:21,560 --> 01:03:25,790
The second one
indicates the secretary.
880
01:03:25,790 --> 01:03:29,200
The third one is
some consultant.
881
01:03:29,200 --> 01:03:30,880
So they're all different.
882
01:03:30,880 --> 01:03:33,070
They have all different roles.
883
01:03:33,070 --> 01:03:41,335
And such a committee is
elected from n members.
884
01:03:44,260 --> 01:03:46,690
And in how many
ways can I do this?
885
01:03:46,690 --> 01:03:53,290
Well, I have n ways to choose
my first term in the sequence.
886
01:03:53,290 --> 01:03:55,590
I have n ways to
choose the leader.
887
01:03:55,590 --> 01:03:59,235
So there's n ways to choose x.
888
01:04:03,090 --> 01:04:04,680
How many ways do I
have to choose y?
889
01:04:04,680 --> 01:04:06,880
Well, if I've chosen
already a leader,
890
01:04:06,880 --> 01:04:08,400
I need to choose someone else.
891
01:04:08,400 --> 01:04:13,140
So I have n minus 1 members
left, n minus 1 ways
892
01:04:13,140 --> 01:04:14,485
to choose y.
893
01:04:17,760 --> 01:04:20,550
I'm just not
allowed to choose x.
894
01:04:23,690 --> 01:04:27,000
And then I will
have n minus 2 ways
895
01:04:27,000 --> 01:04:34,100
to choose a z except x and y.
896
01:04:34,100 --> 01:04:39,270
And so for each x, I have only
n minus 1 ways to choose y.
897
01:04:39,270 --> 01:04:44,010
For each x and y, I have only
n minus 2 ways to choose z.
898
01:04:44,010 --> 01:04:46,640
So if I multiply
all this together,
899
01:04:46,640 --> 01:04:51,190
I get n times n minus
1 times n minus 2
900
01:04:51,190 --> 01:04:54,610
to choose all these
committee-- this
901
01:04:54,610 --> 01:04:56,360
is the total number
of possible committees
902
01:04:56,360 --> 01:05:01,960
that I can select from an
n member set of people.
903
01:05:01,960 --> 01:05:06,450
So let's go to a little bit
of a different example that
904
01:05:06,450 --> 01:05:07,510
uses the same principle.
905
01:05:10,431 --> 01:05:10,930
OK.
906
01:05:10,930 --> 01:05:14,030
Let's make some space.
907
01:05:18,570 --> 01:05:22,790
In the second problem,
I will define to you
908
01:05:22,790 --> 01:05:25,107
a defective dollar bill.
909
01:05:25,107 --> 01:05:26,190
It's not really defective.
910
01:05:26,190 --> 01:05:30,420
But it's a property that we
will assign to dollar bill.
911
01:05:30,420 --> 01:05:32,170
And you can check for
yourself whether you
912
01:05:32,170 --> 01:05:34,410
have one in your wallet.
913
01:05:34,410 --> 01:05:38,230
So let's define a
defective dollar bill
914
01:05:38,230 --> 01:05:41,860
to have the property
that if you look
915
01:05:41,860 --> 01:05:53,540
at the 8-bit serial
number, some of the digits
916
01:05:53,540 --> 01:05:55,590
appear more than once.
917
01:05:55,590 --> 01:06:11,560
So some digit appears
more than once
918
01:06:11,560 --> 01:06:14,702
in the 8-bit serial number.
919
01:06:19,430 --> 01:06:22,574
So you can check our own wallet
and check for your $1 bills
920
01:06:22,574 --> 01:06:24,490
and check whether you
have a defective dollar.
921
01:06:24,490 --> 01:06:27,480
This seems to be a pretty
specific and rare property,
922
01:06:27,480 --> 01:06:28,700
right?
923
01:06:28,700 --> 01:06:33,560
Well, check you dollar bills.
924
01:06:33,560 --> 01:06:36,297
You'll figure out that you have
probably a defective dollar
925
01:06:36,297 --> 01:06:37,130
bill in your wallet.
926
01:06:37,130 --> 01:06:38,580
So that's kind of weird.
927
01:06:38,580 --> 01:06:41,120
But it seems this property.
928
01:06:41,120 --> 01:06:42,912
If you look at
that, it seems to be
929
01:06:42,912 --> 01:06:44,620
something that is
maybe a little bit more
930
01:06:44,620 --> 01:06:46,580
common than we thought it is.
931
01:06:46,580 --> 01:06:48,590
It seems to be so special.
932
01:06:48,590 --> 01:06:50,850
So let's do a counting
argument and find out
933
01:06:50,850 --> 01:06:52,590
what's happening here.
934
01:06:52,590 --> 01:06:59,510
So let's look at a fraction
of the non-defective.
935
01:06:59,510 --> 01:07:07,540
So we are counting the opposite,
the non-defective bills.
936
01:07:07,540 --> 01:07:21,090
Well, that's the number of
non-defective serial numbers
937
01:07:21,090 --> 01:07:27,380
divided by the total
number of serial numbers.
938
01:07:31,680 --> 01:07:40,030
And let's call these small
x and y and count these.
939
01:07:40,030 --> 01:07:40,640
So let's see.
940
01:07:44,340 --> 01:07:46,250
So first of all, let's count y.
941
01:07:46,250 --> 01:07:49,480
Well, that's easy, I have 8
digits in my serial number.
942
01:07:49,480 --> 01:07:52,290
So I have 10 choices
for the first digit,
943
01:07:52,290 --> 01:07:55,170
10 choices for the
second one, and so on.
944
01:07:55,170 --> 01:07:56,970
In total, I have
10 times 10 times
945
01:07:56,970 --> 01:07:59,580
10 to the power 8 choices.
946
01:07:59,580 --> 01:08:01,530
What about x?
947
01:08:01,530 --> 01:08:08,040
Well, I'm using, again,
our generalized product
948
01:08:08,040 --> 01:08:09,760
rule over here.
949
01:08:09,760 --> 01:08:14,070
Well, if I'm going to have
a non-defective dollar bill,
950
01:08:14,070 --> 01:08:18,069
then all the digits in
the 8 digit serial number
951
01:08:18,069 --> 01:08:20,100
have to be different.
952
01:08:20,100 --> 01:08:23,050
So for the first digit,
I have 10 choices.
953
01:08:23,050 --> 01:08:25,649
Now that I've selected
my first digit,
954
01:08:25,649 --> 01:08:32,290
I have 9 digits for my second
choice for my second digit
955
01:08:32,290 --> 01:08:34,020
in the serial number.
956
01:08:34,020 --> 01:08:36,430
Then I have 8
possible choices, 7,
957
01:08:36,430 --> 01:08:37,950
because I've already selected 3.
958
01:08:37,950 --> 01:08:40,090
And I cannot choose
those anymore--
959
01:08:40,090 --> 01:08:43,760
times 6 times 5 times 4 times 3.
960
01:08:43,760 --> 01:08:48,330
And now I have chosen an 8
digit serial number in which
961
01:08:48,330 --> 01:08:51,760
all the digits are different.
962
01:08:51,760 --> 01:08:55,680
OK So how many are these?
963
01:08:55,680 --> 01:08:58,500
Well, this is actually
equal to 10 factorial
964
01:08:58,500 --> 01:09:01,330
divided by 2 factorial.
965
01:09:01,330 --> 01:09:08,100
And it turns out to be
something like 1,814,400.
966
01:09:08,100 --> 01:09:10,140
possible choices.
967
01:09:10,140 --> 01:09:12,359
So now let's look
at the fraction.
968
01:09:12,359 --> 01:09:15,490
It turns out if you
divide this by this,
969
01:09:15,490 --> 01:09:18,640
you get a really
very small fraction.
970
01:09:18,640 --> 01:09:25,800
This is actually
equal to 1.8144%
971
01:09:25,800 --> 01:09:29,620
So a very small fraction
is non-defective.
972
01:09:29,620 --> 01:09:32,370
So almost all the dollars
are sort of defective.
973
01:09:32,370 --> 01:09:35,840
It simply means that they
have this special property
974
01:09:35,840 --> 01:09:40,434
that some digit
occurs more than once.
975
01:09:40,434 --> 01:09:41,600
So it's kind of interesting.
976
01:09:41,600 --> 01:09:45,695
So we can already
see that by counting,
977
01:09:45,695 --> 01:09:47,569
it's sometimes a little
bit counterintuitive.
978
01:09:47,569 --> 01:09:51,170
Because if I would see
this particular property,
979
01:09:51,170 --> 01:09:53,080
I would in first
instance think that it's
980
01:09:53,080 --> 01:09:54,520
a very special property.
981
01:09:54,520 --> 01:09:55,830
But that's not true.
982
01:09:55,830 --> 01:10:00,070
It's very common it turns out.
983
01:10:00,070 --> 01:10:03,860
Now a special case of the
generalized product rule
984
01:10:03,860 --> 01:10:06,120
is the product rule.
985
01:10:06,120 --> 01:10:10,600
And this is defined as follows.
986
01:10:10,600 --> 01:10:13,285
We are going to first of all
define a product over sets.
987
01:10:15,940 --> 01:10:18,760
The definition is
that the product
988
01:10:18,760 --> 01:10:26,120
of a set A1 with A2
up to An is actually
989
01:10:26,120 --> 01:10:27,506
equal to the set of sequences.
990
01:10:33,170 --> 01:10:40,930
So the first entry is
selected from the first set,
991
01:10:40,930 --> 01:10:45,590
the second entry is selected
from the second set, and so on.
992
01:10:48,630 --> 01:10:51,550
And now the product
rule tells us
993
01:10:51,550 --> 01:10:58,470
by just applying that
reasoning over here
994
01:10:58,470 --> 01:11:07,190
that the cardinality of the
product of all those sets
995
01:11:07,190 --> 01:11:13,740
is actually equal to the
cardinality of the first set
996
01:11:13,740 --> 01:11:16,570
multiplied by the
cardinality of the second set
997
01:11:16,570 --> 01:11:20,210
and so on up to the
cardinality of the last set.
998
01:11:20,210 --> 01:11:23,760
Because we have this
number of choices
999
01:11:23,760 --> 01:11:25,960
for the very first
element over here,
1000
01:11:25,960 --> 01:11:28,730
this number of choices for
the second one, and so on.
1001
01:11:28,730 --> 01:11:33,860
And we apply that rule, and we
see that this is the result.
1002
01:11:33,860 --> 01:11:38,150
Now when we use this, in
specific to count all the n-bit
1003
01:11:38,150 --> 01:11:43,970
sequences, we have exactly
2 choices for the first bit.
1004
01:11:43,970 --> 01:11:50,010
We have to set 0,1 in our
example times the set 0, 1 over
1005
01:11:50,010 --> 01:11:53,520
here and so on.
1006
01:11:53,520 --> 01:12:00,270
And that's how we derived that
we have 2 times 2, 2 the power
1007
01:12:00,270 --> 01:12:04,670
n choices for an n-bit sequence.
1008
01:12:04,670 --> 01:12:07,310
So now we come to the sum rule.
1009
01:12:07,310 --> 01:12:11,680
And we will give an
example for that.
1010
01:12:11,680 --> 01:12:15,770
So the sum rule states
that if you look at sets,
1011
01:12:15,770 --> 01:12:18,700
then we may be able
to count their union.
1012
01:12:18,700 --> 01:12:20,610
And we will consider
a very specific case.
1013
01:12:20,610 --> 01:12:25,710
In the next lecture, we will
talk about the general case.
1014
01:12:25,710 --> 01:12:33,500
So the sum rule is the
following counting mechanism.
1015
01:12:33,500 --> 01:12:41,020
If the sets A1 up to
An are all disjoint,
1016
01:12:41,020 --> 01:12:48,010
so they are disjoint
sets, then we
1017
01:12:48,010 --> 01:12:54,580
know that if I try to count
the union of all those set,
1018
01:12:54,580 --> 01:12:59,210
it's going to be the sum of
the separate cardinalities.
1019
01:12:59,210 --> 01:13:02,830
So let me just write
it out actually.
1020
01:13:02,830 --> 01:13:12,250
So it's the cardinality of
A1 plus A2 all the way to An.
1021
01:13:12,250 --> 01:13:13,470
Why is this?
1022
01:13:13,470 --> 01:13:16,210
Well, all the sets are disjoint.
1023
01:13:16,210 --> 01:13:21,270
So there are no
intersections between sets
1024
01:13:21,270 --> 01:13:22,370
that contain elements.
1025
01:13:22,370 --> 01:13:24,580
All the intersections are empty.
1026
01:13:24,580 --> 01:13:30,310
So counting the union is really
counting each separate set.
1027
01:13:30,310 --> 01:13:32,770
And that's why we have the sum.
1028
01:13:32,770 --> 01:13:35,070
And in the next lecture, we
will talk about inclusion,
1029
01:13:35,070 --> 01:13:36,484
exclusion rule.
1030
01:13:36,484 --> 01:13:37,900
And then we will
take into account
1031
01:13:37,900 --> 01:13:41,020
that we have intersections
that are not empty.
1032
01:13:41,020 --> 01:13:44,110
But let's give now
an example where
1033
01:13:44,110 --> 01:13:52,900
we count the number of passwords
with certain properties.
1034
01:13:52,900 --> 01:13:56,784
And we will apply all these
different rules together.
1035
01:13:56,784 --> 01:13:58,450
And that's the type
of problems that you
1036
01:13:58,450 --> 01:14:01,350
would like to be able to solve.
1037
01:14:01,350 --> 01:14:08,380
So in our last example
here, we have that passwords
1038
01:14:08,380 --> 01:14:10,390
have the following property.
1039
01:14:14,850 --> 01:14:17,305
They are 6 to 8 symbols.
1040
01:14:22,110 --> 01:14:25,280
So that's property 1.
1041
01:14:25,280 --> 01:14:27,920
We have that the
very first symbol
1042
01:14:27,920 --> 01:14:32,398
must be special in the
sense that it is a letter.
1043
01:14:37,180 --> 01:14:42,320
And this can an
upper or lowercase.
1044
01:14:46,830 --> 01:14:59,180
And say that the other symbols
are actually letters or digits.
1045
01:14:59,180 --> 01:15:03,720
So let's count the total
number of possible passwords.
1046
01:15:03,720 --> 01:15:06,150
We're going to use the sum rule.
1047
01:15:06,150 --> 01:15:10,530
So let's define
what kinds of sets
1048
01:15:10,530 --> 01:15:13,480
we are taking the symbols from.
1049
01:15:13,480 --> 01:15:17,220
So the first set is
for the first symbol,
1050
01:15:17,220 --> 01:15:21,030
which we call f or first.
1051
01:15:21,030 --> 01:15:25,200
We have all the letters
a, b, c in lowercase,
1052
01:15:25,200 --> 01:15:27,270
and then all of
them in uppercase.
1053
01:15:30,430 --> 01:15:37,900
And in total, we have
52 elements in this set.
1054
01:15:37,900 --> 01:15:41,600
For the second symbol,
or the other symbols,
1055
01:15:41,600 --> 01:15:45,760
we have all these
letters, but also
1056
01:15:45,760 --> 01:15:50,020
all the digits, 0, 1, up to 9.
1057
01:15:50,020 --> 01:15:55,260
And this set actually
has cardinality 62.
1058
01:15:55,260 --> 01:15:58,960
We added 10 digits.
1059
01:15:58,960 --> 01:16:05,260
So let's talk
about-- actually, we
1060
01:16:05,260 --> 01:16:08,872
like to use this in
the sum rule as well.
1061
01:16:18,600 --> 01:16:20,270
So how do we count?
1062
01:16:20,270 --> 01:16:22,150
What kind of possibilities
do we really have?
1063
01:16:22,150 --> 01:16:25,170
So let's describe
the set of passwords
1064
01:16:25,170 --> 01:16:27,940
explicitly in a formula.
1065
01:16:27,940 --> 01:16:32,331
So let p be the set
of possible passwords.
1066
01:16:38,110 --> 01:16:42,390
And this one is actually
equal to-- well,
1067
01:16:42,390 --> 01:16:45,050
I need to choose a first symbol.
1068
01:16:45,050 --> 01:16:51,070
And then I need to choose a
second symbol, and a third,
1069
01:16:51,070 --> 01:16:55,600
and a fourth, and a
fifth, and a sixth.
1070
01:16:55,600 --> 01:16:56,690
That's one possibility.
1071
01:16:56,690 --> 01:16:58,780
I use 6 symbols.
1072
01:16:58,780 --> 01:17:00,660
I can also use 7 or 8 symbols.
1073
01:17:00,660 --> 01:17:01,840
But this is one of them.
1074
01:17:04,770 --> 01:17:10,120
We also denote this
as S to the power 5.
1075
01:17:10,120 --> 01:17:11,385
That's an equivalent notation.
1076
01:17:15,110 --> 01:17:17,840
The other possibilities
for passwords
1077
01:17:17,840 --> 01:17:24,510
are that we first choose
an entry from f, a letter.
1078
01:17:24,510 --> 01:17:28,460
And then we will need to
choose another 6 symbols.
1079
01:17:28,460 --> 01:17:31,940
In total, we have 7.
1080
01:17:31,940 --> 01:17:35,790
And we have another possibility
where we choose a first symbol,
1081
01:17:35,790 --> 01:17:39,290
and then we choose
7 other symbols.
1082
01:17:39,290 --> 01:17:40,570
So has 8 symbols.
1083
01:17:40,570 --> 01:17:41,880
This has in total 7.
1084
01:17:41,880 --> 01:17:43,970
This one has in total 6 symbols.
1085
01:17:43,970 --> 01:17:47,730
So this covers all the
possible passwords.
1086
01:17:47,730 --> 01:17:49,410
So let's count them.
1087
01:17:49,410 --> 01:17:52,730
We know that these sets
are all the different.
1088
01:17:52,730 --> 01:17:54,590
They are distinct.
1089
01:17:54,590 --> 01:17:59,200
These are sequences that have
6 entries, 7, and 8 entries.
1090
01:17:59,200 --> 01:18:04,340
So if you look at
the cardinality of P,
1091
01:18:04,340 --> 01:18:07,710
it's actually equal to
the sum by the sum rule
1092
01:18:07,710 --> 01:18:12,130
that we just
described over there,
1093
01:18:12,130 --> 01:18:17,900
is equal to the very first
one, f times S to the power
1094
01:18:17,900 --> 01:18:23,320
5 plus the cardinality
of the product
1095
01:18:23,320 --> 01:18:26,800
of f with S to the power 6.
1096
01:18:26,800 --> 01:18:37,180
And we have f times
S to the power 7.
1097
01:18:37,180 --> 01:18:41,580
So this is simply by
application of the sum rule.
1098
01:18:41,580 --> 01:18:43,390
And now we can apply
the product rule
1099
01:18:43,390 --> 01:18:46,060
very simply, which is this one.
1100
01:18:46,060 --> 01:18:49,120
So that's equal
to the cardinality
1101
01:18:49,120 --> 01:18:56,100
of f times the cardinality
of S to the power 5.
1102
01:18:56,100 --> 01:18:59,550
And then we have the same
rule applied to this one.
1103
01:18:59,550 --> 01:19:01,980
It's the commonality of
f times the cardinality
1104
01:19:01,980 --> 01:19:04,840
of S to the power 6.
1105
01:19:04,840 --> 01:19:08,590
And then we have the cardinality
of f times the cardinality of S
1106
01:19:08,590 --> 01:19:09,580
to the power 7.
1107
01:19:12,190 --> 01:19:14,820
Now, we simply
plug-in these numbers.
1108
01:19:14,820 --> 01:19:18,979
And then you will have the
total number of passwords
1109
01:19:18,979 --> 01:19:20,020
that you can select from.
1110
01:19:20,020 --> 01:19:27,640
It turns out to be about 1.8
times 10 to the power 14.
1111
01:19:27,640 --> 01:19:30,320
So here we have applied both to
sum rule and the product rule.
1112
01:19:30,320 --> 01:19:32,026
So in general, you
will see that you
1113
01:19:32,026 --> 01:19:33,620
have to apply multiple
rules together
1114
01:19:33,620 --> 01:19:37,750
in order to find an answer
to your counting problem.
1115
01:19:37,750 --> 01:19:39,600
And you'll see that
on a problem set.
1116
01:19:39,600 --> 01:19:42,510
And we will give a few more
examples in next lecture.
1117
01:19:42,510 --> 01:19:46,000
And we will start talking about
the generalization of the sum
1118
01:19:46,000 --> 01:19:48,170
room called inclusion exclusion.
1119
01:19:48,170 --> 01:19:52,220
And we will give you another
type of proof technique called
1120
01:19:52,220 --> 01:19:54,030
combinatorial proofs.
1121
01:19:54,030 --> 01:19:54,530
All right.
1122
01:19:54,530 --> 01:19:56,690
Good luck with the problems.