Page 2 - e modul bismillah

3.3. Mencari Koefisien Fungsi Pembangkit Biasa
Kita telah mendiskusikan dua langkah untuk memecahkan masalah kombinatorial dengan
menggunakan fungsi pembangkit. Langkah pertama kita harus mendapatkan fungsi pembangkit untuk
permasalahan tersebut selanjutnya langkah kedua yaitu mencari koefisien - koefisien yang tepat dari
fungsi pembangkit tersebut. Di bagian ini kita akan mendiskusikan bagaimana cara mencari koefisian
dari fungsi pembangkit tanpa menggunakan aturan perkalian.
Kadang kita bisa menggunakan aturan kombinatorial untuk mendapatkan koefisien. Sebagai
contoh berikut dibuktikan Teorema Binomial dan Teorema Multinomial.
a. Teorema Binomial
= + +
Bukti :

n faktor
Koefisien dari dengan , merupakan banyaknya seluruh cara berbeda memilih
sebanyak kali dan 1 sebanyak kali dari faktor yang tersedia. Banyaknya seluruh
cara memilih sebanyak kali dari faktor yang tersedia adalah

Jadi = =
Disisi lain
(1 x
(1 x+ ) = (1 x+ ) ( . 1 x+ )…+ )
n
= ( x + 0 x 1 ) ( . x + 0 x 1 )… (x + 0 x 1 )

0
= (x + x 1 n
)
Merupakan fungsi pembangkit untuk banyaknya selesaian bilangan bulat

b. Teorema Multinomial
adalah jumlah dari ... di mana

Bukti :
... merupakan banyaknya seluruh cara yang berbeda memilih sebanyak kali
dari n faktor , memilih sebanyak kali dari faktor , memilih sebanyak kali
dari faktor , .... , dan memilih sebanyak dari
faktor . Dengan demikian banyaknya seluruh cara adalah

−
 n  nn  nn − 1 n  2 nn − 1 n − 2 n … 3 − n m− 1 
−
−
1
.
  .    …  
 n 1  n 2   n 3   n m 
−
−
−
! n (nn )! (nn − n )! (nn − n − n − … − n )!
= . 1 . 1 2 … 1 2 3 m− 1
−
−
−
−
n 1 ( ! nn 1 )! n 2 ( ! nn − 1 n 2 )! n 3 !(nn − 1 n − 2 n 3 ) n m ( ! nn − 1 n − 2 n − 3 … − n m )!
! n
=
nn … m !
!! n
2
1
Disisi lain adalah fungsi pembangkit untuk banyaknya selesaian
bilangan bulat

Proposisi 3.1.
a. =
b. =
c. =
d. =