Koefisien binomial \(\binom{n}{k}\) mula-mula didefinisikan menggunakan notasi faktorial. Dengan definisi rekursif notasi faktorial, kita juga memiliki definisi koefisien binomial yang lengkap dan sah secara formal. Rumus rekursif berikut memberikan skema komputasi yang efisien.
Misalkan \(n\) dan \(k\) bilangan bulat dengan \(0\le k\le n\text{.}\) Jika \(k=0\) atau \(k=n\text{,}\) tetapkan \(\binom{n}{k}=1\text{.}\) Jika \(0\lt k\lt n\text{,}\) tetapkan
Rekursi ini memiliki interpretasi kombinatorial yang alami. Kedua ruas menghitung banyaknya himpunan bagian beranggota \(k\) dari \(\{1,2,\dots,n\}\text{.}\) Ruas kanan mula-mula mengelompokkannya menjadi himpunan bagian yang memuat elemen \(n\) dan yang tidak memuatnya. Bentuk tradisional untuk menampilkan rekursi ini diperlihatkan dalam Gambar 3.2. Pola tersebut disebut “Segitiga Pascal.” Selain angka \(1\) pada kedua ujung setiap baris, suatu entri segitiga diperoleh dengan menjumlahkan dua entri yang terletak di kiri atas dan kanan atasnya.
Xing tertarik karena kini ia memiliki dua cara yang secara mendasar berbeda untuk menghitung koefisien binomial. Cara pertama ialah menulis \(\binom{n}{m}=P(n,m)/m!\text{,}\) lalu melakukan operasi aritmetika yang ditentukan. Cara kedua menggunakan rekursi Segitiga Pascal, sehingga hanya memerlukan penjumlahan. Ia pun bereksperimen dengan menulis program komputer untuk menghitung koefisien binomial menggunakan pustaka yang memperlakukan bilangan bulat besar sebagai string. Menurut Anda, cara manakah yang ternyata lebih cepat ketika, misalnya, \(n\) berada di antara \(1800\) dan \(2000\text{,}\) sedangkan \(m\) sekitar \(800\text{?}\)
