Alfabeto

[Pachisi]

Dato un alfabeto con tre lettere $a,b,c$, determinare, con dimostrazione, il numero di parole di $n$ lettere con un numero pari di $a$.

[orsoulx]

Consideriamo una parola di n lettere, le lettere 'a' devono essere in numero pari diciamo $2i$, e potranno disporsi in \( \begin{pmatrix} n \\ 2i \end{pmatrix} \) posizioni diverse; nelle posizioni non occupate i due simboli 'b' e 'c' potranno essere disposti in $ 2^(n-2i) $ modi diversi. Indicando con $ a_n $ il numero di parole diverse di lunghezza $ n $, sara allora \( a_n = \sum_{i=0}^{[n/2]} {\begin{pmatrix} n\\ 2i \end{pmatrix} 2^{n-2i}} \).
Per esprimere in forma chiusa il risultato basta usare lo sviluppo di Newton del binomio. Essendo:
\( 3^n=(1+2)^n=\sum_{i=0}^{n} {\begin{pmatrix} n\\ i \end{pmatrix} 1^i \cdot 2^{n-i}} \) e \( 1=1^n=(-1+2)^n=\sum_{i=0}^{n} {\begin{pmatrix} n\\ i \end{pmatrix} (-1)^i \cdot 2^{n-i}} \), sommandole si elidono i termini con i dispari e si duplicano quelli con i pari, sarà allora $ a_n=(3^n+1)/2 $.

Ciao
B.

[Pachisi]

Bravo. Sempre molto belle le tue soluzioni.

[orsoulx]

@pachisi
quel che dici mi pare di averlo già sentito ... e poi non è vero: ho dimenticato 'potenza del' fra Newton e binomio.
Ciao e grazie
B.

[Pachisi]

Si si, già sentito...