Partisi Bilangan Asli

Gara-gara film The Man Who Knew Infinity, saya jadi penasaran dengan partisi bilangan asli n, yang dipelajari oleh Srinivasa Ramanujan dan Godfrey H. Hardy pada tahun 1918.

Yang dimaksud dengan partisi bilangan asli n adalah cara menguraikan n sebagai jumlah dari beberapa bilangan asli (termasuk n sendiri). Sebagai contoh, bilangan 5 dapat diuraikan dalam 7 cara, yaitu:

5,

4 + 1,

3 + 2,

3 + 1 + 1,

2 + 2 + 1,

2 + 1 + 1 + 1,

dan 1 + 1 + 1 + 1 + 1.

Nah, bila p(n) menyatakan banyaknya partisi bilangan n, maka p(5) = 7. [Di sini, 3 + 2 dan 2 + 3 dianggap sebagai satu cara yang sama.]

Anda mungkin berpikir, apa yang sulit dengan partisi bilangan asli ini? Hmm.. coba hitung berapa p(10), p(25), dan … p(200), seperti yang dikerjakan oleh Ramanujan pada waktu itu. [Bila Anda perlu bantuan, sila intip program yang dibuat oleh Mr. Bee.]

Ada rumus rekursif untuk menghitung p(n). Jika p(n,m) menyatakan banyaknya partisi bilangan n dengan hanya menggunakan bilangan yang lebih kecil daripada atau sama dengan m, maka

dengan p(n,m) = p(n,n) = p(n) untuk m > n (dan, untuk menggenapi rumus, kita definisikan p(0,n) = p(0) = 1). Sebagai contoh,

p(5,4) = p(4,1) + p(3,2) + p(2,3) + p(1,4) = 1 + 2 + 2 + 1 = 6.

Untuk n = 0, 1, 2, …, 7 dan m = 1, 2, 3, …, 7, nilai p(n,m) diberikan dalam tabel di bawah ini:

Tabel ini dapat Anda lanjutkan untuk n dan m lainnya.

Ramanujan dan Hardy menemukan bahwa p(n) membesar hampir secara eksponensial seiring dengan membesarnya n. Persisnya, Ramanujan dan Hardy memperoleh taksiran

Dengan rumus ini, Anda dapat menaksir bahwa nilai p(200) kira-kira sama dengan 4 trilyun. [Nilai p(200) sebenarnya sama dengan 3.972.999.029.388, sila cek di sini.]

Pada tahun 1937, Hans Rademacher menemukan deret yang konvergen ke p(n) untuk setiap n — sila tengok rumusnya di sini.

*

Bandung, 19-09-2016