little combinatoric

[Siren-Of-Step]

ขอบคุณมากๆครับ ขอบคุณจริง ๆ

ปกติเรา ถือว่าลิง แตกต่างกันใช่ปะครับ
รบกวน RM@ ช่วย บอกหลักตีความโจทย์หน่อยครับ

[RM@]

ลิงก็เหมือนคนครับ คนละแต่คนถือว่าต่างกัน ลิงแต่ละตัวก็ถือว่าต่างกัน แต่ถ้าเป็นตุ๊กตาลิงที่หน้าตาเหมือนกัน ขนาดก็เท่ากัน รุ่นเดียวกัน ปั๊มออกมาจากโรงงาน แบบนี้ถือว่าเหมือนกันครับ ห้องพักแต่ละห้องถือว่าต่างกัน เพราะห้องพักจะมีหมายเลขห้องต่างกันแน่นอน ตำแแหน่งของห้องก็ต่างกันด้วย

ปัญหาในเรื่องการแจกของหรือแบ่งกลุ่ม โดยภาพรวมมันมี 4 ประเภทคือ
แจกของต่างกัน ลงในกล่องต่างกัน
แจกของเหมือนกัน ลงในกล่องต่างกัน
แจกของต่างกัน ลงในกล่องเหมือนกัน
แจกของเหมือนกัน ลงในกล่องเหมือนกัน

ก็ทำความเข้าใจปัญหาในแต่ละแบบและฝึกคิดปัญหาในแต่ละแบบให้ชัดเจนหลาย ๆ ข้อ ก็จะไม่สับสนเองครับ.

[MiNd169]

ข้อความเดิมเขียนโดยคุณ Siren-Of-Step

1. จัดคน 12 คน นั่งเก้าอี้รอบโต๊ะอาหารกลมต่าง ๆ กัน 3 โต๊ะ โต๊ะละ 4 คนกระทำได้กี่วิธี

ผมขอถามผู้รู้หน่อยครับ
กรณีถ้าผมทำแบบตัวอย่างข้างล่าง

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

เลือกคน $4$ คนลงโต๊ะ 3 โต๊ะเลือกได้$\dfrac{12!}{4!4!4!}$

แต่ละโต๊ะนั่งได้ $3!$ มี $3$ โต๊ะจึงเปลี่ยนได้อีก $3!$

$\therefore$ $\dfrac{12!3!3!}{4!4!4!} $

ซึ่งคำตอบที่ถูกคือ $\dfrac{12!}{4^3} $

ผมลืมคูณ $3!$ ตรงส่วนไหนหรอครับ

ถ้าผมเปลี่ยนเป็นแบบนี้จะถูกไหม

เลือกคน $4$ คนลงโต๊ะ 3 โต๊ะเลือกได้$\dfrac{12!}{4!4!4!}$

แต่ละโต๊ะนั่งได้ $3!$ มี $3$ โต๊ะจึงเป็น $3!3!3!$

$\therefore$ $\dfrac{12!3!3!3!}{4!4!4!} $

ขอบคุณครับ

[Onasdi]

ใช่ครับมี 3 โต๊ะ จึงต้องคูณ 3! สามครั้งครับ
แล้วก็ไม่ต้องสลับโต๊ะแล้วเพราะว่าการสลับโต๊ะอยู่ในการเลือกคนของเราแล้วครับ
ลองคิดดูครับที่เราใช้ $\frac{12!}{4!4!4!}$ เราให้ความแตกต่างของแต่ละโต๊ะแล้วครับ

[MiNd169]

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

ใช่ครับมี 3 โต๊ะ จึงต้องคูณ 3! สามครั้งครับ
แล้วก็ไม่ต้องสลับโต๊ะแล้วเพราะว่าการสลับโต๊ะอยู่ในการเลือกคนของเราแล้วครับ
ลองคิดดูครับที่เราใช้ $\frac{12!}{4!4!4!}$ เราให้ความแตกต่างของแต่ละโต๊ะแล้วครับ

ขอบคุณครับ

[กิตติ]

2.3 มีผลไม้ต่าง ๆ กัน7ผลจะให้ลิง3ตัว อย่างน้อย 1 ผลกระทำได้กี่วิธี โดย ผลไม้เหลือบ้างก็ได้

