Naskah Soal ONMIPA PT 2011 — Kombinatorika

Pada sebuah permutasi acak dari $26$ huruf $\{a,b,c,d,\dots, z\}$, peluang bahwa huruf $b$ muncul tepat setelah huruf $a$ adalah $\dots$

Misalkan $A$ adalah himpunan dengan $n$ elemen dan $B$ adalah himpunan dengan $m$ elemen dengan $m \le n$. Banyaknya pemetaan satu-satu (injektif) dari $B$ ke $A$ adalah $\dots$

Solusi untuk formula rekursif $v_n = v_{n - 1} + n!n$ dengan $v_0 = 0$ untuk semua $n \in \mathbb{Z}^+$ adalah $\dots$

Misalkan $n$ adalah bilangan delapan digit yang disusun dari enam digit berbeda dengan digit pertama adalah 5. Bila $n$ memuat tiga digit yang sama tetapi bukan 5, maka banyaknya cara menyusun $n$ tersebut adalah $\dots$

Koefisien $x^{104}$ dalam ekspansi $\displaystyle \left(x - \frac{3}{5x}\right)^{210}$ adalah $\dots$

Misalkan $\pi$ adalah permutasi atas himpunan $\{1,2,3,\dots,8\}$. Banyaknya permutasi $\pi$ sehingga bilangan genap tidak dipetakan ke dirinya sendiri adalah $\dots$

Untuk setiap $m,n,k\in\mathbb{N}$, nilai dari $\displaystyle \binom{m}{0}\binom{n}{k} + \binom{m}{1}\binom{n}{k - 1} + \dots + \binom{m}{k}\binom{n}{0} = \dots$

Misalkan $\alpha$ adalah sebuah barisan $a_1,a_2,\dots,a_{20}$ dengan nilai $a_i$ adalah 1 atau 0 untuk semua $i = 1,2,\dots, 20$. Misalkan $X = \{\alpha : a_1 + a_2 + \dots + a_{20} = 10\}$. Banyaknya barisan $\alpha$ sehingga $a_1 + a_2 + \dots + a_{10}\in\{0,1,2\}$ adalah $\dots$

Misalkan $1 \le n \le 2011$ dengan $n$ bilangan asli yang memuat digit 0. Banyaknya $n$ yang demikian adalah $\dots$

Jumlah semua bilangan desimal $0,xyz$ dengan $x,y,$ dan $z$ merupakan tiga digit yang berbeda adalah $\dots$

Tentukan banyaknya bilangan bulat dari $1$ sampai $99999$ sehingga jumlah digit-digit pada bilangan tersebut adalah 22.

Pada suatu acara seminar matematika dihadiri oleh $n$ orang peserta seminar. Tunjukkan bahwa di antara para peserta seminar tersebut, senantiasa terdapat dua orang peserta seminar yang mempunyai jumlah kenalan yang sama.

Sebuah graf dikatakan $k$-reguler bila setiap titik mempunyai derajat $k$. Sebuah perfect matching dari sebuah graf dengan $n$ titik adalah himpunan $n/2$ sisi yang saling asing. Perlihatkan bahwa bila $G$ adalah sebuah graf bipartit $k$-reguler, maka $G$ mempunyai perfect matching.