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
)
{\displaystyle (2,2,1)}
atau bahkan dalam bentuk yang lebih kompak
(
2
2
,
1
)
{\displaystyle (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
⋯
{\displaystyle 1^{m_{1}}2^{m_{2}}3^{m_{3}}\cdots }
, dengan
m
1
{\displaystyle m_{1}}
melambangkan jumlah bilangan 1,
m
2
{\displaystyle m_{2}}
melambangkan jumlah bilangan 2, dan begitu seterusnya. Sebagai contoh,
Partisi dari
n
=
5
{\displaystyle 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
{\displaystyle 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:
∑
n
≥
0
p
(
n
)
q
n
=
∏
i
≥
1
∑
m
≥
0
q
i
m
=
∏
i
≥
1
1
1
−
q
i
.
{\displaystyle \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
p
(
n
)
{\displaystyle p(n)}
sama dengan jumlah yang dapat dimiliki
Partisi bilangan bulat non-negatif
n
{\displaystyle n}
. Sebagai contoh,
p
(
4
)
=
5
{\displaystyle p(4)=5}
karena
4
{\displaystyle 4}
memiliki 5
Partisi, yaitu:
1
+
1
+
1
+
1
{\displaystyle 1+1+1+1}
,
1
+
1
+
2
{\displaystyle 1+1+2}
,
1
+
3
{\displaystyle 1+3}
,
2
+
2
{\displaystyle 2+2}
, dan
4
{\displaystyle 4}
. Nilai dari fungsi tersebut untuk
n
=
0
,
1
,
2
,
…
{\displaystyle 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
{\displaystyle p}
adalah
∑
n
=
0
∞
p
(
n
)
q
n
=
∏
j
=
1
∞
∑
i
=
0
∞
q
j
i
=
∏
j
=
1
∞
(
1
−
q
j
)
−
1
.
{\displaystyle \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
)
+
⋯
{\displaystyle 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
{\displaystyle n}
berakhir di digit 4 atau 9, maka jumlah
Partisi
n
{\displaystyle n}
akan dapat dibagi oleh 5.
Lihat pula
Faktorisasi bilangan bulat
Partisi bidang
Partisi himpunan
Catatan
Referensi
Andrews, George E. (1976). The Theory of Partitions. Cambridge University Press. ISBN 0-521-63766-X.
Hardy, G. H.; Wright, E. M. (2008). An Introduction to the Theory of Numbers. Revised by D. R. Heath-Brown and J. H. Silverman. Foreword by Andrew Wiles. (edisi ke-6th). Oxford: Oxford University Press. ISBN 978-0-19-921986-5. MR 2445243. Zbl 1159.11001.
