กระทู้ที่ 0428
เจอที่ผิดใน Math E-book Releas…
ตั้งกระทู้ใหม่

ทฤษฎีที่แย้งกับ Stars&barsตอบ: 6, อ่าน: 4320

ผมเจอปัญหาที่ใช้ทฤษฏีที่ไ้ด้คำตอบต่างกับวิธี 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 02/09/54 18:10 
ขออนุญาตเสนอความคิดเห็นนะครับ

ถ้าเราลองยุบโจทย์ลงมาเล็กๆ ให้หนังสือเหมือนกัน 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 ได้ครับ

โดยส่วนตัวแล้ว การตีความโจทย์ว่าเป็นการแปะป้ายชื่อลงไป
อาจทำให้เกิดลำดับภายใต้สถานการณ์สมมุตินี้ครับ
นู้น(30)  02/09/54 18:52  [ 1 ] 
ขอบคุณน้องนู้น (คุณครูน้องแท้งค์) นะครับ มาช่วยตอบได้ไวมากๆ เลยครับ ^ ^
ผมอ่านทฤษฎีบทในครั้งแรกแล้วงงๆ ก็ได้การทดสอบของน้องนู้นนี่แหละครับที่มาช่วยนำทาง

ตอนนี้ค่อนข้างมั่นใจแล้วครับว่าหลักการคิดทั้งสองแบบนั้น ล้วนถูกต้องครับ
แต่ 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) นั่นเองครับ
นวย 04/09/54 01:44  [ 2 ] 
ตรงนี้ขอยกโจทย์ย่อส่วนของน้องนู้นมาพูดคุยต่อนะครับ

หนังสือเหมือนกัน 3 เล่ม แจกให้คน 2 คน --> สมมติเป็นเซต {ก,ข} นะครับ
ถ้าใช้ Stars & Bars จะได้ C(2, 1) = 2 --> นั่นคือ {ก,ก,ข} และ {ก,ข,ข}
ถ้าใช้ ทบ. 4.5.4 จะได้ C(3+2-1, 3) = 4 --> นั่นคือ {ก,ก,ก}  {ก,ก,ข}  {ก,ข,ข} และ {ข,ข,ข}

จะเห็นได้ว่า "การเลือกสมาชิกออกมาจากเซตหนึ่ง แบบไม่มีอันดับ โดยยอมให้มีซ้ำ"
ดังที่กล่าวในทฤษฎีบทนั้น หมายรวมถึงกรณีที่ "สมาชิกซ้ำจนกระทั่งมีบางตัวไม่ถูกเลือก" ด้วยครับผม
นวย 04/09/54 01:50  [ 3 ] 

ข้อความนี้อาจมี html tag ที่ไม่อนุญาตให้แสดง
ขอบคุณ คุณนู้น ครับ
และขอบคุณ อจ นวยมากครับ สละเวลาชี้ให้เห็นความเหมือนและความแตกต่าง ของการคิดทั้งสองแบบ นี่แสดงว่า star&bar ครอบคลุมปัญหาได้กว้างกว่า นำมาใช้กับกรณีเฉพาะได้มากกว่า
boonchuay 05/09/54 08:34  [ 4 ] 
แอบมาแสดงว่าทั้งสองแนวคิดนี้ จะได้คำตอบเดียวกันครับ

กรณีทั่วไป แบบบางกลุ่มไม่มีก็ได้
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 อยู่พักใหญ่ครับ
นู้น(30)  05/09/54 19:52  [ 5 ] 
ขอบคุณน้องแท้งค์ที่ยืนยันให้เห็นชัดเจนยิ่งขึ้นคร้าบ

ป.ล. ติดมาจาก facebook เหมือนกันเลยครับ สงสัยต้องเอาปุ่ม like มาใส่ทุกคอมเม้นต์ซะแล้ว 😁
นวย 07/09/54 01:10  [ 6 ] 
วิธีพิมพ์สมการดูได้ที่กระทู้ 0072 ครับ      
อัปโหลดรูป/ไฟล์
ถ้าไม่มีรหัสส่วนตัว กรุณาใส่เลขหน้า "ความน่าจะเป็น" ใน Math E-Book .. หรือตั้งรหัสได้ ที่นี่

ทดลองพิมพ์สมการ