งานเลี้ยงโต๊ะจีนอลวน

[TOP]

งานเลี้ยงโต๊ะจีนอลวน

เหมือนเป็นปัญหาต่อเนื่องจากปัญหาจดหมายผิดซอง เพราะหลังจากมีผู้แก้ปัญหานั้นได้แล้วอีกราว 200 ปีต่อมา จึงมีผู้เสนอปัญหาเกี่ยวกับการจับคู่ที่ซับซ้อนยิ่งขึ้น นัยว่าคราวที่แล้วเป็นการส่งจดหมายไปนัดแขกมาร่วมงานเลี้ยงและเล๊ะเป็นโจ๊กไปแล้ว คราวนี้ถึงเวลาจัดตำแหน่งที่นั่งงานเลี้ยงโต๊ะจีนให้แขก ซึ่งเป็นสามีภรรยา $n$ คู่ ยังจัดที่นั่งให้สามีนั่งไม่ติดกับภรรยาของตนเลยสักคู่เดียว ปัญหาของเราคราวนี้จึงเป็น

จงหาจำนวนวิธีทั้งหมดในการจัดที่นั่งรอบโต๊ะกลมให้กับ สามีภรรยา $n$ คู่ โดยนั่งชายสลับหญิง และสามีจะนั่งไม่ติดกับภรรยาของตน

ปัญหานี้เป็นที่รู้จักกันในชื่อ Married Couples หากใครจำหลักการแก้ปัญหาแบบเรียงสับเปลี่ยนคราวที่แล้วได้ คงพอจะมองออกแล้วว่าควรจะเริ่มแก้ปัญหาข้อนี้อย่างไรดี

กำหนดให้
$c_i$ คือ สามีภรรยาคู่ที่ $i$ นั่งติดกัน รอบโต๊ะกลม
$M(k,n)$ คือ จำนวนวิธีจัดที่นั่งให้ สามีภรรยานั่งติดกัน $k$ คู่ โดยสามีภรรยา $n-k$ คู่ที่เหลือจะนั่งติดกันหรือไม่ก็ได้ รอบโต๊ะกลม

จากหลักการรวมเข้าและหักออกจะได้ว่า
$\begin{array}{rcl}
N(\bar c_1 \bar c_2 \cdots \bar c_n) & = & \displaystyle{N - \sum_{i = 1}^{n} N(c_i) + \sum_{\substack{i,j= 1 \\ i \not= j}}^{n} N(c_i c_j) - \sum_{\substack{i,j,k= 1 \\ i \not= j \not= k}}^{n} N(c_i c_j c_k) + \cdots + (-1)^n N(c_1 c_2 \dots c_n) }\\
& = & N - M(1,n) + M(2,n) - M(3,n) + \cdots + (-1)^n M(n,n)
\end{array}$

เอ แล้วทำยังไงต่อดีละ

กำหนดให้
$M_i$ คือสามีของ $F_i$
$F_i$ คือภรรยาของ $M_i$ เอ๊ะยังไง
$M_x$ คือสามีของใครก็ไม่รู้ละ
$F_x$ คือภรรยาของใครก็ไม่รู้ละ

หลักการเรียงของบนวงกลมแบบหนึ่งคือ $จำนวนการจัดแบบวงกลม = \frac{จำนวนการจัดแบบเส้นตรง}{จำนวนรูปแบบที่ซ้ำ}$

การจัดแบบเส้นตรงในที่นี้ไม่ได้หมายความว่า ตัดความคิดเรื่องวงกลมออกไปหมดเลยนะครับ แต่จัดเป็นเส้นตรงเพื่อให้ง่ายและคุ้นเคยในการพิจารณากรณีต่างๆ โดยคนหัวแถวกับท้ายแถวยังมีความสัมพันธ์ว่าอยู่ติดกันด้วยนะครับ เช่น

จัดแบบเส้นตรง 100%
$\color{red}{M_1} F_x M_2 F_x \cdots M_n \color{red}{F_y}$ เรามองว่า $M_1$ และ $F_y$ นั่งไม่ติดกัน

จัดแบบวงกลมโดยมองให้เป็นเส้นตรง
$\color{red}{M_1} F_x M_2 F_x \cdots M_n \color{red}{F_y}$ เรามองว่า $M_1$ และ $F_y$ นั่งติดกัน

