ปัญหาสร้อยกับ Burnside Lemma

Question

สร้อยคอสามารถทำด้วยลูกปัดสีแดงสองเม็ดสีเขียวสองเม็ดและลูกปัดสีม่วงสี่เม็ด (ทั้งหมด 8)

การใช้คำศัพท์ Burnside นั้นซับซ้อนสำหรับฉันเนื่องจากฉันไม่เข้าใจคำหลัก ฉันต้องการทราบวิธีการทีละขั้นตอน

Answer 1

จะเริ่มต้นด้วย:

เรามี $\frac{8!}{2!2!4!} = 420$การเรียงสับเปลี่ยนของลูกปัดแปดเม็ด เราจะจัดเรียงพวกมันรอบ ๆ ไอเท็ม 8 เม็ดซึ่งหมายความว่าเราต้องใช้กลุ่มไดฮีดรัล$D_{16}$ และการกระทำต่างๆ

มีชั้นเรียน conjugacy เจ็ดระหว่างองค์ประกอบของกลุ่มนี้เราจะพิจารณาพวกเขาในทางกลับกัน

• การดำเนินการระบุตัวตนไม่ได้ทำอะไรเลย ความเป็นไปได้ทั้งหมด 420 รายการยังคงไม่เปลี่ยนแปลงภายใต้การกระทำนี้
• เดี่ยว $1/2$หมุนทุกอย่างรอบ ๆ ลูกปัดสี่เม็ด สิ่งนี้ช่วยรักษาสิ่งต่างๆในรูปแบบ$abcdabcd$ ไม่เปลี่ยนแปลงจึงชอบ $VVRGVVRG$ หรือ $GVRVGVRV$นับสำหรับสิ่งนี้ สร้อยคอดังกล่าวมี 12 เส้น
• ทั้งสอง $1/4$การหมุนทุกอย่างรอบ ๆ ลูกปัดสองเม็ด การดำเนินการนี้จะไม่ทำให้รายการใด ๆ ไม่เปลี่ยนแปลงเนื่องจากจะต้องอยู่ในรูปแบบ$abababab$ และเรามีเพียงสองเม็ดสีแดง
• ทั้งสอง $1/8$การหมุนทำทุกอย่างรอบ ๆ ลูกปัด การดำเนินการนี้ยังไม่ปล่อยให้รายการใด ๆ ไม่เปลี่ยนแปลงเนื่องจากเรามีลูกปัดมากกว่าหนึ่งสี
• ทั้งสอง $3/8$การหมุนทำทุกอย่างรอบ ๆ สามเม็ด การดำเนินการนี้ยังไม่ปล่อยให้รายการใด ๆ ไม่เปลี่ยนแปลงเนื่องจากเรามีลูกปัดมากกว่าหนึ่งสี
• การสะท้อนสี่เส้นผ่านลูกปัดจะพลิกสิ่งต่างๆไปมาเพื่อให้ลูกปัดสองเม็ดอยู่ สร้อยคอของแบบฟอร์ม$abcdedcb$ยังคงไม่เปลี่ยนแปลงผ่านสิ่งนี้ เนื่องจากเรามีจำนวนลูกปัดเท่านั้น$a = e$ต้องเป็นจริง เหลือ 12 รายการเช่น$VRGVVVGR$.
• การสะท้อนทั้งสี่เส้นระหว่างลูกปัดจะพลิกสิ่งต่างๆไปมาเพื่อไม่ให้ลูกปัดติดอยู่ ลักษณะเหล่านี้$abcddcba$และมี 12 รายการดังกล่าวเช่น $VRGVVGRV$

ตอนนี้ใช้Lemma ของ Burnsideมี

$$\frac{1\cdot420 + 1\cdot12 + 2\cdot0 + 2\cdot0 + 2\cdot0 + 4\cdot12 + 4\cdot12}{1+1+2+2+2+4+4} = \frac{528}{16} = 33$$

สร้อยคอที่แตกต่างกัน

รายการด้านล่างนี้คือรายการทั้งหมด:

20 เหล่านี้ไม่สมดุลอย่างสมบูรณ์:

GGRRVVVV GGRVRVVV GGRVVRVV
GGRVVVRV GGVRRVVV GGVRVRVV
GRGRVVVV GRGVRVVV GRRVGVVV
GRRVVGVV GRRVVVGV GRVGRVVV
GRVGVRVV GRVGVVRV GRVGVVVR
GRVRVGVV GRVRVVGV GRVVGVRV
GRVVRVGV GVGVRRVV

