Matematika Discrite BAB II KOMBINATORIK

 

2.1. PERMUTASI DAN KOMBINASI

Author By : Dra. D. L. CRISPINA PARDEDE, DEA

Sebuah permutasi dari sebuah himpunan obyek-obyek berbeda adalah penyusunan berurutan dari obyek-obyek tersebut.

Contoh 2.1.

Misalkan S = {1, 2, 3}. Susunan  3 1 2 adalah sebuah permutasi dari S. Susunan   3 2   adalah sebuah  permutasi-2  (2-permutation)  dari S

Banyak  permutasi-r  dari himpunan dengan n obyek berbeda dinyatakan sebagai P(n,r) dimana

P(n,r) = n . (n - 1) . (n - 2) . (n - 3) . ... . (n – r + 1).

Jika  r  =  n , maka

P(n,n) = n . (n - 1) . (n - 2) . (n - 3) . ... . (n – n + 1).

= n . (n - 1) . (n - 2) . (n - 3) . ... . 1

= n !

atau ditulis           Pn = n !

Contoh 2.2.

P(8,3)      =   8. 7. 6   =   336

Rumus umum     :    n . (n-1) . (n-2)  =

Matematika Diskrit_BAB I STRUKTUR ALJABAR (Ring, Fild)

1.4. SISTEM ALJABAR DUA OPERASI

            Sebuah sistem aljabar dengan dua operasi (S, +, *) dibentuk oleh sebuah himpunan, sebuah operasi aditif ‘+’ dan sebuah operasi multiplikatif ‘*’. Sistem aljabar dengan dua operasi yang akan dibahas di sini adalah ring dan field.

1.4.1. RING

             Sebuah sistem aljabar (S,+,*) adalah sebuah ring jika sifat-sifat berikut dipenuhi :

1. (S, +) merupakan group abel.
2. Himpunan S tertutup terhadap operasi *.
3. Operasi * bersifat asosiatif, untuk setiap  x, y, z Î S  berlaku  (x * y ) * z = x * ( y * z).
4. Untuk setiap  x, y, z Î S  berlaku hukum distributif kiri  x *( y + z) = (x * y) + (x * z) dan hukum distributif kanan (y + z) * x = (y * x) + (z * x).

Contoh 1.18.

Sistem aljabar (Z,+,x) merupakan sebuah ring.

Jika kedua operasi biner pada ring (S,+,*) bersifat komutatif, maka ring tersebut merupakan ring komutatif.

Matematika Diskrit_BAB I STRUKTUR ALJABAR(operasi biner, sifat o.b,)

 

Matematika Diskrit

BAB I STRUKTUR ALJABAR

Disusun Oleh :

Dra. D. L. CRISPINA PARDEDE, DEA.

1.1. OPERASI BINER

Operasi biner pada himpunan tidak kosong S adalah pemetaan dari S x S kepada S. Notasi yang digunakan untuk menyatakan operasi biner adalah +, x, *, · , Å(arti lambang sama dengan, + didalam lingkaran) , Ä(arti lambang sama dengan, x di dalam lingkaran) , dan sebagainya. Hasil dari sebuah operasi, misalnya Ä , pada elemen a dan b akan ditulis sebagai a Ä b.

Contoh 1.1.

Operasi berikut adalah beberapa contoh operasi biner :

-. Operasi pembagian pada bilangan riil.

-. Warna rambut anak yang ditentukan oleh warna rambut orang tuanya.

-. Operasi biner Å yang didefinisikan sebagai   a Å b = a + b – 2ab.

1.2. SIFAT OPERASI BINER

Sifat-sifat yang dimiliki oleh sebuah sistem aljabar nantinya ditentukan oleh sifat-sifat yang dimiliki oleh setiap operasi di dalam sistem aljabar tersebut. Berikut akan diuraikan sifat-sifat yang dapat dimiliki oleh sebuah operasi biner.

Misalkan  *  dan  Å  adalah operasi biner.  Operasi * dikatakan :

