โจทย์คอมบิ แบ่งของ 200 ชิ้น

[Delta Strike]

ถ้ามีของ 200 ชิ้น แบ่งให้เด็ก 80 คน คนละไม่เกิน5ชิ้น จะได้ทั้งหมดกี่วิธี

[polsk133]

ของเหมือนหรือต่างกันครับ

ถ้าเหมือน คิดว่าคงใช้ ฟังก์ชันก่อกำเนิด

[Delta Strike]

ของเหมือนกันครับ

[Thgx0312555]

มีวิธีง่ายๆ 2 วิธี
1. ใช้กฏการบวกเข้า และลบออก
2. ฟังก์ชันก่อกำเนิด

[Delta Strike]

ขอคำชี้แนะด้วยครับ

[กิตติ]

ทำแบบนี้ได้ไหม....คิดว่าทุกคนได้แจกอย่างน้อย 1 ชิ้น แจกของให้ทุกคนคนละ 1 ชิ้น เหลืออีก 120 ชิ้นมาแจกแบบมีคนได้บ้างไม่ได้บ้าง
$x_1+x_2+x_3+...+x_{80}=120$
แปลงให้ $x_i=5-y_i$ โดยที่ $0\leqslant y_i \leqslant 5$จะได้ว่า
$400-\left\{\,y_1+y_2+y_3+...+y_{80}\right\} =120$
$y_1+y_2+y_3+...+y_{80}=280$
จะได้ว่ามีจำนวนวิธีเท่ากับ $\binom{280+80-1}{80-1}=\binom{359}{79} $

แต่ถ้าตีความโจทย์ว่า มีบ้างบางคนไม่ได้รับ จะแปลงเป็น
$x_1+x_2+x_3+...+x_{80}=200$
แปลงให้ $x_i=5-y_i$ โดยที่ $0\leqslant y_i \leqslant 5$จะได้ว่า
$400-\left\{\,y_1+y_2+y_3+...+y_{80}\right\} =200$
$y_1+y_2+y_3+...+y_{80}=200$
จะได้ว่ามีจำนวนวิธีเท่ากับ $\binom{200+80-1}{80-1}=\binom{279}{79} $

[gon]

ของคุณกิตติใช้เงื่อนไขไม่ถูกนะครับ.

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

ซึ่งในที่นี้ตามโจทย์บอกว่า $0\le x_i \le 5$ แล้วเราจะแปลความไปว่า $x_i \ge 0$ แล้วใช้สูตรนี้ $\binom{n+r-1}{r-1}$ ก็จะไม่ถูกต้องครับ เพราะตามสูตรนี้ $\binom{n+r-1}{r-1}$ ค่าของ $x_i$ อาจจะเป็น 6, 7, 8 , ... , 80 ก็ได้ มันไม่ได้ถูกจำกัด

ซึ่งตามโจทย์บอกมาว่า ได้คนละไม่เกิน 5 ชิ้น แสดงว่า $0\le x_i \le 5$ แล้วใช้การแปลงว่า $y_i = 5-x_i$ อันนี้ ไม่มีประโยชน์อะไรครับ เพราะจะได้ตัวแปลงแบบเดิมคือ $0\le y_i \le 5$ ซึ่งก็ไม่สามารถใช้สูตร $\binom{n+r-1}{r-1}$ ได้ เพราะตามสูตรนี้ ค่าของ $y_i$ อาจจะเป็น 6, 7, 8, ... , 80 ได้

คำตอบที่ได้ $\binom{279}{79}$ นั้น จะสมมูลกับปัญหานี้ครับ.
"มีของเหมือนกัน 200 ชิ้น ต้องการแจกให้เด็ก 80 คน โดยไม่มีเงื่อนไขใด ๆ"

สำหรับคำตอบข้อนี้นั้น เท่าที่ผมลองเขียนดูคร่าว ๆ น่าเกลียดมากครับ เพราะตอบติดอนุกรมบวกลบสลับกัน 34 พจน์ ซึ่งผมคิดว่าไม่น่าจะมีวิธีลดรูปให้อยู่ในรูปอย่างง่ายได้ ข้อนี้ควรจะใช้คอมพิวเตอร์คำนวณอนุกรมตอนท้ายจะง่ายกว่าครับ

[กิตติ]

ขอบคุณครับคุณgonช่วยให้ผมเข้าใจการใช้สูตรการแจกของ เดี๋ยวคงต้องกลับไปทำความเข้าใจใหม่อีกทีครับ

[แม่ให้บุญมา]

ฟังก์ชันก่อกำเนิด $f(x)=(1+x+x^2+x^3+x^4+x^5)^{80}$
ใช้คอมพิวเตอร์คำนวณได้ $4.657570399133847e+60x^{200} $
$4.657570399133847e+60$ เป็นคำตอบมันมหาศาลอะไรขนาดนี้เลยหรือครับ

[kongp]

คิดผิดไงครับ อยากให้ ดร. ไพศาล นาคมหาชลาสินธิ์ ท่านมาช่วยตอบ ถ้าท่านไม่ได้ทำวิจัยด้านอื่น วิธีในการทำความเข้าใจหรือโมเดลท่าน Advance มากๆ ทุกคนคงเชื่อถือ มากกว่าคำตอบที่ผมตอบ

