PERMUTASI DENGAN PANJANG YANG TIDAK MEMUAT POLA DENGAN PANJANG EMPAT

PERMUTASI DENGAN PANJANG YANG TIDAK MEMUAT POLA DENGAN PANJANG EMPAT

Seplin Tarakolo dan Djoko Suprijanto Program Studi Magister Pengajaran Matematika FMIPA ITB, Kelompok Keahlian Kombinatorika FMIPA ITB E-mail: [email protected], [email protected]

ABSTRAK: Permutasi dikatakan memuat suatu pola , jika memiliki sedikitnya sebuah subbarisan yang unsur-unsurnya saling berkorespondensi dengan unsur-unsur di . Misalkan adalah sebuah permutasi dengan c dan d sebagai empat unsur di dalamnya (dalam urutan kiri ke kanan, tapi tidak harus berurutan). Jika , maka disebut membentuk pola. Namun, jika tidak terdapat empat unsur di yang membentuk pola seperti itu, maka disebut tidak memuat pola4. Dalam makalah ini, akan ditentukan banyaknya permutasi dengan panjang yang tidak memuat pola dengan panjang empat dan sebuah permutasi khusus yang tidak memuat satu dari pola dengan panjang empat yang disebut permutasi dua-stack sortable. Kata Kunci : permutasi, permutasi dua-stack sortable.

Tinjaulah sekelompok anak-anak dengan tinggi badan yang berbeda bermain di sebuah lapangan. Dalam salah satu permainan, mereka harus berdiri membentuk sebuah barisan dimana setiap anak berdiri menghadap punggung anak yang didepannya dan setiap anak harus dapat melihat semua anak yang lebih pendek dari dia yang berada di depannya. Berapa banyak barisan yang dapat dibentuk? Sebagai contoh, misalkan terdapat 7 anak. Setiap anak dinotasikan dengan angka 1, 2, 3, . . ., 7 berurutan sesuai dengan tinggi mereka dimana angka 1 mewakili anak yang paling pendek dan angka 7 mewakili anak yang paling tinggi. Apakah barisan 1423567 merupakan barisan yang sesuai dengan ketentuan permainan di atas? Jawabannya adalah tidak, karena terdapat anak dengan notasi angka 2 atau anak dengan notasi angka 3 tidak dapat melihat anak dengan notasi angka 1 karena terhalang oleh anak dengan notasi angka 4 yang lebih tinggi daripada anak 2 atau 3. Salah satu contoh barisan

yang memenuhi ketentuan permainan tersebut adalah 6723415. Dapatkah kita menentukan barisan lainnya? Ada berapa banyak barisan yang memenuhi ketentuan permainan? Suatu barisan yang memenuhi ketentuan permainan di atas adalah suatu barisan dimana tidak terdapat 3 anak dalam barisan tersebut misalkan a, b dan c yang berurutan namun tidak harus berturutan dengan a < c < b (a lebih pendek dari c lebih pendek dari b). Jika terdapat 3 anak dalam barisan tersebut maka anak c tidak dapat melihat anak a. Jika contoh di atas banyaknya anak (unsur) adalah 7 bagaimana jika banyak anak adalah n? Berapa banyak barisan yang dapat dibentuk? Pertanyaan – pertanyaaan ini akan dibahas dalam makalah ini. Permutasi Yang Tidak Memuat Suatu Pola Sebelum membahas permutasi yang tidak memuat suatu pola, terlebih

869

Tarakolo dan Suprijanto, Permutasi Dengan Panjang , 870

dahulu diingatkan kembali tentang permutasi. Definisi 1. Susunan semua anggota dari himpunan {1, 2, 3, . . ., n} disebut sebuah permutasi dari n bilangan asli pertama, dimana setiap anggota himpunan terdaftar tepat 1 kali.

Permutasi p dikatakan memuat pola q jika terdapat k unsur pada p sehingga , dan jika dan hanya jika . Dan sebaliknya, p dikatakan tidak memuat q.

