Merepresentasikan Subhimpunan dengan Menggunakan Untai Biner

Dalam matematika, sebuah struktur/objek matematika pada umumnya dapat direpresentasikan dalam berbagai bentuk. Contohnya, fungsi dapat direpresentasikan dalam bentuk formula, tabel, diagram, ataupun grafik. Demikian pula halnya dengan himpunan, yang dapat direpresentasikan dalam bentuk eksplisit (menuliskan semua elemennya, misalnya: {a,b,c,d}), dalam bentuk generator (hanya menuliskan kriterianya saja; misalnya: {x|x bilangan genap}), ataupun dalam bentuk diagram Venn.

Selanjutnya, baca di sini

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)

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 $\frac{2}{10}=0,2$.

Secara umum peluang yang ditanyakan dalam problem ballot ini diberikan oleh $\frac{p-q}{p+q}$.

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)

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)

Untai biner hindar 11

Kelas untai biner (binary words) bukanlah kelas yang asing dalam kombinatorika. Ia adalah kelas untai yang simbolnya terdiri dari 0 atau 1, semisal 0010, 1110100110, dan sebagainya. Himpunan untai biner ${s_1} \ldots {s_n}$ memiliki kardinalitas $2^n$ (karena setiap ${s_i}$ dapat bernilai 0 atau 1). Sebagai contoh, terdapat ${2^3} = 8$ untai biner dengan panjang 3, yaitu 000, 001, 010, 011, 100, 101, 110, dan 111.

Bagaimana dengan kelas untai biner hindar 11? Nama kelas ini, yang dalam bahasa Inggrisnya disebut binary words avoiding two consecutive ones, terdengar tidak familiar. Dari istilahnya, dapat diketahui bahwa ia adalah kelas untai biner yang tidak memuat dua simbol ‘1’ secara berurutan. Sebagai contoh, 0010100, 101001010 adalah untai biner hindar 11, sedangkan 110111000 bukan. Tabel berikut adalah himpunan untai biner dengan panjang $n$, untuk $n = 1,2,...,5$, yang diperoleh dengan cara menuliskan semua untai biner dengan panjang $n$ tertentu, dan mencoret untai yang memuat '11'. Di baris paling bawah adalah kardinalitasnya untuk setiap $n$.

Jika diperhatikan kardinalitasnya, membentuk pola barisan apakah ia? Barisan Fibonacci! Berdasarkan pola ini, anda tentu dapat mengetahui kardinalitas kelas di atas untuk n=6,7, dan seterusnya. Salah satu kajian algoritmis tentang kelas ini diberikan oleh Vajnovszki (2001)

Kombinatorika Enumeratif

Hal menarik dan menjadi tantangan dalam kombinatorika adalah: berapakah kardinalitas (banyaknya anggota) untuk suatu himpunan objek kombinatorial? Ini adalah kajian mendasar dari kombinatorika enumeratif. Sebagai contoh: terdapat 120 permutasi himpunan {H,I,J,K,L}. Dengan kata lain, 210 adalah kardinalitas dari permutasi himpunan {H,I,J,K,L}. Terdapat 210 cara untuk memilih 4 sukarelawan dari 10 orang yang ada. Umumnya siswa sekolah menengah dapat memahami konsep kardinalitas dalam permutasi dan kombinasi, dan memecahkan variasi dari masalah-masalah tersebut, sebagaimana contoh berikut ini:

Berapakah banyak plat nomor kendaraan yang dapat dibentuk, jika plat nomor tersebut diawali dengan huruf B, diikuti empat angka (tidak diawali angka 0), dan diakhiri dengan tiga huruf?

Pertanyaan yang sama, namun jika angkanya hanya terdiri dari tiga angka?

Pertanyaan yang sama, namun jika diakhiri dengan dua huruf?