ทั้งหกนี้ได้รับการแก้ไขภายใต้การสะท้อนที่ผ่านระหว่างลูกปัด:

GRVVVVRG GVRVVRVG GVVRRVVG
RGVVVVGR VRGVVGRV RVGVVGVR

ทั้งห้านี้ได้รับการแก้ไขภายใต้ภาพสะท้อนที่ผ่านลูกปัดสองเม็ด:

RGVVRVVG VRGVVVGR GRVVGVVR
VVRGVGRV VGVRVRVG

ในที่สุดก็มีหนึ่งที่ได้รับการแก้ไขภายใต้การหมุนGRVVGRVVและอีกอันที่ได้รับการแก้ไขภายใต้การหมุนและการสะท้อนผ่านGVRVGVRV

Answer 2

เราอาจปรับใช้ PET ได้เช่นกันเนื่องจากเราต้องการดัชนีวัฏจักร $Z(D_8)$ ของกลุ่ม dihedral $D_8$ ของการสั่งซื้อ $16$เพื่อใช้ Burnside เราคำนวณและหาค่าเฉลี่ยจำนวนการกำหนดสีให้กับแปดช่องที่แก้ไขโดยการเรียงสับเปลี่ยนจากคลาสคอนจูกาซีแต่ละคลาสใน$D_8$โดยคำนึงถึงลำดับของชั้นเรียน ซึ่งหมายความว่าการกำหนดจะคงที่ในรอบดังนั้นเราจึงสามารถวางสีหนึ่งสีในช่องในรอบที่กำหนดโดยแทนที่$a_d$ จากดัชนีด้วย $R^d + G^d + V^d,$ ซึ่งก็คือ PET

การดูเอกสารข้อเท็จจริงต่อไปนี้เกี่ยวกับสร้อยคอและสร้อยข้อมือที่เราได้รับสำหรับดัชนีวัฏจักรของกลุ่ม dihedral$D_8$

$$Z(D_8) = \frac{1}{16} a_1^8 + \frac{1}{4} a_1^2 a_2^3 + \frac{5}{16} a_2^4 + \frac{1}{8} a_4^2 + \frac{1}{4} a_8.$$

เราแสวงหา $$[R^2 G^2 V^4] Z(D_8; R+G+V).$$

ที่นี่เราสมมติว่า OP ขอสมมาตรเต็มเช่น dihedral ซึ่งหมายความว่าป้ายที่จะใช้คือสร้อยข้อมือ ทำงานผ่านเทอร์นทั้งห้าในดัชนีวัฏจักรที่เราได้รับ

• $\frac{1}{16} a_1^8$ $$[R^2 G^2 V^4] \frac{1}{16} (R+G+V)^8 = \frac{1}{16} {8\choose 2,2,4}$$
• $\frac{1}{4} a_1^2 a_2^3$ $$[R^2 G^2 V^4] \frac{1}{4} (R+G+V)^2 (R^2 + G^2 + V^2)^3 \\ = [R^2 G^2 V^4] \frac{1}{4} (R^2 + G^2 + V^2) (R^2 + G^2 + V^2)^3 \\ = [R^2 G^2 V^4] \frac{1}{4} (R^2 + G^2 + V^2)^4 \\ = [R G V^2] \frac{1}{4} (R + G + V)^4 = \frac{1}{4} {4\choose 2,1,1}.$$
• $\frac{5}{16} a_2^4$ $$[R^2 G^2 V^4] \frac{5}{16} (R^2 + G^2 + V^2)^4 = \frac{5}{16} {4\choose 2,1,1}.$$
• $\frac{1}{8} a_4^2$ $$[R^2 G^2 V^4] \frac{1}{8} (R^4 + G^4 + V^4)^2 = 0.$$
• $\frac{1}{4} a_8$ $$[R^2 G^2 V^4] \frac{1}{4} (R^8 + G^8 + V^8) = 0.$$

ดังนั้นเราจึงได้รับคำตอบของเรา

$$\frac{1}{16} {8\choose 2,2,4} + \frac{9}{16} {4\choose 2,1,1} = \bbox[5px,border:2px solid #00A000]{33.}$$