Teorema 8.16.
Untuk setiap \(n\ge1\text{,}\) banyaknya partisi dari \(n\) menjadi bagian-bagian berbeda sama dengan banyaknya partisi dari \(n\) menjadi bagian-bagian ganjil.
Subbab 8.5 Partisi Bilangan Bulat
Salah satu tema yang berulang dalam mata kuliah ini adalah menghitung banyaknya solusi bilangan bulat untuk persamaan berbentuk \(x_1+x_2+\cdots + x_k = n\text{.}\) Bagaimana jika kita ingin menghitung banyaknya solusi semacam itu tanpa memedulikan nilai \(k\text{?}\) Bagaimana jika pada pertanyaan baru ini kita mensyaratkan agar semua \(x_i\) berbeda (i.e., \(x_i\neq x_j\) untuk \(i\neq j\))? Bagaimana pula jika kita mensyaratkan agar setiap \(x_i\) ganjil? Pada awalnya, pertanyaan-pertanyaan ini tentu tidak tampak mudah dijawab, tetapi fungsi pembangkit memungkinkan kita menyatakan sesuatu yang sangat menarik tentang jawaban dua pertanyaan terakhir.
Yang kita maksud dengan partisi \(P\) dari suatu bilangan bulat adalah koleksi bilangan bulat positif (yang tidak harus berbeda) sedemikian sehingga \(\sum_{i\in P} i = n\text{.}\) (Menurut konvensi, kita akan menuliskan elemen-elemen \(P\) dari yang terbesar hingga yang terkecil.) Sebagai contoh, \(2+2+1\) merupakan partisi dari \(5\text{.}\) Untuk setiap \(n\ge0\text{,}\) misalkan \(p_n\) menyatakan banyaknya partisi bilangan bulat \(n\) (dengan \(p_0=1\) menurut konvensi). Perhatikan bahwa \(p_8=22\text{,}\) sebagaimana ditunjukkan oleh daftar dalam Gambar 8.15.
-
8 — bagian berbeda
-
7+1 — bagian berbeda, bagian ganjil
-
6+2 — bagian berbeda
-
6+1+1
-
5+3 — bagian berbeda, bagian ganjil
-
5+2+1 — bagian berbeda
-
5+1+1+1 — bagian ganjil
-
4+4
-
4+3+1 — bagian berbeda
-
4+2+2
-
4+2+1+1
-
4+1+1+1+1
-
3+3+2
-
3+3+1+1 — bagian ganjil
-
3+2+2+1
-
3+2+1+1+1
-
3+1+1+1+1+1 — bagian ganjil
-
2+2+2+2
-
2+2+2+1+1
-
2+2+1+1+1+1
-
2+1+1+1+1+1+1
-
1+1+1+1+1+1+1+1 — bagian ganjil
Perhatikan bahwa terdapat \(6\) partisi dari \(8\) menjadi bagian-bagian yang berbeda. Terdapat pula \(6\) partisi dari \(8\) menjadi bagian-bagian ganjil. Meskipun hal ini mungkin tampak sebagai kebetulan, kesamaan tersebut sebenarnya selalu berlaku, sebagaimana dinyatakan oleh Teorema 8.16. Sebelum menelaah teorema itu beserta buktinya, mari kita pikirkan seperti apa fungsi pembangkit bagi \(p_n\text{,}\) yaitu banyaknya partisi dari \(n\text{.}\) Dari suatu partisi \(n\text{,}\) kita dapat menghitung berapa banyak bagian bernilai \(1\text{,}\) berapa banyak bagian bernilai \(2\text{,}\) dan seterusnya. Hal ini menunjukkan kemiripan dengan masalah keranjang buah yang dibahas sebelumnya dalam bab ini, sehingga menghasilkan fungsi pembangkit
\begin{equation*}
P(x) = \left(\sum_{m=0}^\infty x^{m}\right)\left(\sum_{m=0}^\infty x^{2m}\right) \left(\sum_{m=0}^\infty x^{3m}\right)\cdots \left(\sum_{m=0}^\infty x^{km}\right)\cdots = \prod_{m=1}^\infty\frac{1}{1-x^m}.
\end{equation*}
Di sini, faktor yang jumlahnya memuat suku-suku \(x^{km}\) memperhitungkan banyaknya bagian bernilai \(k\) dalam partisi. Walaupun \(P(x)\) memiliki bentuk yang cukup elegan, bentuk tersebut belum tentu sangat berguna untuk menghitung \(p_n\text{.}\) Bahkan, memperoleh taksiran asimtotik bagi \(p_n\) merupakan masalah yang terkenal sulit dan baru berhasil ditangani oleh Hardy dan Ramanujan pada tahun 1918. Uraian populer mengenai hal ini dapat ditemukan dalam buku Robert Kanigel tahun 1991, The Man who Knew Infinity, atau film tahun 2016 dengan judul yang sama.
Untuk membuktikan hubungan antara banyaknya partisi menjadi bagian-bagian berbeda dan banyaknya partisi menjadi bagian-bagian ganjil, kita akan menggunakan versi terbatas dari fungsi pembangkit \(P(x)\) di atas.
Bukti.
Fungsi pembangkit \(D(x)\) bagi banyaknya partisi dari \(n\) menjadi bagian-bagian berbeda adalah
\begin{equation*}
D(x)=\prod_{n=1}^\infty (1+x^n).
\end{equation*}
Di sisi lain, fungsi pembangkit \(O(x)\) bagi banyaknya partisi dari \(n\) menjadi bagian-bagian ganjil adalah
\begin{equation*}
O(x)=\prod_{n=1}^\infty\frac{1}{1-x^{2n-1}}.
\end{equation*}
Untuk melihat bahwa \(D(x)=O(x)\text{,}\) perhatikan bahwa \(1-x^{2n}=(1-x^n)(1+x^n)\) untuk setiap \(n\ge1\text{.}\) Oleh karena itu,
\begin{align*}
D(x)\amp =\prod_{n=1}^\infty
(1+x^n)=\prod_{n=1}^\infty\frac{1-x^{2n}}{1-x^n} =\frac{\prod_{n=1}^\infty(1-x^{2n})}{\prod_{n=1}^\infty(1-x^n)}\\
\amp =\frac{\prod_{n=1}^\infty(1-x^{2n})}{
\prod_{n=1}^\infty(1-x^{2n-1})\prod_{n=1}^\infty(1-x^{2n})}
=\prod_{n=1}^\infty\frac{1}{1-x^{2n-1}}\\
\amp = O(x).
\end{align*}
