Partisi (teori bilangan)

Dalam teori bilangan dan kombinatorik, partisi dari bilangan bulat positif n adalah suatu cara menulis bilangan n sebagai jumlah dari bilangan bulat positif. Ini juga dikenal sebagai partisi bilangan bulat. Dua penjumlahan yang berbeda dalam urutan tinambahnya dianggap memiliki partisi yang sama.

Contoh

Misalkan, 5 dapat dipartisi dalam tujuh cara:

5

4 + 1

3 + 2

3 + 1 + 1

2 + 2 + 1

2 + 1 + 1 + 1

1 + 1 + 1 + 1 + 1

Ada beberapa penulis yang memperlakukan partisi sebagai barisan tijumlah yang menurun daripada menggunakan ekspresi dengan tanda tambah (+). Sebagai contoh, partisi 2 + 2 + 1 dituliskan sebagai rangkap $(2,2,1)$ atau bahkan dalam bentuk yang lebih kompak $(2^{2},1)$. Pada notasi terakhir, superskrip mengartikan jumlah pengulangannya.

Sebagai gantinya, notasi kelipatan tersebut dapat ditulis sebagai $1^{m_{1}}2^{m_{2}}3^{m_{3}}\cdots$, dengan $m_{1}$ melambangkan jumlah bilangan 1, $m_{2}$ melambangkan jumlah bilangan 2, dan begitu seterusnya. Sebagai contoh, partisi dari $n=5$ ditulis $5^{1},1^{1}4^{1},2^{1}3^{1},1^{2}3^{1},1^{1}2^{2},1^{3}2^{1},1^{5}$. Karena representasi tersebut, maka dapat ditulis langsung menggunakan rumus fungsi pembangkit berikut:$$\sum _{n\geq 0}p(n)q^{n}=\prod _{i\geq 1}\sum _{m\geq 0}q^{im}=\prod _{i\geq 1}{\frac {1}{1-q^{i}}}.$$

Representasi melalui diagram

Partisi bilangan bulat dapat direpresenasikan menggunakan dua diagram. Diagram tersebut di antaranya: diagram Ferrers, yang dinamai dari Norman Macleod Ferrers; dan diagram Young, yang dinamai dari Alfred Young. Dalam diagram Ferre, partisi dari 14, yaitu 6 + 4 + 3 + 1, dapat dinyatakan sebagai:

Keempat belas lingkaran tersebut disusun dengan 4 baris.

Di sisi lain, diagram Young menggunakan kotak daripada lingkaran kecil, seperti diagram Ferrers. Sebagai contoh, diagram Young untuk partisi 5 + 4 + 1 adalah:

sedangkan diagram Ferrers untuk partisi yang sama adalah

Fungsi partisi

Artikel utama: Fungsi partisi (teori bilangan)

Fungsi partisi $p(n)$ sama dengan jumlah yang dapat dimiliki partisi bilangan bulat non-negatif $n$. Sebagai contoh, $p(4)=5$ karena $4$ memiliki 5 partisi, yaitu: $1+1+1+1$, $1+1+2$, $1+3$, $2+2$, dan $4$. Nilai dari fungsi tersebut untuk $n=0,1,2,\dots$ adalah:

1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, ... (barisan A000041 pada OEIS).

Fungsi pembangkit dari $p$ adalah

$\sum _{n=0}^{\infty }p(n)q^{n}=\prod _{j=1}^{\infty }\sum _{i=0}^{\infty }q^{ji}=\prod _{j=1}^{\infty }(1-q^{j})^{-1}.$

Ekspresi bentuk tertutup untuk fungsi partisi masih belum dikethaui. Akan tetapi, fungsi partisi memiliki ekspansi asimtotik yang menghampirinya dengan akurat, serta dapat dihitung dengan tepat menggunankan relasi rekurensi. Fungsi partisi menaik (bertumbuh) sebagai fungsi eksponensial dari akar kuadrat dari argumennya. Invers perkalian dari fungsi pembangkitnya adalah fungsi Euler, dan berdasarkan teorema bilangan pentagonal Euler, fungsi ini merupakan penjumlahan selang-seling dari perpangkatan bilangan pentagonal dari argumennya.

$p(n)=p(n-1)+p(n-2)-p(n-5)-p(n-7)+\cdots$

Srinivasa Ramanujan menemukan bahwa fungsi partisi mempunyai pola nontrivial dalam aritmetika modular, yang kini dikenal sebagai kongruensi Ramanujan. Sebagai contoh, ketika representasi desimal $n$ berakhir di digit 4 atau 9, maka jumlah partisi $n$ akan dapat dibagi oleh 5.

Lihat pula

• Faktorisasi bilangan bulat
• Partisi bidang
• Partisi himpunan