• Non ci sono risultati.

N/A
N/A
Protected

Academic year: 2021

Condividi ""

Copied!
11
0
0

Testo completo

(1)

= (2n)!

n!⇥ (n + 1)! = 1 n + 1

2n n

= Catn, ovvero i numeri di Catalan introdotti nella sezione 3.3. Dunque

Y2(X) = X1 n=0

CatnXn

In particolare abbiamo determinato la OGF dei numeri di Catalan:

X1 n=0

CatnXn= 1 (1 4X)1/2

2X .

7.7 Esercizi

Esercizio 7.1 SianoA(X)una serie formale em 2 N. Provare che per ognin m2N si ha[Xn] (XmA(X)) = [Xn m] A(X).

Esercizio 7.2 Sia A(X)una serie formale. Provare che A0(X) = 0 se e solo se A(X)`e una costante.

Esercizio 7.3 SianoA(X)eB(X)due serie formali em, n2N. Provare che ([Xm]A(X)) ([Xn]B(X)) = [Xn] (([Xm]A(X)) B(X)) . Esercizio 7.4 SiaA(X) =

X1 k=0

1

k!XkeB(X) = X1 k=1

( 1)k 1Xk. Determinare una forma chiusa diA(B(X))e calcolarne il coefficiente del termine di grado 2.

Esercizio 7.5 Calcolare la forma chiusa delle serie formali

A(X) = X1 n=0

nXn, B(X) = X1 n=0

n(n + 1)Xn

Esercizio 7.6 Calcolare in quanti modi `e possibile distribuire 25 caramelle (ugua- li) alla liquirizia a Carlo, Roberta, Giuseppe, Stefano ed Alberto se Carlo ne vuole almeno 8 ma non pi`u di 12, Roberta non pi`u di 4, e Giuseppe ed Alberto almeno 1?

Esercizio 7.7 In una pasticceria in Calle de San Pantalon sono esposte frittelle alla crema, allo zabaione e frittelle tradizionali veneziane senza ripieno. In quanti modi

`e possibile scegliere 15 frittelle se vogliamo che ve ne sia un numero pari 2alla crema, un numero dispari 1allo zabaione ed almeno 5 tradizionali veneziane?

(2)

Esercizio 7.8 Sia A(X) = X1 n=0

2nXn; dire se A(X) `e invertibile in R[[X]] ed eventualmente determinarne un’inversa.

Esercizio 7.9 Provare che la derivata di una serie formale ha le stesse propriet`a (per quanto riguarda la somma e il prodotto) della derivata di funzioni: seA(X)eB(X) sono due serie formali allora

(A(X) + B(X))0 = A0(X) + B0(X)e (A(X)B(X))0 = A0(X)B(X) + A(X)B0(X).

Esercizio 7.10 Sia0 < m 2N edA(X)una serie formale in R[[X]]. Provare che seAm(X) = 1, alloraA(X) `e costante, uguale ad 1 sem `e dispari, a±1sem `e pari. Dedurre che, a seconda chemsia dispari o pari, vi sono esattamente 1 o 2 serie formali la cui potenzam-esima `e la serie formale1 + X.

Esercizio 7.11 Calcolare una forma chiusa della serie formale

A(X) = X1 n=2

(n 1)Xn

Esercizio 7.12 Siaf (x)una forma chiusa della derivataA0(X)di una serie formale A(X)e siaA(0) = 0. Allorag(x) =

Z x 0

f (t) dt`e una forma chiusa diA(X). Esercizio 7.13 Calcolare in quanti modi si pu`o preparare un vassoio di 12 paste di cinque qualit`a diverse con al massimo quattro paste dello stesso tipo (per ogni tipo ci deve essere almeno una pasta!).

