EKSPANSI MULTINOMIAL, KOMBINASI, DAN PERMUTASI

Seri berfikir kombinatorik

EKSPANSI MULTINOMIAL, KOMBINASI, DAN PERMUTASI Oleh: Sutopo Jurusan Fisika FMIPA UM [email protected]

Ditulis pada sekitar bulan Maret 2011. Diunggah pada 3 Desember 2011

PROBLEM Gambar di bawah ini menyatakan grid persegipanjang dari rute jalan. Anda diminta menelusuri jalan itu dari A ke B dengan menggunakan rute sedekat mungkin. Berapa banyak rute yang ada? Perumum hasil yang diperoleh untuk sebarang ukuran grid.

PEMBAHASAN Jika gerakan 1 langkah ke kanan dilambangi dengan huruf K dan gerakan 1 langkah ke atas dilambangi huruf A, maka lintasan yang ditunjukkan pada gambar di samping dinyatakan sebagai: (i) KAKKKAKAKKAAK Gerakan ke kanan menyusuri sisi bawah (sebanyak 8 langkah) kemudian dilanjutkan gerakan ke atas (sebanyak 5 langkah) juga akan sampai ke titik B. Lintasan yang dilalui dapat dinyatakan sebagai: (ii) KKKKKKKKAAAAA Panjang lintasan (ii) sama dengan panjang lintasan (i), yaitu 13 langkah. Komposisinya juga sama, yaitu 8K5A atau {K(8), A(5)}. Kedua lintasan tersebut merupakan lintasan terpendek, sebab semua jenis gerakannya langsung mengarah ke titik B. Bandingkan jika ada gerakan ke bawah atau ke kiri, maka panjang lintasan untuk mencapai titik B pasti lebih dari 13 langkah. Berdasarkan argument tersebut, maka lintasan terpendek untuk mencapai posisi B adalah lintasan yang “panjangnya” 13 langkah dan harus terdiri atas 8 langkah ke kanan dan 5 langkah ke atas.

Sutopo, Fisika UM

1

Ekspansi multinomial dan permutasi/kombinasi

Seri berfikir kombinatorik Lintasan-lintasan lainnya dapat dibentuk dengan membuat permutasi-13 dari {K(8), A(5)}. Banyaknya permutasi yang dihasilkan adalah

! ! !

= 1.287. Dalam bahasa “kombinatorik”,banyaknya lintasan

yang terjadi adalah sama dengan banyaknya cara “memilih 8 posisi dari 13 posisi yang disediakan ! × × × × 13 untuk menempatkan lambang K”, yaitu = = = 1.287, atau banyaknya cara ! ! × × × × 8 “memilih 5 posisi dari 13 posisi yang disediakan untuk menempatkan lambang A”, yaitu sebanyak ! 13 = = 1.287 macam lintasan. ! ! 5

Perluasan hasil di atas: Banyaknya lintasan terpendek untuk berpindah dari titik O(0,0) ke P(m,n) dalam suatu grid adalah +

+

=

Jika dalam pergerakan tersebut harus melewati titik lain, misalnya C(p,q), maka banyaknya lintasan adalah

+

×

− + −

−

=

+

ketika sampai di , setiap lintasan dari O ke

−

×

+ −

−

. Mengapa dikalikan? Jawab:

bertemu dengan semua lintasan dari

ke .

PEMBAHASAN TAMBAHAN 1. Seperti telah dibicarakan, persoalan tersebut sama dengan mencari banyaknya “kata” yang panjangnya ( + ) dan dibentuk dari huruf {K, D} yang masing-masing sebanyak dan . Banyaknya kata tersebut adalah sama dengan koefisien suku pada ekspansi binomial ( + ) =

, ∈

dengan

,

≡

! !

. Karena

!

=

−

maka

! !

!

=

! !(

)!

=

=

=

! !(

.

)!

Jika K dan D diganti dengan angka 1, maka diperoleh identitas: =2 . Apa arti bilangan-bilangan tersebut? Dalam konteks ini, bilangan 2 menyatakan banyaknya lintasan yang dihasilkan dari gerakan n langkah dengan masing-masing langkah berarah ke kanan

Sutopo, Fisika UM

2



, sebagaimana telah disebutkan, menyatakan banyaknya lintasan

atau ke depan. Bilangan

sepanjang n langkah yang terdiri atas langkah ke kanan dan ( − ) langkah ke depan. Bilangan 2 dan koefisien

,