Terdapat beberapa cara untuk menemukan kardinalitas dari himpunan objek kombinatorial. Cara pertama adalah dengan menggunakan formula eksplisit. Cara ini bersifat "straightforward", langsung memperoleh hasil dengan sekali jalan. Contohnya, kardinalitas dari permutasi $n$ objek diberikan oleh formula $n!$ (dibaca: n faktorial). Contoh: $5!=5\times 4\times 3\times 2\times 1=120$, dan $10!=10\times 9\times\ldots\times 2\times 1=3.628.800$. Banyaknya himpunan bagian dari himpunan $n$ objek adalah $2^n$. Misalnya, himpunan dengan 3 anggota $\{a,b,c\}$ memiliki $2^3$ himpunan bagian, yaitu: $\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\}, \{a,b,c\}$ dan $\{\}$ (himpunan kosong) (demikian pula kardinalitas untai biner dengan panjang $n$).

Cara kedua adalah dengan menggunakan formula rekurensi.  Kardinalitas dari untai biner dengan panjang $n$ yang tidak memuat simbol '11' (dua angka 1 yang berurutan) diberikan oleh $f(n) = f(n - 1) + f(n - 2)$, di mana f$(1) = f(2) = 1$ (baca artikel ini). Pastinya anda mengenal bahwa $f(n)$ adalah suku ke $n$ dari barisan Fibonacci. (Sekedar diingat, pola barisan Fibonacci adalah 1,1,2,3,5,8,13, dst. Suku berikutnya adalah jumlah dari dua suku sebelumnya). Perhatikan bahwa $f(n)$ adalah fungsi rekurensi. Berbeda dengan fungsi eksplisit, fungsi rekurensi tidak bersifat straightforward, karena perlu beberapa tahap untuk mengevaluasi nilai fungsi pada $n$ tertentu. Sebagai contoh: untuk menghitung $f(5)$ dilakukan dengan cara berikut:

$$\begin{array}{l} f(5) = f(4) + f(3)\\  = (f(3) + f(2)) + (f(2) + f(1))\\  = ((f(2) + f(1)) + f(2)) + (f(2) + f(1))\\  = ((1 + 1) + 1) + (1 + 1)\\  = 5 \end{array}$$

Cara ketiga adalah dengan menggunakan formula asimtotis  $f(n) \sim g(n)$, yang secara naif berarti $g(n)$ semakin mendekati $f(n)$ untuk nilai $n$ yang cukup besar. Secara matematis berlaku  $\lim \limits_{x \to \infty } \frac{{f(n)}}{{g(n)}} = 1$. Misalnya, ada berapa banyak permutasi 20 objek? Menghitung 20! secara eksak adalah pekerjaan yang "boros" bagi komputer.  Selain itu mungkin perlu ditinjau kembali, apakah dibutuhkan hasil yang eksak atau cukup dengan aproksimasi saja? Jika hanya membutuhkan aproksimasi, maka n! dapat didekati oleh $\sqrt {2\pi n} {\left( {\frac{n}{e}} \right)^n}$. Untuk $n=20$, formula asimtotis ini memberikan hasil $2,4228 \times {10^{18}}$, sedangkan hasil eksaknya adalah  $2.432.902.008.176.640.000$.

Cara keempat adalah dengan menggunakan fungsi pembangkit (generating function). Ekspansi dari fungsi pembangkit mensimulasikan semua objek pada kelas tersebut. Setiap suku merepresentasikan sebuah kemungkinan objek yang dapat dibentuk, dan koefisien untuk suku tersebut merepresentasikan ada berapa cara membentuk objek tersebut. Jadi, yang diinginkan dari fungsi pembangkit adalah koefisien-koefisien pada suku-sukunya, dan bukan nilai fungsi tersebut.  Sebagai contoh, diberikan himpunan {q,r,s,t,u}. Ada berapakah subhimpunan tiga anggota yang dapat dibentuk? Atau pertanyaan matematisnya: ada berapa banyak 3-subhimpunan dari {q,r,s,t,u}? Karena himpunannya hanya terdiri dari 5 elemen, kita dapat menuliskan semua kemungkinannya yaitu: {q,r,s}, {q,r,t}, {q,r,u}, {q,s,t}, {q,s,u}, {q,t,u}, {r,s,t}, {r,s,u}, {r,t,u}, {s,t,u}. Terdapat 10 kemungkinan subhimpunan, dan itulah jawaban dari masalah ini.

