WEBVTT
Kind: captions
Language: en
00:00:13.690 --> 00:00:22.520
So, the previous lecture we have seen examples
of groups, we have seen lots of situations
00:00:22.520 --> 00:00:32.770
where groups arise naturally and we also created
we also synthesized the definition of groups
00:00:32.770 --> 00:00:42.370
after all the discussion. And I said last
time that groups are born to act. So, group
00:00:42.370 --> 00:00:47.350
action is something which is very important
concept all throughout all throughout the
00:00:47.350 --> 00:00:53.300
cases which are there in this course,; I said
symmetry, puzzles and motions all these 3
00:00:53.300 --> 00:00:58.989
things actions are something which are at
the center, they are the most important
00:00:58.989 --> 00:01:06.030
that is the most important concept.
So, I am going to discuss what group action
00:01:06.030 --> 00:01:19.810
is and related object related concepts or
which stabilizer lemma orbits and stabilizers
00:01:19.810 --> 00:01:25.530
and you remember the example that I had last
time, that is something that we are going
00:01:25.530 --> 00:01:35.860
to have the back of our mind that that was
a rectangle, and we could perform certain
00:01:35.860 --> 00:01:44.880
symmetry operations on it doing the thing,
flipping about x axis flipping about y axis
00:01:44.880 --> 00:01:57.060
and rotating it by angle of pi right. And
this we said forms a group. So, that is an
00:01:57.060 --> 00:02:01.730
example that we are going to keep in the back
of our mind ok.
00:02:01.730 --> 00:02:14.560
So, let me take certain point here let me
call this point say p. So, group we understand,
00:02:14.560 --> 00:02:25.071
it is a collection of symmetries of this rectangle
and I consider a set what is the set? The
00:02:25.071 --> 00:02:35.540
set consists of all the shaded region along
with the boundary. So, suppose this is a 2
00:02:35.540 --> 00:02:47.680
comma 0 and this is 0 comma 1 suppose that
is a rectangle. Then I consider all those
00:02:47.680 --> 00:03:01.270
points a comma b for which mod of a is less
than equal to 2 and mod of b is less than
00:03:01.270 --> 00:03:10.310
equal to 1 that is this rectangle right the
shaded region along with the boundary let
00:03:10.310 --> 00:03:17.470
is x.
Now, let me take say f x what happens to p
00:03:17.470 --> 00:03:30.520
when I apply f x, that is when I when I flip
about x axis what happens to p? P goes here
00:03:30.520 --> 00:03:44.900
ok. So, this is what p after the action of
after the action of f x. So, through this
00:03:44.900 --> 00:03:54.460
example only I am going to define action and
if I apply f x the other action the action
00:03:54.460 --> 00:04:08.090
of f y, then it will be somewhere here and
that is what I call f y dot p ok and this
00:04:08.090 --> 00:04:15.800
this point will be here somewhere r pi dot
p.
00:04:15.800 --> 00:04:24.530
So, under the influence of this group, that
is through the group action p moves from this
00:04:24.530 --> 00:04:28.710
position to this position, this position and
this pose these four positions it can moved
00:04:28.710 --> 00:04:40.520
ok. So, theres the basic thing. So, formally
I am going to define the action now in
00:04:40.520 --> 00:04:46.680
the action there is a group and then, there
is a set I have already given you a concrete
00:04:46.680 --> 00:04:53.040
example of action through the rectangle and
this group case ok.
00:04:53.040 --> 00:05:05.690
So, what is a group action? I have a group
we call that group was collection of objects
00:05:05.690 --> 00:05:12.520
along with second operation, which followed
certain axioms that I discussed in the last
00:05:12.520 --> 00:05:16.979
class.
So, here is a group and here is a set. So,
00:05:16.979 --> 00:05:37.840
I have group, I have a set and I say that
G acts on x when do I say this when there
00:05:37.840 --> 00:05:47.330
is an action and what is an action. So, as
was happening earlier; I pick a point in the
00:05:47.330 --> 00:05:58.840
set and I pick an element in the group and
under the influence of this element of the
00:05:58.840 --> 00:06:10.010
group the point p moves somewhere within x
and this is what I call g dot p that just
00:06:10.010 --> 00:06:18.490
a notation I call g dot p.
So, I have I pick a pick some element from
00:06:18.490 --> 00:06:26.560
the group pick an element from set and it
goes to some other element of the set. There
00:06:26.560 --> 00:06:33.430
should be certain axioms which have to be
satisfied before we call it an action, identity
00:06:33.430 --> 00:06:43.220
element of the group is not allowed to move
any point that is first axiom action of identity
00:06:43.220 --> 00:06:58.740
on p is just the axiom . So, these are action
axioms for the action 1 dot p is p; second
00:06:58.740 --> 00:07:14.050
is trusting one I take the point p and I take
2 elements g comma h g and h in group.
00:07:14.050 --> 00:07:26.820
So, first with the help of h I try to move
p, that is I am considering the image of h
00:07:26.820 --> 00:07:33.830
comma p under this map. So, h dot p and then
I am trying to move whatever is the resultant
00:07:33.830 --> 00:07:42.080
I am trying to move it by action of g. What
I could have done is that I could have tried
00:07:42.080 --> 00:07:53.990
to move p, by the action of g h; whether I
g h g h is an element of g this is the group
00:07:53.990 --> 00:08:07.370
law as a group law right. So, for this map
g cross x to x to be called an action, I want
00:08:07.370 --> 00:08:19.130
this to be equal I want that action of h on
g followed by action of g on h p. So, that
00:08:19.130 --> 00:08:26.690
that action is just same as the action of
g h on t. So, that is action and as you can
00:08:26.690 --> 00:08:34.180
see this is precisely what happens in the
example of rectangle that ahead, when on the
00:08:34.180 --> 00:08:48.950
rectangle the group of 4 element acts
and back here now there are other concepts
00:08:48.950 --> 00:08:56.051
orbits and stabilizers.
So, let us pick this particular point orbit
00:08:56.051 --> 00:09:05.080
meaning, under the influence of the group
where all can this point p go. As we can see
00:09:05.080 --> 00:09:13.000
here if point is somewhere like this it can
go here, can go here, it can go here after
00:09:13.000 --> 00:09:20.910
the action of this is f x, after the action
of f y, and this is after the action of our
00:09:20.910 --> 00:09:30.540
pi. So, it can move across these four points
what if the point p were here? On the x axis
00:09:30.540 --> 00:09:41.320
it says if that were the case, then under
the action of f y it would go to this point,
00:09:41.320 --> 00:09:48.520
but under the action of f x it will remain
here, and yet the action of r pi it will again
00:09:48.520 --> 00:09:57.240
go here. So, a point here is going to have
2 elements in its orbit ok. So, what is orbit?
00:09:57.240 --> 00:10:18.440
I will just write here, orbit of a point p;
p is in x what is orbit? Orbit is start with
00:10:18.440 --> 00:10:29.720
p and were all you can p go under the influence
of the group, g dot p such that g is in g
00:10:29.720 --> 00:10:37.140
that is orbit.
So, as you have seen this point has four
00:10:37.140 --> 00:10:43.660
elements in orbit well this point has only
2 elements. Now orbit and if I take this origin
00:10:43.660 --> 00:10:53.230
then orbit is the origin because whatever
thing I do 1 f x, f pi r, r pi this point
00:10:53.230 --> 00:11:03.080
is not going to move there is only one element
in the orbit. So, that is orbit, this is another
00:11:03.080 --> 00:11:20.260
concept which is that of stabilizer.
So, stabilizer is stabilizer for a point p
00:11:20.260 --> 00:11:28.950
is the connection of all those points of the
group, that is all those points of the group
00:11:28.950 --> 00:11:43.089
g in g such that g does not move g does not
move p that is g dot p is simply; all those
00:11:43.089 --> 00:11:48.589
points which all those points of the group
all those elements of the group, which fail
00:11:48.589 --> 00:11:57.480
to act on p in the non-trivial fashion that
is called stabilizer. So, what is orbit? Larger
00:11:57.480 --> 00:12:06.959
the orbit meaning the point is moving much
the point is having much more space in the
00:12:06.959 --> 00:12:16.800
set x, but if if if orbit is small then
point is moving slowly right you see this
00:12:16.800 --> 00:12:22.190
point, this is having a smaller orbit its
moving only here and here, but if point is
00:12:22.190 --> 00:12:26.220
this then it is having four elements now orbit
and steb.
00:12:26.220 --> 00:12:34.810
So, if orbit is small as the intuition says
stabilizer will be bigger. So, smaller the
00:12:34.810 --> 00:12:40.080
orbit bigger the stabilizer. For example,
you consider points which have singled
00:12:40.080 --> 00:12:49.579
an orbit that is orbit is just one; no point
in group is moving that that . So, no point
00:12:49.579 --> 00:13:01.280
of the group is moving a given point of the
set that means, stabilizer is everything right.
00:13:01.280 --> 00:13:21.480
So, if orbit of p is singleton then stabilizer
of p. So, I will also call it just stab; stabilizer
00:13:21.480 --> 00:13:37.720
of p is everything right and such points are
called fixed points they are just fixed throughout
00:13:37.720 --> 00:13:43.600
the action no element of group is able to
move those points ok as you can see in this
00:13:43.600 --> 00:13:52.080
example, this is the fixed point this is the
fixed point in action ok.
00:13:52.080 --> 00:14:02.630
So, here in this example there is only one
fixed point and for this fixed point all four
00:14:02.630 --> 00:14:13.350
elements constitute stabilizer. So, this some
kind of conservation law right orbit and stabilizer.
00:14:13.350 --> 00:14:19.139
Orbit is bigger stabilizer is smaller, orbit
is smaller stabilizer is bigger. So, what
00:14:19.139 --> 00:14:30.450
we have therefore, is orbit stabilizer lemma.
So, its true for finite groups.
00:14:30.450 --> 00:14:55.450
So, I will explain what it is. So, I will
just mention it here orbits stabilizer lemma
00:14:55.450 --> 00:15:10.690
what does it say? It says that take a group
which is finite and you take a set x such
00:15:10.690 --> 00:15:30.180
that g acts on that set and see x is also
finite set, and then you pick any element
00:15:30.180 --> 00:15:42.860
in x. You can consider with the stabilizer
of this point this is set from considered
00:15:42.860 --> 00:15:49.940
the size of this; this is a this modules size
of the stabilizer, how many points are there
00:15:49.940 --> 00:16:01.899
in the stabilizer and then you consider orbit
of p and then you consider size of the orbit
00:16:01.899 --> 00:16:09.350
of p. These are 2 numbers multiply these 2
numbers, multiply the size of the stabilizer
00:16:09.350 --> 00:16:19.459
with the size of the orbit and what you have
is actually size of the group. So, that is
00:16:19.459 --> 00:16:25.160
called orbit stabilizer lemma and lemma, this
is some kind of conservation law. Larger the
00:16:25.160 --> 00:16:33.230
orbit smaller the stabilizer and why should
it be true that involves some quotient
00:16:33.230 --> 00:16:42.839
groups or rather taking cossets, and I
am not going to say much in detail about it.
00:16:42.839 --> 00:16:59.820
So, this has something to do with cossets.
For example in this case if your point is
00:16:59.820 --> 00:17:17.859
this, then the orbit size is 2. So, let me
call this point q; for this point
00:17:17.859 --> 00:17:27.579
we take stabilizer of q what is it? Stabilizer
of q is of course, identity identity is always
00:17:27.579 --> 00:17:34.840
stabilizer and apart from that if you take
flipping of about x axis that is also stabilizer
00:17:34.840 --> 00:17:43.379
for this point. So, stabilizer is size 2.
And what is orbit size? Orbit of q is again
00:17:43.379 --> 00:17:55.200
there are 2 points in the orbits this point
and this point. So, the product. So, stabilizer
00:17:55.200 --> 00:18:11.600
of q times orbit of q is 2 into 2 4, which
is precisely the size of the group just through
00:18:11.600 --> 00:18:13.389
the example we have tried to understand this
thing.
00:18:13.389 --> 00:18:20.779
So, I hope now its clear to you what an action
is, what orbit is, what stabilizers are and
00:18:20.779 --> 00:18:36.450
what is orbit stabilizer lemma ok.
So, let me just try to give you a picture,
00:18:36.450 --> 00:19:07.259
just imagine just hm imagine this the some
set x on which a group G is acting.
00:19:07.259 --> 00:19:19.739
Now, I take a point p and the I can consider
all those points where p can go under the
00:19:19.739 --> 00:19:27.909
influence of G. So, p can go to various points.
So, I consider all those points which are
00:19:27.909 --> 00:19:36.379
there in the orbit of p. So, whatever is outside
it, some other point say q I consider orbit
00:19:36.379 --> 00:19:47.409
of that. Some other point r I consider orbit
of it. The question is how to count how many
00:19:47.409 --> 00:19:53.659
orbits are there and that is quite interesting
question has very interesting answer and has
00:19:53.659 --> 00:20:09.299
very interesting applications. The question
is how many orbits are there for a group action
00:20:09.299 --> 00:20:15.599
for a given group actions? G is a group axis
axis, a group action which is happening is
00:20:15.599 --> 00:20:24.200
finite group how many orbits are there? And
its quite interesting answer and before I
00:20:24.200 --> 00:20:35.809
could give that answer to you, I would define
one more concept which is that of fixed points.
00:20:35.809 --> 00:20:49.620
So, here I pick an element in the group, and
I find out all those elements in the set which
00:20:49.620 --> 00:21:00.369
are fixed by g; that means, those points are
not moved by this particular g.
00:21:00.369 --> 00:21:15.299
So, I considered all those points p in x such
that g fails to move those points. For example,
00:21:15.299 --> 00:21:40.239
if g is identity, then by definition of action
itself, everything is fixed one dot p is equal
00:21:40.239 --> 00:21:47.059
to p is it that is a first axiom in the definition
of growth right. So, when gs identity everything
00:21:47.059 --> 00:21:57.659
is fixed. So, fixed points are quite interesting
those points which are not moved by a given
00:21:57.659 --> 00:22:05.389
element in a group.
And what I am going to say is that, question
00:22:05.389 --> 00:22:15.840
at how many orbits are there for a group action
that question has connection with number of
00:22:15.840 --> 00:22:26.799
fixed points
Now, what is the connection? And that is burnsides
00:22:26.799 --> 00:22:38.799
lemma what does it say it says that for each
g you consider how many fixed points are there?
00:22:38.799 --> 00:22:45.859
Take the summation and divide it by the size
of the group and that is actually number of
00:22:45.859 --> 00:22:56.489
fixed points in an orbit its popularly called
burnsides lemma. So, what it is? This is average
00:22:56.489 --> 00:23:14.580
number of fixed points .
So, average number of fixed points equals
00:23:14.580 --> 00:23:22.700
number of orbits is what burnsides lemma says.
Now how to prove such a statement? Its not
00:23:22.700 --> 00:23:28.179
very difficult and its quite useful, and I
am going to tell you 2 interesting applications
00:23:28.179 --> 00:23:52.330
of burnsides lemma ok.
So, I am going to prove burnsides lemma . So,
00:23:52.330 --> 00:24:07.250
we have to have some let us do this I am asking
all the elements of the group and all the
00:24:07.250 --> 00:24:15.999
elements of the set to be expressed here in
a Cartesian format.
00:24:15.999 --> 00:24:31.269
So, let me take this as G axis this is X axis,
I have action of group on a set x g G is acting
00:24:31.269 --> 00:24:49.630
on X. So, here I am marking elements of G
just just a pictorial representation and here
00:24:49.630 --> 00:25:06.590
I am marking say elements of X ok.
So, here just take some point here, suppose
00:25:06.590 --> 00:25:26.039
this element is g this is x then this is say
g comma x ok. So, all these things are presented
00:25:26.039 --> 00:25:36.309
in a Cartesian format and now I consider a
subset of this. So, you can think of his lattice
00:25:36.309 --> 00:25:43.490
lattice which is there. So, many points
are there on this lattice right it is like
00:25:43.490 --> 00:25:59.659
lattice it is g cross x as a set is just g
cross
00:25:59.659 --> 00:26:05.609
x that is some lattice.
So, in this inside this lattice i define a
00:26:05.609 --> 00:26:27.269
set s what is the set? The set is g comma
x. So, this is a subset of G cross X. So,
00:26:27.269 --> 00:26:42.330
all those elements G comma X for which g dot
axis x; that is x refuses to be moved by g
00:26:42.330 --> 00:26:55.350
or g is not able to move x is the same thing.
So, g dot axis x and every the the proof is
00:26:55.350 --> 00:27:05.080
just about size of S.
How many such ordered pairs g comma x are
00:27:05.080 --> 00:27:16.169
there on this lattice for which g dot axis
x? No there are 2 ways count it and that is
00:27:16.169 --> 00:27:26.950
precisely what gives proof of both sides gamma.
So, what are 2 ways? One way is I fix a g
00:27:26.950 --> 00:27:39.369
and then look for all the elements in this
column for which g dot axis x and then add
00:27:39.369 --> 00:27:47.169
it with the same with the similar number for
another g another g another g like this or
00:27:47.169 --> 00:27:56.529
I fix one x fix one x and then in the same
row, I look for all those gs which are not
00:27:56.529 --> 00:28:04.109
able to move this okay.
So, I can do this calculation on size of S
00:28:04.109 --> 00:28:12.909
in 2 ways column wise and row wise 2 ways
and that is what is going to give me the proof
00:28:12.909 --> 00:28:26.309
of one sides lemma. So, let us do that. So,
let me first fix g and fixing g. So, a fixed
00:28:26.309 --> 00:28:40.679
g and then I ask for how many x are there
which are not moved by this g ok that is fixed
00:28:40.679 --> 00:28:51.759
g right size of the fixed g. And then simply
I am summing it over the whole group right
00:28:51.759 --> 00:29:04.149
and this is what is size of S.
So, here is another way of estimating size
00:29:04.149 --> 00:29:13.989
of s which is you fix x fixing the element
x in the set and then ask like how many elements
00:29:13.989 --> 00:29:25.330
of the group are fixing that x, that is the
size of the stabilizer of x and then you just
00:29:25.330 --> 00:29:33.529
take summation and the 2 numbers are equal.
This summation of fixed points when g is moving
00:29:33.529 --> 00:29:42.379
all across group is same as summation of all
the stabilizer, where x is moving all across
00:29:42.379 --> 00:29:52.259
set x and I just equate these 2 numbers. So,
before I do that, let me just make an estimate
00:29:52.259 --> 00:30:01.739
for the summation of sizes of stabilizers.
So, summation of size of stabilizers actually
00:30:01.739 --> 00:30:13.570
equal to we have seen orbit stabilizer lemma,
the same as mod of size of g divided by size
00:30:13.570 --> 00:30:18.590
of orbit of x orbit into stabilizer size;
size of order, size of orbit and sizes of
00:30:18.590 --> 00:30:32.159
stabilizer is equal to size of g. So, here
it is x and x. So, when I equate these 2 what
00:30:32.159 --> 00:30:39.469
do I get? I just take g on the other side
and divide I get that 1 divided by size of
00:30:39.469 --> 00:30:58.700
G summation g in g and then size of fixed
points is equal to summation x in X 1 divided
00:30:58.700 --> 00:31:12.200
by size of orbit of x.
Now let us pick one element here now our job
00:31:12.200 --> 00:31:17.059
is to estimate this. In fact, we are supposed
to say that this is precisely the number of
00:31:17.059 --> 00:31:27.600
orbits in in an action and g action as this
is the number of orbits. So, let us see how
00:31:27.600 --> 00:31:32.389
much is the contribution from one element?
Contribution from from the one element
00:31:32.389 --> 00:31:42.549
x in axis, 1 divided size of the orbit of
x and therefore, how much is the contribution
00:31:42.549 --> 00:31:51.749
in this summation from one orbit? It is 1
divided by size of orbit of x times size of
00:31:51.749 --> 00:31:59.149
orbit of x which is 1. So, one orbit is contributing
exactly once in this summation and therefore,
00:31:59.149 --> 00:32:10.429
this is precisely number of orbits, this is
precisely the mode of orbits in action.
00:32:10.429 --> 00:32:20.609
So, we arrive at one side lemma which says
that number of orbits is precisely the average
00:32:20.609 --> 00:32:32.899
number of fixed points in an action what is
the application of thi? So, I highlight
00:32:32.899 --> 00:32:43.440
I present 2 applications of burnsides lemma.
So, here is quite interesting example coloring
00:32:43.440 --> 00:32:56.409
a shape. So, let me put a shape very simple
one.. I will take a square and suppose there
00:32:56.409 --> 00:33:11.599
are 2 choices of colors available to me say
red and blue I have 2 options. So, each edge
00:33:11.599 --> 00:33:21.450
each side of this can be colored either red
or blue ok there is possibility where all
00:33:21.450 --> 00:33:29.059
four are red, there is a possibility where
all four are blue ok.
00:33:29.059 --> 00:33:35.980
So, question is how many different shapes
like this how many different squares like
00:33:35.980 --> 00:33:50.580
this can you make. Well there is a possibility
where I have this red, this red, this blue,
00:33:50.580 --> 00:34:03.830
this there is a possibility where I have this
blue, this blue, this red and this red right.
00:34:03.830 --> 00:34:13.980
Probably these 2 things look at 2 these
2 things look like 2 different possibilities,
00:34:13.980 --> 00:34:22.690
but not quite if you treat these colored things
as toys you know, one can actually rotate
00:34:22.690 --> 00:34:37.099
this one can rotate it by 90 degree to obtain
from this shape other one right.
00:34:37.099 --> 00:34:45.200
So, as toys they are same actually right.
So, if you are supposed to count number of
00:34:45.200 --> 00:34:53.450
different toys that you can create by this
kind of coloring scheme, its not its not
00:34:53.450 --> 00:35:00.619
correct to say that this is 2 to the power
4 choices right. For each edge I have 2 choices
00:35:00.619 --> 00:35:06.260
there are four edges they 2 to the power 4
toys are possible that is not quite right
00:35:06.260 --> 00:35:14.000
to say because its easy you see there are
certain situations where although in this
00:35:14.000 --> 00:35:20.480
count that 2 distinct possibilities, but as
toys they are same because you can obtain
00:35:20.480 --> 00:35:26.549
this from this just by rotation. So, as toys
they are same.
00:35:26.549 --> 00:35:36.109
So, what exactly should we do in order to
count right number of toys? And idea is simple
00:35:36.109 --> 00:35:52.750
count number of orbits and then you should
ask here is the action, because we called
00:35:52.750 --> 00:35:58.380
orbits only when there is an action. So, then
we have to see what is happening, what is
00:35:58.380 --> 00:36:08.640
x, what is g ok.
So, here I can take X to be all 2 to the
00:36:08.640 --> 00:36:24.420
power four possibilities in the set of all
2 to the power 4 possibilities and where is
00:36:24.420 --> 00:36:35.650
the action? Action is this these are the things
which keep the toy look same in the shape,
00:36:35.650 --> 00:36:51.940
but probably different in the coloring configuration.
So, what is G? G is the set of symmetries
00:36:51.940 --> 00:37:03.160
of this object in this case this object is
square. So, G is a set of symmetries of square
00:37:03.160 --> 00:37:16.470
and what is the action? Action is quite that
strange one, action is you take a particular
00:37:16.470 --> 00:37:25.730
configuration take a possibility it could
be say R R R B or something and take symmetries
00:37:25.730 --> 00:37:28.840
of rectangle.
So, in this case is a square, take symmetries
00:37:28.840 --> 00:37:36.580
of square, there are eight symmetries of square
and that could be an exercise for you the
00:37:36.580 --> 00:37:41.130
way we proved the way we got convinced
that there are four symmetries of a rectangle,
00:37:41.130 --> 00:37:47.869
in the same way we can also estimate that
for a square there are 8 symmetries ok. So,
00:37:47.869 --> 00:37:58.730
suppose this symmetry is something like
diagonal flipping across one of the diagonals,
00:37:58.730 --> 00:38:07.430
says say this this this diagonal then this
possibility goes to what. So, when you flip
00:38:07.430 --> 00:38:15.359
about this diagonally B goes here R comes
here R comes here and R comes here ok so.
00:38:15.359 --> 00:38:22.180
When in there this action you count number
of orbits and that is when you actually get
00:38:22.180 --> 00:38:28.270
the right number of different toys that you
can create, and in the exercise said we are
00:38:28.270 --> 00:38:34.559
going to have some interesting problems and
some problems which involve cube and tetrahedron.
00:38:34.559 --> 00:38:43.789
So, in the exercise said we are going to have
that ok that is one thing why we should count
00:38:43.789 --> 00:38:50.019
orbits.
Here is another interesting problem. So, maybe
00:38:50.019 --> 00:38:58.410
during the exercise a part the assignment
part I will give you this problem, but let
00:38:58.410 --> 00:39:12.070
me explain you what the problem is. If the
class suppose there are n students s 1 s 2,
00:39:12.070 --> 00:39:31.670
s 3 s n there are any students and each of
them is having a pen p 1, p 2, p 3, p n.
00:39:31.670 --> 00:39:39.329
So, as students as a n students are there
pens each of them is having their own pen,
00:39:39.329 --> 00:39:45.700
teacher comes and randomly distributes these
pens to these students. So, teacher comes
00:39:45.700 --> 00:39:53.170
collects all this point all these pens and
distributes it to students randomly. So, possibly
00:39:53.170 --> 00:40:00.710
s 1 gets the pen of p 3 maybe, s 3 gets
the pen of p n maybe s n gets the pen of p
00:40:00.710 --> 00:40:20.000
2 all this happens.
Now, question is on average and one has and
00:40:20.000 --> 00:40:30.150
one has to device the right meaning of on
average. So, on average how many students
00:40:30.150 --> 00:40:52.190
will get back their own pen
and for this one has to understand what is
00:40:52.190 --> 00:40:58.230
the action this is going on, once has to understand
what is the group involved and what is the
00:40:58.230 --> 00:41:06.769
set which is there.
So, I will just give you some hint. So,
00:41:06.769 --> 00:41:15.920
what is the group what is the action. So,
group is actually permutation group, the permutation
00:41:15.920 --> 00:41:22.790
is happening here right. So, permutation group
which is the group. So, and and the action
00:41:22.790 --> 00:41:54.720
is what . So, this G is S n
which is permutation group what is permutation
00:41:54.720 --> 00:42:02.480
group? I have said the last lecture that you
have n distinct points you permute them and
00:42:02.480 --> 00:42:10.069
once again you permute them, what you get
is, again permutation of the original configuration
00:42:10.069 --> 00:42:14.779
permutation of the original objects.
So, if you collect all possibilities all n
00:42:14.779 --> 00:42:21.319
factorial possibilities of all possible permutations,
it forms a group. When compose to permutations
00:42:21.319 --> 00:42:27.640
and it is again the permutation and the original
configuration itself is one of the permutations,
00:42:27.640 --> 00:42:34.420
identity permutation and for each permutation
there is a reverse permutation, which brings
00:42:34.420 --> 00:42:41.519
it back to the original configuration. So,
set of permutations is a group and this is
00:42:41.519 --> 00:42:48.650
a group of size n factorial right there n
factorial possibilities of a permuting n objects
00:42:48.650 --> 00:42:53.730
of course, we are assuming that those objects
are not tied to each other they are not bound
00:42:53.730 --> 00:42:58.779
to each other ok. So, there is no restriction
the permutation we are permitting them them
00:42:58.779 --> 00:43:02.619
as discrete objects as independent objects
ok.
00:43:02.619 --> 00:43:07.180
So, that is permutation group and the notation
for the permutation group is S n and the action
00:43:07.180 --> 00:43:13.970
which is happening in this problem is this.
So, what is happening? I take an I take a
00:43:13.970 --> 00:43:21.890
permutation let me call sigma and then you
pick one of the pens suppose 10 of the ith
00:43:21.890 --> 00:43:36.470
student and then you take it to j, where s
j gets ten of the ith student that is a that
00:43:36.470 --> 00:43:46.910
is the action. So, hint is that of course,
permitted the action is this action is S n
00:43:46.910 --> 00:44:01.240
the to the permutation group acting on the
set of and the elements naturally action,
00:44:01.240 --> 00:44:08.839
and what we are supposed to count is average
number of students who get back their own
00:44:08.839 --> 00:44:12.539
pen .
So, maybe we are talking about average number
00:44:12.539 --> 00:44:20.750
of fixed points at has a hint. So, probably
it has something to do with average number
00:44:20.750 --> 00:44:30.300
of fixed points, I would not give you hint
beyond this because this is going to be one
00:44:30.300 --> 00:44:35.800
of the exercise in the assignment. So, next
time we are going to learn about applications
00:44:35.800 --> 00:44:46.779
of group actions in understanding some puzzles,
applications of group law in understanding
00:44:46.779 --> 00:44:55.740
some puzzles, and the key word is going to
be parity, groups can be used for parity checking.
00:44:55.740 --> 00:44:59.550
So, I will see you again in the next lecture.
Thank you .