Tugas Makalah Matematika Kombinatorik [PDF]

Citation preview

Makalah Matematika Kombinatorik ( Koefisien Binomial dan Identitas Kombinatorik )



Disusun Oleh : Kelompok 3 Semester 6 Susianti



2017121001



Paiza



2017121002



Sri Muliani



2017121014



Tiara Agnes



2017121022



Trifenia Meliani



2017121035



Firdaus



2017121081



Dosen Pengampuh : Ety Septiati S.Si., M.T



FAKULTAS KEGURUAN DAN ILMU PENDIDIDKAN PROGRAM STUDI PENDIDIKAN MATEMATIKA UNIVERSITAS PGRI PALEMBANG 2020



KATA PENGANTAR



Assalamualaikum Wr, Wb. Segala puji kami panjatkan kepada Allah SWT yang telah melimpahkan rahmat dan karunia-Nya kepada kami, sehingga kami dapat menyelesaikan tugas makalah ini dengan baik. Shalawat serta salam semoga senantiasa selalu tercurah kepada jujungan kita Nabi Muhammad SAW yang telah membawa kita dari zaman kegelapan menuju zaman yang terang seperti saat ini. Makalah ini kami susun untuk memenuhi tugas dari mata kuliah MATEMATIKA KOMBINATORIK yang diampu oleh ibu Ety Septiati S.Si., M.T . Kami ingin mengucapkan terimakasih kepada beliau yang telah membimbing kami, serta semua pihak yang telah membantu dalam proses penyusunan makalah ini. Pada makalah ini, kami akan memaparkan tentang Koefisien Binomial dan Identitas Kombinatorik. Harapan kami semoga makalah ini membantu dan menambah pengetahuan. Walaikumsallam Wr.wb Palembang, Maret 2020



1.



KOEFISIEN BINOMIAL Bilangan-bilangan kombinasi dari suatu himpunan dari n unsur, tetapi selain itu bilangan ini juga mempunyai cukup banyak sifat yang menarik dan memenuhi banyak sekali kesamaan-kesamaan. Karena bilangan ini timbul juga pada teorema binomial Newton, maka bilangan ini juga dikenal dengan nama koefisien binomial. Dalam mengadakan pembahasan atau menganalisa suatu algoritma, maka koefisien binomial juga sering digunakan dan merupakan salah satu senjata yang ampuh dalam upaya mendapatkan jawaban dari suatu persoalan. Bab ini hanya akan membahas sebagian kecil dari sifatsifat koefisien binomial dan member gambaran mengenai pemakaian koefisien dalam beberapa persoalan. Juga akan dibahas beberapa kesamaan yang dipenuhi oleh koefisien ini dan acara-cara untuk memperoleh kesamaan tersebut berdasarkan teorema binomial Newton.



1.1 Rumus Pascal Seperti telah dibahas sebelumnya, koefisien binomial



(nk)



telah



didefinisikan untuk setiap bilangan bulat tidak negatif n dan k. bila k < n n maka ditentukan bahwa = 0, dan untuk unsur nilai k = 0 ditentukan bahwa k n = n. Sedangkan untuk nilai k yang memenhi 1 ≤ k ≤ n, maka nilai: k



()



() n! (nk)= k ! ( n−k )!



¿



n ( n−1 ) …( n−k + 1) k ( k−1 ) … 1



Hal yang juga pernah ditunjukan pada Bab II adalah sifat berikut ini yang berlaku untuk nilai-nilai k dan n yang memenuhi 0 ≤ k ≤ n. n (nk)=(n−k ) Berikut ini adalah suatu teorema yang merupakan salah satu sifat terpenting n lainnya dari . k



()



TEOREMA 1.1 (Rumus Pascal) Setiap bilangan n dan k bulat dimana 1 ≤ k ≤ n-1, akan memenuhi kesamaan berikut ini :



+ n−1 (nk)=(n−1 k ) ( k −1 )



Bukti : Kesamaan ini dapat dengan mudah dibuktikan dengan memasukan rumus dari n yang dituliskan dalam bentuk faktorial seperti dituliskan dengan rumus k 3.1 diatas. Pembaca dianjurkan untuk mencoba membuktikan kesamaan ini sendiri dengan menghitung kedua bagian kiri dan kanan pada kesamaan di atas.



()



Tetapi selain dengan cara langsung ini, kesamaan di atas dapat juga dibuktikan dengan argumentasi kombinatorial berikut ini. Misalkan S adalah suatu himpunan yang terdiri dari n benda. Bedakan salah satu unsur dari S, dan beri tanda “x” pada unsur tersebut. Telah ditunjukan bahwa jumlah n seluruh kombinasi-k dari himpunan S adalah sama dengan . Untuk seluruh k kombinasi-k ini kumpulkan semua kombinasi yang tidak mengandung unsur “x” pada suatu himpunan dari himpunan bagian S yang disebut A dan kumpulkan semua kombinasi lain yang mengandung unsur “x” pada suatu himpunan lain yang disebut B. Jumlah kombinasi yang ada di A adalah n−1 , karena semua kombinasi-k yang ada di A merupakan semua k kombinasi-k yang ada di S, kecuali yang mengandung satu unsur “x”, berarti merupakan kombinasi-k dari n-1 unsur dari S yaitu S – {x} . Sedangkan n−1 semua kombinasi yang ada di B dapat ditulis dalam bentuk , karena k−1 semua kombinasi ini mengandung unsur “x” , jadi dapat dikatakan bahwa banyaknya kombinasi ini sama dengan semua semua kombinasi-kombinasi (k-1) dari semua unsur dari S kecuali “x”. dan menggunakan prinsip penjumlahan diperoleh :



()



( )



( )



+ ( n−1 ) (nk)=(n−1 ) k k −1 Untuk lebih memberikan gambaran yang jelas pada bukti di atas, lihat contoh berikut untuk nilai n = 5 dan k = 3, serta S = { x, y, z, u, v }. Kombinasi-3 dari S yang termasuk A adalah { y, z, u }, { y, z, v }, {y, u, v }, { z, u, v }



Kombinasi ini juga merupakan kombinasi-3 dari himpunan { y, z, u, v }. 4 Banyaknya kombinasi seperti ini adalah . Sedangkan kombinasi-3 yang 3 termasuk dalam B adalah



()



{ x, y, z }, { x, y, u }, { x, y, v } { x, z, u }, { x, z, v }, { x, u, v } Bila semua unsur “x” dihapus pada kombinasi-kombinasi di atas, maka akan diperoleh { y, z }, { y, u }, { y, v }, { z, u }, { z, v }, { u, v } Dan ini merupakan kombinasi-2 dari himpunan { y, z, u, v }, banyaknya 4 kombinasi seperti ini adalah . Jadi diperoleh kesamaan : 2



()



(53 )=(43 )+( 42) Dengan menggunakan teorema 1.1 + ( n−1 ) (nk)=(n−1 ) k k −1 Ini, serta rumus dasar untuk k = 0 dan k = n, yaitu :



(n0 )=(nn )=1 Maka semua koefisien binomial dalam bentuk



