conH := ({h}, 1) l’insieme con valutazione formato da un insieme con un solo elemento e dalla valutazione costante 1. Ponendo
A�→
�ω seA = ω, (h, A1, A2) altrimenti,
definiamo una funzione biiettiva tra B e {ω} ∪ ({h} × B × B) che induce un isomorfismo di insiemi con valutazione
B ∼={ω} ⊕ (H × B × B).
Per la Proposizione 8.13 si ha
FB(X) = 1 + XFB(X)2.
Pertanto FB(X)`e una soluzione in R[[X]]dell’equazioneXY2−Y+ 1 = 0. Per l’Esempio 7.107, si ha
FB(X) = 1−√ 1− 4X
2X e [Xn]FB(X) = Catn, ∀n ∈N.
Vi sono pertantoCatnalberi binari di taglian, ovvero con2n + 1vertici. �
8.6 Esercizi
Esercizio 8.1 Determinare il polinomio di autocorrelazione del patternp = (0, 1) e quindi la OGF FS¬p(X)dell’insieme con valutazione delle sequenze binarie che non contengono p. In particolare dedurre il numero di4-sequenze binarie che non contengonop.
Esercizio 8.2 Determinare il polinomio di autocorrelazione del pattern p = (1, 0, 1, 0) e quindi la OGF FS¬p(X)dell’insieme con valutazione delle sequenze binarie che non contengonop. In particolare dedurre il numero di6-sequenze binarie che non contengonop.
Esercizio 8.3 Determinare il polinomio di autocorrelazione del patternp = (1, 1)di I = {1, 2, 3}e quindi la OGF FS¬p(X)dell’insieme con valutazione delle sequenze che non contengonop. In particolare dedurre il numero di4-sequenze diIche non contengonop.
Esercizio 8.4 Determinare il polinomio di autocorrelazione del pattern p = (0, 0, 0, 0, 0)e quindi la OGF FS¬p(X)dell’insieme con valutazione delle sequenze binarie che non contengonop. In particolare dedurre il numero di7-sequenze binarie che non contengonop.
Esercizio 8.5 Qual `e il numero di sequenze binarie di lunghezza 8 che non contengono una striscia di 3 zeri consecutivi?
Esercizio 8.6 Determinare il polinomio di autocorrelazione del proprio cognome.
Determinare la OGF della successione del numero di sequenze che non contengo- no il proprio cognome sia nel caso dell’alfabeto completo (27 lettere) che nel caso dell’alfabeto formato dalle lettere del proprio cognome.
Esercizio 8.7 Determinare numero di 5-sequenze binarie che non contengono il pattern010.
Esercizio 8.8 Determinare numero di 6-sequenze di{a, b, c, d, e} che non conten- gono il patternabc.
Esercizio 8.9 Determinare numero di 4-sequenze di{0, 1, 2, 3} che contengono il pattern11.
Soluzioni degli esercizi
Soluzione es. 8.1. Usando l’algoritmo per il calcolo del polinomio di autocorrelazione otteniamo subitocp(X) = 1, da cui FS¬p(X) = 1
X2+ (1− 2X) = 1 (X− 1)2. Per la Proposizione 7.65 si ha
1 (X− 1)2 =
�∞ n=0
�1 + n n
� Xn =
�∞ n=0
(n + 1)Xn
e di conseguenza il numero din-sequenze che non contengono il pattern (0, 1) `e uguale a[Xn]FS¬p(X) = n + 1. Si poteva trovare il risultato a mano osservando che una sequenza non contiene il dato pattern solo se uno 0 non `e mai seguito da un 1: basta quindi contare in quanti modi si pu`o posizionare una striscia di 1 all’inizio della sequenza, in tutton + 1(nessun 1, un 1, ..., tutti 1).
Soluzione es. 8.6. Usando l’algoritmo per il calcolo del polinomio di autocorrelazione otteniamo subitocp(X) = 1+X2, da cui FS¬p(X) = X2+ 1
X4+ (1− 2X)(X2+ 1) = X2+ 1
1− 2X + X2− 2X3+ X4. Si ha quindi
FS¬p(X)(1− 2X + X2− 2X3+ X4) = 1 + X2
Poniamo FS¬p(X) = a0 + a1X + a2X2 + ..., dobbiamo calcolare a6. Per l’Osservazione 8.29 si ha,
a0 = 1, a1= 21 = 2, a2= 22 = 4, a3= 23= 8, a4= 24− 1 = 15
e, pern > 4 an `e soluzione di
an− 2an−1+ an−2− 2an−3+ an−4 = 0, ovvero
an= 2an−1− an−2+ 2an−3− an−4
da cui
a5 = 2a4− a3+ 2a2− a1= 30− 8 + 8 − 2 = 28 a6= 2a5− a4+ 2a3− a2= 56− 15 + 16 − 4 = 53.
Soluzione es. 8.6. Usando l’algoritmo per il calcolo del polinomio di autocorrelazione otteniamo subitocp(X) = 1 + X da cui, essendo l’alfabeto{1, 2, 3}composto da tre elementi, si ha
FS¬p(X) = X + 1
X2+ (1− 3X)(X + 1) = X + 1 1− 2X − 2X2. Si ha quindi
FS¬p(X)(1− 2X − 3X2) = X + 1
Poniamo FS¬p(X) = a0 + a1X + a2X2 + ..., dobbiamo calcolare a4. Per l’Osservazione 8.29 si ha,
a0 = 1, a1= 31= 3, a2= 32− 1 = 8 e, pern > 2 an `e soluzione di
an− 2an−1− 2an−2 = 0, ovvero
an= 2an−1+ 2an−2
da cui
a3= 2a2+ 2a1= 16 + 6 = 22, a4= 2a3+ 2a2= 44 + 16 = 60.
Soluzione es. 8.4. Usando l’algoritmo per il calcolo del polinomio di autocorrelazione otteniamo subitocp(X) = 1 + X + X2+ X3+ X4, da cui
FS¬p(X) = 1 + X + X2+ X3+ X4
X5+ (1− 2X)(1 + X + X2+ X3+ X4)
= 1 + X + X2+ X3+ X4 1− X − X2− X3− X4− X5. Si ha quindi
FS¬p(X)(1− X − X2− X3− X4− X5) = 1 + X + X2+ X3+ X4
Poniamo FS¬p(X) = a0 + a1X + a2X2 + ..., dobbiamo calcolare a7. Per l’Osservazione 8.29 si ha,
a0= 1, a1= 21= 2, a2= 22= 4, a3= 23= 8, a4= 24= 16, a5 = 25−1 = 31 e, pern > 5 an `e soluzione di
an− an−1− an−2− an−3− an−4− an−5 = 0, ovvero
an= an−1+ an−2+ an−3+ an−4+ an−5
da cui
a6= a5+ a4+ a3+ a2+ a1 = 31 + 16 + 8 + 4 + 2 = 61 a7 = a6+ a5+ a4+ a3+ a2= 61 + 31 + 16 + 8 + 4 = 120.
Soluzione es. 8.5. Postop = 000eI = {0, 1}abbiamocp(X) = 1 + X + X2 da cui
FS¬p(X) = 1 + X + X2
X3+ (1− 2X)(1 + X + X2)
= 1 + X + X2 1− X − X2− X3. Si ha quindi
FS¬p(X)(1− X − X2− X3) = 1 + X + X2
Poniamo FS¬p(X) = a0 + a1X + a2X2 + ..., dobbiamo calcolare a8. Per l’Osservazione 8.29 si ha,
a0 = 1, a1= 21= 2, a2= 22= 4, a3= 23− 1 = 7 e, pern > 3 an `e soluzione di
an− an−1− an−2− an−3= 0, ovvero
an = an−1+ an−2+ an−3 da cui
a4 = a3+ a2+ a1 = 7 + 4 + 2 = 13 a5 = a4+ a3+ a2= 13 + 7 + 4 = 24 a6= a5+ a4+ a3= 24 + 13 + 7 = 44 a7= a6+ a5+ a4= 44 + 24 + 13 = 81 e infine
a8= a7+ a6+ a5= 81 + 44 + 24 = 149.
Vi sono quindi 149 diverse 8-sequenze binarie che non contengono il pattern000.
Soluzione es. 8.6.
Soluzione es. 8.7.
Soluzione es. 8.8.
Soluzione es. 8.9.
