0
00:00:00,160 --> 00:00:01,400


1
00:00:12,200 --> 00:00:15,630
just now, we have introduced many examples

2
00:00:15,630 --> 00:00:18,370
illustrated that Polya's Theorem can be effectively

3
00:00:18,370 --> 00:00:21,410
help us to perform the calculation of colouring solution

4
00:00:21,410 --> 00:00:23,860
but, everyone will be thinking that

5
00:00:23,860 --> 00:00:24,790
Polya's Theorem is counting

6
00:00:24,790 --> 00:00:27,630
how many different types of colouring solutions are there

7
00:00:27,630 --> 00:00:29,710
but for each type of colouring solutions

8
00:00:29,710 --> 00:00:31,000
how many will it be there

9
00:00:31,000 --> 00:00:33,900
for example, if we used 4 beads for colouring

10
00:00:33,900 --> 00:00:36,520
each bead contains 3 types of colours

11
00:00:36,520 --> 00:00:39,990
we may be asking what if there are 2 red

12
00:00:39,990 --> 00:00:43,740
one blue, one green, how many different solutions are there

13
00:00:43,740 --> 00:00:45,880
for this time, purely using Polya's Theorem

14
00:00:45,880 --> 00:00:47,820
may not be sufficient

15
00:00:47,820 --> 00:00:50,900
we will be thinking, actually we do have a favorable

16
00:00:50,900 --> 00:00:53,540
tool to help us to perform enumeration

17
00:00:53,540 --> 00:00:56,040
does everyone still remember generating function

18
00:00:57,930 --> 00:00:59,930
generating function can actually help us

19
00:00:59,930 --> 00:01:02,510
to perform enumeration of colouring solution

20
00:01:02,510 --> 00:01:04,340
just pick a simple example

21
00:01:04,340 --> 00:01:05,820
for example, we want

22
00:01:05,820 --> 00:01:07,880
paint 3 identical balls

23
00:01:07,880 --> 00:01:12,160
in total, there are 4 types of different colours can be chosen from

24
00:01:12,160 --> 00:01:14,480
its possible colour combination, if

25
00:01:14,480 --> 00:01:18,500
we are using generating function, how are we going to represent it

26
00:01:18,500 --> 00:01:20,810
we will realize actually for a ball, its

27
00:01:20,810 --> 00:01:22,630
colouring solution may use

28
00:01:22,630 --> 00:01:26,140
red, yellow, green, blue, added all up together

29
00:01:26,140 --> 00:01:28,430
which are different solutions for a ball

30
00:01:28,430 --> 00:01:30,950
in total, there are 3 balls, it should be

31
00:01:30,950 --> 00:01:34,580
R plus Y plus B plus G to the power of 3

32
00:01:34,580 --> 00:01:37,030
if, after we have expanded it orderly

33
00:01:37,030 --> 00:01:40,500
then, we will realize the coefficient in front of each item

34
00:01:40,500 --> 00:01:42,850
it represents how many solution is there

35
00:01:42,850 --> 00:01:45,270
we will then think that if Polya's Theorem

36
00:01:45,270 --> 00:01:47,400
may combine with generating function

37
00:01:47,400 --> 00:01:48,700
is it we can find

38
00:01:48,700 --> 00:01:50,220
under a special situation,

39
00:01:50,220 --> 00:01:51,950
how many solutions are there ?

40
00:01:53,050 --> 00:01:54,610
we raise a simple example

41
00:01:54,610 --> 00:01:57,960
for example, there are 3 different colours of beads

42
00:01:57,960 --> 00:02:00,630
we want to string a 4 beads necklace

43
00:02:00,630 --> 00:02:04,000
for this question, we have solved it just now together

44
00:02:04,000 --> 00:02:06,770
at this time, let us analyse it carefully

45
00:02:06,770 --> 00:02:10,090
correspondingly, if we apply generating function into this

46
00:02:10,090 --> 00:02:12,940
how many different amazing solution will it be there

47
00:02:12,940 --> 00:02:15,270
first, we need to analyse its permutation

48
00:02:15,270 --> 00:02:17,420
for example, the first permutation is

49
00:02:17,420 --> 00:02:20,100
rotate 90 degree around the centre

50
00:02:20,100 --> 00:02:21,790
rotate 90 degree around the centre

51
00:02:21,790 --> 00:02:24,190
we know that actually, it is corresponding to

52
00:02:24,190 --> 00:02:25,730
4 order cycle

53
00:02:25,730 --> 00:02:28,920
4 order cycles simply means that under this cycle

54
00:02:28,920 --> 00:02:33,330
in 4 solution, they have all picked the same colour

55
00:02:34,460 --> 00:02:37,220
how are we going to write corresponding generating function

