De betrekkingen worden bij stijgende aantallen a's wat ingewikkelder maar het lijkt me allemaal wel te doen.
Zoudt U het niet erg vinden om dat voor mij te doen. Ik heb het nodig voor een wetenschappelijk artikel en wil graag U naam noemen als auteur van de verdeling. Een andere mogelijkheid is dat U mij laat zien hoe het werkt in een eenvoudiger geval:
Rijen letters van lengte 6 bestaande uit de letters a, b en c (met gelijke kansen), die voldoen aan (1) a komt ten minste eenmaal voor en (2) opeenvolgende letters zijn verschillend.
Het wetenschappelijke artikel is een vervolg op een eerder artikel, dat ik, als U wil, aan U op kan sturen.
Ad van
Iets anders - donderdag 29 mei 2014
Antwoord
We bekijken woorden in het alphabet $\{a,b,c,d,e,f\}$.
We noteren met $W_n$ de verzameling van woorden van lengte $n$, dan geldt natuurlijk $|W_n|=6^n$.
De belangrijke verzameling is $V_n=\{w\in W_n:(\forall i$<$n)(w_i\neq w_{i+1})\}$, de woorden waarin opeenvolgende letters altijd verschillen. Er geldt $|V_n|=6\times5^{n-1}$.
Dat is makkelijk met inductie te bewijzen: het geval $n=1$ is makkelijk: $|V_1|=6$. Voor grotere $n$ verdelen we $V_n$ in zes even grote stukken: $V_{n,t}=\{w\in V_n:w_n=t\}$, met $t\in\{a,b,c,d,e,f\}$. Dat deze stukken even groot zijn volgt coördinaatsgewijs de permutatie $a\to b\to c\to d\to e\to f\to a$ toe te passen. Nu volgt $$ |V_{n+1}|=6\times|V_{n+1,a}|=6\times5\times|V_{n,b}|= 6\times5\times\frac16|V_n|=5\times|V_n| $$
Voor elke $k$ en $n$ noteren we $$ U_{k,n}=\{w\in V_n:|\{i:w_i=a\}|=k\} $$ Voor de kansen waar naar gevraagd werd geldt dan $$ P(X=k)= \frac{|U_{k,n}|}{|V_n|-|U_{0,n}|} $$ waarbij $n=18$ en $k=1, \dots, 9$.
Om de $|U_{k,n}|$ te bepalen noteren we, voor $t\in\{a,b,c,d,e,f\}$, $$ U_{k,n,t}=\{w\in U_{k,n}: w_n=t\} $$ Dan geldt dus $$ |U_{k,n}|=\sum\bigl\{|U_{k,n,t}|:t=a,b,c,d,e,f\bigr\} $$ Verder geldt, voor $s,t\in\{b,c,d,e,f\}$, dat $|U_{k,n,s}|=|U_{k,n,t}|$.
Conclusie: $$ |U_{k,n}|=|U_{k,n,a}|+5\times|U_{k,n,b}| $$ We gaan $|U_{k,n,b}|$ en $|U_{k,n,a}|$ bepalen. We schrijven $ua(k,n)=|U_{k,n,a}|$ en $ub(k,n)=|U_{k,n,b}|$.
We hebben $$ U_{k,n+1,a}=\bigcup\{U_{k-1,n,t}\times\{a\}:t=b,c,d,e,f\} $$ en $$ U(k,n+1,b)=(U(k,n,a)\times\{b\})\cup \bigcup\{U(k,n,t)\times\{b\}:t=c,d,e,f\} $$ deze gelijkheden vertalen zich in $$ ua(k,n+1)=5\times ub(k-1,n) $$ en $$ ub(k,n+1)=4\times ub(k,n)+ ua(k,n). $$ Met behulp van deze twee relaties kunnen formules voor $ua(k,n)$ en $ub(k,n)$ en dus ook voor $|U_{k,n}|$ afgeleid worden.
Voor $k=0$: $ua(0,n)=0$ (geen woord zonder $a$ eindigt in een $a$), en dus $ub(0,n+1)=4\times ub(0,n)$ en omdat $ub(0,1)=1$ zien we $ub(0,n)=4^{n-1}$.
Nu $k=1$: er geldt $ua(1,1)=1$, $ub(1,1)=0$ en $ub(1,2)=1$ (de verzamelingen zijn eenvoudig op te schrijven). Dan volgt uit de eerste formule voor $n\ge 2$ dat $$ ua(1,n)=5\times ub(0,{n-1})=5\times4^{n-2}. $$ en uit de tweede: $$ ub(1,n+1) = 4ub(1,n)+ua(1,n) $$ en voor $n\ge2$ wordt dit $$ ub(1,n+1) = 4ub(1,n)+5\times4^{n-2} $$ Met de beginvoorwaarde $ub(1,2)=1$ geeft Maple's rsolve de oplossing $$ ub(1,n) = \frac{5n-6}{64}\times4^n $$ Nu volgt voor $n\ge2$: $$ |U_{1,n}|=ua(1,n)+5\times ub(1,n) = 5\times 4^{n-2}+5\times\frac{5n-6}{64}\times 4^n = 25(n-2)4^{n-3}+10\times 4^n $$ en $|U(1,1)|=1$.
Dit gaat zo verder, wel opletten dat bij het oplossen van latere recursie de juiste beginvoorwaarde wordt meegenomen.
Dit is een reactie op vraag 73105 