Contoh 1. Misalkan n = 3. Maka permutasi-permutasi dengan panjang 3 adalah 123, 132, 213, 231, 312 dan 321.

Dengan kata lain, permutasi p memuat pola-q jika p memiliki sub barisan dari unsur-unsurnya yang berelasi satu sama lain seperti unsur-unsur pada q.

Proposisi 1. Banyaknya permutasi dengan panjang n adalah n!. Bukti. Misalkan sebuah permutasi dengan panjang n yaitu dengan adalah unsur ke-i pada permutasi p. Tempat dapat diisi sebanyak n unsur, dapat diisi oleh n-1 unsur, dan seterusnya sampai tempat dapat diisi oleh 1 unsur. Jadi banyaknya permutasi dengan panjang n adalah n!. ■ Sekarang perhatikan sebuah permutasi dengan panjang delapan, missalkan p = 25641387 dan sebuah permutasi yang lebih pendek yaitu permutasi dengan panjang tiga, misalkan q = 132. Unsur – unsur 2, 6, 4 pada p dikatakan membentuk sebuah pola atau sub barisan jenis 132 karena unsur-unsur 2, 6, 4 pada p berelasi satu sama lain seperti unsur-unsur 1, 3, 2 pada q. Relasi yang dimaksud adalah unsur pertama adalah unsur terkecil, unsur kedua adalah unsur terbesar dan unsur ketiga adalah unsur pertengahan dari kedua unsur sebelumnya. Oleh karena itu, pada permutasi p ditemukan sebuah pola seperti 132. Sebaliknya, tak ada pola seperti 12345 yang ada pada p. Secara umum, berikut ini diberikan definisi tentang sebuah permutasi yang memuat dan tidak memuat suatu pola. Definisi 2. Misalkan dan ∈

∈ dengan k ≤ n.

Contoh 2. Permutasi m = 3451267 memuat pola-2134 karena terdapat unsur-unsur pada m yaitu 3, 1, 6, 7 yang membentuk sub barisan 3167 yang saling berelasi seperti 2134. Permutasi m dikatakan tidak memuat pola-321 karena tidak terdapat sub barisan menurun dengan panjang tiga.

Banyaknya Permutasi Dengan Panjang n Yang Tidak Memuat Pola Dengan Panjang Empat Dalam bab ini kita akan menentukan banyaknya permutasi dengan panjang n yang tidak memuat pola-q yang dinotasikan dengan , ∈ . Terdapat 24 pola dengan panjang empat yang dimana terdapat banyak ekuivalensi diantara mereka. Ekuivalensi itu antara lain balikan, komplemen dan lain-lain. Misalkan sebuah permutasi ∈ . Balikan dari p dapat didefinisikan sebagai permutasi , dan komplemen dari p dapat didefinisikan sebagai permutasi dimana unsur ke-i adalah . Sebagai contoh, permutasi 2134, balikannya adalah 4312 dan komplemen dari 2134 adalah 3421. Berdasarkan definisi balikan dan komplemen dari suatu permutasi, dapat dinyatakan bahwa jika suatu permutasi p dengan panjang n tidak memuat pola-q, ∈ , maka balikan dari p tidak memuat

871, KNPM V, Himpunan Matematika Indonesia, Juni 2013

balikan dari q dan komplemen dari p tidak memuat komplemen dari q. Contoh permutasi ∈ yang tidak memuat pola-1342, p = 6741235. Diperoleh balikan dari p yaitu 5321476 tidak memuat pola-2431 yang merupakan balikan dari pola-1342 dan komplemen dari p yaitu 2147653 tidak memuat pola-4213 yang merupakan komplemen dari pola-1342. Oleh karena itu = = . Selain balikan dan komplemen, terdapat pula ekuivalen lainnya dari pola permutasi dengan panjang empat yaitu invers. Invers dari suatu permutasi dapat didefinisikan sebagai representasi dari suatu matriks yang merupakan transpose dari matriks yang merupakan representasi dari permutasi yang akan dicari inversnya. Contoh pola-1423 jika direpresentasi ke bentuk matriks, menjadi ( kemudian (

ditranspose

) menjadi

), selanjutnya direpresen-

