WIMO Combinatorics ป.4

[Hutchjang]

รบกวนสอบถามแนวคิดข้อนี้ครับ ที่เฉลยเขาคิดยังไงครับ ไม่เข้าใจแนวคิดในเฉลยครับ

[gon]

คนเขียนเฉลยกับคำถาม น่าจะคุยกันคนละเรื่องครับ

เพราะแค่แบ่งเป็น 2 กลุ่มก็มากกว่า 11 แบบแล้ว

10+1220
11+1219
12+1218
...
615+615

[Hutchjang]

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

คนเขียนเฉลยกับคำถาม น่าจะคุยกันคนละเรื่องครับ

เพราะแค่แบ่งเป็น 2 กลุ่มก็มากกว่า 11 แบบแล้ว

10+1220
11+1219
12+1218
...
615+615

ใช่ครับผม ผมก็คิดว่าอย่างนั้น มันต้องแยกกรณีเป็นตั้งแต่ 2 กลุ่ม ไปจนถึง 123 กลุ่มหรือเปล่าครับ แต่ว่าในแต่ละกรณีของการแบ่งกลุ่ม เราจะมีวิธีการนับอย่างไรครับ อย่างเช่นว่าเราแบ่งเป็น 10 กลุ่ม จะมีทั้งหมดกี่วิธีที่สามารถแบ่งเป็น 10 กลุ่มได้ครับ

[gon]

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

ใช่ครับผม ผมก็คิดว่าอย่างนั้น มันต้องแยกกรณีเป็นตั้งแต่ 2 กลุ่ม ไปจนถึง 123 กลุ่มหรือเปล่าครับ แต่ว่าในแต่ละกรณีของการแบ่งกลุ่ม เราจะมีวิธีการนับอย่างไรครับ อย่างเช่นว่าเราแบ่งเป็น 10 กลุ่ม จะมีทั้งหมดกี่วิธีที่สามารถแบ่งเป็น 10 กลุ่มได้ครับ

นี่เป็นคำถามที่เหนื่อยครับ เช่น ถ้าเราต้องการ 2 กลุ่ม

โดยที่ถ้าคิดว่าลำดับก่อนหลังเป็นคนละวิธีกัน เช่น 10 + 1220 กับ 1220 + 10 เป็น 2 วิธี เป็นต้น

เราสามารถใช้ gernerating function (gf)

$(x^{10}+x^{11}+x^{12}+...)(x^{10}+x^{11}+x^{12}+...) = x^{20}\sum_{r=0}^{\infty}(r+1)x^r$

แล้วคำนวณหาสัมประสิทธิ์ของ $x^{1230}$ ซึ่งจะได้ออกมาเป็น 1211

(แทนจำนวนผลเฉลยที่เป็นจำนวนเต็มบวกของ $a+b = 1230, a,b \ge 10$)

แต่จริง ๆ ปัญหาข้อนี้ที่โจทย์ถาม ถ้าต้องการ 2 กลุ่ม เราต้องตอบ 606 เพราะ การใช้ gf ข้อนี้จะหมายถึง

10+1220
11+1219
...
615+615
มี 606 วิธี

กับ
1220+10
1219+11
...
616+614
อีก 605 วิธี

แต่ถ้าเราไม่จำกัดว่าต้องมีกี่กลุ่ม เราสามารถใช้ gf ได้ทันที

แต่การคำนวณด้วยมือทำได้ยาก เพราะต้องหาสัมประสิทธิ์ของ $x^{1230}$ จากการกระจาย

$(1+x^{10}+x^{20}+...)(1+x^{11}+x^{22}+...)(1+x^{12}+x^{24}+...)...(1+x^{1230}+x^{2460}+...)$

ลองคำนวณหาหาสัมประสิทธิ์ดูครับ ถ้าไม่รวม 1 กลุ่ม พอทำเสร็จแล้ว ลบ 1 (หัก 1230 = 1230) จะคือคำตอบของข้อนี้นั่นเอง

ถ้าสนใจก็อ่านเรื่อง partitions of integers ครับ

[Uncle Laem]

ถ้าเป็นการแบ่งเป็นกลุ่มละเท่าๆกัน น่าจะได้คำตอบตรงกับที่เฉลย?

[Hutchjang]

ขอบพระคุณคุณอา gon และ Uncle Laem มากๆนะครับ