อ้างอิง:
ข้อความเดิมเขียนโดยคุณ MIN+
จะมีวิธีเรียงสับเปลี่ยนหลอดไฟ 10 หลอดที่มีสีแดง 2 หลอด
สีเขียว 2 หลอด สีเหลือง 2 หลอด สีฟ้า 2 หลอด
สีชมพู 2 หลอด ติดเป็นวงกลมบนกำแพงได้ทั้งหมดกี่วิธี
|
อ้างอิง:
ข้อความเดิมเขียนโดยคุณ Little Penguin
จำนวนวิธีเรียงของ $n$ ชิ้น โดยมี $k$ ชนิด ชนิดที่ $i$ มีของ $a_i$ ชิ้น เมื่อ $i=1,2,\cdots k$ (ของชนิดเดียวกัน ถือว่าเหมือนกัน) เป็นวงกลม เท่ากับ
$$\frac{1}{n}\sum_{d|h}\phi(d)\frac{(n/d)!}{\prod_{i = 1}^{k}(a_i/d)!}$$
เมื่อ $h=(a_1,a_2,\cdots,a_k)$ และ $\phi(d)$ คือ Totient function (หรืออีกในนามว่า phi function)
เช่น มี A 3 ตัว B 2 ตัว C 3 ตัว จะมีวิธีเรียงเป็นวงกลมทั้งหมด $$\frac{1}{8}\sum_{d|1}\phi(d)\frac{(8/d)!}{\prod_{i = 1}^{3}(a_i/d)!} =\frac{1}{8}\left(\frac{8!}{3!2!3!}\right)=\frac{(8-1)!}{3!2!3!}$$
Proof: Pólya enumeration theorem
|
$\frac{1}{10}[\frac{\phi{(1)(10/1)!}}{(2/1)!(2/1)!(2/1)!(2/1)!(2/1)!} +\frac{\phi{(2)(10/2)!}}{(2/2)!(2/2)!(2/2)!(2/2)!(2/2)!} ] = 11352$