tasikan kembali menjadi pola permutasi yaitu 1342. Berdasarkan definisi invers dari suatu permutasi tersebut, maka jika suatu permutasi p memuat pola-q maka invers dari p jelas memuat invers dari q sehingga banyaknya permutasi yang tidak memuat pola q sama dengan banyaknya permutasi yang tidak memuat invers dari q. Dengan menggunakan balikan, komplemen dan invers yang terdapat pada 24 pola permutasi dengan panjang empat, maka terdapat 7 pola yang berbeda, yaitu 1234, 1243, 1342, 1324, 1432, 2143 dan 2413. Dari 7 pola yang tersisa ini, dapat disederhanakan lagi dengan menggunakan teorema dari Backelin, West dan Xin [4], yang memiliki bukti sangat kompleks dan

sebuah lema yang pembuktiannya merujuk pada hasil pekerjaan dari Stankova [5]. Teoema 1. Jika q adalah sebuah permutasi dari himpunan {k+1, k+2, . . . , k+r} dengan k bilangan bulat positif, maka = , untuk suatu n bilangan bulat positif. Berdasarkan teorema di atas, maka = dan = . Karena 2134 merupakan balikan komplemen atau komplemen balikan dari 1243 maka = sehingga = . Dengan demikian, pola-1243 dan 2143 dapat dihapus dari daftar pola yang tersisa. Teorema 1 juga menunjukkan bahwa = . Karena 3214 merupakan balikan komplemen atau komplemen balikan dari 1432 maka = sehingga = yang mengakibatkan pola-1432 dapat dihapus dari daftar pola yang tersisa. Lema 1. = suatu n bilangan bulat positif.

, untuk

Stankova [5], telah membuktikan bahwa = . Pola-4132 merupakan balikan invers atau invers balikan dari pola-1342 maka = . Sedangkan pola-3142 merupakan balikan dari pola-2413 sehingga = . Dengan demikian, diperoleh = yang membuat Lema 1 terbukti dan pola-2413 dapat dihapus dari daftar pola yang tersisa. Berdasarkan Teorema 1 dan Lema 1, diperoleh 3 pola permutasi dengan panjang empat yang benar-benar berbeda yaitu pola-1234, 1324 dan 1342. Perhitungan komputer memberikan fakta-fakta numerik yang menarik tentang ketiga pola tersebut (nilai dari , untuk n ≤ 8).

Tarakolo dan Suprijanto, Permutasi Dengan Panjang , 872

  

Untuk : 1, 2, 6, 23, 103, 512, 2740, 15485 Untuk : 1, 2, 6, 23, 103, 513, 2761, 15767 Untuk : 1, 2, 6, 23, 103, 513, 2762, 15793

Dari hasil perhitungan untuk ketiga pola di atas, terdapat paling sedikit dua fakta yang menarik. Pertama, tak selamanya bergantung pada q, artinya terdapat beberapa pola dengan panjang empat yang lebih mudah untuk tidak dimuat oleh suatu permutasi daripada pola yang lain. Ini dapat dilihat untuk n ≥ 7, < < . Ketaksamaan ini akan dibuktikan selanjutnya. Kedua, pola monoton yaitu 1234 berada di tengah dari rangkaian fakta di atas, artinya pola ini bisa lebih mudah atau lebih sulit untuk tidak dimuat pada suatu permutasi. 1. Pola-1324 Lema 2. Jika p suatu permutasi yang tidak memuat pola-1324 maka p merupakan gabungan dari suatu permutasi yang tidak memuat pola-132 dan suatu permutasi yang tidak memuat pola-213. Bukti. Misalkan suatu permutasi yang tidak memuat pola-1324. Unsur-unsur pada p akan diwarnai satu persatu dari kiri ke kanan dengan aturan sebagai berikut: 1. Jika unsur ke-i yaitu diwarnai warna merah sehingga akan membentuk pola 132 dengan seluruh unsur yang berwarna merah maka harus diwarnai dengan warna biru. 2. Jika terdapat unsur yang berwarna biru lebih kecil dari maka harus diwarnai biru. 3. Jika sebaliknya, maka harus diwarnai merah.

