1. ความแตกต่างระหว่างกฎการคูณและกฎการบวก

หัวใจของคอมบินาทอริกส์คือการวิเคราะห์โครงสร้างของเหตุการณ์:

  • กฎการคูณ (Multiplication Principle): ใช้เมื่อกิจกรรมประกอบด้วยขั้นตอนย่อยต่อเนื่องกันที่ต้องทำครบทุกขั้นตอน \(N = n_1 \times n_2 \times \dots \times n_k\)
  • กฎการบวก (Addition Principle): ใช้เมื่อกิจกรรมแบ่งออกเป็นกรณีต่างๆ ที่เกิดขึ้นแยกขาดจากกัน (Mutually Exclusive) อย่างชัดเจน \(N = N_{\text{case 1}} + N_{\text{case 2}} + \dots + N_{\text{case k}}\)

2. การจัดหมู่ (Combination) และสัญลักษณ์ทวินาม

เมื่อเราต้องการเลือกสิ่งของ \(r\) ชิ้นจากของที่แตกต่างกัน \(n\) ชิ้น โดย ไม่คำนึงถึงลำดับ ก่อนหลัง:

\[ C(n, r) = \binom{n}{r} = \frac{n!}{r!(n - r)!} \]
  • ตัวอย่าง: มีนักเรียน 8 คน ต้องการเลือกตัวแทน 3 คน ไปแข่งขัน สามารถทำได้ \(\binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56\) วิธี
  • สมบัติสมมาตร: \(\binom{n}{r} = \binom{n}{n - r}\) เช่น \(\binom{10}{8} = \binom{10}{2} = \frac{10 \times 9}{2} = 45\)

3. หลักการรังนกพิราบ (Pigeonhole Principle)

หลักการทางคณิตศาสตร์ที่ดูเรียบง่ายแต่ทรงพลังอย่างยิ่งในการพิสูจน์ข้อความเชิงการดำรงอยู่ (Existence Proof):

🕊️ นิยามหลักการรังนกพิราบ (Pigeonhole Principle)

ถ้านำของ \(n\) ชิ้น ใส่ลงในกล่อง \(k\) ใบ โดยที่ \(n > k\) จะต้องมีกล่องอย่างน้อยหนึ่งใบที่มีของตั้งแต่ 2 ชิ้นขึ้นไป

\[ n > k \implies \exists \text{ box with } \ge 2 \text{ items} \quad \left( \left\lceil \frac{n}{k} \right\rceil \ge 2 \right) \]
  • รูปแบบทั่วไป (Generalized Pigeonhole): ถ้ามีนก \(n\) ตัวในรัง \(k\) รัง จะต้องมีรังที่มีนกอย่างน้อย \(\lceil \frac{n}{k} \rceil\) ตัว
  • ตัวอย่างประยุกต์: ในกลุ่มคน 13 คน ต้องมีคนอย่างน้อย 2 คนที่เกิดในเดือนเดียวกันอย่างแน่นอน (เพราะปีหนึ่งมี 12 เดือน แต่นกมี 13 คน)