Naskah Soal ONMIPA PT 2014 — Kombinatorika

Pada suatu daerah, setiap nomor telepon terdiri dari 6 angka yang diawali dengan angka 6. Jika Anda mengajukan pemasangan untuk mendapatkan nomor telepon yang memuat tidak lebih dari 4 angka berbeda, besarnya peluang Anda mendapat nomor dimaksud adalah $\dots$

Solusi dari fungsi rekursif $f(n+1)=f(n)+2f(n-1),\forall n>2$, di mana $f(1)=1,f(2)=5$, adalah $\dots$

Koefisien dari $x^{128}$ dalam ekspansi ${\left(\frac{x}{2}-\frac{2}{7x}\right)}^{236}$ adalah $\dots$

Banyaknya semua susunan huruf yang terdiri dari tujuh huruf berbeda sedemikian sehingga huruf pertama, huruf di tengah, dan huruf terakhir adalah sebuah huruf vokal, sedangkan empat huruf lainnya adalah huruf konsonan adalah $\dots$

Pada sebuah wahana terdapat 4 jenis koin bernilai 1.000, 5.000, 10.000, dan 25.000. Banyaknya cara untuk mendapatkan 7 koin dengan total nilai 49.000 adalah $\dots$

Barisan $(a_n)$ diperoleh dari barisan bilangan 1,2,3,… dengan menghapus suku berbentuk kuadrat dan kubik. Suku $a_{\mathrm{1.000.000}}$ adalah $\dots$

Diberikan bilangan ganjil $n\ge 5$. Banyaknya permutasi atas himpunan $\{1,2,\dots ,n\}$ sedemikian sehingga tidak terdapat dua bilangan ganjil yang berurutan adalah $\dots$

Untuk bilangan asli $n$ nilai dari $3\cdot 2\left(\genfrac{}{}{0ex}{}{n}{3}\right)+4\cdot 3\left(\genfrac{}{}{0ex}{}{n}{4}\right)+\cdots +n(n-1)\left(\genfrac{}{}{0ex}{}{n}{n}\right)$ adalah $\dots$

Sebuah titik $(a_1,a_2,\dots ,a_k)\in {\mathbb{R}}^k$ dikatakan sebuah titik lattice jika $a_i$ adalah bilangan bulat untuk semua $i=1,2,\dots ,k$. Perlihatkan bahwa setiap himpunan $L_k$ yang terdiri dari $2^k+1$ buah titik lattice, terdapat dua titik lattice $l_1,l_2\in L_k$ sedemikian sehingga titik tengah dari $l_1$ dan $l_2$ adalah sebuah titik lattice.

Misalkan $G$ adalah sebuah graf dengan $n$ titik $\{v_1,v_2,\dots ,v_n\}$. Sebuah matriks ketetanggaan $A=(a_{ij})$ dari graf $G$ didefinisikan sebagai sebuah matriks bujur sangkar berordo $n$ dengan entri $a_{ij}=\{\begin{array}{ll}1,& \text{bila }\{v_i,v_j\}\text{ adalah sebuah sisi di }G\\ 0,& \text{bila }\{v_i,v_j\}\text{ bukan sebuah sisi di }G\end{array}$

Buktikan bahwa entri $a_{ij}^{(m)}$ dari $A^m$ menyatakan banyaknya jalan (walk) dengan panjang $m$ yang menghubungkan titik $v_i$ dan titik $v_j$.

Setiap sisi $e$ di graf $G$ dikatakan bridge jika penghapusan sisi $e$ dari graf $G$ mengakibatkan komponen (subgraf terhubung maksimal) dari graf $G$ bertambah. Buktikan bahwa suatu sisi $e$ di $G$ adalah bridge jika dan hanya jika $e$ tidak berada di sebuah cycle di $G$.