Uit Hoeveel sommen komt 20?
De oplossing is snel te zien, als je het getal 20 ziet als een ketting van 20 enen.
Een optelsom fabriceren komt dan neer op het doorknippen van de ketting op verschillende plaatsen.
Hieronder is bijvoorbeeld de som  20 = 6 + 2 + 7 + 5  gefabriceerd.
Dus het aantal sommen waar 20 uit komt is gelijk aan het aantal manieren waarop we de 20-ketting in stukken kunnen knippen. Er zijn 19 mogelijke plaatsen waar we kunnen knippen. 
Bij elke plaats moeten we beslissen JA (knippen) of NEE (niet knippen). Dat kan dus op 219 manieren. Alleen de variant waar we NIETS doorknippen levert geen som op, want 20 zelf is geen som.
Het aantal sommen is dus  219 - 1 
oplossing:  219 - 1 = 524287 sommen

Maar goed, dit was een makkie, een veel interessantere vraag is natuurlijk:
Hoeveel ECHT verschillende sommen zijn er waar 20 uit komt?

Want wees nou eerlijk:  4 + 14 + 2  is natuurlijk hetzelfde als 2 + 4 + 14.
Noem P(n) het aantal ECHT verschillende manieren.
Bijvoorbeeld  P(5) = 7, namelijk  5 ,  4+1 , 3+2,  3+1+1 , 2+2+1 , 2+1+1+1 en  1+1+1+1+1
Dat aantal is echter in het algemeen niet zo simpel te berekenen!

Goldbach schreef een brief aan Euler waarin hij hem vroeg naar de waarden van P(n). Creatief  als altijd, produceerde Euler een methode om functies te genereren voor een antwoord op de vraag.
En hij kwam tot een verrassende ontdekking!

De ontdekking van Euler

Een verrassende en geniale ontdekking van Euler ging in drie stappen:

STAP 1
Hij beschouwde het oneindige product:
 (1 + x) • (1 + x2) • (1 + x3) •(1 + x4) •  ......
Als je alle haakjes weg zou werken wordt de coλfficiλnt van xn precies gelijk aan  A(n) !!!

Kijk maar hieronder:

de factor zonder x wordt 1  (van 1 • 1 • 1 •...)
de factor bij x1 wordt ook 1 (van x • 1 • 1 • ...)
de factor bij x2 wordt 1 (van 1 • x2)
de factor bij x3 wordt 2 (van x3 + x2+1)
de factor bij x4 wordt 2 (van x4 + x3+1) ofwel  4 = 3 + 1
de factor bij x5 wordt 3 (van  x5 + x4+1 + x3+2)  ofwel  5 = 4 + 1 = 3 + 2
de factor bij x6 wordt 4 (van x6 + x5+1 + x4+2 + x3+3) ofwel 6 = 5 + 1 = 4 + 2 = 3 + 3
enz.

STAP 2
Beschouw de volgende meetkundige rij:


= 1 + a + a2 + a3 + a4 + .....
dan geldt:  a • S =       a + a2 + a3 + a4 + a5 + ...
dus S - a • S = 1 
S • (1 - a) = 1  ή  
Laten we a nu vervangen door oneven machten van x, dan vinden we achtereenvolgens bijv.
enz. 
Definieer nu een nieuwe functie Q(x):

Dan kunnen we deze Q(x) met de formules erboven anders schrijven als:
Q(x) = (1 + x1 + x1+1 + ...)•(1 + x3 + x3+3 + ...)•(1 + x5 + x5+5 + ...)• ....
Als we nu de haakjes wegwerken en gelijke machten van x bij elkaar zetten dan vinden we (op dezelfde manier als hierboven):

de factor bij 1 wordt 1
de factor bij x wordt 1 
de factor bij x2 wordt 1  (van x1+1)
de factor bij x3 wordt 2 (x1+1+1 + x3)  ofwel  3 = 1+1+1
de factor bij x4 wordt 2  (x1+1+1+1 + x1+3)  ofwel 4 = 1+1+1+1 = 3+1
de factor bij x5 wordt 3  (x1+1+1+1+1 + x1+1+3 + x5)  ofwel  5 = 1+1+1+1+1 = 1+1+3
de factor bij x6 wordt 4  (x1+1+1+1+1+1 + x1+1+1+3 + x3+3 + x5) ofwel ....

We ontdekken het volgende:  Q(x) is het aantal manieren waarop getal x als som van oneven getallen geschreven kan worden.

STAP 3
Het lijkt erop dat geldt Q(x) = P(x)
Dat bewees Euler als volgt:

= (1+x) • (1 + x2) • (1 + x4) • ...
= P(x)

De ontdekking van Euler:

Het aantal verschillende sommen waar n uitkomt is hetzelfde als het aantal manieren waarop n als som van oneven getallen geschreven kan worden!!!

