KOMBINASI PERMUTASI

Permutasi

Di dalam ilmu matematika permutasi diartikan sebagai sebuah konsep penyusunan sekumpulan objek/angka menjadi beberapa urutan berbeda tanpa mengalami pengulangan.

Di dalam permutasi, urutan sangat diperhatikan. setiap objek yang dihasilkan harus berbeda antara satu dengan yang lain. kita ambil contoh, urutan huruf ({ABC} berbeda dengan {CAB} begitu juga dengan {BAC) dan {ACB}). Rumus untuk mencari banyaknya permutasi n unsur jika disusun pada unsur k di mana k ≤ n adalah:

Rumus Permutasi

P(n,k) =   n!  

     (n-k)!

Contoh

Berapakah banyaknya bilangan yang dibentuk dari 2 angka berbeda yang dapat kita susun dari urutan angka 4, 8, 2, 3, dan 5?

Pembahasan:

pertanyaan di atas dapat disimpulkan sebagai permutasi yang terdiri dari 2 unsur yang dipilih dari 5 unsur maka dapat dituliskan sebagai P(5,2). tinggal kita masukkan ke dalam rumus.

P(5,2) =   5!     = 5x 4 x 3 x 2 x 1 = 120 = 20

              (5-2)!        3 x 2 x 1              6

Maka ada 20 cara yang dapat dilakukan untuk menysyn bilangan tersebut menjadi 2 angka yang berbeda-beda (48, 42, 43, 45, 84, 82, 83, 85, 24, 28, 23, 25, 34, 38, 32, 35, 54, 58, 53, 52).

Kombinasi

kombinasi merupakan sebuah kumpulan dari sebagian atau seluruh objek dengan tidak memperhatikan urutannya. di dalam kombinasi, {AB} dianggap sama dengan {BA} sehingga sebuah kombinasi dari dua objek yang sama tidak dapat terulang.

•         Kombinasi r elemen dari n elemen adalah :

F jumlah pemilihan yang tidak terurut r elemen yang diambil dari n buah elemen

•         Kombinasi merupakan bentuk khusus dari permutasi

•         Perbedaan permutasi dengan kombinasi :

F Permutasi : urutan kemunculan diperhitungkan

F Kombinasi : urutan kemunculan diabaikan

•         Jumlah pemilihan yang tidak terurut dari r elemen yang diambil dari n elemen disebut dengan kombinasi-r :

C(_n,r) = _nC_r = ⁿC_r =     n!     

                                r!(n-r)!

•         C(n,r) dibaca “n diambil r” à r objek diambil dari n buah objek

Contoh Soal

Manuel Pelegrini membawa 16 pemain saat Manchester City melawan Liverpool di Etihad Stadium. 11 orang diantaranya akan dipilih untuk bermain pada babak pertama. jika kita tidak memperhatikan posisi pemain, berapakah banyaknya cara yang dapat diambil oleh pelatih untuk memilih pemain?

Pembahasan:

Karena tidak mementingkan posisi pemain, maka kita gunakan rumus kombinasi:

¹⁶C₁₁ =       16!        =  16 x 15 x 14 x 13 x 12 x 11!  

              11!(16-11)!                      11!5!                          

=          524160         =  524160  = 4368

     5 x 4 x 3 x 2 x 1          120
Permutasi dan Kombinasi Bentuk Umum

•         Misal n buah bola tidak seluruhnya berbeda warna (ada beberapa bola yang warnanya sama)

                        n₁ bola diantaranya berwarna 1

                        n₂ bola diantaranya berwarna 2

                        …

                        n_k bola diantaranya berwarna k

            Sehingga n₁ + n₂ + … + n_k = n. Bola-bola tersebut dimasukkan ke dalam n buah kotak, masing-masing kotak berisi paling banyak 1 buah bola.

  Berapa banyak jumlah cara pengaturan n buah bola ke dalam kotak-kotak tersebut ?

•      Jika n buah bola dianggap berbeda semua, maka jumlah cara pengaturan n buah bola ke dalam n buah kotak adalah : P(n,n) = n !

