ทฤษฎีที่แย้งกับ Stars&barsตอบ: 6, อ่าน: 5517
ผมเจอปัญหาที่ใช้ทฤษฏีที่ไ้ด้คำตอบต่างกับวิธี stars&bars ที่อจ นวยนำเสนอ ผมค้นเจอใน
teacher.snru.ac.th/pisit/admin/document/userfiles/115314121601_109.ppt
โจทย์ในแฟ้มนี้
มีกี่วิธีที่จะแจกหนังสือคณิตศาสตร์ที่เหมือนกัน 12 เล่ม แก่นักเรียน 4 คน คือ นิด หน่อย จ๋า อ๋อ
ซึ่งใช้วิธีคำนวณ จาก ทฤษฎีที่ 4.5.4 แก้ปัญหานี้ ซึ่งระบุว่า
ถ้า A เป็นเซตที่มี t สมาชิก จำนวนการเลือกสมาชิก k ตัว แบบไม่มีอันดับจาก A ยอมให้มีซ้ำจะเท่ากับ C(k+t–1 , k)
คำนวณโจทย์นี้ได้เท่ากับ C(12+ 4 –1,12) = C ( 15 , 12 ) = 455 วิธี
แต่ starts&bars จะได้ C(11,3)=11*10*9/6=165 วิํธี
กรุณาเช็คด้วยครับว่าเป็นคนละกรณีกันหรือเปล่า
boonchuay
ขออนุญาตเสนอความคิดเห็นนะครับ
ถ้าเราลองยุบโจทย์ลงมาเล็กๆ ให้หนังสือเหมือนกัน 3 เล่ม
จะแจกให้คน 2 คน โดยทั้งสองคนต้องได้หนังสืออย่างน้อย 1 เล่ม
ถ้าใช้ Stars & Bars จะได้ C(2, 1) = 2
ถ้าใช้ ทบ. 4.5.4 จะได้ C(3+2-1, 3) = 4
พิจารณาความจริง พบว่าแบ่งได้ 2 แบบ คือ
คนแรก 1 เล่ม คนหลัง 2 เล่ม กับ คนแรก 2 เล่ม คนหลัง 1 เล่ม
ดังนั้น โจทย์ในลักษณะนี้ ไม่น่าจะใช้ ทบ. 4.5.4 ได้ครับ
โดยส่วนตัวแล้ว การตีความโจทย์ว่าเป็นการแปะป้ายชื่อลงไป
อาจทำให้เกิดลำดับภายใต้สถานการณ์สมมุตินี้ครับ
นู้น
ขอบคุณน้องนู้น (คุณครูน้องแท้งค์) นะครับ มาช่วยตอบได้ไวมากๆ เลยครับ ^ ^
ผมอ่านทฤษฎีบทในครั้งแรกแล้วงงๆ ก็ได้การทดสอบของน้องนู้นนี่แหละครับที่มาช่วยนำทาง
ตอนนี้ค่อนข้างมั่นใจแล้วครับว่าหลักการคิดทั้งสองแบบนั้น ล้วนถูกต้องครับ
แต่ Stars & Bars จะนับเฉพาะวิธีที่ได้รับของอย่างน้อยคนละ 1 ชิ้น
ส่วนทฤษฎีบท 4.5.4 ในไฟล์ จะนับวิธีที่มีบางคนไม่ได้รับของด้วยครับ จึงได้มากขึ้น (ไม่ใช่เพราะลำดับนะครับ)
ซึ่งที่จริงการนับในกรณีนี้เราอาศัยเทคนิค Stars & Bars ดังตัวอย่าง 13.5 ข. ใน Math E-Book ก็เพียงพอครับ
เช่น ในการแจกหนังสือที่เหมือนกัน 12 เล่ม ให้กับนักเรียน 4 คน
1. ถ้าทุกคนจะต้องได้รับ สามารถเกิดขึ้นได้ C(11,3) แบบ (คิดด้วย Stars & Bars ตรงๆ)
2. ถ้ามีบางคนที่อาจไม่ได้รับ สามารถเกิดขึ้นได้ C(15,3) แบบ คิดโดยเทคนิคต่อไปนี้ครับ
มองเป็นการแถมหนังสือเพิ่มเข้าไปในกอง 4 เล่มก่อน (เท่าจำนวนคน) กลายเป็น 16 เล่ม
แล้วแบ่งแบบ Stars & Bars ตามปกติ ซึ่งทุกคนจะได้รับอย่างน้อย 1 เล่ม จึงคิดได้ C(15,3) แบบ
จากนั้นในทุกแบบที่เกิดขึ้น เราก็จะเอาหนังสือที่แถมนั้นกลับคืนมาคนละเล่มเสมอครับ
ทุกแบบที่นับได้นี้จึงกลายเป็นการแบ่ง 12 เล่ม ซึ่งอาจมีบางคนไม่ได้รับ ไปโดยอัตโนมัติครับ
ส่วนทฤษฎีบท 4.5.4 จะให้ผลแบบข้อ 2. โดยเฉพาะ.. ที่คิดได้ C(15,12) ก็เท่ากับ C(15,3) นั่นเองครับ
หมายเหตุ: ถ้าจะยึดทฤษฎีบท 4.5.4 เป็นหลัก การนับแบบข้อ 1. ก็คงต้องดัดแปลงเทคนิคนิดหน่อยครับ
โดยแจกหนังสือจากในกองให้ไปก่อนเลยคนละ 1 เล่ม แล้วแบ่งหนังสือที่เหลือกันโดยใช้ทฤษฎีบท
ซึ่งจะได้คำตอบเป็น C(11,8) หรือเท่ากับ C(11,3) นั่นเองครับ
นวย
ตรงนี้ขอยกโจทย์ย่อส่วนของน้องนู้นมาพูดคุยต่อนะครับ
หนังสือเหมือนกัน 3 เล่ม แจกให้คน 2 คน --> สมมติเป็นเซต {ก,ข} นะครับ
ถ้าใช้ Stars & Bars จะได้ C(2, 1) = 2 --> นั่นคือ {ก,ก,ข} และ {ก,ข,ข}
ถ้าใช้ ทบ. 4.5.4 จะได้ C(3+2-1, 3) = 4 --> นั่นคือ {ก,ก,ก} {ก,ก,ข} {ก,ข,ข} และ {ข,ข,ข}
จะเห็นได้ว่า "การเลือกสมาชิกออกมาจากเซตหนึ่ง แบบไม่มีอันดับ โดยยอมให้มีซ้ำ"
ดังที่กล่าวในทฤษฎีบทนั้น หมายรวมถึงกรณีที่ "สมาชิกซ้ำจนกระทั่งมีบางตัวไม่ถูกเลือก" ด้วยครับผม
นวย
ขอบคุณ คุณนู้น ครับ
และขอบคุณ อจ นวยมากครับ สละเวลาชี้ให้เห็นความเหมือนและความแตกต่าง ของการคิดทั้งสองแบบ นี่แสดงว่า star&bar ครอบคลุมปัญหาได้กว้างกว่า นำมาใช้กับกรณีเฉพาะได้มากกว่า
boonchuay
แอบมาแสดงว่าทั้งสองแนวคิดนี้ จะได้คำตอบเดียวกันครับ
กรณีทั่วไป แบบบางกลุ่มไม่มีก็ได้
Stars & Bars :
มีของ k ชิ้น เหมือนกัน แบ่งเป็น t กลุ่ม (บางกลุ่มไม่มีก็ได้) เท่ากับ
C(k + t - 1, t - 1)
ทบ. 4.5.4 :
A เป็นเซตที่มี t สมาชิก จำนวนการเลือกสมาชิก k ตัว
แบบไม่มีอันดับจาก A ยอมให้มีซ้ำจะเท่ากับ
C(k + t – 1, k)
จากสมบัติ
C(k + t - 1, t - 1) = C(k + t - 1, k + t - 1 - [t - 1]) = C(k + t – 1, k)
ดังนั้น ทั้งสองวิธีเท่ากันครับ
กรณีทั่วไป แบบทุกกลุ่มต้องมี
Stars & Bars :
มีของ k ชิ้น เหมือนกัน แบ่งเป็น t กลุ่ม (ทุกกลุ่มต้องมี) เท่ากับ
C(k - 1, t - 1)
ทบ. 4.5.4 :
แจกไปกลุ่มละ 1 ก่อน
A เป็นเซตที่มี t สมาชิก จำนวนการเลือกสมาชิก k - t ตัว
แบบไม่มีอันดับจาก A ยอมให้มีซ้ำจะเท่ากับ
C([k - t] + t – 1, k - t) = C(k - 1, k - t)
จากสมบัติ
C(k - 1, k - t) = C(k - 1, k - 1 - [k - t]) = C(k - 1, t - 1)
ดังนั้น ทั้งสองวิธีเท่ากันครับ
ป.ล.
- โดยความเห็นส่วนตัว Stars & Bars ให้ภาพที่ชัดเจนกว่า ทบ. 4.5.4 มากครับ
- ผมเสียเวลาหาที่กด Like อยู่พักใหญ่ครับ
นู้น
ขอบคุณน้องแท้งค์ที่ยืนยันให้เห็นชัดเจนยิ่งขึ้นคร้าบ
ป.ล. ติดมาจาก facebook เหมือนกันเลยครับ สงสัยต้องเอาปุ่ม like มาใส่ทุกคอมเม้นต์ซะแล้ว 😁
นวย