Contoh 3. Misalkan p = 3612745. Berdasarkan aturan pewarnaan di atas, diperoleh subbarisan dari p yang berwarna merah adalah 36127 sedangkan subbarisan yang berwarna biru adalah 45. Berdasarkan aturan-aturan di atas, terlihat bahwa semua unsur yang berwarna merah membentuk sub barisan yang tidak memuat pola-132 sedangkan semua unsur yang berwarna biru membentuk sub barisan yang tidak memuat pola-213. Andaikan terdapat unsur-unsur yang berwarna biru yang memuat pola 213. Misalkan dan berwarna biru dimana s ≤ t dan ≤ dan merupakan unsur paling kecil. Ini berarti akan diwarnai biru karena berdasarkan aturan pertama jika berwarna merah maka akan membentuk pola-132 dengan unsurunsur dan yang berwarna merah dimana . Sehingga akan terdapat dua kemungkinan, yaitu : 1. Jika

berada di kiri maka membentuk pola-1324 pada p. Kontradiksi dengan p yang tidak memuat pola-1324. 2. Jika berada di kanan maka juga berada di kanan yang mengakibatkan namun berdasarkan aturan kedua, harus berwarna biru. Faktanya , sehingga membentuk pola1324 pada p. Kontradiksi dengan p tidak memuat pola-1324. Lema 3. Misalkan adalah tiga pola permutasi dimana setiap permutasi yang tidak memuat pola-q, diperoleh dari sebuah gabungan permutasi yang tidak memuat pola- dengan permutasi yang tidak memuat pola- . Jika dan , untuk setiap bilangan bulat positif n dan a,b suatu konstanta positif maka (√ √ ) , untuk setiap bilangan bulat positif n.

873, KNPM V, Himpunan Matematika Indonesia, Juni 2013

Bukti. Misalkan p suatu permutasi dengan panjang n yang tidak memuat pola-q. Kita dapat mewarnai tiap unsur dari p dengan warna merah atau biru sehingga semua unsur yang berwarna merah membentuk sub barisan yang tidak memuat pola- dan semua unsur yang berwarna biru membentuk sub barisan yang tidak memuat pola- . Jika terdapat tepat k unsur yang berwarna merah maka terdapat ( ) pilihan untuk untuk unsur-unsur yang berwarna merah dan ( ) pilihan untuk posisi unsurunsur yang berwarna merah. Jumlah semua kemungkinan nilai untuk p adalah

∑

( )

(( ) √ √

∑

)

≤ (∑

( )√

√

≤ (√

)

√ )

Teorema 2. Untuk setiap bilangan bulat positif n, berlaku Bukti. Berdasarkan lema 2, diketahui bahwa suatu permutasi p yang tidak memuat pola-1324 merupakan gabungan dari suatu permutasi yang tidak memuat pola-132 dengan suatu permutasi yang tidak memuat pola-213. Menurut Miklos Bona [1], = = . Maka menurut lema 2, (√

√ )

=

2. Pola-1234 bulat

Teorema 3. Untuk setiap bilangan positif k ≤ n, berlaku

Bukti. Untuk membuktikan teorema di atas, sebelumnya kita perlu mendefinisikan order i dari suatu permutasi. Sebuah unsur x pada suatu permutasi dikatakan order i jika x merupakan unsur terakhir dari sub barisan naik dengan panjang-i dan tidak ada sub barisan naik dengan panjang-i + 1 dengan x merupakan unsur terakhir dari sub barisan tersebut. Maka untuk setiap i, unsur-unsur yang berorder i akan membentuk sub barisan menurun. Oleh karena itu, suatu permutasi yang tidak memuat pola monoton naik dengan panjang k dapat di dekomposisikan ke dalam gabungan dari k – 1 sub barisan menurun. Karena terdapat cara untuk mempartisi unsurunsur pada permutasi tersebut ke dalam k – 1 kelas dan terdapat cara untuk memberikan tiap posisi unsur-unsur tersebut ke dalam satu dari k – 1 sub barisan yang ada, maka ketaksamaan di atas terbukti. Akibat 1.