เริ่มจากหาค่า $N$ (จำนวนวิธีจัดที่นั่งชายสลับหญิงรอบโต๊ะกลม)

จัดแบบวงกลมโดยมองให้เป็นเส้นตรง

1. เลือกชายหรือหญิงนั่งหัวแถว ($2$ วิธี)
2. ผู้ชายนั่งสลับกันเอง ($n!$ วิธี)
3. ผู้หญิงนั่งสลับกันเอง ($n!$ วิธี)

ทำได้ $2 (n!)^2$ วิธี

จำนวนรูปแบบที่ซ้ำ

เนื่องจากรูปแบบการนั่งแบบนี้จะซ้ำกันเมื่อนั่งเป็นวงกลม
$\left.\begin{array}{ccccccccc}
M_1 & F_x & M_2 & F_x & \cdots & M_{n-1} & F_x & M_n & F_x \\
F_x & M_1 & F_x & M_2 & \cdots & F_x & M_{n-1} & F_x & M_n \\
M_n & F_x & M_1 & F_x & \cdots & M_{n-2} & F_x & M_{n-1} & F_x \\
\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\
M_2 & F_x & M_3 & F_x & \cdots & M_n & F_x & M_1 & F_x \\
F_x & M_2 & F_x & M_3 & \cdots & F_x & M_n & F_x & M_1
\end{array}\right\} 2n\ \text{แบบ}
$

$\therefore N = \frac{2(n!)^2}{2n} = (n-1)!n!$

หาค่า $M(n,k)$ (จำนวนวิธีจัดที่นั่ง ให้สามีภรรยานั่งติดกัน $k$ คู่ โดยสามีภรรยา $n-k$ คู่ที่เหลือจะนั่งติดกันหรือไม่ก็ได้ รอบโต๊ะกลม)

จัดแบบวงกลมโดยมองให้เป็นเส้นตรง

1. เลือกสามีภรรยา $k$ คู่ จากทั้งหมด $n$ คู่ ($\binom{n}{k}$ วิธี)
2. เลือกที่นั่งคู่ให้ สามีภรรยานั่งติดกัน $k$ คู่ จากที่นั่งทั้งหมด $2n$ ตำแหน่ง (เท่าไหร่หว่า )
3. หนึ่งในภรรยาที่นั่งติดกับสามีตนเอง เลือกว่าจะนั่งทางซ้ายหรือขวามือของสามี($2$ วิธี)
4. สามีที่เลือกมา $k$ คน นั่งบนที่นั่งที่เลือกไว้ในขั้นตอนที่ 2 ($k!$ วิธี)
5. ภรรยาที่เลือกมา $k$ คน นั่งบนที่นั่งที่เลือกไว้ในขั้นตอนที่ 3 ($1$ วิธี)
6. สามีที่เหลือ $n - k$ คน นั่ง ($(n - k)!$ วิธี)
7. ภรรยาที่เหลือ $n - k$ คน นั่ง ($(n - k)!$ วิธี)

ขั้นตอนที่ 2 อาจมีคนสงสัยว่า ทำไมเราไม่เลือกที่นั่ง $k$ คู่ จากที่นั่ง $n$ คู่ละ นั่นก็เพราะการเลือกแบบนั้นจะไม่รวมกรณีเหล่านี้เข้าไปด้วย ทำให้ได้จำนวนวิธีไม่ครบ

1. $\cdots \color{red}{M_1 F_1} M_x \color{red}{F_2 M_2} \cdots$
2. $\color{red}{M_1} \cdots \cdots \color{red}{F_1}$

คงจะเริ่มมองเห็นภาพแล้วใช่ไหมครับ ว่ามันมีความยุ่งยากเพียงใด

เพื่อให้ง่ายขึ้น ลองพิจารณาการเลือกที่นั่งคู่ $k$ คู่ ที่ไม่ยอมให้เลือกที่นั่งคู่คร่อมตรงตำแหน่ง หัวแถวกับท้ายแถว ส่วนตำแหน่งอื่นจะเลือกยังไงก็ได้ ว่าทำได้กี่วิธี ปัญหานี้จะเหมือนกับ การหาจำนวนวิธีวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $k$ ตัว ทับบนตัวเลข $1 - n$ ที่เขียนเรียงลำดับกันในแนวเส้นตรง โดยวางตัวโดมิโนซ้อนกันไม่ได้ ตัวอย่างเช่น

การวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $2$ ตัว ทับลงบนตัวเลข $1 - 6$ ที่เขียนเรียงลำดับกันในแนวเส้นตรง ทำได้ 6 วิธีดังนี้
$\bbox[border:1px black solid,2pt]{1 \quad 2} \quad \bbox[border:1px black solid,2pt]{3 \quad 4} \quad 5 \quad 6$
$\bbox[border:1px black solid,2pt]{1 \quad 2} \quad 3 \quad \bbox[border:1px black solid,2pt]{4 \quad 5} \quad 6$
$\bbox[border:1px black solid,2pt]{1 \quad 2} \quad 3 \quad 4 \quad \bbox[border:1px black solid,2pt]{5 \quad 6}$
$1 \quad \bbox[border:1px black solid,2pt]{2 \quad 3} \quad \bbox[border:1px black solid,2pt]{4 \quad 5} \quad 6$
$1 \quad \bbox[border:1px black solid,2pt]{2 \quad 3} \quad 4 \quad \bbox[border:1px black solid,2pt]{5 \quad 6}$
$1 \quad 2 \quad \bbox[border:1px black solid,2pt]{3 \quad 4} \quad \bbox[border:1px black solid,2pt]{5 \quad 6}$

ถ้าเราไม่นั่งนับทีละแบบ เราจะมีวิธีหาจำนวนวิธีวางตัวโดมิโนได้อย่างไร

หากเราแทนตัวโดมิโนด้วยอักษร "a" และแทนตัวเลขที่ไม่โดนโดมิโนวางทับด้วยตัวอักษร "b" ทั้ง 6 วิธีนั้นจะเป็นคำต่อไปนี้

"aabb" , "abab" , "abba" , "baab" , "baba" , "bbaa"

คุ้นกับปัญหานี้ไหมครับ มันก็คือจำนวนวิธีทั้งหมดในการเีรียง a 2 ตัว และ b 2 ตัว ให้เป็นคำใหม่นั่นเอง ได้จำนวนวิธีทั้งหมดคือ $\frac{4!}{2!2!} = 6$ วิธี

ดังนั้น จำนวนวิธีวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $k$ ตัว ทับบนตัวเลข $1 - n$ ที่เขียนเรียงลำดับกันในแนวเส้นตรง โดยวางตัวโดมิโนซ้อนกันไม่ได้ ทำได้ทั้งสิ้น $\displaystyle{\frac{(n - k)!}{k! (n - 2k)!} = \binom{n - k}{k}}$ วิธี

แล้วถ้าเราเขียนตัวเลข $1 -n$ ในแนววงกลมละ จะมีจำนวนวิธีวางตัวโดมิโนทับได้กี่วิธี

เราแก้ปัญหานี้ด้วยการแบ่งเป็น 2 กรณีคือ