(nk) untuk semua bilangan bulat



tidak negatif n dapat dihitung langsung tanpa menggunakan rumus (3.1) di atas. Bila koefisien binomial dihitung dengan cara demikian, hasilnya biasanya disusun dalam bentuk yang dikenal dengan nama Segitiga Pascal yang digambarkan berikut ini. Dalam susunan ini setiap titik dari segitiga yang tidak bernilai 1 diperoleh dengan menambahkan dua titik pada baris diatasnya, satu dari titik yang langsung diatasnya dan titik lain disebelah kirinya. Hal ini dapat dilakukan sesuai dengan yang dinyatakan oleh teorema 3.1



n



(n0 ) (n1 ) (n2 ) (n3 ) ( n4) (n5 ) (n6) (n7 ) (n8 )



…



0



1



1



1



1



2



1



2



1



3



1



3



3



1



4



1



4



6



4



1



5



1



5



10



10



5



1



6



1



6



15



20



15



6



1



7



1



7



21



35



35



21



7



1



8



1



8



28



56



70



56



28



8



1



⋮



⋮



⋮



⋮



⋮



⋮



⋮



⋮



⋮



⋮



⋮



Gambar lll.1 segitiga pascal Hanya dengan memperhatikan segitiga Pascal di atas dengan seksama, maka dapat diperoleh banyak hal-hal atau sifat-sifat yang menarik dari koefisien



(nk). Sifat-sifat tersebut antara lain adalah : n n 1. Bentuk simetris ( ) = ( dapat langsung dilihat di atas, k n−k ) binomial



2. Kesamaan yang menunjukan jumlah semua himpunan bagian dari suatu himpunan S yang beranggaotakan n unsur yang dinyatakan oleh



(n0 )+(n1 )+(nn )=2



n



dapat diperoleh langsung dengan menjumlahkan semua bilangan yang ada pada salah satu baris. 1.2 Teorema Binomial Bentuk



(nk) disebut koefisien binomial karena koefisien-koefisien ini



memenuhi teorema binomial berikut ini. Sebenarnya teorema dasar dari binomial ini sudah harus diketahui oleh semua siswa yang telah lulus SMA, karena rumus dasar ini merupakan salah satu bentuk yang telah sering dibahas pada mata pelajaran aljabar di SMA.



