1

SOAL DAN PEMBAHASAN

MATEMATIKA DISKRIT

(Disusun dalam rangka memenuhi tugas IV

mata kuliah Matematika Diskrit di Universitas Negeri Makassar)

KELOMPOK VII

M. NURFAJRIN HATTAB (1211040003)

MUH. ALFIANSYAH (1211041019)

LISA RANTE SALONG (1211041021)

JURUSAN MATEMATIKA

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS NEGERI MAKASSAR

MAKASSAR

2014

2

5. Cari kovolusi dari pasangan barisan berikut!

a. (1, 1, 1, 1, … ) dan (1, 1, 1, 1, … )

b. (1, 1, 1, 1, … ) dan (0, 1, 2, 3, … )

c. (1, 1, 1, 0, 0, … ) dan (0, 1, 2, 3, … )

d. (0, 0, 0, 1, 0, 0, … ) dan (6 7, 8, 9, … )

Solusi:

Dari formula (2.2.4) (dalam buku Matematika Diskrit, I Ketut Budayasa)

(∑𝑎𝑛𝑥𝑛

∞

𝑛=0

)(∑𝑏𝑛𝑥𝑛

∞

𝑛=0

) = ∑(∑𝑎𝑘𝑏𝑛−𝑘

𝑛

𝑘=0

)

∞

𝑛=0

𝑥𝑛

Sedemikian sehingga

𝑐𝑛 =∑𝑎𝑘𝑏𝑛−𝑘

𝑛

𝑘=0

(𝑐𝑛) 𝑎𝑑𝑎𝑙𝑎ℎ 𝑘𝑜𝑛𝑣𝑜𝑙𝑢𝑠𝑖 𝑑𝑎𝑟𝑖 (𝑎𝑛) 𝑑𝑎𝑛 (𝑏𝑛)

Perhatikan bahwa:

a. (1, 1, 1, 1, … ) dan (1, 1, 1, 1, … )

𝑎𝑛 = (1, 1, 1, 1, … )

𝑏𝑛 = (1, 1, 1, 1, … ) , maka diperoleh

𝑐𝑛 =∑𝑎𝑘𝑏𝑛−𝑘

𝑛

𝑘=0

𝑐𝑛 =∑1

𝑛

𝑘=0

