โจทย์combiครับ

[dephenul]

มีพวงกุญแจชนิด A,B,C อย่างละ2ชิ้น นำมาร้อยเป็นพวงกุญแจรูปวงกลมจะเป็นไปได้กี่วิธี

[poper]

$\frac{(6-1)!}{2!\times2!\times2!}=15$ ครับ

[dephenul]

ที่ผมลองวาดรูปดูมันไม่ถึง15นะครับ

[dephenul]

2กรณีนี้ถือว่าเหมือนกันนะครับเพราะมันเป็นพวงกุญแจซึ่งพลิกได้
..AA.........................AA
.B...C......................C...B
...BC.........................CB

[poper]

ข้อความเดิมเขียนโดยคุณ dephenul

2กรณีนี้ถือว่าเหมือนกันนะครับเพราะมันเป็นพวงกุญแจซึ่งพลิกได้
..AA.........................AA
.B...C......................C...B
...BC.........................CB

อ้อ จริงครับ ผมลืมนึกไป
แต่พอคิดใหม่(ลองวาดรูปดูด้วย)ได้ 12 ครับ

[poper]

แต่ถ้าคำนวณโดยใช้สูตรยังคงออกมาเป็น 15 เหมือนเดิมอ่ะครับเลยไม่ค่อยแน่ใจ
(แต่ผมเชื่อสูตรมากกว่าวาดรูปนะ)

[picmy]

ผมขอแนะนำสองสูตรละกันนะครับ

(1) จำนวนวิธีการเรียงของ $n$ ชิ้น โดยที่ มีของอยู่ทั้งหมด $r$ ประเภท ประเภทที่ $i$ มีอยู่ $n_i$ ชิ้น ($n_1+n_2+...+n_r=n$) เป็นวงกลม มีค่าเท่ากับ
$$ \frac{1}{n}\sum_{d|(n_1,n_2,...,n_r)}\varphi (d) \frac{\left(\frac{n}{d}\right)!}{\left(\frac{n_1}{d}\right)!\left(\frac{n_2}{d}\right)!...\left(\frac{n_r}{d}\right)!}$$
โดยที่ $(n_1,n_2,...,n_r)$ แทน ห.ร.ม. ของ $n_1,n_2,...,n_r$ และ $\varphi (d)$ คือ Euler's totient function (หรือ Euler's phi function)

http://en.wikipedia.org/wiki/Euler%27s_totient_function
(2) จำนวนวิธีการนำของ $n$ ชิ้น โดยที่ มีของอยู่ทั้งหมด $r$ ประเภท ประเภทที่ $i$ มีอยู่ $n_i$ ชิ้น ($n_1+n_2+...+n_r=n$) มาร้อยเป็นกำไล (หรือ พวงมาลัย) มีค่าเท่ากับ
$$ \frac{1}{2n}\sum_{d|(n_1,n_2,...,n_r)}\varphi (d) \frac{\left(\frac{n}{d}\right)!}{\left(\frac{n_1}{d}\right)!\left(\frac{n_2}{d}\right)!...\left(\frac{n_r}{d}\right)!}+
\cases{0 & , ถ้าท่ามกลางจำนวน \, n_1,n_2,...,n_r \,มีอย่างน้อย\, 3\, ตัวที่เป็นจำนวนคี่ \cr \frac{1}{2}\frac{\left(\sum_{i=1}^{r}\left\lfloor\frac{n_i}{2}\right\rfloor \right)!}{\left\lfloor\frac{n_1}{2}\right\rfloor !...\left\lfloor\frac{n_r}{2}\right\rfloor ! } & , กรณีอื่นๆ} $$

การที่จะพิสูจน์ สูตรสองสูตรนี้สามารถใช้ Pólya enumeration theorem

http://en.wikipedia.org/wiki/P%C3%B3...ration_theorem

[dephenul]

ขอบคุณครับ

[picmy]

ข้อความเดิมเขียนโดยคุณ dephenul

ขอบคุณครับ

ด้วยความยินดีครับ

ผมขออธิบายเพิ่มเติม เกี่ยวกับสูตรข้างบนเล็กน้อยละกันครับ (เผื่อว่าจะมีบางคนไม่ค่อยคุ้นเคยกับฟังก์ชัน $\varphi (d)$)

ที่จริงแล้ว $\varphi (d)$ แทนจำนวนของจำนวนเต็มบวกที่ น้อยกว่าเท่ากับ $d$ และเป็นจำนวนเฉพาะสัมพัทธ์กับ $d$ (นั่นคือ $\varphi (d)=\#\{a : 1 \leq a \leq d\, และ \, (a,d)=1\}$)

ยกตัวอย่างเช่น
$\varphi (1)=1$
$\varphi (2)=1$
$\varphi (3)=2$

ในกรณีของข้อนี้ ใช้สูตร (2) จะได้ว่า จำนวนวิธีที่จะร้อยพวงกุญแจดังกล่าว มีค่าเท่ากับ
$$
\frac{1}{12}\left(\varphi (1)\frac{6!}{2!2!2!}+\varphi (2)\frac{(\frac{6}{2})!}{(\frac{2}{2})!(\frac{2}{2})!(\frac{2}{2})!} \right) +\frac{1}{2}\frac{(\left\lfloor \frac{2}{2}\right\rfloor+\left\lfloor\frac{2}{2}\right\rfloor+\left\lfloor\frac{2}{2}\right\rfloor )!}{\left\lfloor\frac{2}{2}\right\rfloor!\left\lfloor\frac{2}{2}\right\rfloor!\left\lfloor \frac{2}{2}\right\rfloor!}
$$
ตอบเท่าไหร่ ลองคิดต่อดูนะครับ