WisFaq!

Re: Formule voor een reeks vinden

Geachte Gilbert,

Heel hartelijk dank voor uw snelle reactie. Ik had er inmiddels zelf aan gesleuteld en hetzelfde resultaat gevonden.

De vraagstelling kwam uit het volgende probleem voor. Stel je hebt een multiset (reeks, anagram) bestaande uit negen letters waarin alleen de letter a en de letter b voorkomt. De letter a komt drie keer voor en de letter b zes keer.

Je krijgt dan de permutaties hieronder:

aaabbbbbb
aababbbbb
aabbabbbb
aabbbabbb
aabbbbabb
aabbbbbab
aabbbbbba
abaabbbbb
abababbbb
ababbabbb
ababbbabb
ababbbbab
ababbbbba
abbaabbbb
abbababbb
abbabbabb
abbabbbab
abbabbbba
abbbaabbb
abbbababb
abbbabbab
abbbabbba
abbbbaabb
abbbbabab
abbbbabba
abbbbbaab
abbbbbaba
abbbbbbaa
baaabbbbb
baababbbb
baabbabbb
baabbbabb
baabbbbab
baabbbbba
babaabbbb
babababbb
bababbabb
bababbbab
bababbbba
babbaabbb
babbababb
babbabbab
babbabbba
babbbaabb
babbbabab
babbbabba
babbbbaab
babbbbaba
babbbbbaa
bbaaabbbb
bbaababbb
bbaabbabb
bbaabbbab
bbaabbbba
bbabaabbb
bbabababb
bbababbab
bbababbba
bbabbaabb
bbabbabab
bbabbabba
bbabbbaab
bbabbbaba
bbabbbbaa
bbbaaabbb
bbbaababb
bbbaabbab
bbbaabbba
bbbabaabb
bbbababab
bbbababba
bbbabbaab
bbbabbaba
bbbabbbaa
bbbbaaabb
bbbbaabab
bbbbaabba
bbbbabaab
bbbbababa
bbbbabbaa
bbbbbaaab
bbbbbaaba
bbbbbabaa
bbbbbbaaa

Je kunt je dan afvragen:

hoe dikwijls komt een b alleen voor (b): f[1]
hoe dikwijls komt een b als paar voor (bb): f[2]
hoe dikwijls komt een b als een aaneengesloten drietal voor (bbb): f[3]

etc., waarbij b ook een aantal keer niet voor kan komen zoals

vóór de eerste a
tussen twee a-tjes
nà de laatste a

Deze aantallen zijn als volgt:

f[0] = 112
f[1] = 84
f[2] = 60
f[3] = 40
f[4] = 24
f[5] = 12
f[6] = 4

Voor die aantallen zocht ik de formule en, nogmaals, ik ben heel blij met uw antwoord.

Nu heb ik nog een probleem. Ik heb een andere reeks bestaande uit 24 letters waarin alleen de letter a en de letter b voorkomt. De letter a komt 8 keer voor en de letter b 16 keer. Nu ben ik weer geïnteresseerd in de aantallen f[0] ... f[16]. Het is me nog niet gelukt hier uit te komen, laat staan ook nog de formule te vinden. Ik meen, dat f[16] = 9, f[15] = 72 en f[14] = 324. Maar daar kan ik al een fout gemaakt hebben. Ik zou het geweldig vinden als U mij hierbij ook zou kunnen helpen en zal U dan zeker vermelden in het artikel dat ik aan het schrijven ben.

Nogmaals dank, Ad

Ad van der Ven
2-5-2014

Antwoord

Beste Ad,

Ik weet geen eenvoudige manier om een formule af te leiden. Wel is het mogelijk om een eenvoudig computerprogrammaatje te maken dat alle mogelijke posities systematisch aftast en de gevraagde aantallen te tellen. Ik kom op:

F[1] = 1534896
F[2] = 1046520
F[3] = 697680
F[4] = 453492
F[5] = 286416
F[6] = 175032
F[7] = 102960
F[8] = 57915
F[9] = 30888
F[10] = 15444
F[11] = 7128
F[12] = 2970
F[13] = 1080
F[14] = 324
F[15] = 72
F[16] = 9

Als ik de vraag goed heb begrepen, heeft F[0] geen betekenis: de letter b kan toch nooit in een rijtje van 0 keer voorkomen?

Opvallend bij deze reeks is dat het zevende verschil constant is (d.w.z.: maak een nieuwe reeks die bestaat uit de verschillen F[1]-F[2], F[2]-F[3], F[3]-F[4] enz. Dit is het eerste verschil. Doe hetzelfde met deze nieuwe reeks, herhaal dit tot een totaal van 7 keer). Dit betekent dat deze getallen met een 7^e graads polynoom beschreven kunnen worden (zie wikipedia: polynoom).

GHvD
3-5-2014