Binomial Expansion

[modulo]

เผอิญผมได้มีโอกาสเรียนคณิตศาสตร์ โครงการ Gifted คณิตศาสตร์ของภาคเหนืออะครับ (ที่ภาควิชาคณิต ม.ช.) ซึ่งได้เรียนเรื่อง ทฤษฎีบททวินาม

ก็เรียนไปเรื่อย ๆ จนมาถึงสูตรนี้
ⁿ C_r + ⁿC_r+1 = ⁿ⁺¹C_r+1

อ.ที่สอนไม่ให้ใช้การพิสูจน์แบบกระจาย factorial ซึ่งมันจะพิสูจน์ได้ โดยใช้ pascal และอีกวิธีหนึ่ง...

สมมติให้มีของอยู่ n + 1 ชิ้น

OOOO....OO
|- n ชิ้น--| 1 ชิ้น
ต่อมา เราไม่เอา 1 ชิ้นนั้น ก็จะเหลือ n ชิ้น
จาก n ชิ้น เลือกมา r ชิ้น

ต่อมา อ.ก็บอกอะไรสักอย่าง สรุปได้เป็น ⁿC_r+1 และก็ สุดท้ายก็บอกว่าเอามารวมกันแล้วจะได้ ⁿ⁺¹C_r+1

ตอนนั้นผมงง ตั้งแต่ตอนที่สอง ที่ว่า ⁿC_r+1 อะครับ งงมากก...

ถ้าใครพอมีความรู้ รบกวนช่วยอธิบายหน่อยนะครับ

[passer-by]

ขออธิบาย ตั้งแต่เริ่มต้นเลยนะครับ

สมมติมีของ n+1 ชิ้น ต้องการเลือกออกมา r+1 ชิ้น (เท่ากับว่าได้\(\large{n+1 \choose r+1} \) วิธี)

ให้ x เป็นของชิ้นหนึ่งในบรรดาของ n+1 ชิ้น

แน่นอนว่า x อาจถูกเลือกอยู่ใน r+1 ชิ้นหรือไม่ถูกเลือกก็ได้

กรณีที่ 1: ถ้า x รวมอยู่ใน r+1 ชิ้น แสดงว่า เราจะเลือกของเพียง r ชิ้น(เพราะ x เลือกไปแล้ว) จากของ n ชิ้น นั่นคือได้\(\large{n \choose r} \) วิธี

กรณีที่ 2: ถ้า x ไม่รวมอยู่ใน r+1 ชิ้น แสดงว่า เรายังต้องเลือกของ r+1 ชิ้น จากของแค่ n ชิ้น(ไม่คิด x) นั่นคือได้\(\large{n \choose r+1} \) วิธี

ดังนั้น \(\large{n+1 \choose r+1}={n \choose r}+{n \choose r+1} \)

ซึ่งสูตรนี้ สามารถนำมาช่วยพิสูจน์ เอกลักษณ์ ข้างล่างนี้ได้ด้วย

\(\large {r \choose r}+{r+1 \choose r}+{r+2 \choose r}+...+{n \choose r}={n+1 \choose r+1} \)

(อันนี้ให้เป็นของแถมแล้วกันนะครับ )

[TOP]

ที่อาจารย์สอนมาเป็นการมองตามความหมายของการจัดกลุ่ม มากกว่าจะมองที่ตัวเลขเพียงอย่างเดียวครับ

นอกจากจะมองแบบที่น้อง passer-by บอกมาแล้ว เราอาจมองแบบความสัมพันธ์เวียนบังเกิด คือ หากเราต้องหา \({n+1 \choose r+1}\) จาก \({n \choose r}\) ที่ทราบค่าอยู่ก่อนแล้ว จะต้องทำอย่างไรบ้างจึงจะไม่เปลืองแรง

จากกลุ่มสิ่งของ \(r\) ชิ้น ที่ถูกเลือกมาจากของทั้งหมด \(n\) ชิ้น ที่เราเคยจัดไว้แล้ว เพียงเรานำของชิ้นใหม่ \(1\) ชิ้นที่เพิ่มเข้ามา ไปรวมกับกลุ่มสิ่งของนี้ ก็จะได้การจัดกลุ่มสิ่งของ \(r+1\) ชิ้น ที่เลือกมาจากสิ่งของ \(n+1\) ชิ้น ที่มีสิ่งของชิ้นใหม่ \(1\) ชิ้นเพิ่มเข้ามาด้วย จะได้จำนวนวิธีเป็น \({n \choose r}\) วิธี คงเดิม

เหลือเพียงการจัดกลุ่มสิ่งของที่ไม่รวมของชิ้นใหม่ \(1\) ชิ้นนั้น ทำได้โดยเลือกสิ่งของจำนวน \(r+1\) ชิ้น จากสิ่งของเดิมทั้งหมด \(n\) ชิ้น ได้จำนวนวิธีทั้งสิ้น \({n \choose r+1}\) วิธี

ดังนั้นจำนวนวิธีจัดกลุ่มทั้งหมดจึงเป็น \(\displaystyle{{n \choose r} + {n \choose r+1} = {n+1 \choose r+1}}\)


การมองความหมายของสูตรมากกว่าตัวเลขเพียงอย่างเดียว จะได้อะไรสนุกๆมากขึ้นเยอะเลยครับ อย่างเช่น Fermat's Little Theorem ที่บอกว่า

