Funzione generatrice successione di Catalan
Ciao a tutti!
Ho un problema nel calcolare la funzione generatrice della successione di Catalan.
Ho provato a seguire un procedimento analogo a quello per la funzione generatrice della successione di Fibonacci.
Partendo da $ C_{n}=sum_(i = 0)^(n-1)C_{i}C_{n-1-i} $ e dalla definizione di funzione generatrice $ f=sum_(n = 0)^(oo)a_{n}x^{n} $ sono arrivato ad ottenere $ f=c_{0}+c_{1}x+sum_(n = 2)^(oo)(sum_(i = 0)^(n-1)C_{i}C_{n-1-i})x^{n} $ e qui mi pianto.
Con Fibonacci riuscivo a trasformare la sommatoria da 2 a infinito in modo da ottenere nuovamente $ f $ e poi raccogliere.
Qui non so come fare.
Qualcuno può aiutarmi?
Ho un problema nel calcolare la funzione generatrice della successione di Catalan.
Ho provato a seguire un procedimento analogo a quello per la funzione generatrice della successione di Fibonacci.
Partendo da $ C_{n}=sum_(i = 0)^(n-1)C_{i}C_{n-1-i} $ e dalla definizione di funzione generatrice $ f=sum_(n = 0)^(oo)a_{n}x^{n} $ sono arrivato ad ottenere $ f=c_{0}+c_{1}x+sum_(n = 2)^(oo)(sum_(i = 0)^(n-1)C_{i}C_{n-1-i})x^{n} $ e qui mi pianto.
Con Fibonacci riuscivo a trasformare la sommatoria da 2 a infinito in modo da ottenere nuovamente $ f $ e poi raccogliere.
Qui non so come fare.
Qualcuno può aiutarmi?
Risposte
Dunque, dalla letteratura la formula chiusa della successione è:
[tex]\displaystyle C_n=\frac{1}{n+1} \binom{2n}{n}[/tex]
da questo però non ho molte idee su come ricavarla... sto cercando e se riesco ti posto qualche link che ti possa aiutare.
[tex]\displaystyle C_n=\frac{1}{n+1} \binom{2n}{n}[/tex]
da questo però non ho molte idee su come ricavarla... sto cercando e se riesco ti posto qualche link che ti possa aiutare.
Si la formula chiusa la conosco.
Io devo arrivare ad ottenere come funzione generatrice della successione di Catalan la funzione $ frac{1-sqrt(1-4x) }{2x} $ ma non so come arrivarci.
Io devo arrivare ad ottenere come funzione generatrice della successione di Catalan la funzione $ frac{1-sqrt(1-4x) }{2x} $ ma non so come arrivarci.
Diciamo che tutto parte da:
[tex]\displaystyle \frac{C_{n+1}}{C_n} = \frac{2(2n+1)}{n+2}[/tex]
e quindi basta osservare che [tex]C_0=1[/tex] e che:
[tex]\displaystyle C_{n+1} = \prod_{k=0}^n \frac{2(2k+1)}{k+2} = \frac{2^{n+1}}{(n+2)!} \prod_{k=0}^n (2k+1)[/tex]
qui i dettagli non li ricordo ancora troppo bene!
[tex]\displaystyle \frac{C_{n+1}}{C_n} = \frac{2(2n+1)}{n+2}[/tex]
e quindi basta osservare che [tex]C_0=1[/tex] e che:
[tex]\displaystyle C_{n+1} = \prod_{k=0}^n \frac{2(2k+1)}{k+2} = \frac{2^{n+1}}{(n+2)!} \prod_{k=0}^n (2k+1)[/tex]
qui i dettagli non li ricordo ancora troppo bene!
Boh ho provato a fare un po di calcoli usando le varie definizioni di $C_{n}$ tramite ricorrenze che ho trovato... niente non riesco ad arrivare a quella funzione.
"Lord K":
Diciamo che tutto parte da:
[tex]\displaystyle \frac{C_{n+1}}{C_n} = \frac{2(2n+1)}{n+2}[/tex]
e quindi basta osservare che [tex]C_0=1[/tex] e che:
[tex]\displaystyle C_{n+1} = \prod_{k=0}^n \frac{2(2k+1)}{k+2} = \frac{2^{n+1}}{(n+2)!} \prod_{k=0}^n (2k+1)[/tex]
qui i dettagli non li ricordo ancora troppo bene!
Questa formula, trovata su mathworld, non mi sembra molto corretta però... se calcoliamo [tex]C_2[/tex] viene [tex]\frac{5}{2}[/tex]....
Meglio pensarci un poco più approfonditamente....
No, in realtà funziona:
Se calcoliamo $C_{2}$ abbiamo che $n=1$ quindi si ha $C_{2}=prod_{k=0}^{1}=frac{2}{2}*frac{2*3}{3}=2$
comunque non mi aiuta ad arrivare alla funzione generatrice
Se calcoliamo $C_{2}$ abbiamo che $n=1$ quindi si ha $C_{2}=prod_{k=0}^{1}=frac{2}{2}*frac{2*3}{3}=2$
comunque non mi aiuta ad arrivare alla funzione generatrice
[tex]\displaystyle C_n = \prod_{k=0}^n \frac{2(2n-1)}{n+1} = \frac{2^{n+1}}{(n+1)!}\prod_{k=0}^n(2k-1) =\frac{2^{n+1}}{(n+1)!}\frac{(2n-1)!}{2^{n}(n-1)!} =\frac{2^{n+1}}{(n+1)!}\frac{(2n)(2n-1)!}{2^{n}(n-1)!(2n)} = \frac{1}{n+1}\binom{2n}{n}[/tex]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo