Frobeniusgetal

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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

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

Het getal noemt men het frobeniusgetal en noteert het als:

Zonder verlies van algemeenheid kan men veronderstellen dat:

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 bestaat er een expliciete formule voor het frobeniusgetal:

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

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

Als de getallen een rekenkundige rij vormen, met , wordt het frobeniusgetal gegeven door:

Meetkundige rijen[bewerken]

Er bestaat ook een expliciete formule voor het Frobeniusgetal van een verzameling getallen die een meetkundige rij vormen. Als gehele getallen zijn met :

Interpretatie van het frobeniusprobleem[bewerken]

Stel dat de getallen de waarden voorstellen van 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 7. Dit is het frobeniusgetal van 3 en 5: 7.