■

Dalam buku Miklos Bona [2], dikatakan bahwa Ira Gessel telah membuktikan rumus di bawah ini, yaitu rumus untuk mencari banyaknya permutasi dengan panjang n yang tidak memuat pola1234. ∑

(

)( )

dengan k = 4. Namun beberapa tahun yang lalu, Gessel membangun bentuk alternatif di bawah ini untuk rumusnya. ∑

(

)(

)(

)

■

Tarakolo dan Suprijanto, Permutasi Dengan Panjang , 874

3. Pola-1342 Miklos Bona dalam bukunya [2], menemukan rumus untuk menentukan banyaknya permutasi dengan panjang n yang tidak memuat pola-1342 yaitu

Karena permutasi yang dihasilkan yaitu s(p) = 2134 bukan permutasi identitas maka permutasi p bukan permutasi stack sortable. Pada contoh di atas telah diketahui bahwa permutasi p bukan permutasi stack sortable. Dapatkah kita mengidentifikasi permutasi-permutasi yang stack sortable tanpa harus menggunakan metode atau alat ∑ ( ) stack? Permutasi-permutasi yang manakah yang merupakan permutasi stack sortable? Untuk menjawab pertanyaan-pertanyaan tersebut, terlebih dahulu akan dijelaskan Permutasi Stack Sortable akibat dari aturan yang berlaku pada stack terhadap pasangan-pasangan unsur pada Permutasi stack sortable adalah permutasi awal melalui proposisi di bawah permutasi yang setelah disortir melalui ini. aturan tertentu dapat menghasilkan permutasi identitas yaitu permutasi yang Proposisi 2. Misalkan p adalah suatu unsur-unsurnya berurutan membentuk permutasi, s(p) adalah permutasi yang urutan naik. Adapun cara atau metode merupakan peta dari p setelah melalui untuk menyortir suatu permutasi yaitu metode stack dan a, b adalah unsur-unsur stack. Stack merupakan suatu susunan pada p dengan a < b. vertikal di mana unsur-unsur permutasi yang berada di dalamnya membentuk 1. Jika unsur a mendahului unsur b pada p maka unsur a mendahului unsur b susunan atau urutan naik di mana unsur pada s(p). yang kecil berada di atas dan unsur yang 2. Jika unsur b mendahului unsur a pada besar berada di bawah. p dan tidak terdapat unsur c yang Contoh cara kerja stack : Misalkan terletak di antara unsur a dan unsur b permutasi p = 2413 pada p di mana c > b > a maka unsur a mendahului unsur b pada s(p). Permutasi 3. Jika unsur b mendahului unsur a pada Permutasi p Stack s(p) p dan terdapat unsur c yang terletak di 2413 antara unsur a dan unsur b pada p di 413 2 mana c > b > a maka unsur b 413 2 mendahului unsur a pada s(p). Kasus 13 4 ini terjadi ketika unsur-unsur a, b dan 1 c membentuk pola 231. 3 2 4 Bukti. Misalkan p adalah suatu permutasi, 3 4 21 s(p) adalah permutasi yang merupakan peta 3 21 dari p setelah melalui metode stack dan a, b 4 adalah unsur-unsur pada p dengan a < b. 4 213 2134

875, KNPM V, Himpunan Matematika Indonesia, Juni 2013

