Pak Dengklek mempunyai N buah kartu yang telah diberi nomor 1, 2, 3,..., N. Pada awalnya, Pak Dengklek menyusun kartu-kartu tersebut secara ascending (menaik). Selanjutnya, Pak Dengklek ingin menyusun kartu-kartu tersebut dengan aturan tidak boleh ada satu kartupun yang berada pada posisi yang sama dengan posisi awalnya. Jika N=7, berapa banyak susunan yang sesuai dengan aturan di atas yang dapat dibentuk oleh Pak Dengklek?
a. 49
b. 5040
c. 1854
d. 5481
e. 4815
jadi soal ini merupakan soal derangement (https://en.wikipedia.org/wiki/Derangement):
misal untuk D(1) pastinya 0 , karena hanya memiliki 1 elemen , untuk D(2) = 1, karena jika kita memiliki misal elemen 1,2 maka derangementnya hanya 2,1,
jika kita cari hubungan antar D(n) ,misal jika kita iterasi semua kemungkinan n
kita memiliki 1 kemungkinan untuk 1 elemen yaitu : 1
kita memiliki 2 kemungkinan untuk 2 elemen yaitu : 12 21(derangement)
kita memiliki 6 kemungkinan unuk 3 elemen yaitu : 123 213 312 132 231 321
jadi D(3) memiliki hubungan dengan D(2) maupun D(1) : D(3) = D(2) + D(1) ketika 1 menjadi elemen pertama, jadi untuk melakukan semua kemungkinan yang ada diperlukan (n-1) angka yang berbeda, Jadi kita generalisasi rumus rekursifnya menjadi:
D(1) = 0 and D(2) = 1 (Base Case)
D(n) = (n-1)[D(n-1) + D(n-2)]
dengan bottom up :
D(3) = 2*(1 + 0) = 2
D(4) = 3*(2+1) = 9
D(5) = 4*(9+2) = 44
D(6) = 5*(44+9) = 265
D(7) = 6*(265+44) = 1854 (C)
ak maksudkan, semua kemungkinannya:
12, 21
derangementnya : hanya 21
Masuk untuk menulis jawaban
Follow Your Dreams
memakai rumus derangement
!n = (n-1)(!(n-1)+!(n-2))
base case:
!1 = 0
!2 = 1;
!3 = 2(1+0)=2
!4=3(2+1)=9
!5=4(9+2)=55
!6=5(44+9)=265
!7=6(265+44)=1854
C.1854
kok 4(9+2)= 55 setahu saya 44 kok
Pernah Jago OSK
," untuk D(2) = 1, karena jika kita memiliki misal elemen 1,2 maka derangementnya hanya 2,1 " --> kok disini 1
"kita memiliki 2 kemungkinan untuk 2 elemen yaitu : 12 21" --> kok ini jadi 2
knapa begitu ?