Avrei una domanda su una soluzione.
Considera tutte le parole di lunghezza \(n \) e l'alfabeto \( \mathcal{A}=\{a,b,c\} \), qual'è la proporzione di parole dove la lettera "a" è usata un numero dispari di volte?
La soluzione mi dice:
Sia \( T(n,3) \) il numero di succesioni cicliche di lunghezza \(n\) in un alfabeto di \(3 \) lettere e \(\phi\) la funzione toziente di Eulero. Allora
\[ T(n,3) = \frac{1}{n} \sum_{ d \mid n} \phi(n/d)3^d \]
Sia \( A(n,\text{odd}) \) il numero di parole in cui la lettera \( a \) è usata un numero dispari di volte. Allora
\[A(n,\text{odd})= \sum_{i=0}^{\left \lfloor \frac{n-1}{2} \right \rfloor}a_{2i+1} \]
dove \( a_{2i+1} \) è il numero di parole con esattamente \(2i+1 \) lettere "a" utilizzate.
Abbiamo dunque che \( a_{2i+1}= 2^{n-(2i+1)} (n-2i) \)
e pertanto
La proporizione è data da
\[ \frac{ A(n,\text{odd})}{T(n,3)} \]
Ora io non capisco 2 cose.
1) Come fa a dire che \( a_{2i+1}= 2^{n-(2i+1)} (n-2i) \)??
2) \( T(n,3) \) mi restituisce il numero di classi di equivalenza delle successioni non il numero di tutte le parole.
Dove due successioni sono uguali se una la ottieni a partire dall'altra traslando i numeri di \(k \) posizioni. Ad esempio \( (a,b,b) \sim (b,a,b) \)
Come mai è giusto?