Loading [MathJax]/jax/output/HTML-CSS/jax.js

Entri yang Diunggulkan

Sekilas tentang kombinatorika

Kombinatorika secara umum dikatakan sebagai "matematika  pencacahan"; lebih lengkapnya, ia adalah matematika  tentang pencacahan ...

Sabtu, 19 November 2016

Himpunan Partisi

Misalkan ada 4 orang murid, sebut saja si A, B, C, dan D. Sang guru ingin membagi mereka menjadi beberapa kelompok, di mana setiap kelompoknya beranggotakan minimal satu orang. Ada berapa carakah mereka dikelompokkan? Untuk menjawabnya, mari kita tinjau semua kemungkinannya. Pengelompokan yang mungkin terbentuk adalah (setiap kelompok diapit oleh pasangan kurung kurawal):
Terbentuk satu kelompok saja, yaitu
  •  {A,B,C,D}
Terbentuk 2 kelompok, yaitu:
  • {A,B} dan {C,D}; atau 
  • {A,C} dan{B,D}; atau 
  • {A,D} dan {B,C}; atau
  • {A,B,C} dan {D}; atau
  • {A,B,D} dan {C}; atau
  • {A,C,D} dan {B}; atau
  • {B,C,D} dan {A}
Terbentuk 3 kelompok, yaitu:
  •  {A,B}, {C}, dan {D}; atau 
  • {A,C}, {B}, dan {D}; atau 
  • {A,D}, {B}, dan {C}; atau 
  • {B,C}, {A}, dan {D}; atau 
  • {B,D}, {A} dan {C}; atau 
  • {C,D}, {A} dan {B}
Terbentuk 4 kelompok, yaitu:
  • {A}, {B}, {C} dan {D}.

Jadi, sang guru memiliki 15 cara untuk mengelompokkan keempat murid tersebut.

Sekarang, mari kita tinjau masalah ini secara matematika. Keempat murid tersebut membentuk himpunan {A,B,C,D}.  Berdasarkan  uraian di atas, maka terdapat 15 cara (kemungkinan) untuk mengelompokkan elemen-elemen himpunan {A,B,C,D}. Nah, setiap cara pengelompokan dari {A,B,C,D}, misalnya {A,C} dan {B,D}, disebut himpunan partisi dari {A,B,C,D}. Lantas, apakah ciri-ciri dari himpunan partisi?  Perhatikan bahwa untuk himpunan {A,C} dan {B,D} berlaku

Oleh karena sifat tersebut, {A,C} dan {B,D} dikatakan sebagai dua himpunan yang saling lepas (disjoin). Di sisi lain, penggabungan {A,C} dan {B,D} menghasilkan himpunan induknya, yaitu {A,B,C,D}; atau secara matematis dinyatakan  $\{ A,C\}  \cup \{ B,D\}  = \{ A,B,C,D\}.$  Jadi, himpunan partisi memiliki 2 ciri yaitu: (1) saling lepas, dan (2) penggabungannya akan membentuk himpunan induk. Kalian bisa periksa bahwa ke-14 himpunan partisi lainnya memenuhi kedua ciri tersebut.


Nah, kemudian timbul pertanyaan: bagaimana untuk himpunan yang memiliki 5 anggota, misalnya {A,B,C,D,E}. Ada berapa himpunan partisi yang dapat dibentuk? Bagaimana untuk himpunan dengan anggota yang lebih banyak lagi? Tentu himpunan partisinya juga akan semakin banyak, bukan? Jawaban dari pertanyaan ini adalah: bilangan Bell. Beberapa urutan awal dari bilangan Bell adalah 1, 1, 2, 5, 15, 52, 203, 877, dst. Perhatikan bahwa suku ke-4 adalah 15. Hal ini dapat diartikan himpunan dengan 4 elemen memiliki 15 himpunan partisi (dengan kata lain, dapat dipartisi dengan 15 cara). Perhatikan pula bahwa semakin banyak elemen himpunan, maka banyak himpunan partisinya juga meningkat dengan cukup drastis. Misalnya, himpunan dengan 7 elemen, memiliki 877 himpunan partisi.

