Frobeniusgetal

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een Frobeniusgetal, genoemd naar de wiskundige Ferdinand Georg Frobenius, is de oplossing van het zogenaamde Frobeniusprobleem:

  • Gegeven: 2 of meer positieve gehele getallen a1, a2, ..., an waarvan de grootste gemene deler gelijk is aan 1,
  • Vind het grootste natuurlijk getal g dat niet kan voorgesteld worden als een lineaire combinatie van a1, a2, ..., an van de vorm
k1a1 + k2a2 + ... + knan,
waarin k1, k2, ..., kn niet-negatieve gehele getallen zijn. Dat getal noemt men het Frobeniusgetal en wordt voorgesteld als g(a1, a2, ..., an).

Men kan zonder verlies van algemeenheid veronderstellen dat a1 < a2 ... < aN.

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[bewerken]

Voor n=2 bestaat een expliciete formule:

g2(a1, a2) = (a1-1)( a2-1)-1.

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

Voor n>=4 zijn geen algemene formules bekend. Er zijn wel formules bekend voor speciale gevallen, bijvoorbeeld als de getallen een rekenkundige rij of een meetkundige rij vormen.

Rekenkundige rijen[bewerken]

Als de getallen een rekenkundige rij a, a+d, a+2d, ... a +sd vormen met ggd(a,d)=1, wordt het Frobeniusgetal gegeven door:

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

Meetkundige rijen[bewerken]

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 ggd(mn)=1:

g(m^k,m^{k-1}n,m^{k-2}n^2,\dots,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[bewerken]

Stel dat de getallen a1, a2, ..., an de waarden voorstellen van n verschillende munten. Het Frobeniusprobleem vraagt dan: wat is het grootste bedrag dat niet kan worden betaald met deze munten?

Voorbeeld: Stel dat er enkel munten bestaan met waarde 3 en 5. Het grootste bedrag dat niet kan worden uitbetaald met deze munten is 7. Dit is het Frobeniusgetal van 3 en 5: g(3,5)=7.

Bronnen, noten en/of referenties