Koefisien Binomial dan Penghitungan Dasar

Koefisien binomial menghitung cara memilih himpunan bagian dengan ukuran tetap dari himpunan hingga dan berfungsi sebagai blok bangunan dasar enumerasi kombinatorial.

Definition

Koefisien binomial C(n,k) adalah jumlah himpunan bagian k-elemen dari himpunan n-elemen, sama dengan n!/(k!(n-k)!); penghitungan dasar adalah penerapan sistematis aturan penjumlahan dan perkalian pada konfigurasi hingga.

Scope

Topik ini membahas prinsip-prinsip penghitungan fundamental – aturan penjumlahan dan perkalian – serta peran sentral koefisien binomial C(n,k), identitasnya (aturan Pascal, teorema binomial, identitas Vandermonde), dan kemunculannya dalam segitiga Pascal. Ini menetapkan perangkat dasar yang menjadi fondasi semua kombinatorika enumeratif.

Core questions

• Dalam berapa banyak cara k objek dapat dipilih dari n objek yang berbeda?
• Bagaimana aturan penjumlahan dan perkalian menguraikan masalah penghitungan?
• Identitas apa yang menghubungkan koefisien binomial satu sama lain dan dengan teorema binomial?
• Bagaimana segitiga Pascal mengkodekan koefisien ini secara rekursif?

Key concepts

• Aturan penjumlahan dan aturan perkalian
• Permutasi versus kombinasi
• Faktorial
• Segitiga Pascal
• Identitas Vandermonde
• Koefisien multinomial

Key theories

Teorema binomial

Ekspansi (x+y)^n = jumlah dari k C(n,k) x^k y^(n-k) menyatakan koefisien binomial sebagai koefisien aljabar dalam pangkat binomial, menghubungkan penghitungan dengan aljabar polinomial.

Aturan Pascal

Rekurensi C(n,k) = C(n-1,k-1) + C(n-1,k) membangun setiap koefisien binomial dari dua koefisien di atasnya, menghasilkan segitiga Pascal dan mencerminkan apakah himpunan bagian yang dipilih mengandung elemen yang dibedakan.

Clinical relevance

Koefisien binomial mendasari distribusi probabilitas binomial, analisis algoritma kombinatorial, dan setiap pengaturan yang memerlukan penghitungan pilihan yang tidak berurutan, menjadikannya sangat penting dalam probabilitas, statistik, dan ilmu komputer.

History

Susunan segitiga koefisien binomial muncul dalam matematika Tiongkok, Persia, dan India berabad-abad sebelum risalah Pascal tahun 1654 memberikan nama abadi pada konstruksi tersebut di Barat.

Key figures

• Blaise Pascal
• Isaac Newton

Seminal works

• stanley2011

Frequently asked questions

Apa perbedaan antara permutasi dan kombinasi?

Permutasi menghitung susunan di mana urutan penting; kombinasi, yang dihitung oleh koefisien binomial, menghitung pilihan di mana urutan tidak relevan.

Mengapa C(n,0) sama dengan 1?

Hanya ada satu cara untuk tidak memilih apa pun dari suatu himpunan – himpunan bagian kosong – sehingga jumlah himpunan bagian nol-elemen adalah satu.