Pythagoras augustus 1999

Ramanujan en de partitiefunctie

door Frits Beukers

De partitiefunctie geeft aan op hoeveel manieren een aantal knikkers kan worden opgedeeld in groepjes. Samen met Hardy heeft Ramanujan verschillende resultaten over de partitiefunctie ontdekt.

Een partitie van n voorwerpen is een opdeling van deze voorwerpen in groepjes. Zo kun je 5 knikkers verdelen in vier groepjes: één groepje van van 2 en drie groepjes van 1. Deze verdeling geeft een zogenaamde partitie van 5:

5=2+1+1+1.

Het grootste getal schrijven we gewoonlijk voorop. Een andere partitie is 5=3+2. Ook 5=1+1+1+1+1 (vijf groepjes) en 5=5 (één groepje) zijn partities. Álle partities van 5 worden weergegeven in figuur 1:

$\begin{figuur}\epsfysize=45mm \centerline{\epsffile{rama-par.eps}} \smallskip \centerline{Figuur 1. De partities van 5.} \end{figuur}$

Het aantal partities van n geven we aan met p(n). Dit aantal is dus een functie van n. In ons voorbeeld hebben we p(5)=7.

Tellen

Door te tellen kun je voor een aantal kleine waarden van n zelf het aantal partities p(n) berekenen. De eerste paar waarden hebben we verzameld in tabel 2.

$\begin{figuur}\begin{center} \begin{tabular}{\vert c\vert r\vert r\vert r\vert r... ... dat $p(5)=7$\space (zie figuur 1). Kun je $p(7)$\space berekenen?} \end{figuur}$

Bizarre gelijkheden

De partitiefunctie heeft altijd de aandacht getrokken vanwege zijn bijzondere eigenschappen. Euler ontdekte bijvoorbeeld de volgende bizarre gelijkheid:

$\begin{displaymath}\vcenter{\halign{\hfil${} ...$

Kun je hierin een patroon vinden? Als je het niet ziet schrijf dan de betrokken getallen als volgt op en kijk naar de verschillen tussen de getallen in elk paar en tussen de getallen in de opvolgende paren:

$\begin{displaymath}\vcenter{\halign{&\hfil$ ...$

Euler gebruikte deze formule om p(n) snel voor grote waarden van n uit te kunnen rekenen.

Ramanujans benaderingen

Ramanujan heeft in zijn werk daar een aantal opmerkelijke zaken aan toegevoegd. Bekend zijn zijn pogingen om een formule voor p(n) te vinden. Zijn eerste benadering was de functie q₁(n) gegeven door de formule:

$\begin{displaymath}{1\over 2\pi\sqrt{2}}{d\over dn} \exp\left({\pi\sqrt{{2\over3}\left(n-{1\over24}\right)} \over \sqrt{n-{1\over24}}}\right). \end{displaymath}$

Deze functie gaf een verrassend goede benadering voor p(n) zoals je in tabel 3 kunt zien. Ramanujan ontdekte echter een nog betere benadering, die gegeven wordt door de functie q₂(n) met als formule:

$\begin{displaymath}q_1(n)+{(-1)^n\over 2\pi}{d\over dn} \exp\left({{1\over2}\pi\... ...}\left(n-{1\over24}\right)} \over \sqrt{n-{1\over24}}}\right). \end{displaymath}$

Ramanujans vermoeden

Er bleek een rij steeds fijnere correcties op deze formule te bestaan met zulke goede benaderingen. Ramanujan vermoedde daarom dat er een exacte formule voor p(n) zou moeten bestaan. Dit is heel opmerkelijk, want de functie p(n) neemt alleen gehele waarden aan. De benaderende functies zijn, alhoewel ingewikkeld, gewone functies zoals je die in de analyse tegenkomt, en deze functies nemen in het algemeen geen gehele waarden aan. Later, in 1943, ontdekte Rademacher de precieze formule die Ramanujan zocht.

Rademachers formules voor de partitiefunctie

In het Pythagoras artikel hebben we het gehad over de formule van Ramanujan voor de partitie-functie p(n). Echter, de formules die Ramanujan aangaf waren zogenaamde asymptotische benaderingen. Met dit soort formules kan men wel steeds betere benaderingen voor p(n) aangeven, maar men vindt nooit excate gelijkheden. In 1943 ontdekte Hans Rademacher dat, met een kleine aanpassing van Ramanujan's methode het mogelijk is een exacte formule voor p(n) te geven. Hier is de formule die Rademacher vond.

$\begin{displaymath}p(n)={1\over\pi\sqrt{2}} \sum_{k=1}^{\infty}A_k(n)\sqrt{k}{d\... ...{\pi\over k}\sqrt{2n/3-1/36}\right) \over\sqrt{n-1/24}}\right).\end{displaymath}$

De functie $\sinh(x)$ is de 'sinus hyperbolicus' gegeven door

$\begin{displaymath}\sinh(x)={e^x-e^{-x}\over/2}.\end{displaymath}$

Verder worden de coëfficienten A_k(n) gegeven door de formule

$\begin{displaymath}A_k(n)=\sum_{0\le h<k\atop \gcd(h,k)=1} \exp\left(\pi i(s(h,k)-2nh/k)\right),\end{displaymath}$

en de uitdrukking s(h,k), het Dedekind-symbool, wordt op zijn beurt gegeven door

$\begin{displaymath}s(h,k)=\sum_{r=1}^{k-1}{r\over k}\left({hr\over k}- \left[{hr\over k}\right]-{1\over2}\right).\end{displaymath}$

Met [x] bedoelen we het grootste gehele getal dat $\le x$ is. In de formule van A_k(n) komen ook e-machten met $i=\sqrt{-1}$ in de noemer voor, en het is voorstelbaar dat het de lezer begint te duizelen. Echter, de soep wordt niet zo heet gegeten als hij wordt opgediend. Als we uitrekenen wat A_k(n) precies is, dan vinden we voor de eerste paar indices k,

$\begin{eqnarray*}A_1(n)&=&1\\ A_2(n)&=&\cos(\pi n)\\ A_3(n)&=&2\cos(2\pi n/3-\... ...+2\cos(4\pi n/5)\\ A_6(n)&=&2\cos(\pi n/3-5\pi /18)\\ &&\cdots \end{eqnarray*}$

Als we dit alles bij elkaar zien dan mag het een wonder heten dat er uit de oneindige reeks een geheel getal als antwoord komt!

$\begin{figuur}\begin{center} \begin{tabular}{\vert r\vert r\vert r\vert r\vert} ... ... door Ramanujan gevonden benaderingen $q_1(n)$\space en $q_2(n)$ .} \end{figuur}$
Warning: setlocale() [function.setlocale]: Passing locale category name as string is deprecated. Use the LC_* -constants instead in /websites/users/pyth/public_html/pythwww/common/footer.php on line 5

Laatst bijgewerkt op: Tuesday 27 May 2003, 14:10