ช่องนกพิราบ กับ combination ครับผม

[Thgx0312555]

ข้อสองตอบ 55 ครับ ลืมกรณีเช่น ถ้า อีกสองชิ้นมันเหมือนกันล่ะ ??

ถ้าใช้วิธีนี้ก็ควรจะบวกกรณีเพิ่ม ถ้าสองชิ้นเหมือนกันอีก 10 วิธี

แต่มีอีกวิธีหนึ่งที่เก็บได้ทั้งข้อ 2,3 เลยครับ

http://en.wikipedia.org/wiki/Stars_a...probability%29

[polsk133]

เขียนเพิ่มให้ละครับข้อ2

[gon]

ทฤษฎีบท 1. ถ้า $x_1+x_2+x_3+...+x_r = n$ โดยที่ $x_i \ge 0$ แล้ว จำนวนผลเฉลยทั้งหมดจะเท่ากับ $\binom{n+r-1}{r-1}$

ทฤษฎีบท 2. ถ้า $x_1+x_2+x_3+...+x_r = n$ โดยที่ $x_i \ge 1$ แล้ว จำนวนผลเฉลยทั้งหมดจะเท่ากับ $\binom{n-1}{r-1}$

ข้อ 2. มีโดนัทชนิดต่าง ๆ อยู่ 10 ชนิด จงหาจำนวนวิธีทั้งหมดของการสั่งซื้อโดนัท 12 ชิ้น

โดยมีโดนัทแต่ละชนิดอย่างน้อย 1 ชิ้น

จะเข้าทฤษฎีบท 2. พอดี ซึ่งมีจำนวนคำตอบเท่ากับ $$\binom{12-1}{10-1} = \binom{11}{9} = \binom{11}{2} = \frac{11\times 10}{2!} = 55$$

ข้อ 3. กำหนดให้ $x_1, x_2, x_3, x_4$ เป็นจำนวนเต็มที่ไม่ลบโดยที่ $0 \le x_1 \le 3$
จงหาจำนวนคำตอบของสมการ $x_1 + x_2 + x_3 + x_4 = 15$

วิธีที่ 1. ใช้หลักการนำเข้าและตัดออก (principle of inclusion and exclusion)

สมมติให้ $|A|$ แทน จำนวนคำตอบของสมการ $x_1 + x_2 + x_3 + x_4 = 15$ โดยที่ $x_1, x_2, x_3, x_4 \ge 0$

โดยทฤษฎีบท 1. จะได้ว่้า $$|A| = \binom{15+4-1}{4-1} = \binom{18}{3}$$

สมมติให้ $|B|$ แทน จำนวนคำตอบของสมการ $x_1 + x_2 + x_3 + x_4 = 15$ โดยที่ $x_1 \ge4, ~ x_2, x_3, x_4 \ge 0$

จากนั้นสมมติให้ $y_1 = x_1 - 4$ แล้วจะได้ว่า $y_1 \ge 0$

ดังนั้นสมการด้านบนจะเปลี่ยนเป็น $y_1 + x_2 + x_3 + x_4 = 11$ โดยที่ $y_1, x_2, x_3, x_4 \ge 0$

โดยทฤษฎีบท 1. จะได้ $$|B| = \binom{11+4-1}{4-1} = \binom{14}{3}$$

ดังนั้นจำนวนคำตอบของสมการ $x_1+x_2+x_3+x_4 = 15$ โดยที่ $0 \le x_1 \le 3, x_2, x_3, x_4 \ge 0$ จะมีค่าเท่ากับ $$|A|-|B| = \binom{18}{3} - \binom{14}{3}$$

วิธีที่ 2. ใช้ ordinary generating function

ปัญหา จำนวนคำตอบของสมการ $x_1+x_2+x_3+x_4 = 15$ โดยที่ $0 \le x_1 \le 3, x_2, x_3, x_4 \ge 0$ จะแทนด้วยฟังก์ชันก่อกำเนิดสามัญ ดังนี้คือ $$(1+x+x^2+x^3)(1+x+x^2+...)^3 = (1+x+x^2+x^3)\cdot \frac{1-x}{1-x}\cdot (\frac{1}{1-x})^3 = (1-x^4)(1-x)^{-4}$$