1. Misalkan unsur a mendahului unsur b pada p. Unsur a akan lebih dulu diletakkan pada stack daripada unsur b. Karena a < b maka saat unsur b akan diletakkan pada stack, unsur a akan dikeluarkan dari stack dan menjadi unsur pada s(p) sehingga a mendahului b pada s(p). 2. Misalkan unsur b mendahului unsur a pada p dan tidak terdapat unsur c yang terletak di antara unsur a dan b pada p dengan c > b > a. Unsur b akan lebih dulu di letakkan pada stack. Saat unsur a diletakkan pada stack, unsur b tetap berada di stack atau tidak dikeluarkan karena a < b, dan tetap berada di bawah unsur a pada stack. Dengan demikian saat akan dikeluarkan untuk menjadi unsur-unsur pada s(p), unsur a akan mendahului unsur b pada s(p). 3. Misalkan unsur b mendahului unsur a pada p dan terdapat unsur c yang terletak di antara unsur a dan b pada p dengan c > b > a. Unsur b akan diletakkan terlebih dahulu pada stack kemudian disusul unsur c yang diletakkan pada stack. Karena c > b maka unsur b dikeluarkan dan menjadi unsur pada s(p). Dengan demikian unsur b mendahului unsur a pada s(p). Berdasarkan Proposisi 2 di atas, dapat ditentukan permutasi-permutasi yang merupakan permutasi stack sortable melalui teorema di bawah ini. Teorema 4. Suatu permutasi p dikatakan permutasi stack sortable jika dan hanya jika permutasi p tidak memuat pola-231. Bukti. (  ) Misalkan p permutasi stack sortable. Dengan kontradiksi, andaikan p memuat pola-231. Artinya terdapat tiga unsur pada p, misalkan a,b dan c dengan a < b < c. Menurut proposisi

2 bagian ketiga, akan diperoleh unsur b akan mendahului unsur a pada s(p). Artinya s(p) bukan permutasi identitas sehingga p bukan permutasi stack sortable. Kontradiksi dengan p permutasi stack sortable. Jadi pengandaian salah, haruslah permutasi p tidak memuat pola-231. ■■ (  ) Misalkan permutasi p tidak memuat pola-231. Artinya untuk setiap pasang unsur-unsur pada p berada di situasi bagian pertama atau bagian kedua pada proposisi 2. Akibatnya untuk setiap pasang unsur di p, selalu unsur yang kecil mendahului unsur yang besar pada s(p). Dengan demikian s(p) akan membentuk permutasi identitas yang artinya p merupakan permutasi stack sortable. ■ Akibat dari Teorema 4, ada sebagian permutasi yang bukan permutasi stack sortable. Untuk meningkatkan banyaknya permutasi stack sortable, dapat dilakukan dengan menyortir lagi s(p) pada stack dengan menggunakan aturan yang sama. Jika permutasi yang diperoleh dari menyortir s(p) yang dinotasikan dengan s(s(p)) merupakan permutasi identitas ■ maka p disebut permutasi dua-stack sortable. Permutasi dua-stack sortable memiliki karakteristik yang lebih kompleks daripada permutasi stack sortable. Alasannya adalah permutasi dua-stack sortable bersifat tidak selalu monoton, di mana terdapat suatu permutasi yang merupakan permutasi duastack sortable namun subbarisan dari permutasi tersebut bukan permutasi duastack sortable. Sebagai contoh, permutasi q = 35241. Diperoleh s(q) = 32145 dan s(s(q)) = 12345 sehingga q disebut permutasi dua-stack sortable. Namun perhatikan subbarisan dari q, misalkan = 3241. Setelah disortir, diperoleh s( ) = 2314 dan

Tarakolo dan Suprijanto, Permutasi Dengan Panjang , 876