Esercizio 7.14 In quanti modi `e possibile assegnare a 10 bambini venti caramelle alla menta e dieci all’anice in modo che ogni bambino riceva esattamente tre caramelle.

Esercizio 7.15 In un supermercato un pazzo di nome Pascal ha lanciato contro un po- vero vecchio delle confezioni, prendendole alla rinfusa dagli scaffali. Alla fine, prima che qualcuno riuscisse a fermarlo, Pascal era riuscito a lanciare ben 11 confezioni. I testimoni presenti hanno fornito versioni contrastanti sul tipo di confezioni che sono state lanciate contro il vecchio; alla fine tutti concordavano sul fatto che erano state lanciate

1. un numero pari ( 0) di barattoli di passata di pomodoro, 2. almeno 2 bottiglie d’olio,

3. tra 4 e 7 lattine di birra,

4. un souvenir del duomo di Milano.

(3)

Tenendo presente che tutte le possibili versioni coerenti con quanto su descritto sono state effettivamente fornite dai testimoni, quante erano al minimo le persone presenti nel supermercato oltre al vecchio ed a Pascal?

Esercizio 7.16 In vista delle prossime elezioni il partito di Drinkhealthy `e alle pre- se con la scelta dei candidati. In questa prima fase deve essere deciso quanti e quali posti dei 10 disponibili nella lista destinare alle varie categorie; solo in un secon- do momento si sceglieranno i nomi dei candidati. La scelta andr`a fatta rispettando i seguenti vincoli tra le seguenti quattro categorie disgiunte

1. un numero pari di funzionari di partito, 2. un numero dispari di vecchi consiglieri,

3. almeno 5 esponenti dichiaratamente tradizionalisti, 4. al massimo un candidato chiaramente progressista.

Quante sono le possibili scelte in questa fase preliminare?

Esercizio 7.17 Quanti sono i numeri di sei cifre con un numero pari di 7 ed un numero dispari di 9 e due 5?

Esercizio 7.18 Calcolare 1.

X149 k=1

k5; 2.

X299 k=1

k7; 3.

9 999X

k=1

k3.

Esercizio 7.19 Utilizzando le funzioni generatrici fornire una dimostrazione alterna- tiva della formula (2.3):

X

k2Z

r

m + k

◆ ✓ s n + k

=

r + s r m + n

8m, n, r, s 2N.

Soluzioni degli esercizi Soluzione es. 7.1. SiaA(X) =

X1 i=0

aiXi; allora

[Xn](XmA(X)) = [Xn] X1

i=0

aiXi+m=

(an m = [Xn m]A(X) sen m,

0 altrimenti.

(4)

Soluzione es. 7.2. Sia A(X) = X1

i=0

aiXi; per definizione A0(X) = X1 i=1

iaiXi 1. AlloraA0(X) = 0se e solo se per ognin2N si ha

0 = [Xn]A0(X) = [Xn] X1

i=1

iaiXi 1= (n + 1)an+1

ovvero se e solo sean+1 = 0per ogni n 0. PertantoA0(X) = 0se e solo se A(X) = a0.

Soluzione es. 7.3. PostoA(X) = X1 k=0

akXkeB(X) = X1 k=0

bkXksi ha ([Xm]A(X)) ([Xn]B(X)) = ambn;

si conclude essendo

ambn = [Xn]amB(X) = [Xn] (([Xm]A(X)) B(X)) . Soluzione es. 7.4. Si haA(X) = eXe

B(X) = ( X) + ( X)2+ ... =

1

1 ( X) 1

= X

1 + X

AlloraA(B(X)) = e X

1 + X. Siaf (x) = e x

1 + x; allora [X2]A(B(X)) = f00(0)

2!

Essendof0(x) = e x

1 + x · 1 (1 + x)2 e

f00(x) = e x

1 + x · 1

(1 + x)4 + e x

1 + x · 2(1 + x) (1 + x)4 = e

x 1 + x ·

1 2x

(1 + x)4

si ha[X2]A(B(X)) = 1 2e

0 1 + 0 ·

1 2· 0 (1 + 0)4

= 1 2. Soluzione es. 7.5. Da 1

1 X = X1 n=0

Xnsi ottiene derivando che

1 (1 X)2 =

X1 n=0

Xn

!0

= X1 n=1

Xn

!0

= X1 n=1

nXn 1

(5)

Pertanto si ha

A(X) = X1 n=0

nXn= X· X1 n=1

nXn 1= X (1 X)2

Essendo poi1 + 2 + ... + n = (n + 1)n/2, la serieB(X)`e due volte la OGF della successione delle somme parziali di(n)ne pertanto