เป็นสมัยก่อนท่านคงสร้างสูตร คำนวนแป๊บเดียวออกสำหรับข้อนี้

แต่ทางผมอยากใช้หลักจากศึกษาวิชาตรรกศาสตร์ทางคอมพิวเตอร์ก็พบว่ามีเรื่องการนับอยู่ ซึ่งผมสนใจจะทำมาสร้างสูตรคำนวนร่วมกับวิธีทางเรขาคณิต เพราะอาจจะเป็นลู่ทางอื่นต่อไป แต่ยังไม่ขนาดใช้คอมพิวเตอร์ช่วยคำนวน นั่นอาจจะสำหรับเด็กโอลิมปิค หรือ ป.โท ของสถาบันบางแห่งในไทย ย้อนหาเบสิกครับ ก็การที่เราจะไปทำอะไรที่มันใหญ่โต ก็ต้องอาศัยเครือข่ายทางสังคม ไม่ทำก็ดีไปอย่าง

คนที่ทำก็มีที่ไปรอด กับ ไปไม่รอด สุ่มเสี่ยง บางท่านก็ว่าให้เปลี่ยนไปนับถือศาสนาคริสต์ ผมไม่ยักรู้ว่าเกี่ยวกับวงการวิชาการขนาดนี้ การเป็นอาจารย์ผมคิดว่าการปลูกฝังความเข้าใจสำคํญไม่น้อยกว่าความรู้ ถึงแม้ผู้เรียนบางคนจะปฏิเสธหรือไม่ยอมเชื่ออะไรง่ายๆ เพราะคิดแบบนักวิทยาศาสตร์ เชื่อเพราะอะไร "เพราะคิดว่าเป็นสิ่งที่ดี" ซึ่งความดีงามในโลกจริงๆ โดยสามัญแล้วมีองค์ประกอบอุดมคติ เช่น ความบริบูรณ์ ความเป็นนิรันดร์ ความละเอียด ความฝัน ความสูงส่ง ความผิดเพี้ยน ความลงตัว เป็นต้น


* จะเสี่ยงดวงก็ไม่สมกับที่เรียนมหาลัยมา เหมือนต้องคำนวนสองเรื่องขึ้นไปเสมอ

[gnap]

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

มีวิธีง่ายๆ 2 วิธี
1. ใช้กฏการบวกเข้า และลบออก
2. ฟังก์ชันก่อกำเนิด

ช่วยอธิบายฟังก์ชันก่อกำเนิดหน่อยครับ

[Keehlzver]

จากโจทย์ก็ได้ว่า $f(x)=(1+x^2+x^3+...+x^{5})^{80}$ จากความรู้เรื่องฟังก์ชันก่อกำเนิด
จะได้ว่า $f(x)=(x^{6}-1)(1-x)^{-80}=\sum_{s = 0}^{80}(-1)^s \binom{80}{s}x^{480-6s} \sum_{r=0}^{\infty}\binom{79+r}{r}x^r$

จำนวนวิธีของโจทย์ตรงกับสัมประสิทธิ์หน้าพจน์ $x^{200}$
เพราะฉะนั้นต้องดูผลรวมของสัมประสิทธิ์ของ $x^{480-6s+r}$
โดยที่ $0 \leq s \leq 80$ และ $r \geq 0$ เมื่อ $r,s$ เป็นจำนวนเต็มไม่ติดลบ
แก้สมการและหาขอบเขตของ $s,r$
ก็จะได้ว่า $(s,r)=(47,2),(48,8),(49,14),...,(80,200)$

เพราะฉะนั้นคำตอบของข้อนี้คือ $\sum (-1)^s\binom{80}{s} \binom{79+r}{r}$ เมื่อ $(s,r)=(47,2),(48,8),(49,14),...,(80,200)$ ตอบแค่นี้
ได้ตรงกับพี่ gon ที่บอกว่าเป็นอนุกรมบวกลบสลับกัน 34 พจน์

[แม่ให้บุญมา]

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

จากโจทย์ก็ได้ว่า $f(x)=(1+x^2+x^3+...+x^{5})^{80}$ จากความรู้เรื่องฟังก์ชันก่อกำเนิด
จะได้ว่า $f(x)=(x^{6}-1)(1-x)^{-80}=\sum_{s = 0}^{80}(-1)^s \binom{80}{s}x^{480-6s} \sum_{r=0}^{\infty}\binom{79+r}{r}x^r$

จำนวนวิธีของโจทย์ตรงกับสัมประสิทธิ์หน้าพจน์ $x^{200}$
เพราะฉะนั้นต้องดูผลรวมของสัมประสิทธิ์ของ $x^{480-6s+r}$
โดยที่ $0 \leq s \leq 80$ และ $r \geq 0$ เมื่อ $r,s$ เป็นจำนวนเต็มไม่ติดลบ
แก้สมการและหาขอบเขตของ $s,r$
ก็จะได้ว่า $(s,r)=(47,2),(48,8),(49,14),...,(80,200)$

เพราะฉะนั้นคำตอบของข้อนี้คือ $\sum (-1)^s\binom{80}{s} \binom{79+r}{r}$ เมื่อ $(s,r)=(47,2),(48,8),(49,14),...,(80,200)$ ตอบแค่นี้
ได้ตรงกับพี่ gon ที่บอกว่าเป็นอนุกรมบวกลบสลับกัน 34 พจน์

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