Pertanyaan berikutnya, bagaimana cara kita menuliskan seluruh himpunan partisi tersebut secara sistematis? Hmm, jawaban dari pertanyaan ini bisa menjadi artikel tersendiri. Ditunggu saja artikel selanjutanya ya...  (Bersambung)

Rabu, 09 November 2016

Problem Ballot (Kertas Suara)

Mumpung sedang happening perihal pilpres, pilkada, dll. Dalam kombinatorika, ada kelas kombinatorial yang disebut "barisan ballot". Ballot (kertas suara) adalah kertas yang dicoblos/dicontreng oleh pemilih untuk menentukan pilihannya.
Contoh ballot (kartu suara). (lessonpix.com)
Problem ballot adalah sebagai berikut: Dalam suatu pemilihan dengan 2 kandidat (A dan B), kandidat A memperoleh p suara dan kandidat B memperoleh q suara, dengan p>q. Berapakah peluang perolehan suara untuk A selalu lebih besar dari perolehan suara untuk B selama proses penghitungan?
Berikut ilustrasinya agar lebih jelas. Misalkan ada 5 pemilih, dengan hasil A mendapat 3 suara dan B 2 suara. Salah satu kemungkinan urutan penghitungan suaranya yang valid dalam problem ballot tersebut adalah AABAB. Mengapa demikian? Untuk AABAB, proses penghitungannya adalah A, AA, AAB, AABA, dan AABAB. Selama proses penghitungan, jumlah suara untuk A selalu > jumlah suara untuk B. Di sisi lain,  ABBAA adalah urutan penghitungan yang tidak valid. Poses penghitungan untuk ABBAA adalah A, AB, ABB, ABBA, dan ABBAA. Perhatikan bahwa saat penghitungan ballot kedua (AB), jumlah suara untuk B telah menyamai jumlah suara untuk A, sehingga melanggar syarat yang ditetapkan dalam problem ballot.

Sekarang, kita cari solusi dari problem ballot di atas, yaitu di mana p=3 dan q=2. Semua kemungkinan urutan penghitungannya (tanpa memandang valid/tidak valid) adalah: AAABB, AABAB, ABAAB, BAAAB, AABBA, ABABA, BAABA, ABBAA, BABAA, BBAAA. Nah, dari kesepuluh kemungkinan itu, yang valid hanya 2, yaitu AAABB dan AABAB, Oleh karena itu dalam kasus ini, peluang perolehan suara untuk A selalu lebih besar atau sama dengan perolehan suara untuk B selama proses penghitungan adalah 210=0,2.

Secara umum peluang yang ditanyakan dalam problem ballot ini diberikan oleh pqp+q.

Sabtu, 05 November 2016

Terbang dengan TGV

Setelah duduk manis, saya menunggu kereta berangkat. Seluruh kursi terisi penumpang, termasuk yang di sebelah saya. Mungkin karena saat itu Jumat sore, akhir pekan, sehingga saatnya orang-orang mudik dulu. TGV yang saya naiki bertujuan akhir Zurich (Swiss) via Dijon. Jarak Paris ke Dijon sekitar 350 km, dan akan ditempuh selama 1,5 jam. Berarti kecepatan rata-ratanya sekitar 230 km/jam. Nggak sabar juga ingin merasakan kecepatan seperti itu.

Sebuah TGV di Gare de Lyon, Paris.
Sebuah TGV di Gare de Lyon, Paris.

Namun, tidak sepanjang waktu kereta berlari dengan kecepatan di atas 300 km/jam. Sepanjang jalur rel Paris-Dijon, yang dapat dilalui dengan kecepatan tinggi adalah ruas Paris-Montbard, sedangkan Montbard-Dijon hanya dapat dilalui dengan kecepatan biasa (sekitar 100-150 km/jam). Montbard terletak sekitar pertengahan Paris-Dijon.
Akhirnya keretapun berangkat. Kesan terkuat yang saya rasakan adalah: senyap dan seperti melayang. Selepas dari Gare de Lyon, kereta masih berjalan perlahan membelah Paris bagian tenggara. Saya melepas pandangan ke luar jendela. Tampak bangunan-bangunan apartemen, grafiti di tembok, lalu lintas jalan raya, dan sebagainya. Sesekali berpapasan dengan kereta lain dari arah berlawanan. Keluar dari Paris, kereta melaju di antara ladang-ladang gandum dan padang rumput. Rute yang ditempuh datar, tidak melewati pegunungan,
Di suasana yang senyap itu, saya merasakan kereta mulai berakselerasi. Layar LCD yang dipasang di dinding depan menampilkan informasi kecepatan kereta saat ini. Perlahan angka 200km/jam dilewati, dan terus meningkat sampai 280 km/jam. Pohon-pohon dan tiang yang ada di pinggir rel begitu cepatnya terlihat melintas di jendela. Suspensi kereta sangat lembut, tidak ada getaran sedikitpun, sehingga saya merasa kereta seperti melayang bahkan terbang. Begitulah yang saya rasakan, sampai akhirnya kereta mulai mendekati Montbard. Petugas mengumumkan, dengan dwi bahasa (Perancis dan Inggris), bahwa kereta akan berhenti di Montbard, dan agar penumpang yang ingin turun segera bersiap-siap.

Gare de Dijon (www.kyriaddijon.com)

Gare de Dijon dilihat dari atas. (www.wikimedia.com)

Setelah Montbard, keretapun melaju lagi, namun kali ini tidak dengan kecepatan super, karena jalur Montbard-Dijon tidak mendukung kecepatan di atas 200 km/jam. Pemandangan kiri-kanan pun berganti menjadi bukit-bukit dan lembah landai. Sesekali terrlihat kawanan sapi sedang merumput. Walaupun demikian, jalur kereta tetap datar. Akhirnya, setelah menempuh perjalanan selama 1,5 jam, petugas mengumumkan bahwa kereta segera tiba di Dijon. Sayapun bangkit dari kursi, mengambil koper dan bersiap di dekat pintu keluar. Hari sudah mulai gelap dan lampu-lampu kota Dijon sudah menyala. Setelah kereta berhenti sempurna di Dijon Gare (stasiun Dijon), pintupun terbuka. Saya turun dari kereta. Bienvenue a Dijon!

Tua di Luar, Modern di Dalam

Gare de Lyon adalah salah satu di antara sejumlah stasiun besar di Paris; usianya sudah lebih dari 100 tahun. Stasiun ini melayani rute menuju kota-kota besar di tenggara Perancis (seperti Dijon dan Lyon), sampai dengan Swiss (Zurich). Kereta yang dioperasikan dari stasiun ini sebagian besar adalah kereta kecepatan tinggi TGV (train à grande vitesse). Kereta ini bisa berlari sampai lebih dari 300 km/jam. Kereta jenis TGV inilah yang akan saya naiki untuk menuju Dijon. Oya, seluruh kereta rute nasional di Perancis dioperasikan oleh perusahaan nasional SNCF (seperti KAI di Indonesia). Selain itu, ada kereta Eurostar (berangkat dari stasiun Gare du Nord) dengan trayek Paris - London melalui terowongan bawah laut selat Channel.

Gare de Lyon, Paris (parisinfo.com)
 Yang pertama kali saya lakukan adalah: beli tiket. Setelah celingak-celinguk, akhirnya saya menemukan loket penjualan tiket. Loketnya terbagi dua jenis: ada yang untuk langsung berangkat (depart immmediat) dan ada juga yang untuk berangkat di waktu lain. Saya mengantri di loket depart immediat. Sambil mengantri, saya memperhatikan bahwa ternyata orang bisa juga beli tiket melalui mesin tiket. Dengan mesin ini, orang tidak perlu mengantri karena tersedia cukup banyak mesin.