และเนื่องจาก $$(1-x)^{-n} = \sum_{r=0}^{\infty}\binom{n+r-1}{r}x^r$$ ดังนั้น $$(1-x^4)(1-x)^{-4} = (1-x^4)\sum_{r=0}^{\infty}\binom{r+3}{r}x^r = (1-x^4)\sum_{r=0}^{\infty}\binom{r+3}{3}x^r = \sum_{r=0}^{\infty}\binom{r+3}{3}x^r - \sum_{r=0}^{\infty}\binom{r+3}{3}x^{r+4}$$

ดังนั้นสัมประสิทธิ์ของ $x^{15}$ จะได้จากการแทน $r= 15$ ลงในพจน์หน้า และแทน $r=11$ ลงในพจน์หลัง ก็จะได้ $\binom{18}{3} - \binom{14}{3}$

[kongp]

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

วิชานี้ยากตรงมองงานกับเอาทบ.ปรับยังไงให้เข้ากับโจทย์ บางทีอ่าน/เรียนทบ.บทสูงๆ ก็โผล่ไปอีกเรื่อง ส่วนมากจะรู้ก็หลายปีผ่าน

[ผู้โง่เขลา]

ขอบคุณทุกคนมากครับผม

[ผู้โง่เขลา]

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

จะเข้าทฤษฎีบท 2. พอดี ซึ่งมีจำนวนคำตอบเท่ากับ $$\binom{12-1}{10-1} = \binom{11}{9} = \binom{11}{2} = \frac{11\times 10}{2!} = 55$$



วิธีที่ 1. ใช้หลักการนำเข้าและตัดออก (principle of inclusion and exclusion)

สมมติให้ $|A|$ แทน จำนวนคำตอบของสมการ $x_1 + x_2 + x_3 + x_4 = 15$ โดยที่ $x_1, x_2, x_3, x_4 \ge 0$

โดยทฤษฎีบท 1. จะได้ว่้า $$|A| = \binom{15+4-1}{4-1} = \binom{18}{3}$$

สมมติให้ $|B|$ แทน จำนวนคำตอบของสมการ $x_1 + x_2 + x_3 + x_4 = 15$ โดยที่ $x_1 \ge4, ~ x_2, x_3, x_4 \ge 0$

จากนั้นสมมติให้ $y_1 = x_1 - 4$ แล้วจะได้ว่า $y_1 \ge 0$

ดังนั้นสมการด้านบนจะเปลี่ยนเป็น $y_1 + x_2 + x_3 + x_4 = 11$ โดยที่ $y_1, x_2, x_3, x_4 \ge 0$

โดยทฤษฎีบท 1. จะได้ $$|B| = \binom{11+4-1}{4-1} = \binom{14}{3}$$

ดังนั้นจำนวนคำตอบของสมการ $x_1+x_2+x_3+x_4 = 15$ โดยที่ $0 \le x_1 \le 3, x_2, x_3, x_4 \ge 0$ จะมีค่าเท่ากับ $$|A|-|B| = \binom{18}{3} - \binom{14}{3}$$

วิธีที่ 2. ใช้ ordinary generating function

ปัญหา จำนวนคำตอบของสมการ $x_1+x_2+x_3+x_4 = 15$ โดยที่ $0 \le x_1 \le 3, x_2, x_3, x_4 \ge 0$ จะแทนด้วยฟังก์ชันก่อกำเนิดสามัญ ดังนี้คือ $$(1+x+x^2+x^3)(1+x+x^2+...)^3 = (1+x+x^2+x^3)\cdot \frac{1-x}{1-x}\cdot (\frac{1}{1-x})^3 = (1-x^4)(1-x)^{-4}$$

และเนื่องจาก $$(1-x)^{-n} = \sum_{r=0}^{\infty}\binom{n+r-1}{r}x^r$$ ดังนั้น $$(1-x^4)(1-x)^{-4} = (1-x^4)\sum_{r=0}^{\infty}\binom{r+3}{r}x^r = (1-x^4)\sum_{r=0}^{\infty}\binom{r+3}{3}x^r = \sum_{r=0}^{\infty}\binom{r+3}{3}x^r - \sum_{r=0}^{\infty}\binom{r+3}{3}x^{r+4}$$