•      Karena tidak seluruh bola berbeda maka pengaturan n buah bola :

                        n₁! cara memasukkan bola berwarna 1

                        n₂! cara memasukkan bola berwarna 2

                        …

                        n_k! cara memasukkan bola berwarna k

contoh

•      Berapa banyak string yang dapat dibentuk dengan menggunakan huruf-huruf dari kata MISSISSIPPI ?

•      S = {M,I,S,S,I,S,S,I,P,P,I}

                        Huruf M = 1 buah

                        Huruf I = 4 buah

                        Huruf S = 4 buah

                        Huruf P = 2 buah

            Sehingga n = 1 + 4 + 4 + 2 = 11 buah à jumlah elemen himpunan S

•      Ada 2 cara :

                      i.        Permutasi :

                        Jumlah string = P(n; n₁,n₂,n₃,n₄) = P(11; 1,4,4,2) = 34650 buah

1. Kombinasi :

                        Jumlah string = C(11,1) C(10,4) C(6,4) C(2,2) = 34650 buah

Persoalan kombinasi dapat dipandang sebagai cara memilih r buah elemen dari n buah elemen yang ada, tetapi urutan elemen di dalam susunan hasil pemilihan tidak penting

            Contoh :

            Misal sebuah kelompok memiliki 20 orang anggota, kemudian dipilih 5 orang sebagai panitia, dimana panitia merupakan kelompok yang tidak terurut (artinya setiap anggota di dalam panitia kedudukannya sama).

            Sehingga banyaknya cara memilih anggota panitia yang terdiri dari 5 anggota panitia yang terdiri dari 5 orang anggota adalah :

INDUKSI MATEMATIKA

Pengertian Induksi Matematika

Induksi Matematika merupakan suatu teknik yang dikembangkan untuk membuktikan pernyataan. Induksi Matematika digunakan untuk mengecek hasil proses yang terjadi secara berulang sesuai dengan pola tertentu. Indukasi Matematika digunakan untuk membuktikan universal statements " n Î A   S(n) dengan A Ì N  dan N adalah himpunan bilangan positif atau himpunan bilangan asli. S(n) adalah fungsi propositional.

Induksi matematika adalah suatu metode yang digunakan untuk memeriksa validasi suatu pernyataan yang diberikan dalam suku-suku bilangan asli. Dalam pembahasan ini, kita akan menyatakan Prinsip Induksi Matematika dan memberikan contoh-contoh untuk mengilustrasikan bagaimana proses pembuktian dengan menggunakan induksi matematika.

Prinsip-prinsip Induksi Matematika

           1.     Induksi Sederhana.

Misalkan p(n) adalah pernyataan perihal bilangan bulat positif dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n. Untuk membuktikan pernyataan ini, kita hanya perlu menunjukkan bahwa:

             1.  p(1) benar, dan

  2.  Jika p(n) benar maka p(n + 1) juga benar, untuk semua bilangan bulat  positif n ³    1,

•      Langkah 1 dinamakan basis induksi, sedangkan langkah 2 dinamakan langkah
  induksi.
•     Langkah induksi berisi asumsi (andaian) yang menyatakan bahwa p(n) benar. Asumsi tersebut dinamakan hipotesis induksi. 
•    Bila kita sudah menunjukkan kedua langkah tersebut benar maka kita sudah membuktikan bahwa p(n) benar untuk semua bilangan bulat positif n.

Contoh 1.
Gunakan induksi matematik untuk membuktikan bahwa jumlah n buah bilangan ganjil positif pertama adalah n².

Penyelesaian:

(i)    Basis induksi: Untuk n = 1, jumlah satu buah bilangan ganjil positif pertama adalah 1² = 1. Ini benar karena jumlah satu buah bilangan ganjil positif pertama adalah 1.

(ii)   Langkah induksi: Andaikan p(n) benar, yaitu pernyataan

            1 + 3 + 5 + … + (2n – 1) = n²

adalah benar (hipotesis induksi) [catatlah bahwa bilangan ganjil positif ke-n adalah (2n – 1)]. Kita harus memperlihatkan bahwa p(n +1) juga benar, yaitu

1 + 3 + 5 + … + (2n – 1) + (2n + 1) = (n + 1)²