B(X) = X1 n=0

n(n + 1)Xn = 2

1 XA(X) = 2X (1 X)3

Soluzione es. 7.6. Si considerino gli insiemi IC = {8, 9, 10, 11, 12}, IR = {0, 1, 2, 3, 4},IG = IA={1, 2, 3, 4, ...},IS =N. Le OGF caratteristiche di questi insiemi sono

C(X) = X8+ X9+ X10+ X11+ X12= X8· (1 + X + X2+ X3+ X4) R(X) = 1+X +X2+X3+X4 G(X) = A(X) = X +X2+X3+... = X 1 X S(X) = 1 + X + X2+ X3+ ... = 1

1 X

Il numero di modi con cui `e possibile distribuire le 25 caramelle `e uguale al coefficiente diX25nel prodotto delle OGF caratteristiche:

[X25]C(X)· R(X) · G(X) · A(X) · S(X) = [X25]X10(1 X5)2 (1 X)5 =

= [X15]

1

(1 X)5

2X5

(1 X)5 + X10 (1 X)5

=

= [X15] 1

(1 X)5 2[X10] 1

(1 X)5+[X5] 1 (1 X)5 =

19 15

2

14 10

+

9 5

= 2 000 Soluzione es. 7.7. Si considerino gli insiemi IC = {2, 4, 6, 8, ...}, IZ =

{1, 3, 5, 7, ...}, IT = {5, 6, 7, 8, ...}. Le OGF caratteristiche di questi insiemi sono

C(X) = X2+X4+X6+X8+... = X2·(1+X2+X4+X6+...) = X2 1 1 X2 Z(X) = X + X3+ X5+ X7+ ... = X· (1 + X2+ X4+ X6+ ...) = X 1

1 X2 T (X) = X5+ X6+ X7+ X8+ ... = X5 1

1 X

(6)

Il numero di modi con cui `e possibile scegliere 15 frittelle `e uguale al coefficiente di X15nel prodotto delle OGF caratteristiche:

[X15]C(X)· Z(X) · T (X) = [X15] X8

(1 X)(1 X2)2 =

= [X7] 1

(1 X)(1 X2)2 = [X7] 1

(1 X)3(1 + X)2 Ora procediamo con la decomposizione in frazioni semplici:

1

(1 X)3(1 + X)2 = AX2+ BX + C

(1 X)3 +DX + E (1 + X)2 =

= (AX2+ BX + C)(1 + X)2+ (DX + E)(1 X)3 (1 X)3(1 + X)2 =

= (A D)X4+ (2A + B E + 3D)X3+ (A + 2B + C + 3E 3D)X2+ (B + 2C + D 3E)X + C + E (1 X)3(1 + X)2

da cui si ottiene il sistema lineare 8>

>>

><

>>

>>

:

A D = 0 2A + B E + 3D = 0 A + 2B + C + 3E 3D = 0 B + 2C + D 3E = 0 C + E = 1

che ha come soluzioniA = 3/16,B = 10/16,C = 11/16,D = 3/16,E = 5/16. Dunque

[X7] 1

(1 X)3(1 + X)2 = [X7] 0 B@

3

16X2 10

16X + 11 16 (1 X)3 +

3

16X + 5 16 (1 + X)2

1 CA=

= 3

16[X5] 1 (1 X)3

10

16[X6] 1

(1 X)3+11

16[X7] 1

(1 X)3+3

16[X6] 1

(1 + X)2+5

16[X7] 1 (1 + X)2 =

= 3 16

7 5

10

16

8 6

+11

16

9 7

+ 3

16

7 6

5

16

8 7

= 10