ดังนั้นสัมประสิทธิ์ของ $x^{15}$ จะได้จากการแทน $r= 15$ ลงในพจน์หน้า และแทน $r=11$ ลงในพจน์หลัง ก็จะได้ $\binom{18}{3} - \binom{14}{3}$

ทำไมต้องให้ $x\geqslant 4$ครับผม??

[polsk133]

เป็นหลักในการใช้ เพิ่มเข้าตัดออก คือคล้ายๆกับวงกลมออยเลอหน่ะครับ เอา U - A' ก็ได้ A ประมาณนี้ครับ

[kongp]

ลองคิดเองก็ดี นับแบบวงกลม โดยมีตรรกศาสตร์ร่วมด้วย ทำให้แปลความหมายโจทย์ง่าย และใช้ในสังคมได้หลากหลายมากขึ้น เห็นอ.Ross honsenberger แห่งสมาคมคณิตศาสตร์อเมริกา ใช้นับขบคิดบอร์ดเกมส์สอนเด็ก ผมเจอในหนังสือหลายๆ เล่มของ MAA

มือสมัครเล่น เช่น นักเรียนเวลาเจอปัญหาก็หลบเลี่ยง ไปเที่ยวซะบ้าง อุปสรรค์บางทีเวลาหลายๆ ปีก็แก้ไขไม่ได้ เช่น เจอเรื่องลิขสิทธิ์ (privilage) etc. บางคนว่าหากเป็นมืออาชีพทางคณิตศาสตร์จะไปได้ไกลกว่าในการทำโจทย์ยากๆ (แต่ก็ไม่ใช่ง่ายๆ ดั่งฝัน)

[kongp]

มีคนถามว่าใช้หนังสือเล่มไหนกัน บางทีก็ตอบยากเช่นผมอ่านตำราหลายเล่ม เพราะไม่เคยเรียนเหมือนในคณะภาควิชา IT เนื่องจากจบวิศวกรรมอิเล็กทรอนิกส์ ซึ่งมี Methology ต่างกัน จะว่าตามหัวข้องานวิจัยได้ บางคนไม่เข้าใจจับหัวข้อเดียวก็ว่าน้อยไป จับหัวข้อเยอะๆ ก็ว่ากว้างไป

หากได้ค้นเปเปอร์ทางวิศวกรรม จะเหมือนเปิดเฉลยว่าวิธีนั้นดีกว่าวิธีนี้ยังไง ซะโดนปิด จนผมเองก็งงเหมือนเค้าเพิ่งมาทำตอนผมเรียน สนใจดนตรีด้วยกะจะเอามาใช้กับเรื่อง AI ก็ไม่ได้ทำ ทิ้งไปซะงั้น โดนแฮกค์เครื่องเป็นว่าเล่นสมัยเรียนที่ลาดกระบัง ผมเจอของแท้เจาะเครื่องจนเอียน ไม่อยากกันอะไรเท่าไหร่ ไม่ใช่หัวข้อเราเรื่อง Computer Security

กะว่าจะสร้างทบ. เองตอนอายุ 17-18 ปี ตอนนั้นทำโมเดลรูบิค ต่อมาเปลี่ยนไปเรียนวิศวกรรมจำเยอะมากกว่าคิดเองยอมรับเลย เจอตำราหินโคตร กลับมาฟื้นตอนเรียนโทลาดกระบังเพราะเดินดูร้านค้าหนังสือเห็นหนังสือวางขายปกสีสวยเด่นมาก เจอเพื่อน กทม. แกะ windows XP เลยมีไฟขึ้นมาบ้าง เค้าใช้พวก Computational theory นี่ก็คล้ายๆ กัน พื้นฐานพวกเทคโนโลยีสายลับ ประมาณนั้น

[ผู้โง่เขลา]

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

เป็นหลักในการใช้ เพิ่มเข้าตัดออก คือคล้ายๆกับวงกลมออยเลอหน่ะครับ เอา U - A' ก็ได้ A ประมาณนี้ครับ

อ่อขอบคุณมากครับ