s(s( )) = 2134 sehingga bukan permutasi dua-stack sortable. Untuk alasan itulah, karakteristik permutasi dua-stack sortable tidak dapat ditentukan hanya dengan suatu pola yang tidak dimuat oleh permutasi tersebut. Namun, untuk menentukan karakteristik permutasi duastack sortable dapat menggunakan konsep yang serupa dengan permutasi stack sortable dan lebih membatasi definisi pola yang tidak dimuat. Teorema 5. Suatu permutasi p dikatakan permutasi dua-stack sortable jika dan hanya jika permutasi p tidak memuat pola2341 dan tidak memuat pola-3241 kecuali subbarisan dari pola-35241. Bukti. (  ) Misalkan p permutasi dua-stack sortable. Dengan kontradiksi, andaikan p memuat pola-2341. Misalkan a, b, c dan d dengan a < b < c < d adalah unsur-unsur pada p yang membentuk pola-2341. Setelah disortir melalui stack, unsur-unsur a, b dan c akan membentuk pola-231 pada s(p) yang mengakibatkan s(p) bukan permutasi stack sortable. Karena s(p) bukan permutasi stack sortable artinya s(s(p)) bukan permutasi identitas sehingga p bukan permutasi dua-stack sortable. Kontradiksi dengan p permutasi duastack sortable. (  ) Misalkan permutasi p tidak memuat pola-2341 dan tidak memuat pola3241 kecuali subbarisan dari pola-35241. Dengan kontradiksi, andaikan p bukan permutasi dua-stack sortable. Artinya s(p) bukan permutasi stack sortable karena s(s(p)) bukan permutasi identitas. Karena s(p) bukan permutasi stack sortable maka s(p) memuat pola-231. Misalkan e, f dan g dengan e < f < g adalah unsur-unsur pada s(p) yang membentuk pola-231. Menurut

proposisi 2, unsur e berada paling kanan dari unsur-unsur f dan g pada p. Karena e, f dan g membentuk pola-231 pada s(p) maka terdapat unsur h > g yang terletak di antara f dan g dengan e. Jika f mendahului g pada p maka fghe membentuk pola-2341 pada p. Kontradiksi dengan p tidak memuat pola2341. Jika g mendahului f pada p maka gfhe membentuk pola-3241 yang bukan subbarisan dari pola-35241. Kontradiksi dengan p tidak memuat pola-3241 kecuali subbarisan dari pola-35241. Jadi pengandaian salah. Haruslah p permutasi duastack sortable. ■ Akibat dari Teorema 5 ini, jumlah permutasi stack sortable bertambah dengan banyaknya permutasi dua-stack sortable. Untuk permutasi t-stack sortable tidak akan dibahas pada makalah ini. PENUTUP 1. Suatu permutasi p dengan panjang n dikatakan tidak memuat pola-q dengan panjang k dimana k ≤ n jika tidak terdapat subbarisan di p yang unsurunsurnya berelasi satu sama lain seperti unsur-unsur di q. 2. Terdapat 24 pola permutasi dengan panjang empat dimana terdapat ekuivalensi-ekuivalensi diantara 24 pola tersebut sehingga tersisa 3 pola yang benar-benar berbeda yaitu pola1324, 1234 dan 1342. ■ 3. Banyaknya permutasi dengan panjang n yang tidak memuat pola-1324 :

S n 1324  16n

4. Banyaknya permutasi dengan panjang n yang tidak memuat pola-1234 :

∑(

)(

)(

5. Banyaknya permutasi dengan panjang n yang tidak memuat pola-1342 :

)

877, KNPM V, Himpunan Matematika Indonesia, Juni 2013

dan tidak memuat pola-3241 kecuali subbarisan dari pola-35241.

∑

(

)

6. Suatu permutasi p dikatakan permutasi dua-stack sortable jika dan hanya jika permutasi p tidak memuat pola-2341 DAFTAR PUSTAKA Bona,

M. 2006. A Walk Through Combinatorics, An Introduction to Enumeration and Graph Theory, Second Edition, World Scientific. Bona, M. 2012. Combinatorics of Permutations, Second Edition, CRC Press. Bona, M. 2010. The Absence of A Pattern and The Occurrences of Another. Discrete Mathematics and Theore-

tical Computer Science. 12, no.2, 89102. J. Backelin, J. West, G. Xin. 2007. Wilf Equivalence for Singleton Classes. Adv. in Appl. Math. 38 no.2. 133148. Z.Stankova. 1994. Forbidden Subsequences. Discrete Math. 132, no.1-3. 291-316.