Soluzione es. 7.8. Essendo[X0]A(X) = 1 6= 0la serie formaleA(X)`e invertibile.

Si ha poi

A(X) = X1 n=0

2nXn = 1 + 2X 1 + 2X + 22X + ... = 1 + 2X · A(X) PertantoA(X)· (1 2X) = 1, ovveroA 1(X) = 1 2X.

(7)

Soluzione es. 7.9. Siano A(X) = X1

i=0

aiXi e B(X) = X1

i=0

biXi. Allora per ogni n2N si ha

[Xn](A(X) + B(X))0= [Xn](

X1 i=0

(ai+ bi)Xi)0 = (n + 1)(an+1+ bn+1) e

[Xn](A0(X)+B0(X)) = [Xn](

X1 i=1

iaiXi 1+ X1 k=1

kbkXk 1) = (n+1)an+1+(n+1)bn+1

Analogamente per ognin2N si ha

[Xn](A(X)B(X))0 = [Xn](

X1 i=0

( Xi j=0

ajbi j)Xi)0= (n + 1)

n+1X

j=0

ajbn+1 j

e

[Xn](A0(X)B(X) + A(X)B0(X)) =

= [Xn](

X1 i=1

iaiXi 1 X1 k=0

bkXk) + [Xn](

X1 i=0

aiXi X1 k=1

kbkXk 1) =

= [Xn] X1

`=0

( X` j=0

(j + 1)aj+1b` j)X`+ [Xn] X1

`=0

( X` j=0

aj(` j + 1)b` j+1)X` =

= Xn j=0

(j + 1)aj+1bn j+ Xn j=0

aj(n j + 1)bn j+1 =

=

n 1X

j=0

(j + 1)aj+1bn j+ (n + 1)an+1b0+ (n + 1)a0bn+1+

n 1X

j=0

aj+1(n j)bn j =

= (n+1)a0bn+1+

n 1X

j=0

aj+1bn j(j+1+n j)+(n+1)an+1b0= (n+1)

n+1X

j=0

ajbn+1 j

Soluzione es. 7.10. Essendo1 = [X0]Am(X) = ([X0]A(X))m, la serieA(X)ha come termine costante un numero realea0tale cheam0 = 1. Pertantoa0 = 1sem`e dispari, mentrea0 = ±1sem`e pari. Sia per assurdok > 0il pi`u piccolo naturale strettamente positivo tale che[Xk]A(X) = ak 6= 0. AlloraA(X) = a0+ Xk(ak+ ak+1X + ...). Pertanto, postoB(X) = ak+ ak+1X + ...si ha

0 = [Xk]Am(X) = [Xk](a0+ XkB(X))m=

= [Xk] Xm j=0

m j

aj0Xk(m j)Bm j(X) =

m

m 1

am 10 ak =±mak,

(8)

contro l’ipotesi cheak 6= 0. Veniamo alle radicim-esime di1 + X. La serie formale di Taylor-Maclaurin della funzione(1+x)1/m`e una radicem-esima di1+X. Sia ora Bm(X) = 1+X = Cm(X)conB(X), C(X)2R[[X]]. Essendo[X0]Bm(X) = 1alloraBm(X)`e invertibile. Allora

1 = (1 + X)(1 + X) 1= (Bm(X)) 1Cm(X) = (B 1(X)C(X))m; per quanto visto precedentemente si haB 1(X)C(X) = 1sem `e dispari, mentre B 1(X)C(X) =±1sem`e pari. PertantoB(X) = C(X)sem `e dispari, mentre B(X) =±C(X)sem`e pari.

Soluzione es. 7.11. Si ha A(X) =

X1 n=2

(n 1)Xn = X2 X1 n=2

(n 1)Xn 2= X2 X1 n=1

nXn 1=

= X2 X1 n=0

Xn

!0

= X2

1

1 X

0

= X2 (1 X)2 Soluzione es. 7.12. PostoA(X) =

X1 k=0

akXksi haA0(X) = X1 k=1

kakXk 1. Essendo g(x)forma chiusa di A0(X), per ognik 1si hakak = g(k 1)(0)

(k 1)! da cuiak = g(k 1)(0)

k! . Si conclude dal momento che0 = a0e f(k)(0) = g(k 1)(0)per ogni k 1.

Soluzione es. 7.13. Si tratta di calcolare

[X12](X + X2+ X3+ X4)5= [X12]X5

1 X4 1 X

5

=

= [X7] X5 k=0

5 k

( X4)k (1 X)5 =

= [X7]

✓✓5 0

5 1

X4

X1 n=0

4 + n n

Xn =

11 7

5

7 3

= 155 Soluzione es. 7.14. Una volta deciso come distribuire le caramelle all’anice, vi `e un

