Kanada 1982 #4 « Olimpiade Matematika

Kanada 1982 #4

4. Misalkan $p$ adalah permutasi dari himpunan $S_n=\{1,2,\ldots,n\}$ . Suatu elemen $j\in S_n$ disebut titik tetap dari $p$ jika $p(j)=j$ . Misalkan $f_n$ adalah banyaknya permutasi tanpa titik tetap, dan $g_n$ adalah banyaknya permutasi dengan tepat satu titik tetap. Tunjukkan bahwa $|f_n-g_n|=1$ .

Solusi:

Untuk $n=1$ , jelas bahwa $g_1=1,f_1=0$ . Perhatikan bahwa $g_n=nf_{n-1}$ karena untuk mendapat permutasi dengan satu titik tetap, kita melakukan dua langkah: 1) pilih satu bilangan yang menjadi titik tetap, ada $n$ cara; 2) susun $n-1$ bilangan lainnya tanpa titik tetap, ada $f_{n-1}$ cara. Sekarang tinjau sebuah permutasi tanpa titik tetap. Maka $p(1)=j$ bisa dipilih dalam $n-1$ cara. Jika $p(j)=1$ , susunan $n-1$ bilangan lainnya bisa dipilih dalam $f_{n-1}$ cara. Jika $p(j)\ne1$ , $n-2$ bilangan lainnya disusun dalam $f_{n-2}$ cara. Jadi $f_n=(n-1)(f_{n-1}+f_{n-2})$ . Jadi $f_{n+1}-g_{n+1}=n(f_n+f_{n-1})-(n+1)f_n=nf_{n-1}-f_n=g_n-f_n$ . Jadi $f_n-g_n=(-1)^{n-1}(f_1-g_1)$ . Karena $f_1-g_1=0-1=-1$ , maka terbukti bahwa $|f_n-g_n|=1$ untuk $n\ge1$ .