WisFaq!

Paswoorden van 5 letters

We wensen paswoorden te vormen bestaande uit 5 letters.

Vraag :
Hoeveel van dergelijke paswoorden bevatten de letters a en b naast elkaar.

Uitgewerkt antwoord :
Stel A is de gebeurtenis dat er letters a en b naast elkaar voorkomen in een paswoord van 5 letters.

Letters a en b naast elkaar kan dus zijn ab en/of ba

Stel #A = #U - #(niet A)

met #U = 26⁵ = 11881376

Om #(niet A) te bepalen analyseer ik alle voorkomende situaties

1) Paswoorden waarin de letters a en b niet in voorkomen

Aantal = 24⁵

2) Paswoorden waarin de som van het aantal verschijningen van de letter a en/of b gelijk is aan 1
De overige letters beschouw ik als 'tussenschotten'. In deze situatie betekent dit dat ik 4 tussenschotten heb en dus eigenlijk 5 hokjes waarin ik ofwel de letter a ofwel de letter b kan plaatsen

Aantal = 2 (a of b) x 5 (aantal schikkingen van de letter a of b binnen 5 hokjes) x 24⁴(overige waarden der tussenhokjes) = 10.24⁴

3) Paswoorden waarin de som van het aantal verschijningen van de letter a en/of b gelijk is aan 2.
Aantal mogelijke variaties van a en b = 4 (2²)
(aa,ab,ba,bb)

Je kan dan volgende opdeling maken :

De twee letters vlak na elkaar : (aa) en (bb) voldoen aan
'niet A'
Aantal = 2 x 4 x 24³ = 8.24³

De twee letters niet vlak na elkaar : de koppels (a,a), (b,b), (a,b) en (b,a) voldoen aan 'niet A'
Aantal = 4 x ((4x3)/2) x 24³ = 24 x 24³ = 24⁴

4) Paswoorden waarin de som van het aantal verschijningen van de letter a en/of b gelijk is aan 3.
Aantal mogelijke variaties van a en b = 8 (2³)
(aaa,aab,aba,baa,abb,bab,bba,bbb)

Je kan dan volgende opdeling maken :

De drie letters vlak na elkaar : (aaa) en (bbb) voldoen aan 'niet A'

Aantal = 2 x 3 x 24² = 6.24²

Twee van de drie letters vlak na elkaar : de koppels (aa,a),
(bb,b), (aa,b) en (bb,a) voldoen aan 'niet A'

Aantal = 4 x (3x2) x 24² = 24 x 24² = 24³

Geen van de drie letters vlak na elkaar : de tripels (a,a,a),
(b,b,b), (a,a,b), (a,b,a), (b,a,a), (a,b,b), (b,a,b), (b,b,b) voldoen aan 'niet A'

Aantal = 8 x 1 x 24² = 8.24²

4) Paswoorden waarin de som van het aantal verschijningen van de letter a en/of b gelijk is aan 4.
Aantal mogelijke variaties van a en b = 16 (2⁴)
(aaaa,
aaab,aaba,abaa,baaa,
aabb,abab,baab,abba,baba,bbaa,
abbb,babb,bbab,bbba,
bbbb)

Je kan dan volgende opdeling maken :

De vier letters vlak na elkaar : (aaaa) en (bbbb) voldoen aan 'niet A'

Aantal = 2 x 2 x 24 = 4.24

Drie van de vier letters vlak na elkaar : de koppels (aaa,a),
(bbb,b), (aaa,b) en (bbb,a) voldoen aan 'niet A'

Aantal = 4 x 2 x 24 = 8.24

Twee groepjes van 2 letters vlak na elkaar : de koppels (aa,aa), (bb,bb), (aa,bb) en (bb,aa) voldoen aan 'niet A'

Aantal = 4 x 1 x 24 = 4.24

5) Paswoorden waarin de som van het aantal verschijningen van de letter a en/of b gelijk is aan 5.
Aantal mogelijke variaties van a en b = 32 (2⁵)
(aaaaa,
aaaab,aaaba,aabaa,abaaa,baaaa,
aaabb,aabab,abaab,baaab,aabba,ababa,baaba,abbaa,babaa,bbaaa,
aabbb,ababb,baabb,abbab,babab,bbaab,abbba,babba,bbaba,bbbaa
abbbb,babbb,bbabb,bbbab,bbbba
bbbbb)

Je kan dan volgende opdeling maken :

De vijf letters vlak na elkaar : (aaaaa) en (bbbbb) voldoen aan 'niet A'

Aantal = 2

en dus #(niet A) = 24⁵ + 10.24⁴ + 24⁴ + 8.24³ + 8.24²
+ 24³ + 6.24² + 4.24 + 8.24 + 4.24 + 2
= 24⁵ + 11.24⁴ + 9.24³ + 14.24² + 16.24 + 2
#(niet A) = 11745026

=$\Rightarrow$ #A = #U - #(niet A) = 11881376 - 11745026 = 136350

Klopt bovenstaande afleiding ?

Bestaat er ook een vluggere methode om deze vraag te beantwoorden ?

Met dank,

Rudi

Rudi
22-5-2018

Antwoord

De telling ziet er grondig en systematisch uit; ik heb niet alles uitputtend gecontroleerd maar ik vertrouw de uitkomst.

Het is makkelijker en sneller het probleem voor alle $n$ op te lossen. Het kost een paar variabelen maar dan heb je ook wat:

1. $G_n$: het aantal rijen van lengte $n$ zonder $a$ en $b$ naast elkaar
   
2. $A_n$: het aantal rijen van lengte $n$ zonder $a$ en $b$ naast elkaar die eindigen in een $a$
   
3. $B_n$: het aantal rijen van lengte $n$ zonder $a$ en $b$ naast elkaar die eindigen in een $b$
   
4. $E_n$: het aantal rijen van lengte $n$ zonder $a$ en $b$ naast elkaar die eindigen in iets anders dan een $a$ of $b$
   

Dus $G_n=A_n+B_n+E_n$.
Je kunt relaties opstellen:

1. $A_{n+1}=A_n+E_n$ (de rijen die niet eindigen in een $b$ mogen een $a$ krijgen)
   
2. $B_{n+1}=B_n+E_n$ (de rijen die niet eindigen in een $a$ mogen een $b$ krijgen)
   
3. $E_{n+1}=24(A_n+B_n+E_n)$ (alle rijen mogen een letter ongelijk aan $a$ en $b$ krijgen)
   

Merk op dat in de laatste relatie (ook) staat dat $E_{n+1}=24G_n$
Tel alledrie relaties bij elkaar op:
$$
G_{n+1}=25A_n+25B_n+26E_n=25G_n+E_n = 25G_n+24G_{n-1}
$$(want $E_n=24G_{n-1}$).
Samengevat: $G_{n+1}=25G_n+24G_{n-1}$ en $G_1=26$ en $G_2=26^2-2$.
Nu kun je $G_3$, $G_4$, $G_5$, $\dots$ berekenen.

kphart
22-5-2018