solo modo per distribuire le caramelle alla menta in modo che ogni bimbo abbia in tutto esattamente 3 caramelle. `E pertanto sufficiente calcolare in quanti modi `e possibile distribuire le caramelle all’anice. Si tratta di calcolare

[X10](1+X+X2+X3)10= [X10]

1 X4 1 X

10

= [X10](1 X4)10 1 (1 X)10 =

(9)

= [X10] X10 k=0

10 k

( X4)k 1 (1 X)10 =

=

10 0

◆ ✓19 10

10 1

◆ ✓15 6

+

10 2

◆ ✓11 2

= 44 803

Soluzione es. 7.15. Dobbiamo contare quante sono le collezioni di Pomodoro, Olio, Birra e Souvenir con sequenza di occupancy(mP, mO, mB, mS) dove mP 0, mO 2, 4  mB  7, mS = 1. Le OGF degli insiemi in cui variano mP, mO, mB, mSsono

P : 1 + X2+ X4+ ... = X1 k=0

(X2)k = 1 1 X2

O : X2+ X3+ X4+ ... = X2 X1 k=0

Xk = X2 1 X B : X4+ X5+ X6+ X7= X41 X4

1 X

S : X

Si tratta allora di calcolare il coefficiente diX11in 1

1 X2 X2

1 XX41 X4

1 X X = X7 1 1 X2

1 (1 X)2 Si ha

[X11]X7 1 1 X2

1 X4

(1 X)2 = [X4] 1 1 X2

1 X4 (1 X)2 =

= [X4](1+X2+X4)(1 X4)

✓✓1 0

+

2 1

X +

3 2

X2+

4 3

X3+

5 4

X4

=

=

5 4

+

3 2

+

1 0

1 0

= 8

Soluzione es. 7.16. Si tratta di contare il numero di 10-sequenze diI4con occupancy (f, v, t, p)dovef 2 2N,v2 2N+ 1,t 5ep 1. Queste corrispondono a

X10

10! cosh X· sinh X · (X5 5! +X6

6! + ...)· (1 + X 1!) =

=

X5 10!

1

4(e2X e 2X)(1 5! +X

6! + ...)(1 + X) =

=

X5 10!

1

2sinh(2X)(1 5!+ X

6! + ...)(1 + X) =

(10)

=

X5 10!

1 2

(2X +8X3

3! +32X5

5! )(1 + X)(1 5!+ X

6! + ...X5 10!)

=

=

X4 10!

(1 +4X2

3! +16X4

5! )(1 + X)(1 5!+X

6! + ...X4 9! )

=

=

X4 10!

(1 + X +4X2

3! +4X3

3! +16X4 5! )(1

5!+X 6! +X2

7! +X3 8! + X4

9! )

=

=

10!

9! +10!

8! + 4⇥ 10!

3!7! +4⇥ 10!

3!6! +16⇥ 10!

5!5!

= 10+90+480+3 360+4 032 = 7 972 Soluzione es. 7.17. Devo contare sequenze. Indico conEGFila EGF caratteristica di