juga benar. Hal ini dapat kita tunjukkan sebagai berikut:

     1 + 3 + 5 + … + (2n – 1) + (2n + 1)

= [1 + 3 + 5 + … + (2n – 1)] + (2n +1)

= n² + (2n + 1)

= n² + 2n + 1

= (n + 1)²

Karena langkah basis dan langkah induksi keduanya telah diperlihatkan benar, maka jumlah n buah bilangan ganjil positif pertama adalah n².  

2.  Prinsip Induksi yang Dirampatkan

Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat  n ³ n₀. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:

            1. p(n₀) benar, dan

            2. jika p(n) benar maka p(n+1) juga benar,

               untuk semua bilangan bulat n ³ n₀,

Contoh 2.

Untuk semua bilangan bulat tidak-negatif n, buktikan dengan induksi matematik bahwa

2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹ - 1

Penyelesaian:

(i)       Basis induksi. Untuk n = 0 (bilangan bulat tidak negatif pertama), kita  peroleh:

2⁰ = 2⁰⁺¹ – 1. 

Ini jelas benar, sebab 2⁰ = 1

       = 2⁰⁺¹ – 1

= 2¹ – 1

= 2 – 1

= 1

(ii) Langkah induksi. Andaikan bahwa p(n) benar, yaitu

                        2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹ - 1

adalah benar (hipotesis induksi). Kita harus menunjukkan bahwa p(n +1) juga benar, yaitu

                        2⁰ + 2¹ + 2² + … + 2ⁿ + 2ⁿ⁺¹ = 2^{(n+1) + 1} - 1

juga benar. Ini kita tunjukkan sebagai berikut:

2⁰ + 2¹ + 2² + … + 2ⁿ + 2ⁿ⁺¹ = (2⁰ + 2¹ + 2² + … + 2ⁿ) + 2ⁿ⁺¹ = (2ⁿ⁺¹ – 1) + 2ⁿ⁺¹ (hipotesis induksi)

                                                                                                =  (2ⁿ⁺¹ + 2ⁿ⁺¹) – 1

                                                                                                = (2 . 2ⁿ⁺¹) – 1

                                                                                                = 2ⁿ⁺² - 1

                                                                                                = 2^{(n+1) + 1} – 1   

Karena langkah 1 dan 2 keduanya telah diperlihatkan benar, maka untuk semua bilangan bulat tidak-negatif n, terbukti bahwa 2⁰ + 2¹ + 2² + … + 2ⁿ = 2ⁿ⁺¹ – 1
 

3. Prinsip Induksi Kuat

Misalkan p(n) adalah pernyataan perihal bilangan bulat dan kita ingin membuktikan bahwa p(n) benar untuk semua bilangan bulat  n ³ n₀. Untuk membuktikan ini, kita hanya perlu menunjukkan bahwa:

            1. p(n₀) benar, dan

2. jika p(n₀ ), p(n₀+1), …, p(n) benar maka p(n+1) juga benar untuk semua bilangan bulat  n ³ n₀,.

Contoh 4.