Saya sudah menyiapkan kertas bertuliskan "Dijon" untuk saya tunjukkan kepada petugas loket. Saya dapat info bahwa mereka mungkin bisa salah dengar menjadi "Lyon". Maklum, lidah kita kan belum fasih banget bicara di tenggorokan seperti orang Perancis natif hehe. Setelah dapat giliran, sayapun mengucapkan tujuan saya, dan untungnya petugas langsung mengerti bahwa yang saya maksud adalah "Dijon". Jadi saya urung menunjukkan kertas itu. Tiket ke Dijon untuk depart immediat bertarif 65 euro. Harga tiket bisa lebih murah jika beli jauh-jauh hari (maksimum tiga bulan sebelum keberangkatan).
Loket tiket (kiri) dan mesin tiket (kanan) (www.lefigaro.fr)
Setelah tiket di tangan, saya celingukan lagi, apa yang mesti saya lakukan berikutnya? Melihat apa yang dilakukan orang-orang, tampaknya saya harus memvalidasi tiket sebelum naik kereta. Istilahnya adalah "composter". Terdapat banyak mesin validasi bertebaran di seluruh penjuru stasiun. Kita tinggal memasukkan sebagian tiket dengan posisi menghadap ke atas, ke dalam mesin. Setelah itu, mesin akan mencetak kode validasi pada tiket. Kalau nanti di atas kereta kondektur mendapati tiket belum divalidasi, kita bisa kena denda, Untuk lebih yakinnya, saya bertanya kepada petugas, sekalian bertanya kereta saya ada di peron berapa. Ternyata, petugas bilang bahwa tiket saya tidak perlu divalidasi lagi. Saya nggak terlalu tahu sebabnya apa. Tapi saya turuti saja.

Suasana di Gare de Lyon, Paris.

Memvalidasi tiket dengan mesin validasi (media.rtl.fr)
Untuk mengetahui di peron berapa kereta kita, tersedia informasi real time pada beberapa LCD besar. Di situ tertera nomor kereta, tujuan, jadwal berangkat, dan nomor peron. Kita tinggal mencocokkan nomor kereta yang tertera di tiket dengan yang terpampang di LCD. Mungkin saja nomor kereta kita belum muncul karena keberangkatannya masih lama.

Akhirnya, kereta sayapun tiba. Saya segera menuju gerbong dengan nomor yang tertera pada tiket. Setelah itu, saya segera mengantri untuk naik. Gerbong yang saya naiki terdiri dari dua lantai. Saya dapat di lantai bawah. Setelah meletakkan koper besar saya di tempat yang disediakan, saya segera menuju tempat duduk. (Bersambung)

Jumat, 04 November 2016

Dan perjalanan panjang itupun dimulai...

Kisah ini mengawali rangkaian masa studi saya jauh dari tanah air. Hari itu, suatu Sabtu di pertengahan September 2012, setelah perjalanan 18 jam Jakarta-Doha-Paris, pesawat yang saya tumpangi, sebuah Airbus A340 Qatar Airways, akhirnya mendarat di bandara Charles de Gaulle (CDG), Paris.

Setelah pesawat parkir dan pintu dibuka, para penumpang mengantri keluar dari pesawat melalui garbarata (belalai gajah).  Antrian masih terjadi sampai ke dalam gedung. Saya berpikir ada apa ya? Ternyata di ujung antrian telah menunggu beberapa polisi imigrasi. Mereka memeriksa paspor penumpang dengan teliti, mencocokkan foto di paspor dengan pemegangnya, dan kadang-kadang juga mereka menanyakan sesuatu kepada yang bersangkutan. Saya deg-degan juga, sebab ada satu-dua penumpang yang diminta minggir dulu, sepertinya ada masalah. Ketika tiba giliran saya, mereka memeriksa paspor saya. Alhamdulillah tidak ada pertayaaan apapun, dan saya dipersilakan untuk lewat.
Setelah pemeriksaan polisi, penumpang berjalan melalui travelator dan akhirnya sampai di loket imigrasi. Di sini kita mengantri lagi untuk cap imigrasi pada paspor. Seringkali petugas imiggrasi bertanya tentang tujuan kita ke Perancis, tinggal di mana, berapa lama, dan sebagainya. Kalau sudah ditanya-tanya begitu, bisa aja mereka minta kita tunjukkan dokumen pendukungnya, seperti surat keterangan diterima di universitas, surat keterangan tempat tinggal, dan sebagainya. Kalau dokumennya dianggap bermasalah atau kurang lengkap, kita bisa disuruh untuk minggir dulu, dan persoalan bisa jadi ribet nantinya. Akhirnya tiba giliran saya. Walaupun dokumen saya lengkap, tetap saja saya deg-degan. Saya menyerahkan paspor saya kepada petugas. Sang petugaspun memeriksanya. Tanpa bicara sepatah katapun, ia langsung mencap paspor saya. Yess!!