quante volte pu`o essere ripetuta la cifrai. Abbiamo EGF7= 1 + X2

2! + X4

4! + ... = cosh X = eX+ e X 2 EGF9= X + X3

3! +X5

5! + ... = sinh X = eX e X 2 EGF5= X2

2!

EGF0,1,2,3,4,6,8= 1 + X +X2

2! + ... = eX Devo calcolare il coefficiente diX6/6!nel prodotto delle EGF.

X6 6!

e2X e 2X

4 e7XX2 2! =

= 1 8

X6

6! e9X e5X X2=

= 1 8

X4

6! e9X e5X = 6!

8⇥ 4! 94 54 = 22260

Se poi non voglio contare i numeri di 6 cifre che cominciano con lo 0, dovr`o togliere a 32640 i numeri che cominciano con uno zero seguito da 5 cifre con un numero pari di 7, un numero dispari di 9 e due 5. Questi sono

X5 5!

e2X e 2X

4 e7XX2 2! =

= 1 8

X3

5! e9X e5X = 5!

8⇥ 3! 93 53 = 1510 In tutto si hanno dunque22260 1510 = 20750.

(11)

Soluzione es. 7.18. Usiamo la formula

n 1X

k=1

km= 1 m + 1

Xm k=0

m + 1 k

Bknm+1 k. vista nell’Esempio 7.109. Si ha:

pern = 150em = 5: X149

k=1

k5= 1 6

X5 k=0

6 k

Bk1506 k

= 1 6

1506 1

2⇥ 6 ⇥ 1505+1

6⇥ 15 ⇥ 1504 1

30 ⇥ 15 ⇥ 1502+ 1 42

= 1 6

1506 3⇥ 1505+15

6 ⇥ 1504 1

2 ⇥ 1502+ 1 42

= 1 860 679 685 625.

pern = 300em = 7: X299

k=1

k7= 1 8

X8 k=0

8 k

Bk3008 k

= 1 8

3008 4⇥ 3007+28

6 ⇥ 3006 7

3 ⇥ 3004+2

3 ⇥ 3002 1 30

= 8092 325 247 637 507 500.

pern = 10000em = 3:

9999X

k=1

k3= 1 4

X4 k=0

4 k

Bk100004 k

= 1 4

100004 2⇥ 100003+ 100002 1 30

= 2 499 500 025 000 000.

Soluzione es. 7.19. Si riconosce il che la somma considerata `e il termine(m + n)- esimo del prodotto di convoluzione della successione

r k

k

con

s k

k

: per la Pro- posizione 7.16 si tratta del coefficiente (m + n)-esimo del prodotto delle relative OGF che sono, rispettivamente,(1 + X)re(1 + X)s. Ora

(1 + X)r(1 + X)s= (1 + X)r+s=X

k

r + s k

Xk

ed `e[Xm+n] (1 + X)r+s=

r + s m + n

, da cui segue l’identit`a (2.2).

Riferimenti

Documenti correlati

352 (Norme sui referendum previsti dalla Costituzione e sulla iniziativa legislativa del popolo) &#34;se prima della data dello svolgimento del referendum, la legge, o l'atto

Le Spese medie annue per ciascuna Categoria sono calcolate dividendo il totale delle spese delle qualifiche appartenenti alla categoria per le unità di riferimento (mensilità

137 Importo totale della retribuzione di risultato erogata a valere sul fondo dell'anno di rilevazione (euro) 177996 115 Importo totale della retribuzione di risultato non erogata

357 Importo del limite 2016 riferito alla presente macrocategoria come certificato dall'organo di controllo in sede di validazione del fondo/i dell'anno corrente (euro) 302928

179 Valore unitario su base annua della retribuzione di posizione previsto per la fascia meno elevata (euro) 161 Valore unitario su base annua della retribuzione di posizione

Nel caso di PL (Programmazione Lineare) allora se il problema di min- imizzazione ammette soluzione allora il punto di minimo globale si trova nella frontiera del poliedro

Le Spese medie annue per ciascuna Categoria sono calcolate dividendo il totale delle spese delle qualifiche appartenenti alla categoria per le unità di riferimento (mensilità

Si pu` o anche dire che il rango della matrice `e il massimo numero di righe o colonne linearmente indipendenti, o anche il massimo ordine dei minori non nulli della matrice