1. มีตัวโดมิโนวางทับเลข 1
   • มีตัวโดมิโนวางทับเลข n กับ 1
   • มีตัวโดมิโนวางทับเลข 1 กับ 2
   $\begin{array}{ccccc}
   & & \style{background-color: #AAEEFF;}{1} & & \\
   & \style{background-color: #AAEEFF;}{n} & & 2 & \\
   n-1 & & & & 3 \\
   \cdot & & & & 4\\
   & \cdot & & \cdot & \\
   & & \cdot & &
   \end{array}\qquad \qquad \begin{array}{ccccc}
   & & \style{background-color: #AAEEFF;}{1} & & \\
   & n & & \style{background-color: #AAEEFF;}{2} & \\
   n-1 & & & & 3 \\
   \cdot & & & & 4\\
   & \cdot & & \cdot & \\
   & & \cdot & &
   \end{array}$
   ทั้ง 2 กรณีย่อยนี้ เนื่องจากเราวางตัวโดมิโนกันตำแหน่งเลข 1 ไว้หมดแล้ว ดังนั้นการวางตัวโดมิโนที่เหลือ จึงเป็นการวางตัวโดมิโน $k-1$ ตัว ทับบนตัวเลข $n-2$ ตัว ที่เขียนเรียงกันในแนวเส้นตรง ทำได้ทั้งสิ้นกรณีย่อยละ $\displaystyle{\binom{n - k -1}{k - 1}}$ วิธี
   
   
2. ไม่มีตัวโดมิโนวางทับเลข 1
   $\begin{array}{ccccc}
   & & \style{background-color: red;}{1} & & \\
   & n & & 2 & \\
   n-1 & & & & 3 \\
   \cdot & & & & 4\\
   & \cdot & & \cdot & \\
   & & \cdot & &
   \end{array}$
   เมื่อเราไม่วางตัวโดมิโนทับเลข 1 จึงเหลือตัวเลข $n - 1$ ตัว ดังนั้นการวางตัวโดมิโนที่เหลือ จึงเป็นการวางตัวโดมิโน $k$ ตัว ทับบนตัวเลข $n-1$ ตัว ที่เขียนเรียงกันในแนวเส้นตรง ทำได้ทั้งสิ้น $\displaystyle{\binom{n - k -1}{k}}$ วิธี

ดังนั้น จำนวนวิธีวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $k$ ตัว ทับบนตัวเลข $1 - n$ ที่เขียนเรียงลำดับกันในแนววงกลม โดยวางตัวโดมิโนซ้อนกันไม่ได้ ทำได้ทั้งสิ้น $\displaystyle{2 \binom{n - k -1}{k - 1} + \binom{n - k -1}{k} = \frac{n}{n - k}\binom{n - k}{k}}$ วิธี

เราจึงได้ จำนวนวิธีเลือกที่นั่งคู่ให้ สามีภรรยานั่งติดกัน $k$ คู่ จากที่นั่งทั้งหมด $2n$ ตำแหน่ง รอบโต๊ะกลม โดยมองให้เป็นเส้นตรง ได้ทั้งหมด $\displaystyle{\frac{2n}{2n - k}\binom{2n - k}{k}}$ วิธี

จำนวนรูปแบบที่ซ้ำ

มีค่าเป็น $2n$ ครับโดยพิจารณาแบบเดียวกับกรณีทั้งหมด

ดังนั้นเราจะได้ จำนวนวิธีจัดที่นั่ง ให้สามีภรรยานั่งติดกัน $k$ คู่ โดยสามีภรรยา $n-k$ คู่ที่เหลือจะนั่งติดกันหรือไม่ก็ได้ รอบโต๊ะกลม
$\begin{array}{rcl}
M(k,n) & = &\displaystyle{\binom{n}{k} \cdot \frac{2n}{2n - k}\binom{2n - k}{k} \cdot 2 \cdot k! \cdot ((n - k)!)^2 \cdot \frac{1}{2n}} \\
& = & \displaystyle{2(n!) \binom{2n - k}{k} \frac{(n - k)!}{2n - k}}
\end{array}$

และเนื่องจาก $M(0,n) = (n-1)!n! = N$ จริง ดังนั้น

$\begin{array}{rcl}
N(\bar c_1 \bar c_2 \cdots \bar c_n) & = & N - M(1,n) + M(2,n) - M(3,n) + \cdots + (-1)^n M(n,n) \\
& = & \displaystyle{2(n!) \sum_{k = 0}^{n} (-1)^k \binom{2n - k}{k} \frac{(n - k)!}{2n - k}}
\end{array}$

หมายเหตุ: คำตอบของปัญหานี้ที่พบได้ทั่วไป จะไม่สนใจว่าเกิดรูปแบบซ้ำขึ้น จึงมีคำตอบเป็น
$\displaystyle{2(n!) \sum_{k = 0}^{n} (-1)^k \frac{2n}{2n - k} \binom{2n - k}{k} (n - k)!}$

[กรza_ba_yo]

อืมสุดยอดคับ

[-+-.Bird.+.+]

ขอบคุณคร้าบบบ

[มือใหม่หัดเรียน]

*0* สุดยอด

[banker]

ผมว่าแค่คิดไม่ให้ภรรยานั่งติดกัยสามีก็ยากอยู่แล้ว คงต้องหาเหตุผลมากกว่าจำนนวนวิธีข้างต้นซะอีก