Sekarang kita cari pemecahannya dengan menggunakan fungsi pembangkit. Fungsi pembangkit dari masalah ini diberikan oleh ${(x + y)^5}$. Namun ini bukan jawaban dari permasalahan ini, karena jawabannya terdapat pada koefisien dari ekspansi fungsi pembangkit. Mengapa demikian?  Misalkan x melambangkan sebuah "elemen anggota subhimpunan", dan y melambangkan sebuah "elemen bukan anggota subhimpunan". Oleh karena itu, ekspresi ${x^m}{y^n}$ melambangkan "terdapat $m$ elemen anggota subhimpunan", dan "terdapat $n$ elemen bukan anggota subhimpunan" (dalam masalah ini, $m+n=5$). Karena subhimpunan yang dimaksud terdiri atas tiga elemen, maka subhimpunan ini direpresentasikan sebagai ${x^3}{y^2}$, dan ini dapat berarti: $xxxyy$, $xxyxy$, $xxyyx$, $xyxxy$,  $xyxyx$, $xyyxx$, $yxxxy$, $yxxyx$, $yxyxx$, $yyxxx$. Terdapat 10 kemungkinan. Namun mencacah dengan cara ini tentu sangat merepotkan. Cara yang lebih efisien adalah cukup dengan mengekspansi ${(x + y)^5}$, dan jawabannya ada pada koefisien untuk suku ${x^3}{y^2}$. Ekspansi dari ${(x + y)^5}$ adalah ${x^5} + 5{x^4}y + 10{x^3}{y^2} + 10{x^2}{y^3} + 5x{y^4} + {y^5}$, dan koefisien dari suku ${x^3}{y^2}$ adalah 10, yang merupakan jawaban dari masalah ini.

Permutasi dan Kombinasi

Terdapat demikian banyaknya kelas kombinatorial. Berdasarkan konteks pengkajiannya, kelas kombinatorial disajikan dalam representasi tertentu, antara lain dalam bentuk graf, diagram, matriks, ataupun untai/barisan (string/words/sequences). Contohnya, permutasi dan kombinasi umumnya direpresentasikan dalam bentuk barisan, dan mereka merupakan kelas yang sangat familiar bagi para pelajar sekolah menengah. Namun, tentunya kelas-kelas kombinatorial tidak hanya itu. Berikut disajikan beberapa kelas kombinatorial yang cukup familiar.

Permutasi

Misalkan di sebuah taman terdapat  sebuah bangku panjang yang dapat memuat 3 orang. Pada saat yang bersamaan, ada tiga orang, sebut saja A, B, dan C, yang ingin duduk di bangku tersebut. Ada berapakah kemungkinan urutan duduk dari ketiga orang itu pada bangku tersebut?

Ketiga orang tersebut dapat duduk dalam enam kemungkinan urutan: ABC, ACB, BAC, BCA, CAB, dan CBA. Nah, setiap kemungkinan urutan itu disebut sebagai permutasi, atau lengkapnya permutasi dari himpunan $\{A,B,C\}$. Dalam hal ini, permutasi memiliki kardinalitas 6.  Ilustrasi berikut menggambarkan keenam kemungkinan tersebut:

6 kemungkinan posisi duduk untuk A, B, dan C.

Bagaimana jika ada empat orang yang ingin duduk? Tentu satu orang tidak mendapat tempat, sehingga ia harus berdiri. Jika si D yang berdiri, maka A, B, dan C memiliki enam cara untuk duduk. Demikian pula jika si A yang berdiri, maka B,C, dan D memiliki enam cara untuk duduk. Sama halnya jika, B atau C yang berdiri, maka ketiga orang lainnya memiliki enam cara untuk duduk. Jadi, jawaban dari persoalan ini adalah: terdapat 24 susunan duduk untuk tiga orang dari empat orang yang ada. Persoalan ini dapat dikatakan sebagai permutasi 3 dari 4, dan dinotasikan sebagai $P(4,3)$ (notasi lainnya adalah $_4P_3$, $P_4^3$, dan $P_{4,3}$ ).

