ดูหนึ่งข้อความ
  #2  
Old 25 กันยายน 2010, 17:22
Onasdi's Avatar
Onasdi Onasdi ไม่อยู่ในระบบ
กระบี่ประสานใจ
 
วันที่สมัครสมาชิก: 12 พฤษภาคม 2005
ข้อความ: 760
Onasdi is on a distinguished road
Default

ที่เอา 4! หาร ก็คือต้องการกำจัดตัวซ้ำใช่ไหมครับ
ถ้าดินสอที่เลือกมาเป็น a,b,c,d ก็จะนับซ้ำไป 4! ครั้ง (ใน $6\times6\times6\times6$) ถูกต้องครับ
แต่ถ้าดินสอที่เลือกมาคือ a,a,a,a เราจะไม่ได้นับซ้ำไปเลย
จะเห็นว่าแต่ละแบบเกิดซ้ำเป็นจำนวนครั้งไม่เท่ากันครับ จึงใช้วิธีนี้ไม่ได้

ข้อนี้ใช้เทคนิคที่ชื่อว่า stars and bars ครับ
เราแทนดินสอที่เราต้องการด้วยดาว 4 ดวง แล้วเอาดาว 4 ดวงนี้มาเรียงสับเปลี่ยนกับไม้ 5 แท่ง (5 มาจาก 6-1)
ถ้าเรามองแต่ไม้ 5 แท่ง จะเกิดช่องว่างระหว่างไม้ขึ้น 6 ช่อง ให้แต่ละช่องแทนดินสอแต่ละแบบ และจำนวนดาวในช่องนั้นๆ แทนจำนวนดินสอแบบนั้นที่เราจะซื้อ

ตัวอย่างเช่น
★|★★||★|||
แทนการซื้อดินสอแบบแรก 1 แท่ง แบบที่สอง 2 แท่ง แบบที่สาม 0 แท่ง แบบที่สี่ 1 แท่ง แบบที่ห้า 0 แท่ง และแบบที่หก 0 แท่ง

ลองสังเกตดูจะพบว่า การเรียงสับเปลี่ยนของดาวกับไม้วิธีนึง จะแทน การเลือกซื้อดินสอวิธีนึง พอดี

25 กันยายน 2010 17:22 : ข้อความนี้ถูกแก้ไขแล้ว 1 ครั้ง, ครั้งล่าสุดโดยคุณ Onasdi
ตอบพร้อมอ้างอิงข้อความนี้