dapat digunakan untuk menghitung berbagai fenomena, antara lain

sebagai berikut. 2

No

,

1

Banyaknya kata yang panjangnya n karakter dan dibentuk dari dua huruf berbeda, misal {B,I}

2

Banyaknya bilangan asli n digit yang dibentuk dari dua bilangan asli berbeda, misal {1,2} Banyaknya cara mendistribusikan n bola berlabel dalam dua wadah berlabel. Lihat gambar di bawah.

3

4

Banyaknya himpunan bagian dari suatu himpunan yang beranggotakan elemen

5

Banyaknya urutan mencetak gol dalam suatu pertandingan sepak bola jika total gol yang tercipta selama pertandingan sebanyak n gol.

=

! !

!

Banyaknya kata n karakter yang memuat huruf {B, I} ) dengan komposisi huruf B ( ) , I ( , atau ( ) ( ) B ,I Banyaknya bilangan n digit dengan komposisi angka: ) ) ( ) 1( ) , 2( , atau 1( ,2 Banyaknya cara mendistribusikan n bola berlabel dalam dua wadah berlabel sehingga wadah pertama berisi bola dan wadah kedua berisi = ( − ) bola, atau sebaliknya. Banyaknya himpunan bagian yang memiliki anggota = − (atau = − ) yang diambil dari suatu himpunan yang beranggotakan elemen. Banyaknya urutan mencetak gol jika sampai akhir pertandingan tim A mencetak gol dan tim B mencetak = ( − ) gol, atau sebaliknya.

Contoh mendistribusikan 3 bola berlabel pada dua wadah berlabel, atau urutan terciptanya gol pada suatu pertandingan sepakbola jika jumlah gol yang tercipta selama pertandingan sebanyak 3 gol.  I

II

 I

 II

I

 II

 I

 II

 I

 II

 I

 II

 I

 II

 I

 II

2. Banyaknya suku dalam ekspansi binomial sama dengan banyaknya variasi notasi koefisien dengan bergerak dari 0 sampai n. Jadi banyaknya suku adalah (n+1). Tetapi, bilangan itu juga harus sama dengan “banyaknya susunan ( , ) yang merupakan penyelesaian persamaan + = , 0 ≤ ≤ , dengan = 1, 2.” Proposisi ini ekivalen dengan “banyaknya cara mendistribusikan n bola tak berlabel dalam dua wadah berlabel. Dengan demikian, setidaknya ada tiga macam fenomena yang diwakili oleh bilangan ( + 1), yaitu:  Banyaknya suku yang berbeda dalam ekspansi binomial orde n.  Banyaknya susunan ( , ) yang merupakan penyelesaian persamaan + = , 0≤ ≤ .  Banyaknya cara mendistribusikan n bola tak berlabel dalam dua wadah berlabel.

Sutopo, Fisika UM

3



3. Berapa banyaknya cara mendistribusikan n bola tak berlabel dalam k wadah berlabel? Berdasarkan hasil nomor 3, persoalan ini setara dengan (i) banyaknya suku yang berbeda dalam ekspansi “k-nomial” orde n, dan (ii) banyaknya susunan ( , , … , ) yang merupakan penyelesaian persamaan + + ⋯+ = , 0≤ ≤ , ∈ . Jika bola-bola tersebut direpresentasikan sebagai huruf O, dan wadah-wadahnya direpresentasikan sebagai suatu kotak yang dibuat dari para OOO OO OOOO O yang disekat-sekat dengan garis vertical, …. (seperti pada gambar), maka persoalan tadi dapat diganti dengan “mencari banyaknya Representasi wadah dan bola beserta salah satu contoh kata yang panjangnya (n+k+1) karakter dan mendistribusikan n bola ke dalam k wadah. Banyaknya garis vertical untuk membuat k wadah adalah (k+1) dibentuk oleh sejumlah huruf O (sebanyak n buah) dan garis vertical (sebanyak k+1) dengan ketentuan bahwa karakter pertama dan terakhir pada kata-kata tersebut harus berupa garis vertikal” Karena karakter pertama dan terakhir harus berupa garis vertical, maka hanya ( + 1 − 2 = − 1) garis vertical yang bebas diubah-ubah posisinya. Dengan kata lain, persoalan diubah lagi menjadi: “mencari banyaknya kata yang panjangnya ( + − 1) karakter dan dibentuk oleh n buah huruf O dan ( + 1 − 2 = − 1) garis vertical”. Banyaknya huruf yang dihasilkan sama dengan banyaknya cara memilih n posisi dari ( + − 1) posisi yang tersedia untuk menempatkan huruf O, atau setara dengan itu, banyaknya cara memilih ( − 1) posisi dari ( + − 1) posisi yang tersedia ( )! + −1 untuk menempatkan garis vertikal |, yaitu = . )! !( −1 Dapat disimpulkan: Untuk sebarang   

∈ , dan 1 ≤

≤ , maka

+

( −1 = −1

)! !(

)!

menyatakan:

Banyaknya suku dengan notasi koefisien yang berbeda pada ekspansi “multinomial” ( + + ⋯+ ) Banyaknya susunan ( , , … , ) yang merupakan penyelesaian persamaan + +⋯+ = , 0≤ ≤ , ∈ Banyaknya cara mendistribusikan n bola tak berlabel dalam k wadah berlabel (boleh ada wadah yang dibiarkan kosong).

Sutopo, Fisika UM

4


Seri berfikir kombinatorik 4. Berapa banyaknya cara mendistribusikan n bola tak berlabel dalam k wadah berlabel jika tiap wadah minimal berisi satu bola? Masalah tersebut identik dengan mencari banyaknya sekuensi ( , , … , penyelesaian persamaan + +⋯+ = , 1≤ ≤ , ∈ .

) yang merupakan

Penyelesaian Karena setiap wadah harus berisi minimal satu bola, maka persoalan tersebut sama dengan mencari banyaknya cara mendistribusikan ( − ) bola tidak berlabel ke dalam wadah berlabel. Ini sama dengan mendistribusikan = ( − ) bola ke dalam wadah berlabel, yaitu + −1 = −1

−

+ −1 = −1

−1 . −1

Jika > maka tidak ada cara yang bisa dilakukan, sebab pasti ada wadah yang tidak terisi. Fakta tersebut diperkuat oleh rumus di atas. Berdasarkan formula tersebut, jika > maka ( − 1) > −1 ( − 1) sehingga = 0. Berarti tidak ada cara yang bisa dilakukan untuk memenuhi −1 persyaratan tiap wadah berisi minimal satu bola.

DISKUSI LEBIH SERIUUUSSS DAN MENDALAMMMMM Pembahasan di atas sepenuhnya berpijak pada definisi: Permutasi adalah susunan sejumlah objek dengan memperhatikan urutannya. Permutasi- berarti permutasi yang memuat karakter, atau objek, atau slot, atau posisi, dsb. Contoh, suku-suku di ruas kanan yang diperoleh dari ekspansi binomial ( + ) = + + + adalah permutasi-2, sebab masing-masing susunan memuat dua karakter dan urutan sangat diperhatikan (BA dibedakan dengan AB). Berpijak pada definisi itu, dan pembahasan sebelumnya, maka ungkapan ekspansi “multinomial”: (

+

) =

+ ⋯+

⋯ ∈

dengan

,

,…,

≡

! !

!…

!

,

,…,

…

dapat dieksplorasi lebih lanjut sebagai berikut.

1. Ruas kiri menyatakan “semesta pembicaraan” terhadap mana akan dibuat berbagai permutasidari elemen himpunan { , , … , }. Penggunaan kata permutasi- di sini sepenuhnya konsisten dengan definisi permutasi dan fakta bahwa setiap suku di ruas kanan terdiri atas karakter. Untuk meyakinkan hal ini, ambil contoh paling sederhana, yaitu suku pertama di mana = dan = 0, > 2. Suku tersebut adalah = … . Atau buatlah multinomial yang ×

Sutopo, Fisika UM

5


Seri berfikir kombinatorik lebih sederhana, misalnya ( + + ) = dimaknai sebagai kependekan dari AAAA, suku memuat 4 karakter.

+4 + 12 +6 + ⋯ + . Jika dimaknai sebagai AAAB dst, jelaslah bahwa setiap

2. Apa makna setiap suku di ruas kanan? Bentuk umum setiap suku di ruas kanan adalah ,

…

,…,

. Suku tersebut, secara keseluruhan, menyatakan ada

susunan (permutasi- ) yang di dalamnya memuat unsur-unsur yang masing, ,…, masing muncul sebanyak kali, = 1,2, … , . Contoh, untuk ekspansi ( + + ) , suku (6 ) menyatakan ada 6 susunan (permutasi-4) yang tersusun atas 2 huruf A dan 2 huruf B, yaitu: AABB, ABAB, ABBA, BBAA, BABA, BAAB. Jika dibahas secara parsial, maka nilai koefisien permutasi-n, sedangkan ( , ,…, sejumlah permutasi tadi dibuat.

menyatakan banyaknya , ,…, ) menyatakan komposisi unsur-unsur terhadap mana

3. Berapa banyaknya suku di ruas kanan pada ekspansi tersebut? Jawabnya adalah sama dengan banyaknya sekuensi yang dibuat dari penyelesaian persamaan: + + ⋯ + = ; ( )! + −1 0 ≤ ≤ , yaitu = . Sebagai contoh, banyaknya suku pada ekspansi )! !( −1 ( )! ( + + ) adalah = 15. )! !(

4. Berapa jumlahan koefisien di ruas kanan? Jawabnya dapat ditentukan dengan mengisi setiap = 1 untuk semua = 1,2, . . ; maka ruas kiri menghasilkan dan diperoleh identitas:

,

⋯ ∈

,…,

=

5. Apa yang dapat disimpulkan dari pembahasan no 3 & 4? Jawab: banyaknya permutasi- yang dihasilkan dari { , , … , } adalah sebanyak ; dan dari jumlah itu dapat dikelompokkan ke dalam

(

)! !(

)!

kelompok berdasarkan komposisi unsur-unsur yang ada di dalamnya. Untuk

kasus ( + + ) misalnya, banyaknya permutasi-4 yang dihasilkan adalah 3 = 81 macam, dan dapat dikelompokkan ke dalam 15 kelompok (masing-masing kelompok memiliki komposisi huruf yang berbeda). Perhatikan bahwa n adalah ukuran permutasi (misalnya, banyaknya huruf dalam suatu kata) dan k adalah banyaknya anggota himpunan dari mana permutasi dibuat, yaitu { , , … , }. Berdasarkan macam elemennya, ada kelompok yang di dalamnya memuat unsur yang muncul lebih dari sekali (sehingga terjadi pengulangan), dan ada kelompok yang semua unsurnya berbeda (tidak terjadi pengulangan). Kelompok yang disebutkan terakhir hanya akan terjadi jika

Sutopo, Fisika UM

6


Seri berfikir kombinatorik ≤ . Sebagai contoh, semua kelompok yang dihasilkan dari ( + + ) mengandung pengulangan, sedangkan yang dihasilkan dari ( + + ) ada kelompok yang tidak !

mengandung pengulangan, yaitu kelompok dalam suku

. Banyaknya permutasi dalam

! ! !

kelompok ini sebanyak 3! = 6 macam; yaitu: ABC, BCA, CAB, ACB, CBA, BCA. Secara umum bisa ditunjukkan bahwa, jika = , maka ada satu kelompok permutasi- , yang dihasilkan dari ( , , … , ) , yang di dalamnya tidak terjadi pengulangan. Kelompok itu muncul pada suku 1,1, … ,1 … (yaitu pada saat semua unsur muncul satu kali). Banyaknya permutasi pada kelompok ini adalah ! = !, seperti yang diduga!! Jika

<

maka ada

! !(

)!

macam unsur dari { ,

suku (kelompok) yang memuat

,…,

},

masing-masing muncul satu kali, sehingga dalam masing-masing kelompok itu tidak terjadi permutasi dengan pengulangan (pembuktian diuraikan pada nomor 6 di bagian berikutnya). Banyaknya permutasi- pada setiap kelompok tersebut adalah

!

= ! Jadi, total banyaknya

! !… ! ×

permutasi- yang tidak mengandung pengulangan adalah

! )!

!(

× !=

! (

)!

= ,

. Jika

hasilnya sebanyak ! (seperti dinyatakan sebelumnya) Dapat dirangkum: Banyaknya permutasi- (yang tidak mengandung pengulangan) yang dibuat dari suatu himpunan yang beranggotakan

≥

!

elemen, dilambangi ( , ),

(

)!

.

(SEPERTI YANG BANYAK DITULIS DALAM BUKU-KUKU TEKS!!!) Sebagai contoh, ambil kasus sederhana misalnya dari ekspansi ( + = 3. Ekspansi trinomial itu adalah: ( + Ada

+ ) = !

2 2,0,0

+

2 0,2,0

2 2,0,0

+

+

+ ) , yaitu

2 1,1,0

+

2 1,0,1

= 2 dan 2 0,1,1

+

= 3 kelompok yang tidak mengalami pengulangan (yaitu 3 suku terakhir). Total

! !

banyaknya permutasi dari ketiga kelompok itu = 3 × 6. Pembuktian bahwa jika dari { ,

,…,

≤

maka ada

! )!

!(

! ! !

=

! !

2! = (

! )!

=(

! )!

suku (kelompok) yang memuat

. macam unsur

} dengan masing-masing unsur muncul satu kali.

Sebagaimana telah dijelaskan, bahwa banyaknya suku pada ekspansi “k-nomial orde n” adalah (

)! !(

)!

dengan

, yang diperoleh dengan menyelesaikan persamaan menyatakan pangkat dari

Sutopo, Fisika UM

+

+⋯+

= ,

≥0

dalam suatu suku.

7


Seri berfikir kombinatorik Dengan argumen serupa, persoalan tadi dapat dipecahkan dengan menyelesaikan persamaan: +

+⋯+

= ,

≤ 1,

≤

Karena ≤ maka ada macam yang bernilai 1 dan ada ( − ) macam Salah satu susunan yang memenuhi kondisi tersebut adalah sebagai berikut: 0

0 0 …. sebanyak −

0

1

1 1 … sebanyak n

Banyaknya permutasi dengan komposisi seperti itu adalah

yang bernilai 0.

1

(

)!

(

)! !

=

! [TERBUKTI] )! !

(

7. Apa yang terjadi jika urutan unsur-unsur dalam setiap susunan tidak dianggap penting? Jika urutan tidak penting, maka semua susunan (permutasi) yang dihasilkan dalam setiap kelompok (suku) adalah sama, sehingga setiap suku dipandang sebagai satu susunan. Jadi, dalam hal ini, banyaknya susunan yang dihasilkan dari ekspansi adalah sama dengan banyaknya suku dalam ekspansi tersebut, yaitu

(

)! )!

!(

.

Jika suatu susunan yang tidak memperhatikan urutannya disebut kombinasi, maka banyaknya kombinasi- yang dibentuk dari anggota-anggota himpunan { ,

,…,

}, adalah

(

)! !(

)!

Banyaknya kombinasi itu termasuk kombinasi dengan pengulangan, yaitu suatu susunan di mana paling sedikit ada satu unsur { , , … , } yang muncul lebih dari sekali. Misal, ekspansi ( + ) menghasilkan kombinasi: , , dan . Dua yang disebut pertama adalah kombinasi dengan pengulangan. Kombinasi tanpa pengulangan hanya akan terjadi jika ≤ . Jika = maka hanya ada satu kombinasi, yaitu ( … ) itu sendiri. Untuk ≤ , banyaknya suku yang di dalamnya tanpa !

terjadi pengulangan adalah

!(

)!

(sudah ditunjukkan di nomor 6). Karena setiap suku

menyatakan suatu kombinasi- yang khas, maka banyaknya kombinasi- yang dihasilkan dari { ,

,…,

Sutopo, Fisika UM

} adalah

! !(

)!

. Selanjutnya ditulis secara

8

−

≡

! !(

)!

.


Seri berfikir kombinatorik KESIMPULAN: Dari ekspansi k-nomial orde n: (

+

) =

+ ⋯+

…

,

,

,…,

…

Dapat diperoleh: Kombinasi-n:  Sebanyak

Permutasi-n:

(

)! !(

)!

 Sebanyak

susuna,

 Masing-masing susunan berbentuk (

) (

)

…

(

)

dengan

+

susunan,

 Yang dapat dikelompokkan menjadi …+

=

(

)! !(

)!

kelompok.  Bentuk umum tiap kelompok: … dengan , ,…, + …+ =  Jika > , semua susunan yang dihasilkan mengandung pengulangan !  Jika ≤ , ada ( )! susunan yang tidak

 Jika > , semua susunan yang dihasilkan mengandung pengulangan !  Jika ≤ , ada susunan yang tidak )! !(

mengandung pengulangan

mengandung pengulangan

Catatan: Tulisan tersebut dibuat berdasarkan pemikiran logis semata, tidak merujuk pada kaedah/teorema matematika tertentu, karena penulis memang tidak tahu teori-teori itu, jika memang ada. Ini adalah pemikiran bebas orang fisika yang mencoba memahami hakekat permutasi & kombinasi.

Sutopo, Fisika UM

9


EKSPANSI MULTINOMIAL, KOMBINASI, DAN PERMUTASI

Recommend Documents