TOP
16 กุมภาพันธ์ 2008, 13:44
งานเลี้ยงโต๊ะจีนอลวน
เหมือนเป็นปัญหาต่อเนื่องจากปัญหาจดหมายผิดซอง เพราะหลังจากมีผู้แก้ปัญหานั้นได้แล้วอีกราว 200 ปีต่อมา จึงมีผู้เสนอปัญหาเกี่ยวกับการจับคู่ที่ซับซ้อนยิ่งขึ้น นัยว่าคราวที่แล้วเป็นการส่งจดหมายไปนัดแขกมาร่วมงานเลี้ยงและเล๊ะเป็นโจ๊กไปแล้ว :blood: คราวนี้ถึงเวลาจัดตำแหน่งที่นั่งงานเลี้ยงโต๊ะจีนให้แขก ซึ่งเป็นสามีภรรยา $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}$
เอ แล้วทำยังไงต่อดีละ :confused:
กำหนดให้
$M_i$ คือสามีของ $F_i$
$F_i$ คือภรรยาของ $M_i$ เอ๊ะยังไง :rolleyes:
$M_x$ คือสามีของใครก็ไม่รู้ละ
$F_x$ คือภรรยาของใครก็ไม่รู้ละ :laugh:
หลักการเรียงของบนวงกลมแบบหนึ่งคือ $จำนวนการจัดแบบวงกลม = \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$ (จำนวนวิธีจัดที่นั่งชายสลับหญิงรอบโต๊ะกลม)
จัดแบบวงกลมโดยมองให้เป็นเส้นตรง
เลือกชายหรือหญิงนั่งหัวแถว ($2$ วิธี)
ผู้ชายนั่งสลับกันเอง ($n!$ วิธี)
ผู้หญิงนั่งสลับกันเอง ($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$ คู่ที่เหลือจะนั่งติดกันหรือไม่ก็ได้ รอบโต๊ะกลม)
จัดแบบวงกลมโดยมองให้เป็นเส้นตรง
เลือกสามีภรรยา $k$ คู่ จากทั้งหมด $n$ คู่ ($\binom{n}{k}$ วิธี)
เลือกที่นั่งคู่ให้ สามีภรรยานั่งติดกัน $k$ คู่ จากที่นั่งทั้งหมด $2n$ ตำแหน่ง (เท่าไหร่หว่า :confused: )
หนึ่งในภรรยาที่นั่งติดกับสามีตนเอง เลือกว่าจะนั่งทางซ้ายหรือขวามือของสามี($2$ วิธี)
สามีที่เลือกมา $k$ คน นั่งบนที่นั่งที่เลือกไว้ในขั้นตอนที่ 2 ($k!$ วิธี)
ภรรยาที่เลือกมา $k$ คน นั่งบนที่นั่งที่เลือกไว้ในขั้นตอนที่ 3 ($1$ วิธี)
สามีที่เหลือ $n - k$ คน นั่ง ($(n - k)!$ วิธี)
ภรรยาที่เหลือ $n - k$ คน นั่ง ($(n - k)!$ วิธี)
ขั้นตอนที่ 2 อาจมีคนสงสัยว่า ทำไมเราไม่เลือกที่นั่ง $k$ คู่ จากที่นั่ง $n$ คู่ละ นั่นก็เพราะการเลือกแบบนั้นจะไม่รวมกรณีเหล่านี้เข้าไปด้วย ทำให้ได้จำนวนวิธีไม่ครบ
$\cdots \color{red}{M_1 F_1} M_x \color{red}{F_2 M_2} \cdots$
$\color{red}{M_1} \cdots \cdots \color{red}{F_1}$คงจะเริ่มมองเห็นภาพแล้วใช่ไหมครับ ว่ามันมีความยุ่งยากเพียงใด :laugh:
เพื่อให้ง่ายขึ้น ลองพิจารณาการเลือกที่นั่งคู่ $k$ คู่ ที่ไม่ยอมให้เลือกที่นั่งคู่คร่อมตรงตำแหน่ง หัวแถวกับท้ายแถว ส่วนตำแหน่งอื่นจะเลือกยังไงก็ได้ ว่าทำได้กี่วิธี ปัญหานี้จะเหมือนกับ การหาจำนวนวิธีวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $k$ ตัว ทับบนตัวเลข $1 - n$ ที่เขียนเรียงลำดับกันในแนวเส้นตรง โดยวางตัวโดมิโนซ้อนกันไม่ได้ ตัวอย่างเช่น
การวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $2$ ตัว ทับลงบนตัวเลข $1 - 6$ ที่เขียนเรียงลำดับกันในแนวเส้นตรง ทำได้ 6 วิธีดังนี้
$\bbox{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}$
ถ้าเราไม่นั่งนับทีละแบบ เราจะมีวิธีหาจำนวนวิธีวางตัวโดมิโนได้อย่างไร :rolleyes:
หากเราแทนตัวโดมิโนด้วยอักษร "a" และแทนตัวเลขที่ไม่โดนโดมิโนวางทับด้วยตัวอักษร "b" ทั้ง 6 วิธีนั้นจะเป็นคำต่อไปนี้
"aabb" , "abab" , "abba" , "baab" , "baba" , "bbaa"
คุ้นกับปัญหานี้ไหมครับ :cool: มันก็คือจำนวนวิธีทั้งหมดในการเีรียง 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$ ในแนววงกลมละ จะมีจำนวนวิธีวางตัวโดมิโนทับได้กี่วิธี :confused:
เราแก้ปัญหานี้ด้วยการแบ่งเป็น 2 กรณีคือ
[B]มีตัวโดมิโนวางทับเลข 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}}$ วิธี
ไม่มีตัวโดมิโนวางทับเลข 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)!}$
เหมือนเป็นปัญหาต่อเนื่องจากปัญหาจดหมายผิดซอง เพราะหลังจากมีผู้แก้ปัญหานั้นได้แล้วอีกราว 200 ปีต่อมา จึงมีผู้เสนอปัญหาเกี่ยวกับการจับคู่ที่ซับซ้อนยิ่งขึ้น นัยว่าคราวที่แล้วเป็นการส่งจดหมายไปนัดแขกมาร่วมงานเลี้ยงและเล๊ะเป็นโจ๊กไปแล้ว :blood: คราวนี้ถึงเวลาจัดตำแหน่งที่นั่งงานเลี้ยงโต๊ะจีนให้แขก ซึ่งเป็นสามีภรรยา $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}$
เอ แล้วทำยังไงต่อดีละ :confused:
กำหนดให้
$M_i$ คือสามีของ $F_i$
$F_i$ คือภรรยาของ $M_i$ เอ๊ะยังไง :rolleyes:
$M_x$ คือสามีของใครก็ไม่รู้ละ
$F_x$ คือภรรยาของใครก็ไม่รู้ละ :laugh:
หลักการเรียงของบนวงกลมแบบหนึ่งคือ $จำนวนการจัดแบบวงกลม = \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$ (จำนวนวิธีจัดที่นั่งชายสลับหญิงรอบโต๊ะกลม)
จัดแบบวงกลมโดยมองให้เป็นเส้นตรง
เลือกชายหรือหญิงนั่งหัวแถว ($2$ วิธี)
ผู้ชายนั่งสลับกันเอง ($n!$ วิธี)
ผู้หญิงนั่งสลับกันเอง ($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$ คู่ที่เหลือจะนั่งติดกันหรือไม่ก็ได้ รอบโต๊ะกลม)
จัดแบบวงกลมโดยมองให้เป็นเส้นตรง
เลือกสามีภรรยา $k$ คู่ จากทั้งหมด $n$ คู่ ($\binom{n}{k}$ วิธี)
เลือกที่นั่งคู่ให้ สามีภรรยานั่งติดกัน $k$ คู่ จากที่นั่งทั้งหมด $2n$ ตำแหน่ง (เท่าไหร่หว่า :confused: )
หนึ่งในภรรยาที่นั่งติดกับสามีตนเอง เลือกว่าจะนั่งทางซ้ายหรือขวามือของสามี($2$ วิธี)
สามีที่เลือกมา $k$ คน นั่งบนที่นั่งที่เลือกไว้ในขั้นตอนที่ 2 ($k!$ วิธี)
ภรรยาที่เลือกมา $k$ คน นั่งบนที่นั่งที่เลือกไว้ในขั้นตอนที่ 3 ($1$ วิธี)
สามีที่เหลือ $n - k$ คน นั่ง ($(n - k)!$ วิธี)
ภรรยาที่เหลือ $n - k$ คน นั่ง ($(n - k)!$ วิธี)
ขั้นตอนที่ 2 อาจมีคนสงสัยว่า ทำไมเราไม่เลือกที่นั่ง $k$ คู่ จากที่นั่ง $n$ คู่ละ นั่นก็เพราะการเลือกแบบนั้นจะไม่รวมกรณีเหล่านี้เข้าไปด้วย ทำให้ได้จำนวนวิธีไม่ครบ
$\cdots \color{red}{M_1 F_1} M_x \color{red}{F_2 M_2} \cdots$
$\color{red}{M_1} \cdots \cdots \color{red}{F_1}$คงจะเริ่มมองเห็นภาพแล้วใช่ไหมครับ ว่ามันมีความยุ่งยากเพียงใด :laugh:
เพื่อให้ง่ายขึ้น ลองพิจารณาการเลือกที่นั่งคู่ $k$ คู่ ที่ไม่ยอมให้เลือกที่นั่งคู่คร่อมตรงตำแหน่ง หัวแถวกับท้ายแถว ส่วนตำแหน่งอื่นจะเลือกยังไงก็ได้ ว่าทำได้กี่วิธี ปัญหานี้จะเหมือนกับ การหาจำนวนวิธีวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $k$ ตัว ทับบนตัวเลข $1 - n$ ที่เขียนเรียงลำดับกันในแนวเส้นตรง โดยวางตัวโดมิโนซ้อนกันไม่ได้ ตัวอย่างเช่น
การวางตัวโดมิโนขนาด $1 \times 2$ จำนวน $2$ ตัว ทับลงบนตัวเลข $1 - 6$ ที่เขียนเรียงลำดับกันในแนวเส้นตรง ทำได้ 6 วิธีดังนี้
$\bbox{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}$
ถ้าเราไม่นั่งนับทีละแบบ เราจะมีวิธีหาจำนวนวิธีวางตัวโดมิโนได้อย่างไร :rolleyes:
หากเราแทนตัวโดมิโนด้วยอักษร "a" และแทนตัวเลขที่ไม่โดนโดมิโนวางทับด้วยตัวอักษร "b" ทั้ง 6 วิธีนั้นจะเป็นคำต่อไปนี้
"aabb" , "abab" , "abba" , "baab" , "baba" , "bbaa"
คุ้นกับปัญหานี้ไหมครับ :cool: มันก็คือจำนวนวิธีทั้งหมดในการเีรียง 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$ ในแนววงกลมละ จะมีจำนวนวิธีวางตัวโดมิโนทับได้กี่วิธี :confused:
เราแก้ปัญหานี้ด้วยการแบ่งเป็น 2 กรณีคือ
[B]มีตัวโดมิโนวางทับเลข 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}}$ วิธี
ไม่มีตัวโดมิโนวางทับเลข 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)!}$