Masih meneruskan persoalan di atas, bagaimana jika ada lima orang yang ingin duduk? Jawabannya adalah permutasi 3 dari 5, atau $P(5,3)=60$. Jika enam orang? Jawabannya adalah $P(6,3)=120$. Pertanyaan yang lebih umum: bagaimana jika terdapat $n$ orang? Jawabannya adalah $P(n,3)$.

Nah, bagaimana kalau kapasitas bangkunya yang ditambah. Misalkan kita ganti bangkunya dengan yang lebih besar sehingga mampu memuat empat orang. Jika ada empat orang yang ingin duduk, maka jawabannya adalah permutasi 4 dari 4 (dalam hal ini cukup disebut sebagai permutasi-4), dinotasikan sebagai $P_4$. Jika ada lima orang? Jawabannya adalah $P(5,4)=120$.

Sekarang, kita bicara secara umum: jika sebuah bangku dapat memuat $k$ orang dari $n$ orang yang ada, terdapat berapa kemungkinan susunan duduk $k$ orang tersebut pada bangku? Tapi tunggu dulu. Sebelum dijawab, kita harus menyadari bahwa masalah ini tentu tidak hanya untuk bangku taman. Oleh karena itu, kita dapat mengajukan pertanyaan yang lebih umum, yaitu: ada berapa cara untuk mengurut $k$ objek dari $n$ objek yang tersedia? Jawabannya adalah $P(n,k)=\frac{n!}{(n-k)!}$.

Kombinasi

Sebuah klub olahraga futsal memiliki anggota 12 orang anggota.  Pada suatu kompetisi, sang pelatih akan memilih 5 orang di antara mereka untuk membentuk sebuah tim bertanding. Anggaplah semua anggota memiliki skill yang sama, sehingga setiap orang memiliki kesempatan yang sama untuk dipilih. Ada berapa kemungkinankah tim bertanding yang dapat dibentuk?
Dalam permasalahan ini, urutan pemilihan tidaklah penting. Tim yang beranggotakan si A, B, C, D, dan E, adalah sama dengan tim yang beranggotakan si C, E, D, B, dan A. Nah, karena urutan pemain tidak penting, maka masalah ini disebut masalah kombinasi. Setiap kemungkinan tim yang dapat dibentuk disebut kombinasi 5 orang dari 12 orang, atau singkatnya, kombinasi 5 dari 12, dan dinotasikan sebagai $C(12,5)$.
Secara umum, $C(n,k)=\frac{n!}{k!(n-k)!}$, sehingga $C(12,5)=792$. Jadi, terdapat 792 kemungkinan tim yang dapat dibentuk.

Sekilas tentang kombinatorika

Kombinatorika secara umum dikatakan sebagai "matematika pencacahan"; lebih lengkapnya, ia adalah matematika tentang pencacahan (enumerasi), eksistensi, konstruksi, dan optimisasi berkenaan dengan himpunan hingga yang memenuhi konfigurasi tertentu. 

Himpunan-himpunan yang memiliki konfigurasi sama tersebut membentuk suatu "kelas kombinatorial", yaitu kumpulan objek sejenis yang mengemban sejumlah sifat-sifat kombinatorika. 

Dalam kehidupan sehari-hari, sebuah koin mata uang dipandang sebagai sebuah objek. Namun secara kombinatorika, koin dapat dianggap sebagai dua buah objek, yaitu: koin dengan sisi angka, dan koin dengan sisi gambar. Karena sifat-sifat kombinatorial inilah, koin membentuk sebuah kelas kombinatorial. Sebuah koin terdiri memiliki dua objek; dua buah koin memiliki empat objek; tiga buah koin memiliki delapan objek, dan seterusnya. Demikian halnya dengan sebuah dadu. Sebuah dadu memiliki enam objek; dua buah dadu memiliki tiga puluh enam objek; dan seterusnya. 

