Formule om het aantal combinatie sommen te berekenen om een resultaat te bekome

Hallo,

Ik ben opzoek naar een formule of manier om volgend probleem op te lossen:

Ik wil te weten komen met hoeveel verschillende sommen je het getal 137 kan bekomen.

Enkele voorwaarden.
1. Je mag enkel getallen gebruiken $<$46.
2. Ieder getal mag je slechts 1 maal gebruiken
3. Er moeten telkens 6 verschillende getallen gebruikt worden.

Voorbeeld van som die je kan gebruiken:

2+9+11+33+40+42 =137

Bestaat er een formule om te zien hoeveel verschillende sommen er mogelijk zijn om 137 te bekomen, gelet op bovenstaande voorwaarden?

Raf
Iets anders - dinsdag 18 oktober 2016

Antwoord

Bij zo'n probleem kijk ik eerst naar wat eenvoudiger gevallen: het aantal manieren om $x+y+z=10$ met verschillende $x$, $y$ en $z$ te maken (willekeurig, alles kleiner dan $4$, alles kleiner dan $5$, enzovoort).
Wat je dan zult zien is dat je het best systematisch te werk kunt gaan: omdat $(2,3,5)$ dezelfde oplossing is als $(5,2,3)$ bekijken we alleen oplossingen met $x$, $y$ en $z$ in opklimmende grootte.
Stel alles moet kleiner dan $8$ zijn:
dan begin je met $z=7$ en telt het aantal manieren om $10-z$ als $x+y$ te schrijven is met $x$ kleiner dan $y$ en $y$ kleiner dan $z$;
volgende stap $z=6$ en weer tellen, dan $z=5$ en tellen, enzovoort. Dat tellen is makkelijk want in dit geval moet $\frac12(10-z($<$y$<$(10-z)$ en dat aantal $y$-en is $\frac12(10-z)-1$ als $10-z$ even is en $\frac12(10-z-1)$ als $10-z$ oneven is.
Bij viertallen $(x,y,z,w)$ doe je hetzelfde, maar het wordt meer werk: je laat $w$ naar beneden lopen van $7$ naar $1$ en telkens tel je het aantal manieren om $10-w$ te schrijven als $x+y+z$, en dat gaat dan als boven waarbij je $z$ nu van $w-1$ naar $1$ laat lopen.

Voor jouw probleem moet je wat notatie invoeren (en dat is hierboven ook handig): noteer men $d(k,n,g)$ het aantal manieren op $n$ als som van $k$ verschillende getallen te schrijven die allemaal kleiner zijn dan $g$".
Met de beperking in je som is $d(6,137,46)$ het getal dat je zoekt.
De redenering hierboven geeft dat
$$
d(6,137,46) = \sum_{z=1}^45 d(5,137-z,z)
$$(merk op dat $d(5,137-z,z)=0$ als $z\le137/6$).
Volgende stap
$$
d(5,137-z,z)=\sum_{y=1}^{z-1} d(4,137-z-y,y)
$$Dit kun je het beste doen door er een programmaatje voor te schrijven.

kphart
zaterdag 22 oktober 2016

©2001-2024 WisFaq