บทพิสูจน์ของเบิร์นไซด์
ทฤษฎีบทของเบิร์นไซด์บางครั้งเรียกว่าทฤษฎีบทการนับของเบิร์นไซด์ ทฤษฎีบท โคชี-โฟรเบนิ อุส หรือทฤษฎีบทการนับวงโคจรเป็นผลลัพธ์ในทฤษฎีกลุ่มที่มักมีประโยชน์ในการพิจารณาสมมาตรเมื่อนับวัตถุทางคณิตศาสตร์ ทฤษฎีบทนี้ถูกค้นพบโดยออกัสติน หลุยส์ โคชีและเฟอร์ดินานด์ จอร์จ โฟรเบนิอุสและเป็นที่รู้จักกันดีหลังจากวิลเลียม เบิร์นไซด์อ้างถึง[ 1 ]ผลลัพธ์นี้แจกแจงวงโคจรของกลุ่มสมมาตรที่กระทำต่อวัตถุบางอย่าง กล่าวคือ มันนับวัตถุที่แตกต่างกัน โดยพิจารณาวัตถุที่สมมาตรกันเป็นสิ่งเดียวกัน หรือนับวัตถุที่แตกต่างกันจนถึงความสัมพันธ์สมมูลสมมาตรหรือนับเฉพาะวัตถุในรูปแบบมาตรฐานตัวอย่างเช่น ในการอธิบายสารประกอบอินทรีย์ที่เป็นไปได้ของบางประเภท เราจะพิจารณาสารประกอบเหล่านั้นจนถึงสมมาตรการหมุนเชิงพื้นที่ ภาพวาดที่หมุนต่างกันของโมเลกุลที่กำหนดจะเหมือนกันทางเคมี (ในขณะที่ภาพสะท้อนอาจให้สารประกอบที่แตกต่างกัน )
คำแถลง
อนุญาตเป็นกลุ่มจำกัด ที่กระทำต่อเซตสำหรับแต่ละใน, อนุญาตแทนเซตขององค์ประกอบในที่ได้รับการแก้ไขโดย( ไม่เปลี่ยนแปลง ทางซ้าย โดย)): นั่นคือ ทฤษฎีบทของเบิร์นไซด์ยืนยันสูตรต่อไปนี้สำหรับจำนวนวงโคจรซึ่งแสดงด้วยสัญลักษณ์: [ 2 ]
ดังนั้น จำนวนวงโคจร ( จำนวนธรรมชาติหรือ+∞ ) จึงเท่ากับ จำนวนจุด เฉลี่ยที่ถูกตรึงโดยสมาชิกของGสำหรับกลุ่มอนันต์ยังคงมีการจับคู่แบบหนึ่งต่อหนึ่ง อยู่ :
ตัวอย่าง
สร้อยคอ
มีสตริงบิต ที่เป็นไปได้ 8 แบบ ที่มีความยาว 3 แต่เมื่อนำปลายสตริงมาต่อกัน จะได้สร้อยคอ สองสี ที่มีความยาว 3 เพียงสี่แบบที่แตกต่างกัน ซึ่งกำหนดโดยรูปแบบมาตรฐาน 000, 001, 011, 111: สตริงอื่นๆ เช่น 100 และ 010 จะเทียบเท่ากับ 001 โดยการหมุน ในขณะที่ 110 และ 101 จะเทียบเท่ากับ 011 กล่าวคือ ความเท่าเทียมกันของการหมุนจะแบ่งเซตออกเป็นสองส่วนของสายต่างๆ ออกเป็นสี่วงโคจร:สูตรของเบิร์นไซด์ใช้จำนวนการหมุน ซึ่งคือ 3 ครั้ง รวมทั้งการหมุนศูนย์ และจำนวนสตริงบิตที่ยังคงไม่เปลี่ยนแปลงจากการหมุนแต่ละครั้ง เวกเตอร์ทั้งแปดตัวไม่เปลี่ยนแปลงจากการหมุนศูนย์ และสองตัว (000 และ 111) ไม่เปลี่ยนแปลงจากการหมุนอีกสองครั้ง ดังนั้นจำนวนวงโคจรคือ:
สำหรับความยาว 4 จะมีสตริงบิตที่เป็นไปได้ 16 แบบ; มีการหมุน 4 แบบ; การหมุนแบบศูนย์จะไม่เปลี่ยนแปลงสตริงทั้ง 16 แบบ; การหมุน 1 รอบและการหมุน 3 รอบแต่ละแบบจะไม่เปลี่ยนแปลงสตริงสองแบบ (0000 และ 1111); การหมุน 2 รอบจะไม่เปลี่ยนแปลงสตริงบิต 4 แบบ (0000, 0101, 1010, 1111) ดังนั้นจำนวนสร้อยคอที่แตกต่างกันจึงเป็นดังนี้:ซึ่งแสดงโดยรูปแบบมาตรฐาน 0000, 0001, 0011, 0101, 0111, 1111
กรณีทั่วไปของข้อมูลnบิตและkสี จะแสดงด้วยพหุนามสร้อยคอ
การระบายสีลูกบาศก์
ทฤษฎีบทของเบิร์นไซด์สามารถคำนวณจำนวนการระบายสีที่แตกต่างกันโดยการหมุนของหน้าลูกบาศก์โดยใช้สีสามสีได้
อนุญาตเป็นเซตของการผสมสีหน้าที่เป็นไปได้ 3 6แบบ ที่สามารถนำไปใช้กับลูกบาศก์คงที่ และให้กลุ่มการหมุนGของลูกบาศก์กระทำต่อเซตดังกล่าวโดยการขยับหน้าสี: การระบายสีสองแบบในทั้งสองกลุ่มจะอยู่ในวงโคจรเดียวกันก็ต่อเมื่อกลุ่มหนึ่งเป็นการหมุนของอีกกลุ่มหนึ่งเท่านั้น การระบายสีที่แตกต่างกันตามการหมุนจะสอดคล้องกับวงโคจรของกลุ่ม และสามารถหาได้โดยการนับขนาดของเซตคงที่สำหรับองค์ประกอบทั้ง 24 ของGซึ่งเป็นการระบายสีที่ไม่เปลี่ยนแปลงในแต่ละการหมุน:

