Lewati ke konten utama

Indeks Sblm Naik Lnjt

\(\newcommand{\set}[1]{\{#1\}} \newcommand{\ints}{\mathbb{Z}} \newcommand{\posints}{\mathbb{N}} \newcommand{\rats}{\mathbb{Q}} \newcommand{\reals}{\mathbb{R}} \newcommand{\complexes}{\mathbb{C}} \newcommand{\twospace}{\mathbb{R}^2} \newcommand{\threepace}{\mathbb{R}^3} \newcommand{\dspace}{\mathbb{R}^d} \newcommand{\nni}{\mathbb{N}_0} \newcommand{\nonnegints}{\mathbb{N}_0} \newcommand{\dom}{\operatorname{dom}} \newcommand{\ran}{\operatorname{ran}} \newcommand{\prob}{\operatorname{prob}} \newcommand{\Prob}{\operatorname{Prob}} \newcommand{\height}{\operatorname{height}} \newcommand{\width}{\operatorname{width}} \newcommand{\length}{\operatorname{length}} \newcommand{\crit}{\operatorname{crit}} \newcommand{\inc}{\operatorname{inc}} \newcommand{\HP}{\mathbf{H_P}} \newcommand{\HCP}{\mathbf{H^c_P}} \newcommand{\GP}{\mathbf{G_P}} \newcommand{\GQ}{\mathbf{G_Q}} \newcommand{\AG}{\mathbf{A_G}} \newcommand{\GCP}{\mathbf{G^c_P}} \newcommand{\PXP}{\mathbf{P}=(X,P)} \newcommand{\QYQ}{\mathbf{Q}=(Y,Q)} \newcommand{\GVE}{\mathbf{G}=(V,E)} \newcommand{\HWF}{\mathbf{H}=(W,F)} \newcommand{\bfC}{\mathbf{C}} \newcommand{\bfG}{\mathbf{G}} \newcommand{\bfH}{\mathbf{H}} \newcommand{\bfF}{\mathbf{F}} \newcommand{\bfI}{\mathbf{I}} \newcommand{\bfK}{\mathbf{K}} \newcommand{\bfP}{\mathbf{P}} \newcommand{\bfQ}{\mathbf{Q}} \newcommand{\bfR}{\mathbf{R}} \newcommand{\bfS}{\mathbf{S}} \newcommand{\bfT}{\mathbf{T}} \newcommand{\bfNP}{\mathbf{NP}} \newcommand{\bftwo}{\mathbf{2}} \newcommand{\cgA}{\mathcal{A}} \newcommand{\cgB}{\mathcal{B}} \newcommand{\cgC}{\mathcal{C}} \newcommand{\cgD}{\mathcal{D}} \newcommand{\cgE}{\mathcal{E}} \newcommand{\cgF}{\mathcal{F}} \newcommand{\cgG}{\mathcal{G}} \newcommand{\cgM}{\mathcal{M}} \newcommand{\cgN}{\mathcal{N}} \newcommand{\cgP}{\mathcal{P}} \newcommand{\cgR}{\mathcal{R}} \newcommand{\cgS}{\mathcal{S}} \newcommand{\bfn}{\mathbf{n}} \newcommand{\bfm}{\mathbf{m}} \newcommand{\bfk}{\mathbf{k}} \newcommand{\bfs}{\mathbf{s}} \newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}} \newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}} \newcommand{\surjection}{\xrightarrow[\text{onto}]{}} \newcommand{\nin}{\not\in} \newcommand{\prufer}{\text{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\ds}{\displaystyle} \newcommand{\mbf}[1]{\mathbf{#1}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \definecolor{fillinmathshade}{gray}{0.9} \newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}} \)

Pendahuluan

Dalam bab ini, kita memperkenalkan teknik enumerasi yang ampuh dan umumnya disebut teorema enumerasi Pólya.

¹

Seperti banyak hasil matematika lainnya, inti hasil ini mula-mula ditemukan oleh orang selain matematikawan yang namanya kemudian dikaitkan dengannya. J.H. Redfield menerbitkan hasil ini pada tahun 1927, sepuluh tahun sebelum karya Pólya. Karya Redfield baru ditemukan kembali pada tahun 1960, ketika nama Pólya sudah terlanjur melekat kuat pada teknik tersebut.

Pendekatan Pólya terhadap pencacahan memungkinkan kita menggunakan simetri (seperti simetri objek geometri, misalnya poligon) untuk membentuk fungsi pembangkit. Fungsi-fungsi pembangkit ini kemudian dapat digunakan untuk menjawab pertanyaan kombinatorial seperti

Berapa banyak kalung berbeda yang terdiri atas enam manik dan dapat dibentuk menggunakan manik merah, biru, dan hijau? Bagaimana dengan kalung berisi \(500\) manik?
Berapa banyak tangga nada yang terdiri atas \(6\) nada?
Berapa banyak isomer senyawa xilenol, \(\text{C} _6\text{H} _3(\text{CH} _3)_2(\text{OH} )\text{?}\) Bagaimana dengan \(\text{C} _n \text{H} _{2n+2}\text{?}\) (Dalam kimia, isomer adalah senyawa kimia yang memiliki jumlah atom yang sama dari setiap unsur, tetapi susunan atom-atom tersebut berbeda.)
Berapa banyak graf tak isomorfik pada empat simpul? Berapa banyak di antaranya yang memiliki tiga sisi? Bagaimana dengan graf pada \(1000\) simpul dan \(257,000\) sisi? Berapa banyak graf \(r\)-reguler pada \(40\) simpul? (Suatu graf disebut \(r\)-reguler jika setiap simpul berderajat \(r\text{.}\))

Untuk menggunakan teknik Pólya, kita memerlukan gagasan grup permutasi. Namun, pembahasan kita akan mandiri dan digerakkan oleh contoh. Kita mulai dengan versi sederhana dari pertanyaan pertama di atas.

Sblm Ke Atas Lnjt