Teorema 1.2: Misalkan n suatu bilangan bulat positif. Maka untuk setiap nilai x dan y akan dipenuhi: ( x + y¿n = y n + n



(n1 ) xy



n−1



+



(n2 ) x . y 2



n−2



+…+



n x (n−1 )



n−1



y + xn



k n−k =∑ n x y k=0 k



()



Bukti : Cara 1 : tuliskan (x+y¿n sebagai hasil kali dari n buah faktor x+y. Bentuk ini diekspansikan sehingga semua bentuk kurung hilang. Karena untuk setiap faktor dapat dipilih salah satu suku x atau y, maka hasil dari perkalian faktorfaktor ini adalah 2n, dan semua suku Ini dapat diatur dalam bentuk x k y n−k, untuk nilai k = 0, 1, 2, … n. suku x k y n−k diperoleh dengan memilih x sebanyak k faktor dan y sebanyak n-k faktor. Jadi jumlah bentuk suku x k y n−k muncul setelah ekspansi dilakukan sama dengan jumlah dari kombinasi-k dari himpunan yang terdiri dari n faktor, dan jumlah ini adalah n



(nk) Jadi diperoleh



k n−k ( x + y¿ = ∑ n x . y k=0 k n



()



Cara 2: Cara lain untuk menunjukan teorema di atas adalah dengan menggunakan rumus induksi pada n. Untuk basis induksi n = 1. maka rumus di atas akan menjadi n



1 x0 y1 1 x1 y0 k n−k ( x + y¿1 = ∑ 1 x y = + =x+y 0 1 k−0 k



()



()



()



Jadi rumus di atas benar untuk nilai n = 1. Misalkan rumus di atas benar untuk nilai n, maka harus ditunjukan bahwa rumus di atas juga benar untuk nilai n + 1. Untuk itu tuliskan bentuk n



( x + y¿



n +1



k n−k = ( y + x ) (∑ n x y ) k=0 k



()



n



= y (∑ k=0



n



n x k y n−k ) + x ( n x k y n−k ) ∑ k k=0 k



()



n y n+1 = ( 0



()



(nn ) x



n



∑( k =1



()



n −1



n k n+1−k + ( x y ¿ ∑ nk x k+1 y n−k ) + k k=0



)



()



n+1



Bila penjumlahan yang kedua pada hasil terakhir ini semua diganti dengan k1, maka bentuk penjumlaha menjadi : n



n x k y n+1−k ) k −1



(∑ ( ) k=1



Dengan demikian akan diperoleh n



(x+y¿



n +1



=y



n+ 1



+∑ k =1



n+ n x k y n+1−k + x n+1 k k −1



[( ) ( ) ]



dengan merggunakan kesamaan Pascal, maka bentuk terakhir ini dapat ditulis sebagai n



( x + y ¿n +1 = y n+ 1 + ∑ n+1 x k y n+1−k + x n+1 k k =1



( )



atau n +1



( x + y ¿n +1 = ∑ n+1 x k y n+1−k k=0 k =0



( )



Jadi rumus di atas juga benar bila nilai n diganti dengan n+1, dan berdasarkan langkah induksi, maka teorema di atas terbukti. Perlu diperhatikan bahwa teorema binomial di atas dapat ditulis dalam berbagal bentuk yang kelihatannya tidak sama, tetapi bila diteliti lebih jauh ternyata bahwa nilainya adalah sama. Bentuk bentuk yang ekuivalen dari teorema binomial antara lain adalah: n



( x + y¿n = ∑ k=0



n x y (n−k )



n



k



n−k



n−k k =∑ n x y k k=0 n



=∑ k=0



()



n x (n−k )



n−k



yk



Kesetaraan dari ketiga bentuk di atas dengan bentuk teorema binomial Newton dapat dengan mudah ditunjukan dengan menggu nakan: n (nk)=(n−k )



k = 0, 1, 2,…n



dan penukaran perubah x dengan y Rumus binomial di atas terdifinisi untuk setiap n bilangan bulat positif dan x serta y sembarang. Hal khusus untuk nilai y = 1 sering muncul dan banyak menimbulkan rumus yang sangat praktis. Untuk nilai y = 1 ini bentuk binomial yang baru adalah n



n



( x + y )n = ∑ n X k = ∑ n X k k=0 k k=0 n−k



()



( )



Untuk hal – hal yang lebih khusus lainnya mislnya untuk nilai n – 2,3, atau 4, maka rumus binomial merupakan rumus yang telah sering sekali diketemukan oleh mahasiswa sejak kelas III SMP . rumus – rumus tersebut adalah : ( x + y )2 = x2 + 2xy + y2 ( x + y )3 = x3 + 3xy2 + y3 ( x + y )4 = x4 + 4x3y + 6x2y2 + 4xy3 + y2 Jika diperhatikan disini, maka koefisien dari setiap suku adalah sama dengan koefisien yang ada pada baris-baris segitiga Pascal. Dari sini dapat ditunjukan bahwa proses pembentukan tap titik dari segitiga Pascal dengan penjumlahan dua titik sebelumnya adalah benar. 1.3 Kesamaan–Kesamaan Koefisien Binomial Seperti telah disinggung didepan, koefisien-koefisien binomial banyak mempunyai sifat-sifat yang menarik. Sifat pertama yang sering digunakan adalah sifat berikut ini yang berlaku untuk blangan-bilangan bulat positif n dan k:



(nk)= nk (n−1 k−1 )



rumus ini mudah ditunjukan dengan menggunakan definisi faktorial () dan kenyataan bahwa



(nk) = 0, bila k > n.



Sifat lain yang juga sering diketemukan adalah sifat yang diperoleh dari rumus berikut ini yang pernah dibuktikan pada bab Il yaitu



(n0 ) + (n1 ) + (n2 ) + ........ + (nn ) = 2



n



Rumus Iwl dapat juga ditunjukan dari teorema binomial dengan menggantikan nilai x dan y dengan nilai 1. Sedangkan bila nilal x digantikan dengan nilai 1 dan nilal y digantikan dengan nilai -1, maka teorema binomial akan memberikan



(n0 ) - (n1 ) + (n2 ) - ........ +(-1) (nn ) = 0 n



yang berlaku untuk tiap nilai n bilangan bulat. Bila suku-suku yang nya negatif dipindahkan ke sisi yang lain, maka dapat diperolen suatu kesamaan yang berbentuk



(n0 ) + (n2 ) + ........ = (n1 ) + (n3 ) + ....... Kesamaan Ini dapat dinyatakan dalam bentuk kombinatorial seperti berikut. Bila s suatu himpunan dengan n unsur, maka jumlah semua Himpunan bagian dari s yang mempunyal anggota ganjil akan sama dengan jumlah semua himpunan bagian dari s yang mempunyai anggota genap Sekarang akan ditunjukan dua cara membuktikan sifat koefisien binomial berikut ini:



(n1 ) + 2 (n2) + 3 (n3 ) + ....... +n ( nn) = n 2



1



n−1



Cara yang pertama dilakukan dengan menggunakan dua sifat yang telah dibuktikan di atas. Penggunaan sifat pertama akan mengubah bagian kiri dari kesamaan di atas menjadi



(n−1 0 )



n



n−1 + n 1



(n−1 2 )



( )



+ ....... +n



+ n



( n−1 n−1 )



= n



n−1 + n−1 + n−1 +.......+ n−1 0 1 2 n−1



[( ) ( ) ( )



( )]



Jumlah terakhir ini sama dengan n 2n−1



berdasarkan sifat yang telah



ditunjukan di atas. Cara lain menunjukan sifat ini adalah dengan mengekspansikan bentuk n( 1 + x )n =



(n0 ) + x (n1) + x (n2 ) + ........ +x (nn ) 2



n



Bila dilakukan proses diferensiasi (penurunan) terhadap perubah x dari kedua bagian pada persamaan di atas, maka akan diperoleh bentuk n(1+ x)n −1 =



(n1 ) + 2x (n2 ) + ........ +nx (nn) n−1



Dengan mengganti nilai x dengan 1, maka terbukti sifat yang diminta Banyak kesamaan-kesamaan dalam bentuk kombinatorial yang dapat ditunjukan dengan melakukan secara berturut-turut deferen sisi atau penurunan dan perkalian dari deret binomial. Berikut adalah salah satu contoh bagaimana proses penurunan dan perkalian suatu deret binomial dapat menimbulkan suatu kesamaan yang baru Pandang rumus binomial berikut ini n



(1+ x)n = ∑ k=0



(nk ) x



k−1



Bila pada kedua bagian kiri dan kanan dari persamaan di atas dilakukan penurunan atau diferensiasi terhadap variabel x, maka akan diperoleh bentuk n



n(1+ x)n −1= ∑ k k =1



(nk) x



k−1



kemudlan kedua bagian kiri dan kanan dikalikan dengan variabel x bentuk berikutnya yang akan diperoleh adalah



n n−1



n x (1+ x)



=∑k k =1



(nk) x



k



Terakhir bila dilakukan penurunan lagi terhadap variabel x, maka akan diperoleh suatu bentuk yang masih tergantung pada x n



n[ (1+ x)n−1+ ( n−1 ) x (1+ x)n−2 ] = ∑ k k =1



2



(nk) x



k−1



Dan bentuk terakhir Int dengan mengganti nilal x dengan 1, maka dengan mudah dapat diperlihatkan bahwa n



n[ 2n−1 +( n−1)2n−2 ] = ∑ k k =1



2



(nk)



sehingga diperoleh rumus berikut n



n(n+1)2n−2= ∑ k k =1



2



(nk)



untuk setiap bilangan bulat positif n. Cara lain yang sering juga digunakan untuk membuktikan kesamaankesamaan adalah cara dengan argumentasi kombinatorial. Misal nya akan ditunjukan bahwa n



∑( k=0



2



n = 2n n k



) ( )



untuk setiap bilangan bulat positif n. Untuk Ini misalkan dibentuk suatu himpunan S yang mempunyai 2n buah unsur. Maka bagian kanan dari persamaan di atas menyatakan jumlah dari kombinasi-n dari semua unsur-unsur dari S. Sekarang unsur-unsur dari s dibagi dua kedalam dua buah himpunan A dan B yang masing-masing mempunyal n unsur. Maka setiap kombinasi-n yang dibentuk pada s merupakan gabungan dari kombinasi -k yang dapat dibuat pada himpunan A dan kombinasi-(n-k) yang dapat dibuat pada himpunan B, dan hal ini dilakukan untuk setiap nilai k = 0,1, 2, … ,n karena kombinasi-k pada A



n k



()



adalah



n dan kombinasi-(n-k) pada B adalah n−k



( )



, maka dengan



mrnggunakan prinsip perkalian pada kedua bentuk di atas dan prinsip penjumlahan untuk semua nilal k yang mungkin akan diperoleh bentuk n



2n n n =∑ n k =0 k n−k



( ) ( )( ) n n ¿ ∑ ( )( ) k k n



k =0



1.4 Perluasan Definisi



Berikut ini akan diperluas daerah definisi koefisien binomial



(nk )



sehingga



bilangan n dan k tidak terbatas pada bilangan bulat positif dimana nilal k ¿ n, tetapl n dapat terdefinisi untuk setiap bilangan riil sembarang dan k terdefinisi untuk setiap bilangan bulat sembarang, termasuk bilangan bulat negatif dan nol. Hal itu dilakukan dengan memberikan definisi baru pada



(nk )



seperti berikut:



r = r(r−1)( r−2)...(r−k+1) k k( k−1)...1



()



yang terdefinisi untuk setiap r bilangan bulat dan k bilangan bulat positif, sedangkan untuk nilal k yang lain digunakan definisi berikut:



r =1 0



()



untuk k = 0 dan r bilangan riil sembarang serta



r =0 k



()



untuk r bilangan riil sembarang dan k bilangan bulat negatif. Jadi menurut definisi ini dapat dihitung



7 5 3 1 1 − 7 2 2 2 2 2 2 = 5×4×3×2×1 5



()



( )( )( )( )( )



Untuk definisi baru ini kesamaan berikut juga masih berlaku untuk nilal bilangan real dan k ¿ 0:



(rk)= rk (r−1 k −1 ) demikian pula kesamaan



(rk)=( r−1k )+(r−1 k −1 ) Hal lain yang juga dapat ditunjukan dengan definisi baru dari koefisien binomial ini adalah rumus dalam bentuk Jumlahan berikut ini



(r0)+(r +11 )+(r +22 )+. . .(r +kk )=(r +kk+1 ) Yang benar untuk setiap r bilangan riil dan k bilangan bulat. Hal ini dapat dengan mudah ditunjukan dengan secara berulang-ulang menggunakan rumus Pascal



(



r+k +1 r+k r+k −1 r +k −1 = + + k k k −1 k −2



)( )(



= r+k + k = r+k + k



( )( ( )(



)(



)



r+k −1 + r +k −2 +. .. r+1 + r+1 k−1 k−2 1 0 r+k −1 + r +k −2 +. .. r+1 + r + r k−1 k−2 1 0 −1



)( )(



) ( )( ) ) ( )()( )



Karena suku yang terakhir



r =0 −1



( )



maka rumus penjumlahan diatas



terbukti.



Rumus penjumlahan lain yang juga penting dan merupakan rumus sekawan dari rumus penjumlahan di atas adalah rumus berikut, yang hanya berlaku untuk bilangan bulat tidak negatif n dan k:



(0k )+(1k )+(2k )+. ..( nk )=( n+1 k +1 ) Rumus ini akan dibuktikan dengan menggunakan induksi matematik yang bekerja pada variabel n. Untuk setiap langkah harus dilakukan pembuktian untuk nilai k = 0 dan k > 0. pertama-tama akan dibuktikan basis induksi, yaitu untuk nilain = 0. jumlahan diatas akan menjadi



0 1 = k k +1



()( ) Untuk nilai k = 0, kedua bagian di atas bernilai 1, sedangkan untuk nilai k > 0 kedua bagian di atas bernilai 0. jadi rumus benar untuk nilai n = 0. sekarang sekarang misalkan rumus benar untuk nilal n, dan harus buktikan bahwa rumus juga benar untuk nilal n+1. Berdasarkan pemisalan Induksi yang telah dianggap benar maka diperoleh



n+1 +( (0k )+( 1k )+( 2k )+. ..+(nk )+(n+k 1 )=(n+1 ) k +1 k ) ( n+1)+1 =( n+2 )=( ) k +1 k+1 Bentuk yang terakhir In: diperoleh aarl rumus segitiga Pascal, dan dari bentuk Ini terlihat bahwa rumus Juniahan di atas benar unti nila n+1. Berdasarkan induksi matematik dapat disimpulkan bahwa rumus di atas benar untuk semua nilai n dan k yang bulat dan tidak negatif. Dalam rumus itu, bila dipilih nilai k = 1 maka akan terjadi bentuk



0 1 2 n n+1 + + +. ..+ = 1 1 1 1 1+1



()()() ()( ) atau akan diperoleh rumus jumlahan yang sering dijumpai untuk n bilangan bulat positif yang pertama yaitu.



1+2+3+. ..+n=



n(n+1) 2



Sebagal kesimpulan disini diberikan bahwa dalam membuktikan kesamaankesamaan pada koefisien binomial dapat digunakan beberapa cara yaitu antara lain: 1. Dengan menggunakan rumus faktorial dari koefisien binomial. 2. Dengan menggunakan rumus Pascal dari koefisien binomial. 3. Dengan induksi matematik 4. Dengan menggunakan teorema binomial, serta integrasi maupun diferensiasi termasuk perkalian. 5. Dengan menggunakan argumentasi kombinatorial.



1.5 Sifat Satu Modus Dari Koefisien Binomial Bila diperhatikan secara dalam, akan terlihat bahwa koefisien binomial pada setiap baris dari segitiga Pascal merupakan sedere bilangan bilangan yang naik untuk sementara, dan kemudian tu lagu. Barisan bilangan yang demikian disebut mempunyai sifat modus. Jadi suatu barisan bilangan S1, S2,…., Sn disebut mempunyai sifat satu modus bila ada bilangan bulat t yang memenuhi 1 ¿ t ≤n sedemikian sehingga S1 ¿ S2 ¿ S3… ¿ St Dan juga St ¿ St+1 ¿ St+2 … ¿ Sn



Bilangan St adalah bilangan terbesar pada barisan tersebut. Pada definisi di atas tidak diminta bahwa bilangan t harus tunggal. Jadi bila S 0 = 1, S1 = 3, S2 = 3 dan S3 = 2, maka barisan ini juga memenuhi S0 ¿ S1 ¿



S2 , S2 ¿ S3



Dan juga S0 ¿ S1, S1 ¿ S2 ¿ S3 dalam hal ini t dapat bernilai 2 atau 1. Teorema berikut ini membuktikan bahwa barisan koefisien binomial akan memenuhi sifat satu modus, dan bilangan yang terbesar akan terletak ditengah barisan TEOREMA 3.3: Misalkan n suatu bilangan bulat positif. Barisan koefisien binomial berikut



(n0 ),( n1) ,( n2 ) ,...,( nn) memenuhi sifat satu modus. Untuk n yang genap maka akan dipenuhi n n < n < n . ..> n > n n > −+1 n−1 n 2 2



()(



)



( )()



sedangkan untuk nilai n yang ganjil, maka akan dipenuhi kedua ketidaksamaan berikut ini n n n n <
. ..> n−1 n 2 2



( )( ) (



( )()



n nn −1 nn +1 =  ...  (n n−1)  n 2 2



) ( )



()



Bukti: Perhatikan hasil bagi dari barisan koefisien binomial yang berturutan berikut ini. Untuk nilai 1  k  + n akan dipenuhi: n 0 = n k −1



()



( )



n! k ! ( n−k ) ! n−k +1 = n! k ( k −n ) ! ( n−k +1 ) !



Dengan demikian bila salah satu dari ketiga hal berikut ini dipenuhi kn–k+1,k=n–k+1,nn–k+1 Maka akan dipenuhi pula salah satu ketiga hal berikut (k ¿ ¿ n−1)(¿nk ) ,(k n −1) ¿(¿ nk ),(k n−1)(¿nk )¿ ¿ ¿ ¿ sedangkan ketidaksamaan k  n – k + 1 dipenuhi jika dan hanya jika dipenuhi ketidaksamaan k dengan k ≤



(n+ 1) (n+ 1) , jika n bilangan genap, maka syarat k ekivalen 2 2



n (n+ 1) (n−1) , dan untuk n ganjil k ekivalen dengan k ≤ , Jadi 2 2 2



barisan koefisien binomial akan naik seperti yang dikatakan pada teorema. Sekarang perhatikan syarat k = n - k + 1 yang akan dipenuhi dan hanya jika 2k = n + 1. Bila n genap, maka 2k n  n + 1 untu tiap k. sedangkan untuk n ganjil maka 2k = n + 1. k =



(n+1) Jadi untuk nilal n genap. maka tidak 2



akan ada dua koefisien binomial berurutan yang sama, sedangkan untuk nilal



n satu-satunya pasangan koefisien binomial berurutan yang adalah



dan



(



(nn−1) 2



(



(nn+ 1) , 2



)



)



Dengan cara yang sama dapat di tunjukan bahwa barisan koefisien binomial yang berikutnya akan menurun. Bita untuk setiap bilangan riell x didefinisikan suatu fungsi [x] sebagal bilangan bulat terbesar yang lebih kecil atau sama dengan x, maka dengan mudah akan dapat ditunjukan kebenaran akibat dari teorema III.3 berikut ini: AKIBAT : barisan Untuk setiap bilangan bulat positif n koefisien binomial terbesar dari .n Barisan( ¿n0)¿ , ¿ ¿ adalah [ n ] . 2



( )



1.6 Teorema Multinomial Bagian berikut ini akan membahas perluasan dari teorema binomial yang dikenal dengan nama Teorema Multinomial. Bila pada teorema binomial bentuk yang dipelajari adalah (x + y)n, maka pada teorema multinomial, bentuk-bentuk yang dipelajari antara lain adalah bentuk (x + y + z)n atau lebih umum lagi bentuk (x1 + x2 + ... + xk)n Dalam mengekspansikan bentuk Ini biasanya akan diketemukan besaran yang juga merupakan perluasan dari besaran koefisien binomial. Besaran yang baru ini dikenal dengan nama koefisien multinomial yang didefinisikan sebagai n! n1 ! n2 ! …n k ! dimana dipenuhi hubungan n = n1 + n2 + ... nk Bentuk faktorial Ini dapat dituliskan secara singkat seperti koefisien binomial berikut



( n1nn … n k ) 2



Sepintas besaran Ini merupakan mirip dengan koefisien binomial yang telah dipelajari sebelum Ini. Hal ini memang kenyataannya derniklan, karena untuk nilai k = 2, bentuk faktorial di atas akan berubah menjadi koefisien binomial karena n1 + n2 = n atau ( n1.n n 2) =( n1nn−n1 ) n kalau dilihat pada pembahasan bab II, maka bentuk ( n1n ... nk ) menyatakan 2



banyaknya permutasi yang mungkin dibuat dari suatu himpunan ganda yang terdiri dari k unsur yang masing-masing mempunyal faktor pengulangan n1, n2, .... , nk. Sebelum diberikan teorema yang berkaitan dengan teorema multinomial, maka akan diperkenalkan terlebih dahulu salah satu bentuk khusus dari koefisien multinomial untuk n dan k = 3. Bila bentuk ( x1 + x2 + x3 )3 diekspansikan sampai semua kurung berhasil dihilangkan, maka akan diperoleh bentuk x 31+ x32 + x 33 +3 x 21 x 2 +3 x 21 x 3 + 3 x 1 x 22 + 3 x 22 x 3 + 3 x 1 x 23 + 3 x 2 x 23 + 6x1x2x2 Kalau diperhatikan dengan teliti, maka semua suku yang ada pada ekspansi Ini dapat ditulis dalam bentuk x n1 x n2 x n3 . .. x nk 1



2



3



k



Dimana pangkat dari masing-masing xI yaitu n1, n2 dan n3 adalah bilangan bulat tidak negatif dan jumlah dari n1 + n2 + n3 = 3. Sedangkan koefisien konstanta dari setiap suku yang ada juga memenuhi bentuk umum berikut. 3!



( n1 .3n n3 ) = n1 ! n2 ! n 3 ! 2



Teorema 1.4 : Misalkan n suatu bilangan bulat positif. Maka untuk setiap bilangan riel × 1, ×2, ... ×t akan berlaku n n n n n ( ×1 + ×2 + ... + ×t )n =  ( n1n … n t ) x 1 x 2 x 3 … x t 1



2



3



t



2



Dimana tanda penjumlahan di atas berlaku untuk setiap nilai bilangan Bulat positif n1, n2, ... nt yang memenuhi persamaan n1 + n2 + ... + nt = n.



Bukti: Sama seperti membuktikan teorema binomial, maka bentuk di atas ekspansikan terus sehingga semua kurung yang ada dihilangkan. Hal ini dilakukan dengan mengalikan semua n faktor yang berbentuk ( x 1 + x2 + ... + xt ). Dari setiap faktor ini dapat dipilih salah satu suku yang ada yaitu x 1 + x2 + ... + xt. Jadi akan terbentuk sebanyak tn sukui dimana setiap suku akan berbentuk x n1 x n2 … x nt , dimana setiap ni adalah bilangan bulat tidak negatif 1



2



t



dan Jumlah dari seluruh ni adalah n. setiap suku x n1 x n2 … x nt dapat diperoleh 1



2



t



dengan memiliki sebanyak ni faktor dari n faktor x1 yang ada, kemudian memilih n2 faktor dari n – n1 sisa faktor x2 yang ada, dan seterusnya. Akhirnya akan dipilih sebanyak nt faktor xt dari sejumlah sisa n – n1 – n2 - ..... – nt-1 yang ada. Jadi dengan menggunakan prinsip perkalian akan diperoleh sejumlah.



) . . . ( n−n1−. .. nn ) ( .nn ) ( .n−n n 1



1



t −1



2



t



Suku yang berbentuk x n1 x n2 … x nt . Dan dengan menuliskan dalam bentuk 1



2



t



faktorial dapat ditunjukan dengan mudah bahwa jumlah ini besarnya sama dengan n! n = ( n1n … n t ) n1 ! n2 ! …n t ! 2



Sebagai contoh misalkan akan diekspansikan bentuk ( x1 + x 2 + . . . + x 5 )7 maka koefisien dari suku x 21 x 3 x 34 x 5 adalah 7!



(2 071 3 1 ) = 2! 0 ! 1 ! 3 ! 1! = 420 Sedangkan bila yang akan diekspansikan adalah bentuk



( 2 x 1−3 x2 +5 x 3 )6 2



maka koefisien dari suku x 31 x 2 x 23 adalah ( 3 61 2 ) 23 (−3 ) ( 5 ) = -36000



1.7 Teorema Binomial Newton



Teorema binomial Newton dibuktikan oleh Newton pada sekitar tahun 1676. Teorema ini merupakan perluasan dari teorema binomial biasa, dimana bentuk yang akan diekspansikan adalah bentuk (x+y) dimana  adalah sembarang bilangan riel, Jadi tidak perlu merupakan bilangan bulat tidak negatif lagi. Perbedaan dengan teorema binomial biasa adalah untuk bentuk  yang merupakan bilangan riel, ekspansi yang diperoleh akan menghasilkan suatu deret yang tidak hingga, sehingga masih harus dipertanyakan konvergensi dari deret tersebut untuk beberapa nilal tertentu dari x dan y. karena pembahasan dari konvergensi suatu deret adalah pembahasan yang sifatnya lebih mengarah pada mata kuliah kalkulus atau analisa matematik, maka disini hanya akan dipelajari beberapa hal khusus saja dari deret yang berbentuk yang sudah terjamin konvergensinya. Demikian pula bukti dari teorema Newton Ini dapat diketemukan pada banyak buku kalkulus lanjut yang ada. Teorema 1.5 (Binomial Newton): Misalkan  adalah suatu bilangan riel sembarang. Maka untuk setiap bilangan riel x dan y yang memenuhi



| xy| < 1, akan dipenuhi hubungan berikut Ini



∞



(x + y) = ∑ ¿ ¿¿ ) X k Y −k k=0



dimana ¿ ¿) didefinisikan sebagai ¿ ¿) =



(−1 )(−2 ) …(−k +1) k!



Hal khusus dimana nilal  merupakan suatu bilangan bulat positif n, maka untuk nilal k > n bentuk ¿ ¿) akan bernilai 0 dan rumus ekspansi akan menjadi n



(x + y)n = ∑ ¿ ¿¿) ❑k ❑n−k k=0



dan akan diperoleh rumus binomial yang telah dibicarakan sebelumnya.



2.



IDENTITAS KOMBINATORIK Dalam kombinatorik, terdapat satu identitas yang terkenal. Identitas itu dinamakan sebagai Identitas Kombinatorial. Identitas Kombinatorial n n C n+1 k =C k−1 +C k untuk 1    n.



a. Bukti identitas Kombinatorial Secara Aljabar Identitas di atas bisa dibuktikan secara aljabar secara induktif (dimulai dari hasil akhir). Kita akan mulai dari kesimpulan. Lalu, dijabarkan secara aljabar untuk memperoleh hasil yang lebih sederhana. n n C n+1 k =C k−1 +C k



( n+1 ) ( n )( n−1 ) … ( n+2−k ) ( n+1−k ) ! ( n ) ( n−1 ) … ( n−k +2 ) ( n−k +1 ) ! = + k ! ( n+1−k ) ! ( k−1 ) ! ( n−k +1 ) ! ( n ) ( n−1 ) … ( n−k +1 ) ( n−k ) ! k ! ( n−k ) ! ( n+1 ) ( n )( n−1 ) …(n+ 2−k ) k!



=



( n ) ( n−1 ) …(n−k + 2) k ( k −1 ) ! k



+



( n ) ( n−1 ) …( n−k + 1) k! ( n+1 ) ( n )( n−1 ) …(n+ 2−k ) k!



=



( n ) ( n−1 ) …(n−k + 2) k (k −1)k !



+



( n ) ( n−1 ) …( n−k + 2)(n−k +1) k! n+1=k +n−k +1 n+1=n+1



Terbukti



b. Identitas Kombinatorial dengan Argumen Kombinatorial Misalkan ada sebuah himpunan X sebanyak n unsur. X = { a 1 , a2 , a3 , … , an } Jika di himpunan ini ditambahkan 1 unsur lagi, yaitu {a n+1}, maka berapa banyak kombinasi yang dapat dibentuk atas k unsur? Pertanyaan di atas dapat dijawab dengan 2 cara:



Cara I: Dengan menambahnya elemen {a n+1}, maka bertambah 1 menjadi n+1. banyak kombinasi yang terbentuk adalah C n+1 k Cara II: Pisah menjadi 2 kejadian yang saling lepas: (i). kombinasi yang mengandung {a n+1} (ii). kombinasi yang tidak mengandung {a n+1} Pada kejadian (i), kita menyimpan unsur {a n+1}, lalu tinggal menentukan banyaknya kombinasi dari { a 1 , a2 , a3 , … , an } atas (k-1) unsur. (menarik satu karena kita sudah menyimpan unsur {a n+1}). Jadi, banyaknya kombinasi kejadian ini pada saat C nk−1 Pada kejadian (ii), kita membuang unsur {a n+1}. Lalu kita tinggal menentukan kombinasi dari



{a 1 , a2 , a3 , … , an }



atas k unsur. Jadi,



banyaknya kombinasi kejadian ini C nk Dari kedua cara di atas, hasilnya sama, maka dapat disimpulkan bahwa: n n C n+1 k =C k−1 +C k



Terbukti



Argumen untuk membuktikan teorema ini disebut dengan argumen kombinatorial. Contoh : Hitunglah C 2009 +C32008 +C2007 +…+C 33 3 3 Jawab : Ingat identitas sebelumnya itu n n C n+1 k =C k−1 +C k



Tambahkan k dengan 1 n n C n+1 k+1=C k +C k+1



Pindahkan C nk+1 Maka Hasilnya : n C nk = C n+1 k+1−¿ C k+1



Kembali ke soal. Kita dapat menyederhanakan soal di atas sebagai



n



∑ C ik dimana n=2009 dan k=3 i=k



n



i



Jabarkan ∑ C k i=k



n



∑ C ik = C kk + Ckk +1+ Ckk +2+ …+C nk i=k



a Ubah setiap suku C abmenjadi C a+1 b+1−C b +1 (kecuali suku pertama) n



k+1 k+3 k+2 n +1 n ∑ C ik = 1+C k+2 k+1 −C k+1 +C k+1 −C k+1 +C k +1−C k+1 i=k n



∑ C ik = C n+1 k+1 i=k



Lalu, substitusikan n = 2009 dan k=3, maka diperoleh C 2009 +C32008 +C2007 +…+C 33 = C 2010 3 3 4



2.1 Melihat lebih dalam pada Identitas Kombinatorik Contoh : Bandingkan dua bukti identitas berikut. Perhatikan bahwa pendapat kombinatorik lebih memperhatikan pada artian identitas dari pada bentuk aljabarnya.



 n   n  1   n  1     r r  1      r  (Identitas Pascal) Bukti: metode 1: pembuktian secara aljabar  n  1  n  1  n  1 !  n  1 !      r  1   r   r  1 ! n  r  ! r ! n  r  1 !



   



 n  1 ! r 







 n  1 !(n  r )



r.(r  1)!(n  r )! r !(n  r )(n  r  1)!



 n  1 ! r    n  1 !(n  r ) r !(n  r )!



 n  1 ! r  n  r  r !(n  r )!



 n  1 ! n  r !( n  r )!







 n !



 n   r !( n  r )!  r 



Dari kedua pembuktian tersebut, kita ketahui bahwa pendapat kombinatorik digunakan berdasarkan pada pandangan bahwa dua sisi identitas sebagai suatu cara penghitungan beberapa (multi)himpunan yang terpisah. Pemikiran seperti itu berguna dalam membuktikan banyak identitas yang melibatkan koefisien binomial. Pada identitas seperti itu, sering lebih mudah untuk melihat bahwa salah satu sisi menyatakan banyaknya (multi)himpunan dalam beberapa situasi. Triknya yaitu dengan melihat bagaimana sisi yang lainnya menyatakan suatu cara yang terpisah dalam menghitung koleksi yang sama dari (multi)himpunan tersebut. metode 2 : pembuktian secara kombinatorik.



n    r  , artinya banyaknya himpunan bagian yang memuat r anggota dari himpunan yang memuat n anggota (misalkan, S =



 x1 , x2 ,..., xn  ). Begitu juga



 n  1   dengan bentuk yang ada di sebelah kanan,  r  1  dan



 n  1    r .



 n  1    r  1  , artinya banyaknya himpunan bagian yang memuat (r-1) anggota dari himpunan yang memuat (n-1) anggota (misal, S-{ xn } =



 x1 , x2 ,..., xn 1 ).



 n  1    r  , artinya banyaknya himpunan bagian yang memuat r anggota dari himpunan yang memuat (n-1) anggota.



Sehingga diperoleh himpunan bagian yang memuat xn atau yang tidak memuat xn . Ada sebanyak



C  n  1, r  1



himpunan bagian yang memuat xn yang banyak



anggotanya sejumlah r-anggota. Dengan menghilangkan 1 anggota yaitu xn dari himpunan bagian tersebut, maka didapatkan himpunan bagian yang memiliki (r-1) anggota. Sehingga diperoleh semua himpunan bagian dari



 x1 , x2 ,..., xn 1 Ada



C  n  1, r 



yang anggotanya sebanyak (r-1).



memuat



himpunan bagian yang anggotanya sebanyak r yang tidak



xn , karena pada kasus ini semua r anggota berasal dari



 x1 , x2 ,..., xn 1 .



Dengan menggunakan aturan penjumlahan, sisi sebelah



kanan juga berarti banyaknya r-anggota himpunan bagian dari n-anggota



 x1 , x2 ,..., xn  .



Contoh : S   x, y , z , u , v Misalkan n  5 , r  3 , dan . Tunjukkan bahwa :



5  4  4        3  2   3 Perhatikan bahwa: Kombinasi-3 di S adalah: {x,y,z}, {x,y,u}, {x,y,v}, {x,z,u}, {x,z,v}, {x,u,v},{y,z,u}, {y,z,v}, {y,u,v}, {z,u,v}. (Ini berarti):



5    10  3 S adalah himpunan dengan 5 objek. Buang 1 objek, misalkan x.



Kombinasi-3 di S yang memuat x : {x,y,z}, {x,y,u}, {x,y,v}, {x,z,u}, {x,z,v}, {x,u,v}. Kemudian penghapusan x dari Kombinasi-3 di S yang memuat x, menghasilkan: {y,z}, {y,u}, {y,v}, {z,u}, {z,v}, {u,v}, hasil ini merupakan kombinasi-2 dari {y,z,u,v}. (Ini berarti):



 4    2 Kombinasi-3 di S yang tidak memuat x :{y,z,u}, {y,z,v}, {y,u,v}, {z,u,v}. Hasil ini berarti merupakan kombinasi-3 dari {y,z,u,v}. (Ini berarti):



 4    3 Dengan kaidah penjumlahan maka diperoleh:



 4  4     64  2  3 5  4  4      Jadi, diperoleh:  3   2   3 



Contoh Bandingkan dua bukti identitas berikut. Perhatikan bahwa pendapat kombinatorik lebih memperhatikan pada artian identitas dari pada bukti dengan induksi.



n  n  n n       ...     2 0 1  n Bukti: metode 1 : dengan menggunakan induksi matematika. C 0, 0   1  20 1. untuk n  0 , maka  . Jadi benar untuk



0 C  0,0      20 0 2. Andaikan benar untuk n  k berlaku



k  k  k  k       ...     2 0 1 k       . Akan ditunjukkan benar untuk n  k  1



 k  1  k  1   k  1 k 1     ...   2  0   1   k  1 Bukti:



 k   k  k  2k 1  2.2k  2        ...     k   0 1 k k  k  2    2    ...  2   0 1 k  k   k    k   k    k   k    k   k                     ...           0    0   1    1   2    k  1   k    k  dengan menggunakan identitas pascal, persamaan diatas menjadi  k   k    k   k   k   k    k   k                    ...          0 0 1 1 2 k  1               k   k    k   k  1   k  1  k  1  k        ......     0  1   2   k  k



 k   k   k  1   k  1      1  0   k   0   k  1 ,



Karena



maka



 k  1   k  1  k  1 2k 1      .....     0   1   k  1 metode 2: dengan menggunakan kombinatorik. n Bagian sebelah kanan (yaitu: 2 ) adalah banyaknya himpunan bagian



dari himpunan yang anggotanya sebanyak n. Cara lain untuk menghitung banyaknya



himpunan



bagian



adalah



dengan



menggunakan



aturan



penjumlahan untuk menyelesaikan masalah dalam n+1 kasus: himpunan kosong; subset dengan satu anggota; …; subset dengan n anggota. Pilih satu himpunan bagian yang anggotanya sebanyak r anggota. Ini sama saja dengan memilih r anggota dari n anggota tanpa ada pengulangan. Jadi,



kasus pertama dapat diselesaikan dengan diselesaikan dengan



C  n,1



C  n, 0 



cara, kasus kedua dapat



cara, dan seterusnya hingga kasus ke-(n+1).



Dengan menggunakan aturan penjumlahan maka banyaknya himpunan bagian adalah



C  n, 0  C  n,1 C n, n  + +…+  . (ini sama dengan sisi sebelah kiri)



n n n n       ...     2 n Jadi, diperoleh:  0   1  contoh untuk metode 2: Misal



S   x, y , z



3 . Banyaknya himpunan bagian dari S adalah 2  8 .



 3  3  3   3 3       2 Akan ditunjukkan  0   1   2   3  Mencari himpunan bagian



S   x, y , z 



:



 3   Kasus 1: A:= { }, n(A) = 1  0 



Kasus 2:



B :   x ,  y ,  z 



 3   , n(B) = 3  1 



 3   Kasus 3: C:= { {x,y}, {x,z}, {y,z} }, n(C) = 3  2   3   Kasus 4: D:= { {x,y,z}}, n(D) = 1  3  Jadi, banyaknya himpunan bagian dari S adalah



 3   3  3   3 3             1 3  3 1  8  2 n(A) + n(B) + n(C) + n(D) =  0   1   2   3   n  m   n   n  r           m  r   r   m  r  Contoh :



Dari sekelompok orang yang berjumlah n orang, akan dibentuk subgrup yang beranggotakan m orang. Dari subgrup ini akan dipilih r pemimpin. Ada berapa cara pemilihan ini dapat dilakukan? Kita dapat menghitungnya dalam dua cara. Cara yang pertama adalah sebagai berikut.



n   1. Kita dapat memilih subgrup m orang dari n orang sebanyak  m  cara.  m   2. Kita dapat memilih r pemimpin dari subgrup tersebut sebanyak  r  cara Dengan aturan perkalian maka secara keseluruhan dapat dilakukan dengan



 n  m      m  r  cara. Cara kedua dari pemilihan tersebut adalah sebagai berikut.



n   1. Kita dapat memilih r pemimpin untuk subgrup sebanyak  r  cara. 2. Kita dapat memilih anggota subgrup selain pemimpin (m-r) sebanyak



 nr    m r Dengan aturan perkalian maka secara keseluruhan dapat dilakukan dengan



 n  n  r      r  m  r  cara. Bukti:  n  m  n! m! .      m  r  m ! n  m  ! r ! m  r  !







m !n ! r !m ! n  m  !(m  r )!







n! r ! n  m  !(m  r )!



 n  n  r  n! (n  r )! .     r  m  r  r ! n  r  !  m  r  !(n  r  m  r )!







n! 1 . r ! ( m  r )! n  m  !







 n m n!     r ! n  m  !(m  r )!  m   r 



Contoh : Banyak cara membentuk subgrup dengan anggota 4 orang dari 8 orang



8   sebanyak  4  cara.  4   Banyak cara memilih 2 pemimpin dari subgrup sebanyak  2  cara Dengan aturan perkalian maka secara keseluruhan dapat dilakukan dengan Cara Pertama :



 8  4      4  2  cara.  8  4  8! 4! 8  7  6  5  4! 4  3  2 .  .  70  6  420     4!4  3  2 2!2  4  2  4!4! 2!2! Cara Kedua :



8   Banyak cara memilih 2 pemimpin dari 8 orang sebanyak  2  cara. 8 2   Banyak cara memilih anggota subgrup selain pemimpin sebanyak  4  2  Dengan aturan perkalian maka secara keseluruhan dapat dilakukan dengan



 8  8  2      2  4  2  cara.



 8  6  8! 6! 8  7  6! 6  5  4! .  .  28 15  420     2!6! 2!4!  2  2  2!6! 2!4! 2.2 Bukti dengan induksi matematika: 1. untuk n  1 , maka



1  1 1 y1 k    x 0 y10    x1 y11  y  x   x  y  k 0   0  1 . 1



1



  k x



k



Jadi benar untuk n  1 , berlaku



 x  y



1 1    x k y1 k k 0  k 



1



2. Andaikan benar untuk n  p berlaku



 x  y



p



p  p    x k y p  k k 0  k  .



Akan ditunjukkan benar untuk n  p  1 berlaku:



 x  y



p 1



p 1  p  1 k p 1k   x y k 0  k 



bukti:



 x  y p   x  y  x  y p 1



 p  p  k pk    x  y     x y   k 0  k    p  p   p  p   x    x k y p k   y    x k y p  k   k 0  k    k 0  k    p  p   p  p      x  x k y p  k      x k y p k  y   k 0  k    k 0  k    p  p   p  p      x k 1 y p  k      x k y p 1k   k 0  k    k 0  k   p 0  p 1  p    p  p   p  p     x k 1 y p  k    x k 1 y p  k      x k y p 1 k    x k y p 1 k  k p  k  k 0  k   k 0  k    k 1  k   p 1    p  p   p   x p 1    x k 1 y p  k      x k y p 1k  y p 1  k 0  k     k 1  k  



Kemudian ganti nilai k pada



 x  y



p 1



p 1



 p



k 0



 



  k x



k 1



y p k dengan (k-1) maka diperoleh



p    p  k p 1 k   p  p  k p 1 k   x p 1     y p 1       x y x y k 1  k  1    k 1  k  



p  p   p   k p 1k  x p 1     y p 1     x y k  1 k k 1    



Dengan menggunakan identitas pascal diperoleh:



 x  y



p 1



p p 1  p   p   k p 1 k  p  1 k p 1k p 1  x p 1     x y  y       x y k 1  k  1   k   k 0  k 



 x  y Jadi,



p 1



p 1  p  1 k p 1k   x y k 0  k 



Jadi berdasarkan induksi matematika maka terbukti bahwa:



 x  y



n



n  n    x k y n k , n  , n  0 k 0  k 



2.3 Bukti secara kombinatorial: k nk Koefisien dari x y ,



dimana 0  k  n , adalah banyaknya cara dalam



memilih x pada k faktor (yang berarti memilih y pada (n-k) faktor) dari n faktor yang mungkin. Total semua cara yang mungkin untuk memilih



n C  n, k      k  . Jadi diperoleh, sebanyak k dari koleksi sebanyak n adalah



 x  y



n



n n    x k y n  k k 0  k 



ilustrasi: 2 2 misalkan n = 4, maka koefisien dari x y pada perkalian berikut:



 x  y



4



  x  y  x  y  x  y  x  y



faktor faktor 1 2



faktor 3



faktor 4



adalah banyaknya cara memilih x pada 2 faktor dari x pada 4 faktor (baik memilih x atau y akan memberikan hasil yang sama). perhatikan tabel berikut. Dipilih



Dipilih



faktor x 1,2



faktor y 3,4



1,3 1,4 2,3 2,4 3,4



2,4 2,3 1,4 1,3 1,2



2 2 Sehingga diperoleh koefisien dari x y yang terjadi dari hasil ekspansi



 4 4! 6   2 2!2!   adalah (yang artinya banyaknya cara memilih 2 objek yang berbeda dari suatu koleksi 4 ojek yang berbeda) x  y Tulis 



dengan



n



sebagai hasil kali n faktor yang masing-masing faktornya sama



 x  y .



(Teorema Multinomial)



 x1  x2  ...  xm 



n



n   r1 r2 rm   x1 x2 ...xm  r1 r2 ... rm  ,



sehingga



r1  r2  ...  rm  n Bukti: rm r1 r2 Koefisien dari x1 x2 ...xm adalah banyaknya cara memilih x1 dari r1 pada n



faktor, x2 dari r2 pada n  r1 faktor yang tersisa, x3 dari r3 pada n  r1  r2 faktor yang tersisa, …, dan xm dari rm pada n  r1  r2  ...  rm faktor yang



rm r1 r2 tersisa. Dengan demikian bilang dari hasil kali bentuk x1 x2 ...xm menjadi



sama. Berdasarkan prinsip perkalian dinyatakan dengan



 n  n  r1   n  r1  r2   n  r1  r2  ...  rm1      ...   r3 rm  r1  r2      perhatikan:  n  n  r1   n  r1  r2   n  r1  r2  ...  rm1   ...      r3 rm  r1  r2      



 n  r1  !   n  r1  r2  !  ...   n  r1  r2  ...  rm1  ! n!   n  r1  !r1 !  n  r1  r2  !r2 !  n  r1  r2  r3  !r3 !  n  r1  r2  ...  rm1  rm  !rm !







n! 1  r1 ! r2 !r3 !...rm 1 ! 0! rm !







n! r1 ! r2 !r3 !...rm !



   r1



n r2



  ... rm 



n      r1 r2 ... rm  disebut koefisien multinomial.



 x1  x2  ...  xm  Jadi diperoleh:



n



n   r1 r2 rm   x1 x2 ...xm  r1 r2 ... rm 