Hulp bij berekenen aantal mogelijkheden (wiskunde/kansbereke

[-Elmer-]

Ik vind het eigenlijk een beetje genant om te vragen maar loop toch een beetje vast op een bepaalde berekening. Wellicht dat iemand me er mee kan helpen?

Het startpunt is een vooraf gedefiniteerde seqentie met een lengte van 20. Bijvoorbeeld:
AAAAAAAAAAAAAAAAAAAA (20x A)

Nu wil ik graag berekenen hoeveel mogelijkheden er zijn als ik op maximaal drie random posities een wijziging aanbreng welke kan bestaan uit B, C of D.
De volgorde is belang dus ("...A" betekend + 15x A)
BAAAA...A =! ABAAA...A =! AABAA...A =! etc...
En alle mogelijk combinaties zijn geldig, dus met terugleggen:
BBBAA...A is een geldige combinatie evenals CCCAA...A en DDDAA..A

Stel dat op alle posities een dergelijke mutaties mag worden uitgevoerd is het natuurlijk super eenvoudig, gewoon 4^20 aantal mogelijkheden maar hoe de correctie uit te voeren voor de 17 posities die niet mogen veranderen. De mutaties hoeven niet naast elkaar te li
Als op iedere positie ggen.

---

Om de berekening te maken heb ik een iets eenvoudigere opzet gemaakt met een sequentie van lengte l=5 en mogelijkheden m=2 (A/B).
Uitgangsequentie: AAAAA

Met muatie op 1 positie (p=1)
BAAAA
ABAAA
AABAA
AAABA
AAAAB
--> er komen dus 5 mogelijkheden bij.
Zou je kunnen zien als 5! - 4! maar dat is onzin en loopt helemaal spaak bij meerdere mutaties
Zou je ook kunnen zien als "l"

Met mutatie op 1 of 2 posities
De mogelijkheden die ontstaan bij een mutatie op 1 plek (zie bovenstaand) dus 5 +

BBAAA
BABAA
BAABA
BAAAB

ABBAA
ABABA
ABAAB

AABBA
AABAB

AAABB
--> Er komen dus 5 + 10 =15 mogelijkheden bij
Zou je kunnen zien als l + (l-1)!

Tot 3 posities een mutatie
Mogelijkheden p=1 (5) + p=2 (10) = 15
+
BBBAA BABBA BAABB
BBABA BABAB
BBAAB

ABBBA ABABB
ABBAB

AABBB
Dus totaal 5 + 10 + 10 = 25 mogelijkheden bij
Zou je kunnen zien als l + (l-1)! + (l-2)! maar dat klopt niet

Bij maximaal vier mutaties heb je (p=4)
(p=1) + (p=2) + (p=3) = 5 + 10 + 10 = 25
+
BBBBA
BBBAB
BBABB
BABBB
ABBBB

Dus totaal komen er nog eens 5 bij --> 30 mogelijkheden nu

En tot slot een muatatie op maximaal 5 posities (p=5)
(p=1) + (p=2) + (p=3) + (p=4) = 30
+ BBBBB
Er komt er nu nog 1 bij dus totaal wordt 31 en dat is natuurlijk logisch want
m^l = 2^5 = 32 (incl. startsequentie)

Samengevat gaat het er dus om een functie te brouwen voor deze reeks die universeel genoeg is om om alle drie de parameters probleemloos te kunnen wijzigen
l=5
m=2
p=0..5

p=0 (heb ik maar even geintroduceert om te corrigeren voor de uitgangs-sequentie)
--> 1
p=1
--> 1 + 5 = 6
p=2
--> 1 + 5 + 10 = 16
p=3
--> 1 + 5 + 10 + 10 = 26
p=4
--> 1 + 5 + 10 +10 + 5 = 31
p=5
--> 1 + 5 + 10 + 10 + 5 + 1 = 32

Best een leuke reeks waar zeker iets kwadratisch in moet komen geloof ik... maar ik loop er een beetje op vast en dat is heeeeeeeeeeeeeeel irritant. Eigenlijk wil ik niet geholpen worden maar heb wel een beetje het antwoord nodig Alvast veel dank!

[Orion84]

Ik zou de situaties per aantal mutaties beschouwen (wat je zelf eigenlijk ook al doet in je versimpelde voorbeeld).

0 mutaties:
1 mogelijkheid: 20x A

1 mutatie:
20 x 3=60 mogelijkheden, namelijk twintig posities waar 1 van de 3 andere letters kan staan

2 mutaties:
60 opties voor 1 mutatie. In elk van die opties nog een teken vervangen, 19 posities (want mutatie niet overschrijven) en 3 opties per positie:
60 x 19 x 3 = 3420
Daarmee krijg je echter elke optie dubbel, voorbeeld:
ABA...AC kan je maken door eerst de laatste A door een C te vervangen en daarna de 2e A door een B, of door eerst de B op zijn plek te zetten en daarna de C.
Dus delen door 2 geeft 1710

3 mutaties:
1710 opties voor 2 mutaties. In elk van die opties nog een teken vervangen, 18 posities, 3 opties per positie:
1710 * 18 * 3 = 92340
In dit geval krijg je elke optie 3 keer, dus delen we door 3 geeft 30780

Optellen geeft:

1 + 60 + 1710 + 30780 = 32551

Formule is dus (voor 20 posities en 3 alternatieve letters):

0 mutaties: 1 = m₀
1 mutaties: (m0 x 20 x 3) / 1 = m₁
2 mutaties: (m1 x 19 x 3) / 2 = m₂
3 mutaties: (m2 x 18 x 3) / 3 = m₃

Oftewel:
m₀ = 1
m_i+1 = (m_i x (20 - i) x 3) / (i + 1)

Totaal: Som over m_i met i van 0 tot max. mutaties

Als ik die methode loslaat op jouw handmatige voorbeeld met 5 posities, max. drie mutaties met alleen de B als optie kom ik op hetzelfde uit als jij, dus ik gok dat mijn methode klopt

[ Voor 26% gewijzigd door Orion84 op 16-03-2013 16:48 ]

[Anoniem: 26306]

Orion84 schreef op zaterdag 16 maart 2013 @ 16:20:

3 mutaties:
1710 opties voor 2 mutaties. In elk van die opties nog een teken vervangen, 18 posities, 3 opties per positie:
1710 * 18 * 3 = 92340
In dit geval krijg je elke optie 3 keer, dus delen we door 3 geeft 30780

Volgens mij zit je er hier naast. Stel je zou het hebben over AAA waarbij je alle 3 de tekens vervangt door B, C of D. Je hebt 3! ∙ 3 = 18 mogelijkheden.
Voor de posities heb je 20 ∙ 19 ∙ 18 mogelijkheden, dat is 6840. Vermenigvuldig dat met 18 en je krijgt 123120 mogelijkheden voor alleen de wijzigingen waarbij je 3 posities mogelijk wijzigt.

Het enige dat nu nog erbij komt kijken is het aantal posities dat je beschouwt. Dan kom je bij 3 posities op 20 inderdaad aan 20 ∙ 19 ∙ 18. Volgens mij is dat gelijk aan 20! - (20-3)!
Als we het totale aantal posities p noemen, het aantal mogelijkheden per positie n en het aantal posities dat je wijzigt m, dan kom je op de volgende formule:

x = n ∙ (m!) ∙ (p! - (p-m)!)

Nu kun je vast ook wel een formule bedenken die dit in één keer voor alle m bepaalt, maar daar heb ik nu even geen zin in
[edit]
Volgens mij heb ik ergens een fuckup gemaakt, dus bovenstaande klopt niet.

[ Voor 3% gewijzigd door Anoniem: 26306 op 16-03-2013 17:22 ]

[-Elmer-]

Orion84 schreef op zaterdag 16 maart 2013 @ 16:20:

Formule is dus (voor 20 posities en 3 alternatieve letters):

0 mutaties: 1 = m₀
1 mutaties: (m0 x 20 x 3) / 1 = m₁
2 mutaties: (m1 x 19 x 3) / 2 = m₂
3 mutaties: (m2 x 18 x 3) / 3 = m₃

Oftewel:
m₀ = 1
m_i+1 = (m_i x (20 - i) x 3) / (i + 1)

Totaal: Som over m_i met i van 0 tot max. mutaties

Als ik die methode loslaat op jouw handmatige voorbeeld met 5 posities, max. drie mutaties met alleen de B als optie kom ik op hetzelfde uit als jij, dus ik gok dat mijn methode klopt

Dit voelt heel logisch en je deugedelijke voorbeeld maakt het ook inzichelijk. Stompzinnig dat ik er zelf niet achter kwam maar desalnittemin onwijs bedankt voor het meedenken!

Anoniem: 26306 schreef op zaterdag 16 maart 2013 @ 17:05:
[...]
Volgens mij zit je er hier naast. Stel je zou het hebben over AAA waarbij je alle 3 de tekens vervangt door B, C of D. Je hebt 3! ∙ 3 = 18 mogelijkheden.

Dat klopt niet. Het zijn toch 3^3 mogelijke alternatieven als je iedere positie veranderd en drie mogelijke opties hebt per positie?
AAA

BBB BBC BBD BCB BDB BCC BDD BCD BDC
CCC CCB CCD CBC CDC CBB CDD CBD CDB
DDD DDB DDC DBD DCD DBB DCC DBC DCB

[ Voor 45% gewijzigd door -Elmer- op 16-03-2013 18:17 ]

[KopjeThee]

Veel verder dan een sommatie zal je ook niet komen, denk ik. Er bestaat geen gesloten formule voor dit probleem. Wikipedia: Binomial coefficient
"Although there is no closed formula for...". Terwijl dit alleen nog maar het geval is met 2 mogelijke waarden.

De algemene formule zal wel iets zijn als:
som van i=0 tot p ( (l kies i)*(m-1)^i )
De interpretatie van elke i: Kies i posities om te wijzigen, en er zijn (m-1)^i mogelijkheden om die i posities te wijzigen. m-1, Omdat 1 van die m mogelijke waarden natuurlijk de oorspronkelijke waarde is. Die waarde is dus geen wijziging.

Het geval uit de OP met
l=20
m=4
p=3
wordt dan
i=0: 1
i=1: 20*3=60
i=2: 190*9=1710
i=3: 1140*27=30780
Totaal: 32551

Dit komt overeen met Orion's resultaat.

[ Voor 61% gewijzigd door KopjeThee op 17-03-2013 12:52 ]

[iChaos]

Ik ben er even mee aan de slag gegaan, en op 1 regel code na heb ik een stukje Python geschreven die de uitkomst brute-forced: geef de mogelijke mutaties op, en de reekslengte, en hij doet ca. 10 miljoen berekeningen met random indexes en random mutaties, en als die mutatie nieuw is slaat hij hem op. Vervolgens kijkt hij hoeveel unieke mutaties er zijn geweest. Je weet helaas nooit of je echt klaar bent met het aantal opties, dus die 10 miljoen kan net zo goed ook 50 miljoen zijn eer je het vindt (gelukkig is het geen zware berekening dus zal dat op een moderne PC maar enkele minuten duren). Als je vervolgens een patroon probeert te vinden in aantal mogelijkheden en de mogelijke mutaties, kan je wellicht een formule vormen die de mogelijkheden berekent. Probleem is wel dat je die formule dus nooit door beredenatie kan vinden, maar zult moeten brute-forcen om te kijken hoe hij in elkaar steekt, en met enkele steekproeven de algemene formule voor het probleem vindt.

De code upload ik vandaag wel even als er interesse voor is. Mogelijk zit ik ergens ook fout met mijn beredenatie. Met wiskunde B in 5VWO en wat kennis van Python ben ik zeker geen persoon die dit kan berekenen op een intelligentere wijze

[KopjeThee]

iChaos schreef op zondag 17 maart 2013 @ 14:53:
Probleem is wel dat je die formule dus nooit door beredenatie kan vinden, ...

Natuurlijk wel :
som van i=0 tot p ( (l kies i)*(m-1)^i )

Of de aanpak van Orion.