英语原文共 9 页，剩余内容已隐藏，支付完成后下载完整资料
COUNTING WITH GROUP
We are now going to use group theory to do some fancy counting.
Lemma 2.157.
(i) Let a group G act on a set X. If and ，then = .
(ii) If a finite group G acts on a finite set X and if x and y lie in the same orbit，then =.
Proof.
(i) If , then = . If = , we have
==== .
Therefore, fixes ,and so .The reverse inclusion is proved in the same way, for =.
(ii) If and are in the same orbit, then there is with = , and so .
Theorem 2.158 (Burnsidersquo;s Lemma).23Let G act on a finite set X. If N is the number of orbits, then
where is the number of fixed by .
Proof. List the elements of X as follows: choose , and then list all the elements in the orbit ; say,={}then choose ,and list the elements of as ,continue this procedure until all the elements of X are listed. Now list the elements of G, and form the following array of 0rsquo;s and 1rsquo;s, where
Now , the number of fixed by ,is the number of 1rsquo;s in the th row of the array; therefore, is the total number of 1rsquo;s in the array. Let us now look at the columns. The number of 1rsquo;s in the first column is the number of that fix ; by definition, these comprise . Thus, the number of1rsquo;s in column 1
23Burnsidersquo;s influential book, The Theory of Groups of Finite Order, had two editions. In the first edition, he attributed this theorem to G. Frobenius; in the second edition, he gave no attribution at all. However, the commonly accepted name of this theorem is Burnsidersquo;s lemma. To avoid the confusion that would be caused by changing a popular name, P. M. Neumann suggested that it be called “not-Burnsidersquo;s lemma.” Burnside was a fine mathematician, and there do exist theorems properly attributed to him. For example, Burnside proved that if p and q are primes, then there are no simple groups of order .
is . Similarly, the number of 1rsquo;s in column 2 is . By Lemma 2.157(ii), = . By Theorem 2.141, the number of 1rsquo;s in the r columns labeled by the is thus
The same is true for any other orbit: its columns contain exactly 1rsquo;s. Therefore, if there are N orbits, there are 1rsquo;s in the array. We conclude that
We are going to use Burnsidersquo;s lemma to solve problems of the following
sort. How many striped flags are there having six stripes (of equal width) each
of which can be colored red, white, or blue? Clearly, the two flags in Figure 2.19
are the same: the bottom flag is just the reverse of the top one (the flag may be
viewed by standing in front of it or by standing in back of it).
Let X be the set of all 6-tuples of colors; if , then
where each denotes either red, white, or blue. Let be the permutation that
reverses all the indices:
(thus, “turns over” each 6-tuple x of colored stripes). The cyclic group G =
acts on X; since ,the orbit of any 6-tuple consists of either 1 or 2 elements: either fixes or it does not. Since a flag is unchanged by turning it over, it is reasonable to identify a flag with an orbit of a 6-tuple. For example, the orbit consisting of the 6-tuples
(r, w, b,r, w, b) and (b, w,r, b, w,r)
describes the flag in Figure 2.19. The number of flags is thus the number N of
orbits; by Burnsidersquo;s lemma, N = 1/2 [F((1)) F(tau; )]. The identity permutation (1) fixes every , and so F((1)) = (there are 3 colors). Now tau; fixes a 6-tuple x if and only if x is a “palindrome,” that is, if the colors in read the same forward as backward. For example,
= (r,r, w, w,r,r)
is fixed by . Conversely, if
= (c1, c2, c3, c4, c5, c6)
is fixed by = (1 6)(2 5)(3 4), then c1 = c6, c2 = c5, and c3 = c4; that is, is a palindrome. It follows that F(tau; ) = , for there are 3 choices for each of c1, c2, and c3. The number of flags is thus
Let us make the notion of coloring more precise.
Definition. Given an action of a group G on X = {1, . . ., n} and a set C of q colors, then G acts on the set of all n-tuples of colors by
tau; (, . . ., ) = (, . . ., ) for all tau; isin; G.
An orbit of (, . . ., ) is called a (q, G)-coloring of X.
Example 2.159.
Color each square in a 4 times; 4 grid red or black (adjacent squares may have the same color; indeed, one possibility is that all the squares have the same color). If X consists of the 16 squares in the grid and if consists of the two colors red and black, then the cyclic group G = i of order 4 acts on X, where R is clockwise rotation by ; Figure 2.20 shows how R acts: the right square is Rrsquo;s action on the left square. In cycle notation,
R = (1, 4, 16, 13)(2, 8, 15, 9)(3, 12, 14, 5)(6, 7, 11, 10),
R2 = (1, 16)(4, 13)(2, 15)(8, 9)(3, 14)(12, 5)(6, 11)(7, 10),
R3 = (1, 13, 16, 4)(2, 9, 15, 8)(3, 5, 14, 12)(6, 10, 11, 7).
A red-and-black chessboard does not change when it is rotated; it is merely
viewed from a different position. Thus, we may regard a chessboard as a (2, G)-
coloring of X; the orbit of a 16-tuple corresponds to the four ways of viewing
the board.
By Burnsidersquo;s lemma, the number of chessboards is
Now F((1)) = , for every 16-tuple is fixed by the identity. To compute F(R), note that squares 1, 4, 16, 13 must all have the same color in a 16-tuple fixed by R. Similarly, squares 2, 8, 15, 9 must have the same color, squares 3, 12, 14, 5 must have the same color, and squares 6, 7, 11, 10 must have the same color,and squares 6, 7, 11, 10 must have the same color. We conclude that F(R) = ; note that the exponent 4 is the number of cycles in the complete factorization
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[410395]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