(karena 𝑎𝑖 = 1, untuk setiap 𝑖 dan 𝑎𝑗 = 1, untuk setiap 𝑗

Dengan demikian (𝑐𝑛) = (1, 2, 3, 4, … ) atau

𝑐𝑛 = 𝑛 + 1 ; ∀𝑛 ∈ ℕ

b. (1, 1, 1, 1, … ) dan (0, 1, 2, 3, … )

𝑎𝑛 = (1, 1, 1, 1, … )

𝑏𝑛 = (0, 1, 2, 3, … ), maka diperoleh

𝑐𝑛 =∑𝑎𝑘𝑏𝑛−𝑘

𝑛

𝑘=0

3

𝑐𝑛 =∑𝑏𝑛−𝑘

𝑛

𝑘=0

(karena 𝑎𝑖 = 1, untuk setiap 𝑖 )

Dengan demikian (𝑐𝑛) = (0, 1, 3, 6, 10, 15,… ) atau

𝑐𝑛 = {

0, 𝑛 = 0

𝑛2 + 𝑛

2, 𝑛 ≥ 1, ∀𝑛 ∈ ℕ

c. (1, 1, 1, 0, 0, … ) dan (0, 1, 2, 3, … )

𝑎𝑛 = (1, 1, 1, 0, 0, … )

𝑏𝑛 = (0, 1, 2, 3, … ), maka diperoleh

𝑐𝑛 =∑𝑎𝑘𝑏𝑛−𝑘

𝑛

𝑘=0

Perhatikan:

𝑐0 = 𝑎0𝑏0 = (1)(0) = 0

𝑐1 = 𝑎0𝑏1 + 𝑎1𝑏0 = (1)(1) + (1)(0) = 1

𝑐2 = 𝑎0𝑏2 + 𝑎1𝑏1 + 𝑎2𝑏0 = (1)(2) + (1)(1) + (1)(0) = 3

𝑐3 = 𝑎0𝑏3 + 𝑎1𝑏2 + 𝑎2𝑏1 + 𝑎3𝑏0 = (1)(3) + (1)(2) + (1)(1) + (1)(0) = 6

𝑐4 = 𝑎0𝑏4 + 𝑎1𝑏3 + 𝑎2𝑏2 + 𝑎3𝑏1 + 𝑎4𝑏0

= (1)(4) + (1)(3) + (1)(2) + (0)(1) + (0)(0) = 9

𝑐5 = 𝑎0𝑏5 + 𝑎1𝑏4 + 𝑎2𝑏3 + 𝑎3𝑏2 + 𝑎4𝑏1 + 𝑎5𝑏0

= (1)(5) + (1)(4) + (1)(3) + (0)(2) + (0)(1) + (0)(0)

= 12

⋮

Dengan demikian (𝑐𝑛) = (0, 1, 3, 6, 9, 12,… ) atau

𝑐𝑛 = {0, 𝑛 = 01, 𝑛 = 1

(𝑛 − 1)3, 𝑛 ≥ 2, ∀𝑛 ∈ ℕ

d. (0, 0, 0, 1, 0, 0, … ) dan (6 7, 8, 9, … )

𝑎𝑛 = (0, 0, 0, 1, 0, 0, … )

𝑏𝑛 = (6 7, 8, 9, … ), maka diperoleh

4

𝑐𝑛 = ∑ 𝑎𝑘𝑏𝑛−𝑘𝑛𝑘=0

Perhtikan:

𝑐0 = 𝑎0𝑏0 = (0)(6) = 0

𝑐1 = 𝑎0𝑏1 + 𝑎1𝑏0 = (0)(7) + (0)(6) = 0

𝑐2 = 𝑎0𝑏2 + 𝑎1𝑏1 + 𝑎2𝑏0 = (0)(8) + (0)(7) + (0)(6) = 0

𝑐3 = 𝑎0𝑏3 + 𝑎1𝑏2 + 𝑎2𝑏1 + 𝑎3𝑏0 = (0)(9) + (0)(8) + (0)(7) + (1)(6) = 6

𝑐4 = 𝑎0𝑏4 + 𝑎1𝑏3 + 𝑎2𝑏2 + 𝑎3𝑏1 + 𝑎4𝑏0

= (0)(10) + (0)(9) + (0)(8) + (1)(7) + (0)(6) = 7

𝑐5 = 𝑎0𝑏5 + 𝑎1𝑏4 + 𝑎2𝑏3 + 𝑎3𝑏2 + 𝑎4𝑏1 + 𝑎5𝑏0

= (0)(11) + (0)(10) + (0)(9) + (1)(8) + (0)(7)

+ (0)(6) = 8

⋮

Dengan demikian (𝑐𝑛) = (0, 0, 0, 6, 7, 8, … ) atau

𝑓(𝑥) = {0, 0 ≤ 𝑛 ≤ 2

𝑛 + 3, 𝑛 ≥ 3, ∀𝑛 ∈ ℕ

16. Seorang manager dari suatu perusahaan yang bergerak dibidang transportasi

merencanakan membeli 3 jenis kenadaraan baru, sedan, bus dan truk. Sang

manajer ingin membeli 𝑛 buah kendaraan baru yang terdiri dari paling sedikit

satu sedan, paling banyak 10 bus dan sekurang-kurangnya 2 tapi tak lebih

dari 15 truk.

Ada berapa cara hal ini dapat dilakukan, jika dua kendaraan sejenis tidak

dibedakan?

Solusi:

Diketahui : akan dibeli 𝑛 buah kendaraan baru

Mobil sedan ≥ 1

Mobil Bus ≤ 10

2 ≤ Mobil Truk ≤ 15

Dua kendaraan sejenis tidak dibedakan

Ditanyakan: Ada berapa cara untuk membeli 𝑛 buah kendaraan baru?

5

Perhatikan bahwa:

Paling sedikit satu mobil sedan, maka mobil sedan tersebut berasosiasi

dengan sebuah faktor (𝑥 + 𝑥2 + 𝑥3 +⋯) dalam fungsi pembangkit

biasa.

Paling banyak sepuluh mobil bus, maka mobil bus tersebut berasosiasi

dengan sebuah faktor (1 + 𝑥 + 𝑥2 + 𝑥3 +⋯+ 𝑥10) dalam fungsi

pembangkit biasa.

Sekurang-kurangnya dua tetapi tidak lebih dari 15 mobil truk, maka

mobil truk tersebut berasosiasi dengan sebuah faktor (𝑥2 + 𝑥3 + 𝑥4 +

⋯+ 𝑥15) dalam fungsi pembangkit biasa.

Ekspansi fungsi dari fakor-faktor dalam fungsi pembangkit yang diperoleh

pada bagian sebelumnya adalah:

1

1 − 𝑥= ∑𝑥𝑛

∞

𝑛=0

= 1 + 𝑥 + 𝑥2 +⋯ (𝟏)

Dari (1) diperoleh untuk (𝑥 + 𝑥2 + 𝑥3 +⋯) = 𝑥(1 + 𝑥 + 𝑥2 +⋯)

(𝑥 + 𝑥2 + 𝑥3 +⋯) = 𝑥 (1

1 − 𝑥)

(𝑥 + 𝑥2 + 𝑥3 +⋯) =𝑥

1 − 𝑥 (𝟏. 𝟏)

1 − 𝑥𝑛+1

1 − 𝑥= ∑𝑥𝑘

𝑛

𝑘=0

= 1 + 𝑥 + 𝑥2 +⋯+ 𝑥𝑛 (𝟐)

Dari (2) diperoleh untuk (1 + 𝑥 + 𝑥2 + 𝑥3 +⋯+ 𝑥10) =1−𝑥10+1

1−𝑥

(1 + 𝑥 + 𝑥2 + 𝑥3 +⋯+ 𝑥10) =1 − 𝑥11

1 − 𝑥 (𝟐. 𝟐)

Dari (2) diperoleh untuk:

(𝑥2 + 𝑥3 + 𝑥4 +⋯+ 𝑥15) = 𝑥2(1 + 𝑥 + 𝑥2 +⋯+ 𝑥13)

(𝑥2 + 𝑥3 + 𝑥4 +⋯+ 𝑥15) = 𝑥2 (1 − 𝑥13+1

1 − 𝑥)

6

(𝑥2 + 𝑥3 + 𝑥4 +⋯+ 𝑥15) = 𝑥2 (1 − 𝑥14

1 − 𝑥)

(𝑥2 + 𝑥3 + 𝑥4 +⋯+ 𝑥15) =𝑥2 − 𝑥16

1 − 𝑥 (𝟐. 𝟑)

Ekspansi fungsi lain yang digunakan:

1

(1 − 𝑥)𝑛=∑(

𝑛 + 𝑘 − 1𝑘

) 𝑥𝑘∞

𝑘=0

= 1 + (𝑛1) 𝑥 + (

𝑛 + 12

) 𝑥2 +⋯ (𝟑)

Dengan demikian fungsi pembangkit dari pemecahan ini adalah:

𝑃(𝑥) = (𝑥 + 𝑥2 + 𝑥3 +⋯)(1 + 𝑥 + 𝑥2 +⋯+ 𝑥10)(𝑥2 + 𝑥3 +⋯+ 𝑥15)

𝑃(𝑥) = (𝑥

1 − 𝑥) (1 − 𝑥11

1 − 𝑥)(𝑥2 − 𝑥16

1 − 𝑥) 𝑑𝑎𝑟𝑖 (𝟏. 𝟏), (𝟐. 𝟐)& (𝟐. 𝟑)

𝑃(𝑥) = (𝑥)(1 − 𝑥)−1(1 − 𝑥11)(1 − 𝑥)−1(𝑥2 − 𝑥16)(1 − 𝑥)−1

𝑃(𝑥) = (1 − 𝑥)−3(1 − 𝑥11)(𝑥)(𝑥2 − 𝑥16)

𝑃(𝑥) = (1 − 𝑥)−3(1 − 𝑥11)(𝑥3 − 𝑥17)

𝑃(𝑥) = (1 − 𝑥)−3(𝑥3 − 𝑥17 − 𝑥14 + 𝑥28)

𝑃(𝑥) = (1 − 𝑥)−3(𝑥3 − 𝑥14 − 𝑥17 + 𝑥28)

𝑃(𝑥) = (𝑥3 − 𝑥14 − 𝑥17 + 𝑥28)∑(3 + 𝑟 − 1

𝑟) 𝑥𝑟

∞

𝑟=0

𝑑𝑎𝑟𝑖 (𝟑)

𝑃(𝑥) =∑(3 + 𝑟 − 1

𝑟) 𝑥𝑟+3 −

∞

𝑟=0

∑(3 + 𝑟 − 1

𝑟) 𝑥𝑟+14

∞

𝑟=0

−∑(3 + 𝑟 − 1

𝑟) 𝑥𝑟+17 +∑(

3 + 𝑟 − 1𝑟

) 𝑥𝑟+28∞

𝑟=0

∞

𝑟=0

𝑃(𝑥) =∑(𝑟 − 1𝑟 − 3

) 𝑥𝑟 −

∞

𝑟=3

∑ (𝑟 − 12𝑟 − 14

) 𝑥𝑟 −

∞

𝑟=14

∑ (𝑟 − 15𝑟 − 17

) 𝑥𝑟∞

𝑟=17

+ ∑ (𝑟 − 26𝑟 − 28

) 𝑥𝑟∞

𝑟=28

7

Banyak cara yang dimaksud = koefisien 𝑥𝑛 dalam 𝑃(𝑥)

=

{

0, 𝑛 < 3

(𝑛 − 1

𝑛 − 3) , 3 ≤ 𝑛 < 14

(𝑛 − 1

𝑛 − 3) − (

𝑛 − 12

𝑛 − 14) , 14 ≤ 𝑛 < 17

(𝑛 − 1

𝑛 − 3) − (

𝑛 − 12

𝑛 − 14) − (

𝑛 − 15

𝑛 − 17) , 17 ≤ 𝑛 < 28

(𝑛 − 1

𝑛 − 3) − (

𝑛 − 12

𝑛 − 14) − (

𝑛 − 15

𝑛 − 17) + (

𝑛 − 26

𝑛 − 28) , 𝑛 ≥ 28

***

DAFTAR PUSTAKA

Budayasa, I.K. 2008. Matematika Diskrit. Surabaya: Unesa University Press