วิธีที่ทำแอบจำมาจากในกระทู้ของMC
แจกผลไม้ให้ลิงคนละ 1 ผลก่อน เลือกมาได้$\binom{7}{3} $แล้วแจกให้ทั้งสามตัวได้อีก $3!$ รวมเป็น$\frac{7!}{4!} $
จากนั้นให้วิธีแบบ$stars \quad and \quad Bars$ เหลือผลไม้อีก 4 ผลที่แตกต่างกัน
ได้ทั้งหมด$\binom{4+3-1}{3-1} =\binom{6}{2} $
รวมแจกได้$\frac{7!}{4!}\times \frac{6!}{2!4!} = 7\times 6 \times 5 \times 5\times 3 = 450\times 7 = 3150$
ไม่แน่ใจว่าจะจำวิธีได้ถูกไหม เดี๋ยวคงมีคนมาช่วยดูให้

[กิตติ]

2.1มีกล้วย 6 ผล และส้ม 8 ผล จะให้ลิงตัวหนึ่งอย่างน้อย 1 ผลกระทำได้กี่วิธี

ถ้าเรามองให้ผลไม้ทั้งสองรวมกันเป็นหนึ่งกอง มี 14 ผล วิธีการหยิบผลไม้อย่างน้อยหนึ่งผลเท่ากับ
$\binom{14}{1} +\binom{14}{2}+...+\binom{14}{14} = 2^{14}-1 $

2.2 มีผลไม้ต่าง ๆ กัน8 ผลจะให้ลิงตัวหนึ่งอย่างน้อย 1 ผลกระทำได้กี่วิธี

เท่ากับ$\binom{8}{1}+\binom{8}{2} +...+\binom{8}{8} = 2^8-1 $

[RM@]

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

วิธีที่ทำแอบจำมาจากในกระทู้ของMC
แจกผลไม้ให้ลิงคนละ 1 ผลก่อน เลือกมาได้$\binom{7}{3} $แล้วแจกให้ทั้งสามตัวได้อีก $3!$ รวมเป็น$\frac{7!}{4!} $
จากนั้นให้วิธีแบบ$stars \quad and \quad Bars$ เหลือผลไม้อีก 4 ผลที่แตกต่างกัน
ได้ทั้งหมด$\binom{4+3-1}{3-1} =\binom{6}{2} $
รวมแจกได้$\frac{7!}{4!}\times \frac{6!}{2!4!} = 7\times 6 \times 5 \times 5\times 3 = 450\times 7 = 3150$
ไม่แน่ใจว่าจะจำวิธีได้ถูกไหม เดี๋ยวคงมีคนมาช่วยดูให้

แบบนี้ผลไม้จะแจกหมดเลยทั้ง 7 ลูกนะครับ

[กิตติ]

ใช่อย่างที่คุณRM@บอกครับ ถ้าอย่างนั้นก็แก้ใหม่เป็น
แจกหมดเลย แจกได้$ \binom{6}{2} $
เหลือ 1 ผล แจกได้$\binom{4}{3} \binom{5}{2} $
เหลือ 2 ผล แจกได้$\binom{4}{2} \binom{4}{2} $
เหลือ 3 ผล แจกได้$\binom{4}{1} \binom{3}{2} $
เหลือ 4 ผล แจกได้$1$
รวมแล้วจะแจกได้$ 15+40+36+12+1=104$

จำนวนวิธีทั้งหมดเท่ากับ $104\times 210= 21840$
น่าจะคิดแบบนี้หรือเปล่าครับ ช่วยดูหน่อยครับ

[Siren-Of-Step]

ข้อ 2.1 ในเฉลยบอกว่า 62 วิธีเองอะครับ