• KOMUTATIF ,        jika  a * b = b * a, untuk setiap   a, b.
• ASOSIATIF,           jika  (a * b) * c  = a * (b * c), untuk setiap   a, b, c.
• Mempunyai :
  • IDENTITAS, jika terdapat  e  sedemikian hingga a * e = e * a = a, untuk setiap a.
  • IDENTITAS KIRI, jika terdapat e₁ sedemikian hingga e₁ * a = a, untuk setiap a.
  • IDENTITAS KANAN, jika terdapat e₂ sedemikian hingga a * e₂ = a, untuk setiap a.
  • Mempunyai sifat INVERS, jika untuk setiap  a  terdapat  a^-1  sedemikian hingga      a * a^-1 = a^-1 * a = e, dimana  e adalah elemen identitas untuk operasi  *. a^-1 disebut invers dari elemen  a.
• DISTRIBUTIF terhadap operasi  Å , jika untuk setiap a, b, c  berlaku  a * (b Å c ) = ( a * b) Å (a * c)  dan  (b Å c ) * a = ( b * a) Å (c * a).

Matematika Diskrit_BAB I STRUKTUR ALJABAR (subgroup siklik, normal)

1.3.5. SUBGROUP SIKLIK

            Misalkan (G,*) sebuah group dengan elemen identitas e Î G. Jika a Î G, maka subgroup siklik yang dibangun oleh  a  adalah himpunan

                                           gp(a)   = { ... , a^-2 , a^-1 , a⁰ , a¹ , a² , ... }

                                                      = { aⁿ | n Î Z }.

Dimana a⁰ = e. Dalam hal ini berlaku pula hukum eksponen, a^m * aⁿ = a^m+n untuk m,nÎZ. Sebagai contoh,  a⁴ * a² = a⁶ ,  a¹ * a¹ = a² .

            Untuk  n Ï Z₊ , aⁿ dapat dicari dengan mengingat bahwa a⁰ = e dan hukum eksponen a⁰ = a¹ * a^-1.  Berdasarkan kedua hal tersebut, maka  a^-1 adalah  invers dari  a  untuk operasi * dan  a^-2 , a^-3 dan seterusnya dapat dicari.

Order dari subgroup siklik gp(a) = { aⁿ | n Î Z } adalah integer positif  m  terkecil sedemikian hingga  a^m = e.

Contoh 1.13.

Perhatikan group (Z₄, Å) dari contoh 1.12. di atas. Elemen identitas pada group tersebut adalah 0. Subgroup siklik yang dibangun oleh  2 Î Z₄ adalah gp(2) = { 2ⁿ | n Î Z } = {0, 2}.  Order dari gp(2) tersebut adalah 2.

            Jika terdapat  x Î G sedemikian hingga  gp(x) = G, maka group G disebut group siklik dan  elemen  x  tersebut dinamakan generator dari G.

Contoh 1.14.

Perhatikan group (Z₄,Å) dari contoh 1.12. Subgroup siklik yang dibangun oleh  1 Î Z₄ adalah gp(1) = { 1ⁿ | n Î Z } = {0, 1, 2, 3}. Oleh karena gp(1) = Z₄, maka (Z₄,Å) merupakan group siklik dan 1 merupakan generator.

Matematika Diskrit_BAB I STRUKTUR ALJABAR (semi group, monoid, group)

1.3. SISTEM ALJABAR SATU OPERASI

            Sistem aljabar satu operasi  (S,*) dibentuk oleh sebuah himpunan dan sebuah operasi yang didefinisikan terhadapnya. Berdasarkan sifat-sifat yang dimiliki, sistem aljabar satu operasi dapat dibedakan menjadi beberapa jenis seperti yang akan diuraikan berikut ini.

1.3.1. SEMIGROUP

            Sistem aljabar  (S, *) merupakan semigroup, jika

1. Himpunan S tertutup di bawah operasi *.
2. Operasi * bersifat asosiatif.

Contoh 1.5.

(Z,+) merupakan sebuah semigroup Jika operasi biner pada semigroup (S,*) tersebut bersifat komutatif, maka semigroup (S,*) disebut juga semigroup abel.

Contoh 1.6.

(Z,+) merupakan sebuah semigroup abel

1.3.2. MONOID

            Sistem aljabar  (S, *) merupakan monoid, jika