Antrian pos imigrasi. (http://www.parisgeo.cnrs.fr/)
Jalur keluar setelah ambil bagasi.

Setelah ambil bagasi, sayapun mencari pangkalan bus shuttle bandara. Sebagai informasi,  terdapat berbagai transportasi umum menuju bandara CDG, seperti: KRL (di sini disebut RER), TGV (kereta kecepatan tinggi), bus kota reguler,  dan bus  shuttle bandara.   Nah, saya memilih naik bus bandara, karena salah satu trayeknya, yaitu  no. 4, bertujuan  ke Gare de Lyon (salah satu stasiun besar di Paris untuk kereta-kereta jurusan tenggara Prancis, termasuk Dijon, kota yang saya tuju). Bus  ini dioperasikan oleh  Air France. Kala itu nama busnya "Les Cars Air France", namun sekarang menjadi "Le Bus Direct". Mungkin manajemennya bukan Air France lagi? Entahlah.
Bus Bandara Les Cars Air France
Metro RER 
Saat keluar dari gedung bandara, saya langsung diterpa oleh hawa dingin yang belum pernah saya rasakan sebelumnya. Suhu AC  terdingin yang pernah saya rasakan cuma 16 derajat. Yang saya alami sekarang ini mungkin di bawah 10 derajat. Brrr, tidak terbayang bagaimana suhu di musim dingin nanti yang suhunya katanya bisa sampai di bawah nol.

Setelah bus yang saya tunggu datang, para calon penumpang segera mengantri untuk naik dari pintu depan. Orang-orangpun antri dengan tertib untuk naik bus.
Bus tidak memiliki kondektur. Kita langsung bayar ke supir, bisa bayar tunai ataupun pakai kartu bank. Supirnya juga bisa bahasa Inggris. Setelah membayar 17,5  euro, saya pun langsung cari tempat duduk kosong. Oiya, koper besar sudah ditaruh di bagasi bus sebelum kita naik. Jadi yg kita bawa ke dalam cuma tas kabin saja.
Bus mengitari areal bandara untuk mengambil beberapa penumpang lagi di sejumlah halte. Keluar dari area bandara, bus melaju di jalan bebas hambatan sampai akhirnya sampai di Paris. Lokasi bandara CDG berada di luar kota Paris, seperti halnya bandara Soekarno-Hatta kita, yg berada di luar kota Jakarta.
Saat itu jam pulang kerja. Ternyata di Paris ada macet juga. Bedanya, macetnya tidak sampai total, dan tidak banyak motor seperti di Jakarta. Ini karena sistem transportasi massal di Paris sangat andal. Buspun berjalan di lalu lintas yang padat merayap. Saya berharap bus akan melintas dekat menara Eiffel, namun ternyata tidak karena rute yang dilalui tidak melintasi pusat kota. Sementara saya simpan dulu keinginan untuk melihat menara Eiffel. Saya akan kembali lain waktu.
Halte bus bandara di stasiun Gare de Lyon (parisinfo,com)

Begitulah, akhirnya bus tiba di halte Gare de Lyon. Haltenya tidak besar. Sejumlah penumpang termasuk saya turun untuk melanjutkan perjalanan. Sambil menggeret koper dan memikul tas ransel, saya celingak celinguk sebentar untuk mencari lobi stasiun. Tadi rasanya saya melihat stasiunnya, tapi kok sekarang nggak ada ya? Sebenarnya lokasi stasiun ada di belakang halte, namun tidak kelihatan karena posisinya lebih tinggi. Di belakang halte ada tangga untuk menuju lobi stasiun. Tapi karena saya tidak ngeh, saya ambil jalan memutar. Tapi sudahlah, yang penting saya sudah sampai di stasiun hehe... Tahap selanjutnya adalah beli tiket kereta dan berangkat ke Dijon!

(Bersambung)