Toegegeven, je hebt er verder niets aan, maar 't is wel een geweldig mooi bewijs!


Het berekenen van het aantal echt verschillende sommen waar n uitkomt kan ook wel op een simpelere manier. Noem Pk(n) het aantal sommen met k of minder termen.
Dan kunnen we recursievergelijkingen voor Pk opstellen als we het volgende bedenken:

1. Het aantal sommen met k of minder termen is gelijk aan het aantal met exact k termen plus het aantal met k -1 of minder termen.
2. Als we een verdeling van n in exact k termen hebben, dan kunnen we 1 van elke term aftrekken en dan hebben we een verdeling van n - k in exact k termen. Er is een 1-op-1 relatie tussen de sommen van n in exact k termen en de sommen van n - k in k of minder termen.

Dat geeft de volgende recursievergelijking:

Pk(n) =Pk-1(n) + Pk(n - k)

Daarmee maken we makkelijk de volgende tabel:

n

k

1 2 3 4 5 6 7 8 9 10 11 12 13 14
-1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 2 2 2 2 2 2 2 2 2 2 2 2 2
3 1 2 3 3 3 3 3 3 3 3 3 3 3 3
4 1 3 4 5 5 5 5 5 5 5 5 5 5 5
5 1 3 5 6 7 7 7 7 7 7 7 7 7 7
6 1 4 7 9 10 11 11 11 11 11 11 11 11 11
7 1 4 8 11 13 14 15 15 15 15 15 15 15 15
8 1 5 10 15 18 20 21 22 22 22 22 22 22 22
9 1 5 12 18 23 26 28 29 30 30 30 30 30 30
10 1 6 14 23 30 35 38 40 41 42 42 42 42 42
11 1 6 16 27 37 44 49 52 54 55 56 56 56 56
12 1 7 19 34 47 58 65 70 73 75 76 77 77 77
13 1 7 21 39 57 71 82 89 94 97 99 100 101 101
14 1 8 24 47 70 90 105 116 123 128 131 133 134 135


De blauwe 70 is bijvoorbeeld berekend door de blauwe 65 en de blauwe 5 bij elkaar op te tellen. In het groen is hetzelfde gebeurd.
De rode diagonaal is nu precies het aantal manieren om echt verschillende sommen te maken waar n uitkomt!

De tabel uitbreiden geeft als diagonaal:
1,2,3,5,7,11,15,22,30,42,56,77,101,135,176,231,297,385,490,627

Conclusie:  "Er zijn 627 echt verschillende sommen waar 20 uitkomt"

Een leuke variant:

Op hoeveel verschillende manieren kan 20 geschreven worden als de som van opeenvolgende gehele getallen?
Deze is niet zo moeilijk; de som van een aantal opeenvolgende getallen is altijd gelijk aan een aantal keer het gemiddelde. Zo is bijvoorbeeld  8 + 9 + 10 + 11 + 12 = 3 • 10 want het gemiddelde is 10, en daarom zijn eerste en laatste (8 en 12)  gemiddeld 10, en ook ιιn-na-eerste en ιιn-na-laatste (9 en 11), enzovoort.
Als er een oneven aantal getallen zijn zal het gemiddelde geheel zijn, als er een even aantal getallen staan zal het gemiddelde eindigen op ....,5.
Willen we nou bijvoorbeeld onderzoeken op hoeveel manieren 105 geschreven kan worden als som van opeenvolgende getallen, dan delen we 105 door 2, 3,... en kijken wanneer delen door een even getal een resultaat ....,5 heeft of wanneer delen door een oneven getal een geheel resultaat heeft:

deler resultaat som
2 52,5 52+53
3 35 34+35+36
5 21 19+20+21+22+23
6 17,5 15+16+17+18+19+20
7 15 12+13+14+15+16+17+18
10 10,5 6+7+8+9+10+11+12+13+14+15
14 7,5 x

Vanaf hier kan het niet meer omdat de deler te groot wordt; er passen geen 7 getallen meer onder 7,5.
De derde kolom geeft zodoende 6 manieren om 105 als som van opeenvolgende getallen te schrijven.  

Dezelfde procedure op 20 toepassen geeft maar ιιn oplossing: 
20 = 2 + 3 + 4 + 5 + 6

De volgende stap in de evolutie
In het vorige onderzochten we hoeveel optelsommen er zijn waar n uitkomt (het aantal additieve partities van n).
De logisch volgende stap is dan natuurlijk: hoeveel vermenigvuldigsommen zijn er waar n uitkomt? (het aantal multiplicatieve partities). We letten weer alleen op "echt" verschillende vermenigvuldigsommen; dus de volgorde van de factoren is niet van belang; we vinden 3 • 4 hetzelfde als 4 • 3.