ถ้า \(a\) เป็นจำนวนนับและ \(p\) เป็นจำนวนเฉพาะ แล้วจะได้ว่า \(a^p \equiv a \bmod p\) (หรือ \(p \mid a^p - a\) นั่นเอง)

ก็มีคนมองว่า เราสามารถพิสูจน์ทฤษฎีนี้โดยใช้ความรู้เรื่องการจัดกลุ่มได้เช่นกัน

พิสูจน์

สมมติว่าเรามีลูกปัด \(a\) สีเป็นจำนวนมาก เราต้องการนำลูกปัดเหล่านี้มาร้อยเป็นสร้อยคอ โดยที่สร้อยคอแต่ละเส้น ประกอบด้วยลูกปัดจำนวน \(p\) ลูก

เริ่มต้นจากจากนำลูกปัดมาร้อยในด้ายเส้นหนึ่ง(ยังไม่ต่อปลายด้ายเข้าด้วยกัน) เราจะได้รูปแบบสีของลูกปัดบนด้ายแต่ละเส้นจำนวน \(a^p\) รูปแบบ

หากเราคัดด้ายเส้นที่ประกอบด้วยลูกปัดสีเดียวกันทั้งหมดทิ้งไป (มีอยู่ \(a\) รูปแบบ) จะเหลือรูปแบบทั้งหมด \(a^p - a\) รูปแบบ

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

ยกตัวอย่างเช่น สร้อยคอที่ประกอบด้วยลูกปัด 8 ลูก โดยมีลูกปัดให้เลือก 2 สีคือแดง(R) หรือ เขียว(G)

1. ด้าย -RRRRGGGG- , -RRRGGGGR- , -RRGGGGRR- , -RGGGGRRR- , -GGGGRRRR- , -GGGRRRRG- , -GGRRRRGG- , -GRRRRGGG- เมื่อนำมาต่อเป็นสร้อยคอ ถือว่ามีรูปแบบซ้ำกัน
2. ด้าย -RRGGRRGG- , -RGGRRGGR- , -GGRRGGRR- , -GRRGGRRG- เมื่อนำมาต่อเป็นสร้อยคอ ถือว่ามีรูปแบบซ้ำกัน
3. ด้าย -RGRGRGRG- , -GRGRGRGR- เมื่อนำมาต่อเป็นสร้อยคอ ถือว่ามีรูปแบบซ้ำกัน

นอกจากนี้ให้สังเกตด้วยว่า

1. ด้าย A แต่ละเส้น หากขยับลูกปัดหมุนวนไปจำนวน 8 ลูก จะกลับมาเป็นรูปแบบของด้ายเส้นเดิมอีกครั้ง สร้อยคอที่เกิดจากการต่อด้าย A จึงมาจากด้าย A ที่เป็นไปได้จำนวน 8 รูปแบบ
2. ด้าย B แต่ละเส้น หากขยับลูกปัดหมุนวนไปจำนวน 4 ลูก จะกลับมาเป็นรูปแบบของด้ายเส้นเดิมอีกครั้ง สร้อยคอที่เกิดจากการต่อด้าย B จึงมาจากด้าย B ที่เป็นไปได้จำนวน 4 รูปแบบ
3. ด้าย C แต่ละเส้น หากขยับลูกปัดหมุนวนไปจำนวน 2 ลูก จะกลับมาเป็นรูปแบบของด้ายเส้นเดิมอีกครั้ง สร้อยคอที่เกิดจากการต่อด้าย C จึงมาจากด้าย C ที่เป็นไปได้จำนวน 2 รูปแบบ

สมมติว่า \(x\) เป็นจำนวนลูกปัดที่น้อยที่สุด ที่ต้องถูกขยับหมุนวนในด้ายแต่ละเส้น เพื่อให้ได้รูปแบบซ้ำกับด้ายเส้นเดิมอีกครั้ง จะได้ว่า \(x \mid p\)

หาก \(p\) เป็นจำนวนเฉพาะ จะได้ว่า \(x = 1\) หรือ \(x = p\)

แต่กรณีที่ \(x = 1\) ซึ่งหมายถึงขยับลูกปัด \(1\) ลูก แล้วได้รูปแบบเดิมเสมอ ไม่เกิดขึ้นแน่นอน เพราะรูปแบบนี้คือสร้อยที่ประกอบด้วยลูกปัดสีเดียวกันทั้งหมด ซึ่งเราคัดออกไปในตอนแรกแล้ว

ดังนั้นจึงเหลือเพียงกรณีเดียวเท่านั้นคือ \(x = p\) นั่นก็หมายความว่า สร้อยคอแต่ละเส้นที่ประกอบด้วยลูกปัดเป็นจำนวนเฉพาะ \(p\) ลูก มาจากการต่อด้ายที่เป็นไปได้ \(p\) รูปแบบแน่นอน (แตกต่างจากกรณีที่ \(p\) ไม่ใช่จำนวนเฉพาะ เช่น \(p=8\) ในตัวอย่างข้างต้น ที่มาจากการต่อด้าย A 8 รูปแบบ หรือมาจากการต่อด้าย B 4 รูปแบบ หรือ มาจากการต่อด้าย C 2 รูปแบบ)

เมื่อหักรูปแบบสร้อยคอที่ซ้ำกันออกไป จึงได้จำนวนรูปแบบสร้อยคอที่แตกต่างกันทั้งหมดเป็น \(\frac{a^p - a}{p}\) รูปแบบ

เนื่องจากจำนวนรูปแบบเป็นจำนวนเต็ม ดังนั้นจึงสรุปได้ว่า \(p \mid a^p - a\)