Contoh lainnya, "pakaian" dapat dipandang sebagai suatu kelas kombinatorial. Misalnya sebuah objek pakaian didefinisikan terdiri dari unsur "baju" dan "celana" (karena terdiri dari dua unsur maka dikatakan sebagai "pakaian berukuran 2") Nah, misalkan pula baju dan celana dapat memiliki warna tertentu saja, yaitu biru (B), merah (M), atau kuning (K). Berbagai kemungkinan warna inilah yang memunculkan sifat-sifat kombinatorika pada objek pakaian. Kita dapat memiliki berbagai kemungkinan pakaian yang dapat dibentuk, misalkan  baju kuning, celana merah (KM); baju kuning, celana biru (KB); baju merah, celana kuning (MK), dan berbagai kemungkinan lainnya. 

Kombinatorika "mengabstraksi" objek-objek tersebut. Jadi, tidak terlalu penting apakah objek itu pakaian, mobil, dadu, atau yang lainnya. Agar dapat "dikaji" secara kombinatorika, terdapat sejumlah cara untuk merepresentasikan objek nyata, antara lain dengan graf, barisan (sebutan lainnya untai, kata, string, sequences/words), atau diagram.

Dengan mengabstraksikan objek pakaian sebagai "barisan", terbentuk sebuah himpunan yang memiliki 9 anggota, yang setiap anggotanya berupa barisan berukuran 2, yaitu BB, BM, BK, MB, MM, MK, KB, KM, dan KK, sebagaimana ilustrasi berikut:

Selanjutnya, misalkan didefinisikan pakaian berukuran 3, dengan sebuah unsur tambahan "sepatu". Misalkan pula sepatu memiliki dua kemungkinan warna, yaitu hijau (H) dan coklat (C). Maka akan terbentuk himpunan berukuran 3 yang memiliki 18 anggota yaitu BBH, BBC, BMH, BMC, BKH, BKC, MBH, MBC, MMH, MMC, MKH, MKC, KMH, KMC, KKH, KKC, sebagaimana ilustrasi berikut:

Dengan cara menambah unsur pembentuk pakaian, kita dapat mendapatkan himpunan pakaian berukuran 4, 5, dan seterusnya. Himpunan-himpunan pakaian dengan berbagai ukuran tersebut membentuk sebuah kelas kombinatorial "pakaian".

Nah, untuk kelas pakaian di atas, dapat diajukan pertanyaan-pertanyaan, antara lain:

• Bagaimana cara mengetahui semua kemungkinan kombinasi pakaian dengan ukuran tertentu? Pertanyaan ini terkait dengan konstruksi.
• Bagaimanakah menghitung banyaknya kemungkinan pakaian dengan ukuran tertentu? Pertanyaan ini terkait dengan enumerasi.
• Ada berapa banyak kombinasi pakaian yang mungkin jika celana merah dilarang digunakan? Pertanyaan ini terkait dengan restriksi.
• Pada kelas pakaian yang diuraikan di atas, apakah terdapat pakaian dengan baju putih, celana merah, sepatu putih? Pertanyaan ini terkait dengan eksistensi.

.... dan banyak lagi. Berbagai pertanyaan itulah yang membentuk berbagai kajian dalam kombinatorika, seperti kombinatorika enumeratif, kombinatorika optimasi, aljabar kombinatorika.

Terdapat banyak sekali kelas-kelas kombinatorial, dan mungkin kelas yang paling primitif adalah kelas bilangan biner. Kelas lainnya contohnya adalah permutasi, permutasi multi himpunan, partisi himpunan, partisi integer, dan banyak lagi (bahkan, rantai DNA adalah sebuah kelas kombinatorial). 
Mungkin titik awal lahirnya kombinatorika sebagai cabang formal dari matematika adalah pada tahun 1736 ketika Euler membuktikan ketiadaan solusi pada masalah "Tujuh jembatan Königsberg". Namun, manusia mengenal problem-problem kombinatorika jauh sebelum itu. Umumnya bersifat rekreatif, seperti Chinese rings dan diagram Murasaki. 
Saat ini, kajian-kajian dalam kombinatorika telah diterapkan dalam domain ilmu lainnya, seperti kriptografi, bioinformatika, geometri, statistika, dan bahkan untuk hal-hal rekreatif seperti memecahkan puzzle.