Frobeniusgetal

Een frobeniusgetal, genoemd naar de wiskundige Ferdinand Georg Frobenius, is een oplossing van het zogenaamde frobeniusprobleem:

Gegeven: 2 of meer positieve gehele getallen $a_{1},a_{2},\ldots ,a_{n}$ waarvan de grootste gemene deler gelijk is aan 1. Vind het grootste natuurlijk getal $g$ dat niet voorgesteld kan worden als een lineaire combinatie van deze getallen met niet-negatieve gehele getallen als coëfficiënten.

Het getal $g$ noemt men het frobeniusgetal en noteert het als:

$g_{n}(a_{1},a_{2},\ldots ,a_{n})$

Zonder verlies van algemeenheid kan men veronderstellen dat:

$a_{1}<a_{2}<\ldots <a_{n}$

De voorwaarde dat de grootste gemene deler (ggd) van de getallen gelijk is aan 1 is noodzakelijk, omdat er anders oneindig veel getallen zijn die niet kunnen voorgesteld worden als een niet-negatieve, geheeltallige lineaire combinatie van de gegeven getallen. Als de ggd groter is dan 1, is immers elk getal dat geen veelvoud is van de ggd, onmogelijk uit te drukken op die manier. Er bestaat dan ook geen grootste van dergelijke getallen. Als de ggd gelijk is aan 1, is de verzameling getallen die niet kunnen geschreven worden als een combinatie van de gegeven getallen, eindig, en dus bestaat er steeds een grootste getal.

Oplossingen

Voor $n=2$ bestaat er een expliciete formule voor het frobeniusgetal:

$g_{2}(a_{1},a_{2})=(a_{1}-1)(a_{2}-1)-1$

Voor $n=3$ is het probleem expliciet opgelost door Ernst Selmer en Öyvind Beyer in 1978; hun resultaat werd vereenvoudigd door Rödseth en later door Greenberg.

Voor $n\geq 4$ is er geen algemene formule bekend. Er zijn wel formules bekend voor speciale gevallen, bijvoorbeeld als de getallen een rekenkundige rij of een meetkundige rij vormen.

Rekenkundige rijen

Als de getallen een rekenkundige rij $a_{k}=a+(k-1)d$ vormen, met $\mathrm {ggd} (a,d)=1$, wordt het frobeniusgetal gegeven door:

$g(a,a+d,a+2d,\dots ,a+(n-1)d)=\left(\left\lfloor {\frac {a-2}{n-1}}\right\rfloor +1\right)a+(d-1)(a-1)-1$

Meetkundige rijen

Er bestaat ook een expliciete formule voor het Frobeniusgetal van een verzameling getallen die een meetkundige rij vormen. Als $m,n,k$ gehele getallen zijn met $\mathrm {ggd} (m,n)=1$:

$g(m^{k},m^{k-1}n,m^{k-2}n^{2},\ldots ,n^{k})=n^{k-1}(mn-m-n)+{\frac {m^{2}(n-1)(m^{k-1}-n^{k-1})}{m-n}}$

Interpretatie van het frobeniusprobleem

Stel dat de getallen $a_{1},a_{2},\ldots ,a_{n}$ de waarden voorstellen van $n$verschillende munten. Het frobeniusprobleem vraagt dan wat het grootste bedrag is dat niet kan worden betaald met deze munten.

Stel bijvoorbeeld dat er slechts munten beschikbaar zijn met waarden 3 en 5. Het grootste bedrag dat niet kan worden uitbetaald met deze munten is 77. Dit is het frobeniusgetal van 3 en 5: $g(3,5)=7$7.

Bronnen, noten en/of referenties