56
00:02:37,220 --> 00:02:40,110
it can be said that, our this 4 beads

57
00:02:40,110 --> 00:02:41,640
they are all red

58
00:02:41,640 --> 00:02:42,680
it simply means that

59
00:02:42,680 --> 00:02:44,420
it is R to the power of 4

60
00:02:44,420 --> 00:02:44,880
maybe,

61
00:02:44,880 --> 00:02:45,680
all are blue

62
00:02:45,680 --> 00:02:47,810
which is B to the power of 4

63
00:02:47,810 --> 00:02:49,920
there are total of 4 different types of colours

64
00:02:49,920 --> 00:02:53,690
therefore, for this kind of 4 order cycle, if we used it directly

65
00:02:53,690 --> 00:02:56,190
the method of generating function, it can be written as

66
00:02:56,190 --> 00:02:58,880
R to the power of 4 plus Y to the power of 4

67
00:02:58,880 --> 00:03:00,630
add up with B to the power of 4

68
00:03:00,630 --> 00:03:02,360
add up with G to the power of 4

69
00:03:02,360 --> 00:03:03,460
it simply means that

70
00:03:03,460 --> 00:03:04,640
for this kind of cycle

71
00:03:04,640 --> 00:03:07,520
it can be represented through the use of generating function

72
00:03:07,520 --> 00:03:10,110
if we rotated it for 180 degree

73
00:03:10,110 --> 00:03:12,300
it will produce two-by-two exchanged

74
00:03:12,300 --> 00:03:16,680
then, the two-by-two exchange simply means they are within an internal cycle

75
00:03:16,680 --> 00:03:18,590
2 beads are using the same colour

76
00:03:18,590 --> 00:03:22,110
how many possibility are there if 2 beads are having the same colours

77
00:03:22,110 --> 00:03:24,340
which is R square plus Y square

78
00:03:24,340 --> 00:03:26,780
add up with G square and so on

79
00:03:26,780 --> 00:03:29,280
we will realize over here, we also use

80
00:03:29,280 --> 00:03:31,820
the size of their corresponding cycle

81
00:03:31,820 --> 00:03:34,630
and also their corresponding each internal cycle

82
00:03:34,630 --> 00:03:37,720
should be using the same colour this kind of situation

83
00:03:37,720 --> 00:03:41,510
then it can write out the corresponding generating function

84
00:03:41,510 --> 00:03:43,790
if we are considering flipping also

85
00:03:43,790 --> 00:03:46,040
similarly, if for the diagonal line which

86
00:03:46,040 --> 00:03:47,610
does not go through the bead

87
00:03:47,610 --> 00:03:51,070
its corresponding permutation should be two-by-two exchanged

88
00:03:51,070 --> 00:03:53,470
similarly, it can be written into the corresponding

89
00:03:53,470 --> 00:03:54,760
generating function form

90
00:03:54,760 --> 00:03:57,060
which is R square plus B square

91
00:03:57,060 --> 00:03:58,490
add up with G square

92
00:03:58,490 --> 00:04:00,170
because it contains 2 items

93
00:04:00,170 --> 00:04:03,330
therefore, it contains the quadratic component

94
00:04:03,330 --> 00:04:04,040
another one

95
00:04:04,040 --> 00:04:06,890
another one is going through the diagonal line of the beads

96
00:04:06,890 --> 00:04:09,020
actually, 1 order cycle contains 2

97
00:04:09,020 --> 00:04:12,120
add up with one 2 order cycle

98
00:04:12,120 --> 00:04:15,380
after writing it out, it means that under 1 order cycle

99
00:04:15,380 --> 00:04:18,190
1 bead colour selection can be red

100
00:04:18,190 --> 00:04:22,000
it can also be blue, can also be green

101
00:04:22,000 --> 00:04:24,430
at that time, R plus B plus G

102
00:04:24,430 --> 00:04:25,670
it contains 2

103
00:04:25,670 --> 00:04:29,310
therefore, the quadratic component of R plus B plus G

104
00:04:29,310 --> 00:04:31,320
for 2 order cycle

105
00:04:31,320 --> 00:04:33,250
can be written as R square plus

106
00:04:33,250 --> 00:04:35,780
G square plus B square and so on

107
00:04:35,780 --> 00:04:39,080
for fixed one, there are 4

108
00:04:39,080 --> 00:04:40,960
they are all 1 order cycle

109
00:04:40,960 --> 00:04:44,570
which is R plus B plus G to the power of 4

110
00:04:44,570 --> 00:04:46,630
sometimes, for different types of situations

111
00:04:46,630 --> 00:04:48,980
we will list all the generating functions out

112
00:04:48,980 --> 00:04:51,570
at this time, substitute all the permutation into

113
00:04:51,570 --> 00:04:52,390
Polya's Theorem

