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

partition-algorithm

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:

partition-table

Tabel Nilai p(n,m) untuk n, m = 1,…,7

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

partition-estimate

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

 

Advertisements

3 comments

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s