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 ${\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 $\left(\genfrac{}{}{0ex}{}{m}{0}\right)\left(\genfrac{}{}{0ex}{}{n}{k}\right)+\left(\genfrac{}{}{0ex}{}{m}{1}\right)\left(\genfrac{}{}{0ex}{}{n}{k-1}\right)+\cdots +\left(\genfrac{}{}{0ex}{}{m}{k}\right)\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\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+\cdots +a_{20}=10\}$. Banyaknya barisan $\alpha$ sehingga $a_1+a_2+\cdots +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.