สัมประสิทธิ์ทวินามและการนับพื้นฐาน
สัมประสิทธิ์ทวินามใช้นับจำนวนวิธีในการเลือกเซตย่อยที่มีขนาดคงที่จากเซตจำกัด และเป็นองค์ประกอบพื้นฐานของการแจงนับเชิงการจัดหมู่
Definition
สัมประสิทธิ์ทวินาม C(n,k) คือจำนวนของเซตย่อยที่มี k สมาชิกจากเซตที่มี n สมาชิก ซึ่งเท่ากับ n!/(k!(n-k)!); การนับพื้นฐานคือการประยุกต์ใช้กฎการบวกและกฎการคูณอย่างเป็นระบบกับโครงแบบจำกัด
Scope
หัวข้อนี้กล่าวถึงหลักการนับพื้นฐาน ได้แก่ กฎการบวกและกฎการคูณ และบทบาทสำคัญของสัมประสิทธิ์ทวินาม C(n,k) เอกลักษณ์ของสัมประสิทธิ์ทวินาม (กฎของปาสคาล, ทฤษฎีบททวินาม, เอกลักษณ์ของว็องเดอร์มงด์) และการปรากฏของสัมประสิทธิ์ทวินามในสามเหลี่ยมปาสคาล ซึ่งเป็นการสร้างชุดเครื่องมือเบื้องต้นที่ใช้ในการสร้างการจัดหมู่เชิงแจงนับทั้งหมด
Core questions
- สามารถเลือกวัตถุ k ชิ้นจากวัตถุ n ชิ้นที่แตกต่างกันได้กี่วิธี?
- กฎการบวกและการคูณช่วยในการแยกย่อยปัญหาการนับได้อย่างไร?
- เอกลักษณ์ใดบ้างที่เชื่อมโยงสัมประสิทธิ์ทวินามเข้าด้วยกันและกับทฤษฎีบททวินาม?
- สามเหลี่ยมปาสคาลเข้ารหัสสัมประสิทธิ์เหล่านี้แบบเรียกซ้ำได้อย่างไร?
Key concepts
- กฎการบวกและกฎการคูณ
- การเรียงสับเปลี่ยนกับการจัดหมู่
- แฟกทอเรียล
- สามเหลี่ยมปาสคาล
- เอกลักษณ์ของว็องเดอร์มงด์
- สัมประสิทธิ์พหุนาม
Key theories
- ทฤษฎีบททวินาม
- การกระจาย (x+y)^n = ผลรวมของ C(n,k) x^k y^(n-k) สำหรับทุก k แสดงสัมประสิทธิ์ทวินามเป็นสัมประสิทธิ์พีชคณิตในกำลังของทวินาม ซึ่งเชื่อมโยงการนับเข้ากับพีชคณิตพหุนาม
- กฎของปาสคาล
- ความสัมพันธ์เวียนเกิด C(n,k) = C(n-1,k-1) + C(n-1,k) สร้างสัมประสิทธิ์ทวินามแต่ละตัวจากสองตัวที่อยู่เหนือกว่าในสามเหลี่ยมปาสคาล และสะท้อนว่าเซตย่อยที่เลือกมีสมาชิกที่โดดเด่นหรือไม่
Clinical relevance
สัมประสิทธิ์ทวินามเป็นพื้นฐานของการแจกแจงความน่าจะเป็นทวินาม การวิเคราะห์อัลกอริทึมเชิงการจัดหมู่ และสถานการณ์ใดๆ ที่ต้องการนับการเลือกที่ไม่มีลำดับ ทำให้สัมประสิทธิ์ทวินามเป็นสิ่งที่พบได้ทั่วไปในความน่าจะเป็น สถิติ และวิทยาการคอมพิวเตอร์
History
ตารางสามเหลี่ยมของสัมประสิทธิ์ทวินามปรากฏในคณิตศาสตร์จีน เปอร์เซีย และอินเดียหลายศตวรรษก่อนที่ตำราของปาสคาลในปี ค.ศ. 1654 จะทำให้โครงสร้างนี้มีชื่อที่ยั่งยืนในโลกตะวันตก
Key figures
- Blaise Pascal
- Isaac Newton
Related topics
Seminal works
- stanley2011
Frequently asked questions
- ความแตกต่างระหว่างการเรียงสับเปลี่ยนและการจัดหมู่คืออะไร?
- การเรียงสับเปลี่ยนนับการจัดเรียงที่ลำดับมีความสำคัญ; การจัดหมู่ ซึ่งนับโดยสัมประสิทธิ์ทวินาม นับการเลือกที่ลำดับไม่เกี่ยวข้อง
- ทำไม C(n,0) จึงเท่ากับ 1?
- มีเพียงหนึ่งวิธีเท่านั้นในการไม่เลือกสิ่งใดจากเซต — คือเซตว่าง — ดังนั้นจำนวนเซตย่อยที่มีศูนย์สมาชิกจึงเท่ากับหนึ่ง