[{([Son'car])}]

ให้กล้วย$0,1,2,3,4,5,6$ผล$\;\;\;$รวม$7$วิธี
ให้ส้ม$0,1,2,3,4,5,6,7,8$ผล$\;\;\;$รวม$9$วิธี
จะได้วีธีให้ส้มและกล้วย$7x9$วีธี
แต่ต้องให้อย่างน้อย1ผลจึงต้องลบกรณีที่ให้กล้วย$0$ผลและส้ม$0$ผลไป$1$วีธี
ดังนั้นจำนวนวิธีทั้งหมด$=7x9-1=62$วีธีครับ

[กิตติ]

วิธีน้อง{([Son'car])}

กลับมานั่งทวนความหมายของ$\binom{n}{1} +\binom{n}{2}+...+\binom{n}{n} $
เป็นการจัดหมู่ด้วยการหยิบของทีละ $1,2,3,...,n$ ชิ้น โดยของแต่ละชิ้นเหมือนกัน
วิธีที่ผมทำโดยการเทของมารวมกัน คิดเป็นแบบของเหมือนกัน จึงไม่ถูกต้อง เพราะมีการนับซ้ำซ้อน จำนวนวิธีเลยมากกว่าเยอะ .โจทย์ถามว่า มีกล้วย 6 ผล และส้ม 8 ผล จะให้ลิงตัวหนึ่งอย่างน้อย 1 ผลกระทำได้กี่วิธี
น่าจะหมายความว่า เกิดผลลัพธ์กี่แบบ อย่างเช่น ส้ม 1ผลกับกล้วย 2ผล

[RM@]

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

ใช่อย่างที่คุณRM@บอกครับ ถ้าอย่างนั้นก็แก้ใหม่เป็น
แจกหมดเลย แจกได้$ \binom{6}{2} $
เหลือ 1 ผล แจกได้$\binom{4}{3} \binom{5}{2} $
เหลือ 2 ผล แจกได้$\binom{4}{2} \binom{4}{2} $
เหลือ 3 ผล แจกได้$\binom{4}{1} \binom{3}{2} $
เหลือ 4 ผล แจกได้$1$
รวมแล้วจะแจกได้$ 15+40+36+12+1=104$

จำนวนวิธีทั้งหมดเท่ากับ $104\times 210= 21840$
น่าจะคิดแบบนี้หรือเปล่าครับ ช่วยดูหน่อยครับ

ผมไม่เข้าใจที่คุณกิตติเขียนทั้งหมดนะครับ วิี๊ธีคิดผมว่ามันดูแปลก ๆ เริ่มตั้งแต่ตอนที่เอา stars and bars ซึ่งเป็นวิธีการแจกของที่เหมือนกันลงในกล่องที่ต่างกัน ไปใช้กับการแจกของในข้อนี้ ซึ่งเป็นการแจกของที่ต่างกันลงในกล่องที่ต่างกัน

ถ้าเป็นวิธีคิดของคุณกิตติ แจกทั้งหมด 7 ใบ จะได้ $\binom{6}{2}\times7\times6\times5 = 3150$ วิธี

แต่ถ้าคิดแบบตรงไปตรงมา คือแบ่งผลไม้เป็นกลุ่ม กลุ่มละ (1,1,5),(1,2,4),(1,3,3),(2,2,3) จะแบ่งได้

$\frac{7!}{1!1!5!2!} + \frac{7!}{1!2!4!} + \frac{7!}{1!3!3!2!} + \frac{7!}{2!2!3!2!} = 21 + 105 + 70 + 105 = 301$

จากนั้นในแต่ละกรณี แต่ละกลุ่มเลือกว่าจะให้ลิงตัวใด จะแจกได้ $3\times2\times1 = 6$ วิธี

ดังนั้น ถ้าแจกผลไม้หมดทั้ง 7 ลูก ให้ลิง 3 ตัว โดยที่ลิงแต่ละตัวได้ผลไม้อย่างน้อย 1 ผล จะทำได้ $301\times6 = 1806$ วิธี

ซึ่งเมื่อเปรียบเทียบกับการใช้ exponential generating function

$(x+\frac{x^2}{2!} + \frac{x^3}{3!} + ...)^3$

จะพบว่าสัมประิสิทธิ์ของ $\frac{x^7}{7!}$ ซึ่งจะแทนการแจกผลไม้ที่ต่างกัน 7 ผลให้ลิง 3 ตัว โดยที่แต่ละตัวได้อย่างน้อย 1 ผล จะเท่ากับ $\frac{43}{120}\times 7! = 43\times 42 = 1806$ ซึ่งให้ผลลัพธ์ตรงกับวิธีปกติ

[กิตติ]

คงเป็นเพราะผมเข้าใจวิธีการใช้star&Barไม่ถูกเองมากกว่าครับ ผมเข้าใจไปเองว่าน่าจะใช้กับกรณีที่แจกของต่างกันได้
อ่านที่คุณRM@อธิบายแล้วเข้าใจชัดแจ่มแจ้งครับ ขอบคุณครับที่ช่วยอธิบาย ผมจะได้เข้าใจถูก

[MiNd169]

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

คงเป็นเพราะผมเข้าใจวิธีการใช้star&Barไม่ถูกเองมากกว่าครับ ผมเข้าใจไปเองว่าน่าจะใช้กับกรณีที่แจกของต่างกันได้
อ่านที่คุณRM@อธิบายแล้วเข้าใจชัดแจ่มแจ้งครับ ขอบคุณครับที่ช่วยอธิบาย ผมจะได้เข้าใจถูก

star&Bar คืออะไรหรอครับ