114
00:04:52,390 --> 00:04:54,430
if we do not consider the single solution

115
00:04:54,430 --> 00:04:57,190
it directly can apply the corresponding C(Pi)

116
00:04:57,190 --> 00:05:00,840
it may then find the solution number for all equivalence class

117
00:05:00,840 --> 00:05:01,970
but now, we are using

118
00:05:01,970 --> 00:05:03,750
generating function way to solve it

119
00:05:03,750 --> 00:05:06,030
will realize that actually PG bar

120
00:05:06,030 --> 00:05:08,460
can be written into B to the power of 4

121
00:05:08,460 --> 00:05:10,260
add up R to the power of 4

122
00:05:10,260 --> 00:05:10,930
and so on

123
00:05:10,930 --> 00:05:12,060
we expand each item

124
00:05:12,060 --> 00:05:14,600
then it will be getting the corresponding equation

125
00:05:14,600 --> 00:05:16,990
each item is representing several meaning

126
00:05:17,930 --> 00:05:21,520
for example, B square over here

127
00:05:21,520 --> 00:05:25,120
R G means that it is corresponding to

128
00:05:25,120 --> 00:05:26,810
2 black beads

129
00:05:26,810 --> 00:05:28,140
one red bead

130
00:05:28,140 --> 00:05:29,360
one green bead

131
00:05:29,360 --> 00:05:31,860
whereas B square, R G are corresponding to

132
00:05:31,860 --> 00:05:33,520
the coefficient, how many is it

133
00:05:33,520 --> 00:05:35,730
under this kind of polynomial equation

134
00:05:35,730 --> 00:05:37,720
we may coincidently realize that

135
00:05:37,720 --> 00:05:39,250
its coefficient is 2

136
00:05:39,250 --> 00:05:41,530
means that there are 2 different types of methods

137
00:05:41,530 --> 00:05:43,480
through the demonstration, we will realize that

138
00:05:43,480 --> 00:05:44,640
we can have this kind of

139
00:05:44,640 --> 00:05:46,010
arrangement of 2 beads

140
00:05:46,010 --> 00:05:47,840
besides, we can also have

141
00:05:47,840 --> 00:05:49,500
other arrangement of black beads

142
00:05:49,500 --> 00:05:53,990
through this kind of representation, we will realize

143
00:05:53,990 --> 00:05:55,490
actually, generating function and

144
00:05:55,490 --> 00:05:58,290
Polya's Theorem, if they are combined

145
00:05:58,290 --> 00:06:00,630
it can more sophisticatedly

146
00:06:00,630 --> 00:06:03,090
solve the corresponding solution number

147
00:06:03,090 --> 00:06:05,010
if we take the original Polya's Theorem

148
00:06:05,010 --> 00:06:08,040
M to the power of CPI to conduct the change

149
00:06:08,040 --> 00:06:08,860
you will realize

150
00:06:08,860 --> 00:06:14,330
inside each m to the power of C(pi) is corresponding to

151
00:06:14,330 --> 00:06:16,730
component can be expanded completely

152
00:06:17,770 --> 00:06:19,780
the corresponding m within it

153
00:06:19,780 --> 00:06:22,120
actually is the colouring solution

154
00:06:22,120 --> 00:06:23,820
if, it may be a bead

155
00:06:23,820 --> 00:06:25,810
remain the same colour as it is

156
00:06:25,810 --> 00:06:30,470
it may us B1 plus B2 and accumulatively added all the way down

157
00:06:30,470 --> 00:06:33,290
their corresponding the power of CP1

158
00:06:33,290 --> 00:06:34,930
then, if there are 2

159
00:06:34,930 --> 00:06:35,960
2 order cycle

160
00:06:35,960 --> 00:06:37,120
2 order cycle means that

161
00:06:37,120 --> 00:06:40,480
pick the same colour within the same cycle bracket

162
00:06:40,480 --> 00:06:42,180
at this time, we can write that

163
00:06:42,180 --> 00:06:45,500
it is B1 square component, add up with B2

164
00:06:45,500 --> 00:06:49,170
square component, accumulatively added until BN square component

165
00:06:49,170 --> 00:06:51,270
corresponding to the external power should be

166
00:06:51,270 --> 00:06:52,840
the number of 2 order cycle

167
00:06:52,840 --> 00:06:54,380
and so on

168
00:06:54,380 --> 00:06:55,040
Then

169
00:06:56,290 --> 00:06:57,630
Polya's Theorem is changed to

170
00:06:57,630 --> 00:06:59,750
Polya's Theorem with generating function

171
00:07:02,810 --> 00:07:04,620
through the use of such kind of equation

172
00:07:04,620 --> 00:07:08,180
it can be used to solve more and more problems