Bilangan bulat positif disebut prima jika dan hanya jika bilangan bulat tersebut habis dibagi dengan 1 dan dirinya sendiri. Kita ingin membuktikan bahwa setiap bilangan bulat positif n (n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima. Buktikan dengan prinsip induksi kuat.

Penyelesaian: 

Basis induksi. Jika n = 2, maka 2 sendiri adalah bilangan prima dan di sini 2 dapat dinyatakan sebagai perkalian dari satu buah bilangan prima, yaitu dirinya sendiri.

Langkah induksi. Misalkan pernyataan bahwa bilangan 2, 3, …, n dapat dinyatakan sebagai perkalian (satu atau lebih) bilangan prima adalah benar (hipotesis induksi). Kita perlu menunjukkan bahwa n + 1 juga dapat dinyatakan sebagai perkalian bilangan prima. Ada dua kemungkinan nilai n + 1:

(a)           Jika n + 1 sendiri bilangan prima, maka jelas ia dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima.

(b)          Jika n + 1 bukan bilangan prima, maka terdapat bilangan bulat positif a yang membagi habis n + 1 tanpa sisa. Dengan kata lain,

            (n + 1)/ a = b   atau (n + 1) = ab

yang dalam hal ini, 2 £ a £ b £ n. Menurut hipotesis induksi, a dan b dapat dinyatakan sebagai perkalian satu atau lebih bilangan prima. Ini berarti, n + 1 jelas dapat dinyatakan sebagai perkalian bilangan prima, karena n + 1 = ab.                                     

Karena langkah (i) dan (ii) sudah ditunjukkan benar, maka terbukti bahwa setiap bilangan bulat positif n (n ³ 2) dapat dinyatakan sebagai perkalian dari (satu atau lebih) bilangan prima.

sekian

wassalamualaikum wr.wb

RELASI DAN FUNGSI

pengertian relasi

hubungan antara elemen himpunan dengan elemen himpunan yang lain. Hubungan ini bersifat abstrak, dan tidak perlu memiliki arti apapun baik secara konkrit maupun secara matematis.

Jika terdapat himpunan A dan himpunan B (A bisa sama dengan B), maka relasi R dari A ke B adalah subhimpunan dari A×B.

sifat-sifat relasi

1.     1. Refleksif (Reflexive)

Relasi R pada himpunan A disebut refleksif jika (a,a) Î R untuk setiap a Î A

Definisi di atas menyatakan bahwa di dalam relasi refleksif setiap elemen di dalam A berhubungan dengan dirinya sendiri. Juga menyatakan bahwa relasi R pada himpunan A tidak refleksif jika ada a Î A tetapi tidak terdapat (a,a).

Contoh :

Misalkan A = {1, 2, 3, 4} dan relasi R di bawah ini didefinisikan pada himpunan A, maka :

a.    Relasi R = { (1,1), (1,3), (2,1), (2,2), (3,3), (4,2), (4,3), (4,4) } bersifat refleksif karena terdapat elemen relasi yang berbentuk (a,a) yaitu (1,1), (2,2), (3,3), dan (4,4)

b.    Relasi R = {(1,1), (2,2), (2,3), (4,2), (4,3), (4,4)} tidak bersifat refleksif karena tidak terdapat (3,3).

2. Setangkup (Symmetric)

Relasi R pada himpunan A disebut setangkup jika (a,b) Î R, maka (b,a) Î R , untuk a,b Î A

Definisi di atas menyatakan bahwa relasi R pada himpunan A tidak setangkup jika (a,b) Î R sedemikian sehingga (b,a) Ï R.

Contoh :

Misalkan A adalah himpunan mahasiswa Teknik Informatika STIKOM Poltek Cirebon dan R adalah relasi pada A sedemikian sehingga (a,b) Î R jika dan hanya jika a satu jurusan dengan b.

Maka jika dibalik, b pun se-jurusan dengan a. Jadi bisa dikatakan bahwa R setangkup.

3. Tolak-Setangkup (antisymmetric) :

Relasi R pada himpunan A disebut tolak-setangkup jika (a,b) Î R dan (b,a) Î R maka a = b, untuk semua a,b Î A.

Definisi di atas menyatakan bahwa jika (a,b) Î R, maka (b,a) Ï R kecuali a = b. Juga menyatakan bahwa relasi R pada himpunan A tidak tolak-setangkup jika ada elemen berbeda a dan b  sedemikian  sehingga (a,b) Î R dan (b,a) Î R.

Contoh:

1.    Relasi “habis membagi” pada himpunan bilangan bulat positif dikatakan tidak setangkup karena jika a habis membagi b, b tidak habis membagi a, kecuali jika a = b.

Misalnya, 2 habis membagi 4, tetapi 4 tidak habis membagi 2. Karena itu (2,4) Î R tetapi (4,2) Ï R.

Relasi “habis membagi” pada himpunan bilangan bulat positif dikatakan tolak-setangkup karena jika a habis membagi b dan b habis membagi a maka a = b.

Misalnya, 4 habis membagi 4 maka oleh karena itu (4,4) Î R dan 4 = 4.

4. Menghantar (transitive)

 Relasi  R  pada  himpunan  A disebut menghantar jika (a,b) Î R  dan (b,c) Î R, maka (a,c) Î R untuk semua a,b,c Î A

Misalkan A adalah himpunan orang, dan R adalah relasi pada A sedemikian sehingga (a,b) Î R jika dan hanya jika b adalah keturunan a.

 Jika b adalah keturunan a, yaitu (a,b) Î R,  dan c adalah keturunan  b,  yaitu  (b,c) Î R  maka c juga keturunan a, yaitu (a,c) Î R.

 Jadi, R adalah relasi menghantar. Tetapi, jika T adalah relasi pada A sedemikian sehingga (a,b) Î T jika a adalah ibu dari b, maka T tidak menghantar.

Macam-macam Penyajian Bentuk Relasi :

a. Diagram Panah

Anggota-anggota himpunan P berelasi dengan anggota himpunan Q dengan relasi “menyukai”. Hal tersebut ditunjukkan dengan arah panah. Oleh karena itu, diagramnya disebut diagram panah.

b. Diagram Kartesius

Diagram kartesius merupakan diagram yang terdiri atas sumbu X dan sumbu Y. Pada diagram kartesius, anggota himpunan P terletak pada sumbu mendatar (sumbu-X), sedangkan anggota himpunan Q terletak pada sumbu tegak (sumbu-Y). Relasi yang menghubungkan himpunan P dan Q ditunjukkan dengan noktah atau titik sepertiterlihat pada gambar.
c. Himpunan Pasangan Berurutan
Selain menggunakan diagram panah dan kartesius, sebuah relasi yang menghubungkan himpunan yang satu dengan himpunan lainnya dapat disajikan dalam bentuk himpunan pasangan berurutan. Adapun cara penulisannya adalah anggota himpunan P ditulis pertama, sedangkan anggota himpunan Q menjadi pasangannya.
Berdasarkan soal di atas, maka diperoleh himpunan pasangan berurutan sebagai berikut.
{(Rani, basket), (Rani, bulu tangkis), (Dian, basket), (Dian, atletik), (Isnie, senam), (Dila, basket), (Dila, tenis meja)}

fungsi

Misalkan A dan B himpunan. — Relasi biner f dari A ke B merupakan suatu fungsi jika setiap elemen di dalam A dihubungkan dengan tepat satu elemen di dalam B. — — Jika f adalah fungsi dari A ke B kita menuliskan — f : A ® B — yang artinya f memetakan A ke B. — — A disebut daerah asal (domain) dari f dan B disebut daerah hasil (codomain) dari f. FUNGSI

Nama lain untuk fungsi adalah pemetaan atau transformasi.

Kita menuliskan f(a) = b jika elemen a di dalam A dihubungkan dengan elemen b di dalam B.

jika f(a) = b, maka b dinamakan bayangan (image) dari a dan a dinamakan pra-bayangan (pre-image) dari b.

Himpunan yang berisi semua nilai pemetaan f disebut jelajah (range) dari f. Perhatikan bahwa jelajah dari f adalah himpunan bagian (mungkin proper subset) dari B.

Fungsi injektif

Fungsi f: A → B disebut fungsi satu-satu atau fungsi injektif jika dan hanya jika untuk sebarang a₁ dan a₂ dengan a₁ tidak sama dengan a₂ berlaku f(a₁) tidak sama dengan f(a₂). Dengan kata lain, bila a₁ = a₂ maka f(a₁) sama dengan f(a₂).

Fungsi surjektifFungsi f: A → B disebut fungsi kepada atau fungsi surjektif jika dan hanya jika untuk sebarang b dalam kodomain B terdapat paling tidak satu a dalam domain A sehingga berlaku f(a) = b. Dengan kata lain, suatu kodomain fungsi surjektif sama dengan kisarannya (range).

Fungsi bijektifFungsi f: A → B disebut disebut fungsi bijektif jika dan hanya jika untuk sebarang b dalam kodomain B terdapat tepat satu a dalam domain A sehingga f(a) = b, dan tidak ada anggota A yang tidak terpetakan dalam B. Dengan kata lain, fungsi bijektif adalah sekaligus injektif dan surjektif.