Niente B dispari [era: Problemino di combinatoria]

[xxalenicxx]

[Mi raccomando i titoli: se si trova nella categoria "combinatoria", è ovvio che debba essere un problema di combinatoria.... M.]
-------------------------

Salve, volevo proporvi un problemino semplice ma carino:

Supponiamo di avere una parola lunga n, composta dalle lettere A e B.
Quante sono tutte le possibili parole di lunghezza n, formate dalle 2 lettere tali che nella parola non ci siano k lettere B consecutive con k dispari o B singole (quindi sequenze del tipo....ABA....). Quindi ad esempio:

Esempi:
La parola AABBBABB non va bene perchè ci sono 3 B consecutive e 3 è un numero dispari.
La parola ABBAABBBBABB va bene!, perchè tutte le lettere B consecutive sono in numero pari.
La parola ABBBBABAAABB non va bene, perchè c'è una B da sola (...ABA...).

[enomis_costa88]

Considero gli intervalli di B consecutivi. Siano numerati da destra verso sinistra.
Sia quindi $ I_1 $ il primo intervallo di B consecutivi, $ I_2 $il secondo $ I_m $ l'ultimo.
Ogni intervallo contiene un numero $ N_i $ di lettere B consecutive e $ N_i \equiv 0 (mod 2) $ .
Il numero totale di B è $ \sum_{i=1}^m N_i $ .
Ho quindi che il numero totale di B mod 2 è $ \sum_{i=1}^m N_i \equiv 0 (mod 2) $.
Ho un numero pari di B presenti, sia quindi 2k=$ \sum_{i=1}^m N_i $.
Sia j il numero di A presenti. Ho che 2k+j=n;j=n-2k.

Ho in totale k coppie di B, senza perdita di generalità posso accoppiare le lettere B due a due e supporre che una lettera sia sempre adiacente alla propria compagna.

k coppie di B e j A si dispongono in:

$ \frac{(j+k)!}{j!k!} $ = $ \frac{(n-2k+k)!}{(n-2k)!k!} $=
$ \frac{(n-k)!}{(n-2k)!k!} $ = $ {n-k \choose k} $ modi differenti.

Fissato un numero n di lettere totali posso avere un numero di coppie di B compreso tra 0 e $ [\frac{n}{2}] $.

Il numero di parole possibili di lunghezza n composte da lettere A e B tali che non ci siano S lettere B consecutive con S dispari è dato da:
$ \sum_{k=0}^{ [\frac{n}{2}] } {n-k \choose k} $
che probabilmente si potrà anche scrivere in modo più carino..

Buon pomeriggio, Simone

[xxalenicxx]

Si, esatto hai scelto la strada un pò più lunga però ok.

$ \sum_{k=0}^{[\frac{n}{2}]}{n-k \choose k} = F_{n+1} $

Dove $ F_{n+1} $ è l'(n+1)-esimo numero di Fibonacci! Tra l'altro per dimostrare che la sommatoria è uguale a $ F_{n+1} $, si può ragionare nel seguente modo:

Con a_n indichiamo il numero di tutte le possibili soluzioni, quindi:

a_1 = 1 1. A
a_2 = 2 1. AA 2.BB
a_3 = 3 1.AAA 2.ABB 3.BBA

a_4 possiamo ricavarcelo facilmente per iterazione in questa maniera:

a_4 = A * ( AAA OR ABB OR BBA) + BB * (AA OR BB) che è uguale proprio a:
a_4 = A * a_3 + BB* a_2

Scusate per gli operatori, con * indico la concatenazione.
In generale quindi possiamo scrivere che:
a_n = A * a_{n-1} + BB * a_{n-2}

Intendendo che posso concatenare A con a_{n-1} soluzioni e BB con a_{n-2} soluzioni

L'equazione appena scritta è la successione di Fibonacci. Attenzione ai casi base, qui a_1 = 1 e a_2 = 2, in Fibonacci F_1 = 1 e F_2 = 1 F_3 = 2 ecc. Da qui si spiega il numero $ F_{n+1} $