just now, we have introduced many examples
illustrated that Polya's Theorem can be effectively
help us to perform the calculation of colouring solution
but, everyone will be thinking that
Polya's Theorem is counting
how many different types of colouring solutions are there
but for each type of colouring solutions
how many will it be there
for example, if we used 4 beads for colouring
each bead contains 3 types of colours
we may be asking what if there are 2 red
one blue, one green, how many different solutions are there
for this time, purely using Polya's Theorem
may not be sufficient
we will be thinking, actually we do have a favorable
tool to help us to perform enumeration
does everyone still remember generating function
generating function can actually help us
to perform enumeration of colouring solution
just pick a simple example
for example, we want
paint 3 identical balls
in total, there are 4 types of different colours can be chosen from
its possible colour combination, if
we are using generating function, how are we going to represent it
we will realize actually for a ball, its
colouring solution may use
red, yellow, green, blue, added all up together
which are different solutions for a ball
in total, there are 3 balls, it should be
R plus Y plus B plus G to the power of 3
if, after we have expanded it orderly
then, we will realize the coefficient in front of each item
it represents how many solution is there
we will then think that if Polya's Theorem
may combine with generating function
is it we can find
under a special situation,
how many solutions are there ?
we raise a simple example
for example, there are 3 different colours of beads
we want to string a 4 beads necklace
for this question, we have solved it just now together
at this time, let us analyse it carefully
correspondingly, if we apply generating function into this
how many different amazing solution will it be there
first, we need to analyse its permutation
for example, the first permutation is
rotate 90 degree around the centre
we know that actually, it is corresponding to
4 order cycle
4 order cycles simply means that under this cycle
in 4 solution, they have all picked the same colour
how are we going to write corresponding generating function
it can be said that, our this 4 beads
they are all red
it simply means that
it is R to the power of 4
maybe,
all are blue
which is B to the power of 4
there are total of 4 different types of colours
therefore, for this kind of 4 order cycle, if we used it directly
the method of generating function, it can be written as
R to the power of 4 plus Y to the power of 4
add up with B to the power of 4
add up with G to the power of 4
it simply means that
for this kind of cycle
it can be represented through the use of generating function
if we rotated it for 180 degree
it will produce two-by-two exchanged
then, the two-by-two exchange simply means they are within an internal cycle
2 beads are using the same colour
how many possibility are there if 2 beads are having the same colours
which is R square plus Y square
add up with G square and so on
we will realize over here, we also use
the size of their corresponding cycle
and also their corresponding each internal cycle
should be using the same colour this kind of situation
then it can write out the corresponding generating function
if we are considering flipping also
similarly, if for the diagonal line which
does not go through the bead
its corresponding permutation should be two-by-two exchanged
similarly, it can be written into the corresponding
generating function form
which is R square plus B square
add up with G square
because it contains 2 items
therefore, it contains the quadratic component
another one
another one is going through the diagonal line of the beads
actually, 1 order cycle contains 2
add up with one 2 order cycle
after writing it out, it means that under 1 order cycle
1 bead colour selection can be red
it can also be blue, can also be green
at that time, R plus B plus G
it contains 2
therefore, the quadratic component of R plus B plus G
for 2 order cycle
can be written as R square plus
G square plus B square and so on
for fixed one, there are 4
they are all 1 order cycle
which is R plus B plus G to the power of 4
sometimes, for different types of situations
we will list all the generating functions out
at this time, substitute all the permutation into
Polya's Theorem
if we do not consider the single solution
it directly can apply the corresponding C(Pi)
it may then find the solution number for all equivalence class
but now, we are using
generating function way to solve it
will realize that actually PG bar
can be written into B to the power of 4
add up R to the power of 4
and so on
we expand each item
then it will be getting the corresponding equation
each item is representing several meaning
for example, B square over here
R G means that it is corresponding to
2 black beads
one red bead
one green bead
whereas B square, R G are corresponding to
the coefficient, how many is it
under this kind of polynomial equation
we may coincidently realize that
its coefficient is 2
means that there are 2 different types of methods
through the demonstration, we will realize that
we can have this kind of
arrangement of 2 beads
besides, we can also have
other arrangement of black beads
through this kind of representation, we will realize
actually, generating function and
Polya's Theorem, if they are combined
it can more sophisticatedly
solve the corresponding solution number
if we take the original Polya's Theorem
M to the power of CPI to conduct the change
you will realize
inside each m to the power of C(pi) is corresponding to
component can be expanded completely
the corresponding m within it
actually is the colouring solution
if, it may be a bead
remain the same colour as it is
it may us B1 plus B2 and accumulatively added all the way down
their corresponding the power of CP1
then, if there are 2
2 order cycle
2 order cycle means that
pick the same colour within the same cycle bracket
at this time, we can write that
it is B1 square component, add up with B2
square component, accumulatively added until BN square component
corresponding to the external power should be
the number of 2 order cycle
and so on
Then
Polya's Theorem is changed to
Polya's Theorem with generating function
through the use of such kind of equation
it can be used to solve more and more problems