- องค์ประกอบเอกลักษณ์จะกำหนดค่าสีทั้ง 3 และ 6สี
- การหมุนใบหน้า 90 องศาจำนวนหกครั้ง โดยแต่ละครั้งจะแก้ไขการระบายสี 3 3 ครั้ง
- การหมุนใบหน้า 180 องศา 3 ครั้ง โดยแต่ละครั้งแก้ไขการระบายสี 3 และ 4สี
- การหมุนจุดยอด 120 องศาแปดครั้ง โดยแต่ละครั้งจะกำหนดค่าสี 3 2 ค่า
- การหมุนขอบ 180 องศาจำนวนหกครั้งแต่ละครั้งจะแก้ไขการระบายสี 3 3สี
สามารถดูรายละเอียดการตรวจสอบได้ ที่นี่
ดังนั้นขนาดชุดคงที่โดยเฉลี่ยจึงเป็นดังนี้:
มีวิธีการระบายสีหน้าของลูกบาศก์สามสีที่แตกต่างกันโดยการหมุน 57 วิธี โดยทั่วไปแล้ว จำนวนวิธีการระบายสีหน้าของลูกบาศก์ที่มีnสีที่แตกต่างกันโดยการหมุน คือ:
คลาสการผันคำกริยา
อนุญาตเป็นกลุ่มจำกัด พิจารณาการกระทำของกลุ่มโดยตัวมันเองกำหนดโดยแผนที่การผันคำกริยาที่ไหนวงโคจรเหล่านี้คือชั้นการสมมูลของและเซตของจุดคงที่ขององค์ประกอบคือตัวรวมศูนย์ดังนั้น ตามทฤษฎีบทของเบิร์นไซด์ จำนวนชั้นสมมูลของเท่ากับนั่นคือ ขนาดเฉลี่ยของตัวจัดตำแหน่งศูนย์กลาง
การพิสูจน์
ในการพิสูจน์ทฤษฎีบทของเบิร์นไซด์ ขั้นตอนแรกคือการแสดงผลรวมของสมาชิกกลุ่มg ∈ G ใหม่ ให้เป็นผลรวมที่เทียบเท่ากันของเซตของสมาชิกx ∈ X :
ที่นี่คือเซตของจุดของถูกกำหนดโดยองค์ประกอบของ, ในทางตรงกันข้ามเป็นกลุ่มย่อยที่มีเสถียรภาพของซึ่งประกอบด้วยสมมาตรเหล่านั้นที่ตรึงจุดไว้.
ทฤษฎีการรักษาเสถียรภาพวงโคจรกล่าวว่า สำหรับแต่ละมีการจับคู่แบบหนึ่งต่อ หนึ่งตามธรรมชาติ ระหว่างวงโคจรและเซตของโคเซตซ้ายทฤษฎีบทของลากรองจ์บ่งชี้ ว่า
ดังนั้น ผลรวมจึงสามารถเขียนใหม่ได้ดังนี้
การเขียนเป็นการรวมกันที่ไม่ต่อเนื่องของวงโคจรในให้
เมื่อนำทุกอย่างมารวมกัน จะได้ผลลัพธ์ที่ต้องการ:
นี่คล้ายกับการพิสูจน์สมการชั้นการสมมูลซึ่งพิจารณาการกระทำการสมมูลของโดยตัวมันเอง นั่นคือ เป็นเช่นนั้นและดังนั้นตัวกันสั่นของคือตัวรวมศูนย์.
การแจงนับเทียบกับการสร้าง
ทฤษฎีบทของเบิร์นไซด์นับจำนวนวัตถุที่แตกต่างกัน แต่ไม่ได้สร้างวัตถุเหล่านั้นขึ้นมา โดยทั่วไป การสร้างเชิงการจัดเรียงที่มีการปฏิเสธไอโซมอร์ฟจะพิจารณาสมมาตรของบนวัตถุแต่แทนที่จะตรวจสอบว่ามันจะตรวจสอบว่ายังไม่ได้ถูกสร้างขึ้น วิธีหนึ่งในการทำเช่นนี้คือการตรวจสอบว่าไม่น้อยกว่าในเชิงพจนานุกรมโดยใช้สมาชิกที่น้อยที่สุดตามลำดับตัวอักษรของแต่ละคลาสสมมูลเป็นรูปแบบมาตรฐานของคลาส[ 3 ]การนับวัตถุที่สร้างขึ้นด้วยเทคนิคดังกล่าวสามารถตรวจสอบได้ว่าบทพิสูจน์ของ Burnside ถูกนำไปใช้อย่างถูกต้อง
ประวัติศาสตร์: บทพิสูจน์ที่ไม่ใช่ของเบิร์นไซด์
วิลเลียม เบิร์นไซด์กล่าวและพิสูจน์บทพิสูจน์นี้ในหนังสือเกี่ยวกับกลุ่มจำกัดของเขาในปี 1897 โดยอ้างอิงถึงฟรอเบนิอุสในปี 1887แต่แม้กระทั่งก่อนฟรอเบนิอุส สูตรนี้ก็เป็นที่รู้จักของคอชีในปี 1845 ดังนั้น บทพิสูจน์นี้จึงบางครั้งถูกเรียกว่าบทพิสูจน์ที่ไม่ใช่ของเบิร์นไซด์ [ 4 ] การอ้างอิงบทพิสูจน์ไปยังบุคคลอื่นที่ไม่ใช่ผู้ค้นพบดั้งเดิมเป็นตัวอย่างของกฎของสติกล์เลอร์เกี่ยวกับการตั้งชื่อตามบุคคล
ดูเพิ่มเติม
หมายเหตุ
- ↑เบิร์นไซด์ 1897 , §119
- ↑ร็อตแมน 1995 บทที่ 3
- ↑ Cull, Paul; Pandey, Rajeev (1994). "Isomorphism and the N-Queens problem" . ACM SIGCSE Bulletin . 26 (3): 29– 36. doi : 10.1145/187387.187400 . S2CID 207183291 .
- ↑ Neumann, Peter M. (1979). "บทพิสูจน์ย่อยที่ไม่ใช่ของ Burnside". The Mathematical Scientist . 4 (2): 133– 141. ISSN 0312-3685 . MR 0562002 . .