Domino in scatola

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Re: Domino in scatola

Messaggio da FrancescoVeneziano » 04 ott 2011, 16:50

Quello che intendevo è:
Trovi la ricorrenza, che per mia comodità adesso riscrivo come
$$C_{n+2}=2C_{n+1}+C_n+4\sum_{i=0}^{n} C_i,$$ che vale per ogni $n\geq 0$.
Definisci la funzione generatrice $$C(x)=\sum_{n\geq 0} C_n x^n.$$

Prendi la tua ricorrenza, la moltiplichi per $x^n$, e sommi su tutti gli n ottenendo
$\sum_{n\geq 0} C_{n+2} x^n=2\sum_{n\geq 0} C_{n+1} x^n+\sum_{n\geq 0} C_n x^n+4\sum_{n\geq 0} \sum_{i=0}^n C_i x^n$
Adesso osservi che
$\sum_{n\geq 0} C_{n+1} x^n = \frac{C(x)-1}{x}$
$\sum_{n\geq 0} C_{n+2} x^n = \frac{C(x)-1-2x}{x^2}$
$\sum_{n\geq 0} \sum_{i=0}^n C_i x^n = \frac{C(x)}{1-x}$
e quindi sostituendo nella relazione di prima ottieni
$$\frac{C(x)-1-2x}{x^2}=2 \frac{C(x)-1}{x} + C(x) + 4 \frac{C(x)}{1-x}.$$
Risolvi per $C(x)$ ed hai
$$C(x)=\frac{1-x}{x^3-3x^2-3x+1}=\frac{1-x}{(x+1)(x^2-4x+1)}.$$

Se chiami $\alpha_\pm=2\pm\sqrt{3}$ le due radici di $x^2-4x+1$, espandendo in frazioni parziali hai che
$$C(x)=\frac{\alpha_+}{6(1-\alpha_+ x)}+\frac{\alpha_-}{6(1-\alpha_- x)}+\frac{1}{3(1+x)}$$
e quindi, espandendo le tre serie geometriche sulla destra e confrontando con la definizione di $C(x)$,
$$C_n=\frac{\alpha_+^{n+1}+\alpha_-^{n+1}+2(-1)^n}{6}\sim \frac{\alpha_+^{n+1}}{6}.$$

Questo metodo è completamente automatico, trova e dimostra la formula chiusa, e non richiede grossi salti di immaginazione.

Chi vuole saperne di più può cercare Generatingfunctionology (lo trovate gratis e legalmente su internet) e studiarsi i primi capitoli.
Wir müssen wissen. Wir werden wissen.

stergiosss
Messaggi: 48
Iscritto il: 07 set 2011, 20:26

Re: Domino in scatola

Messaggio da stergiosss » 05 ott 2011, 10:33

fph ha scritto: Se vuoi una trattazione più completa, incluso cosa succede quando ci sono radici ripetute, guardati la lezione C3 del senior di un anno qualunque, il primo pezzo è sempre sulle successioni per ricorrenza.
Grazie, ma dove le posso trovare le lezioni del senior?
FrancescoVeneziano ha scritto:Questo metodo è completamente automatico, trova e dimostra la formula chiusa, e non richiede grossi salti di immaginazione.

Chi vuole saperne di più può cercare Generatingfunctionology (lo trovate gratis e legalmente su internet) e studiarsi i primi capitoli.
E grazie anche a te :wink: l'ho scaricato e ora provo a dargli un'occhiata.

Anche se nella tua spiegazione non mi è chiaro questo passaggio
FrancescoVeneziano ha scritto: $\sum_{n\geq 0} \sum_{i=0}^n C_i x^n = \frac{C(x)}{1-x}$
ma fa niente, penso di aver capito il ragionamento.


Grazie a entrambi per l'aiuto :)

fph
Site Admin
Messaggi: 3700
Iscritto il: 01 gen 1970, 01:00
Località: in giro
Contatta:

Re: Domino in scatola

Messaggio da fph » 05 ott 2011, 10:37

stergiosss ha scritto: Grazie, ma dove le posso trovare le lezioni del senior?
http://olimpiadi.dm.unibo.it/videoLezio ... r=Training

BTW, perdona, mi sono sbagliato, intendevo A3, non C3 (che non esiste). Vado a rieditare il vecchio messaggio per i posteri...
--federico
[tex]\frac1{\sqrt2}\bigl(\left|\text{loves me}\right\rangle+\left|\text{loves me not}\right\rangle\bigr)[/tex]

Avatar utente
FrancescoVeneziano
Site Admin
Messaggi: 601
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Re: Domino in scatola

Messaggio da FrancescoVeneziano » 05 ott 2011, 11:56

Lo vedi se espandi la serie geometrica di $1/(1-x)$ e svolgi il prodotto tra le serie
$$C(x)\frac{1}{1-x}=(1+2x+C_2x^2+C_3x^3+\cdots)(1+x+x^2+x^3+\cdots)=1+(1+2)x+(1+2+C_2)x^2+\cdots$$
Wir müssen wissen. Wir werden wissen.

stergiosss
Messaggi: 48
Iscritto il: 07 set 2011, 20:26

Re: Domino in scatola

Messaggio da stergiosss » 08 ott 2011, 15:27

fph ha scritto:
stergiosss ha scritto: Grazie, ma dove le posso trovare le lezioni del senior?
http://olimpiadi.dm.unibo.it/videoLezio ... r=Training

BTW, perdona, mi sono sbagliato, intendevo A3, non C3 (che non esiste). Vado a rieditare il vecchio messaggio per i posteri...

Gentilissimo grazie :) (lo ribadisco, questo smile mi fa schifo :D )

Grazie a entrambi per il materiale linkato, sto trovando molto interessante Generatingfunctionology e i video :wink:


Ora che ho appreso qualche nuova tecnica sono dell'idea che il metodo più "comodo" di risolvere questo problema fosse:
1) Trovare la ricorrenza per $C(n)$ come ho fatto nel primo post
2) Applicare il "trucco" suggerito da fph per trovare $S_n = 3S_{n-1}+3S_{n-2}-S_{n-3}$
3) Risolvere questa successione, e di conseguenza la $C(n)$, con le funzioni generatrici

Rispondi