Sequenze di elementi

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Sequenze di elementi

Messaggio da Hawk » 24 set 2012, 19:14

Trovare $ f(n) $, cioè il numero di sequenze di $ n $ elementi dall'insieme $ A=\{0,1,2\} $ in modo tale che non vi siano due $ 0 $ vicini.
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »

spugna
Messaggi: 421
Iscritto il: 19 mar 2009, 22:18
Località: Forlì

Re: Sequenze di elementi

Messaggio da spugna » 27 set 2012, 21:31

Sia $S_n$ l'insieme delle sequenze di $n$ elementi che soddisfano l'ipotesi (tanto per intenderci abbiamo $f(n)=|S_n|$) e $g(n)$ il numero di sequenze appartenenti a $S_n$ che non iniziano con uno $0$
Detto questo, una sequenza appartenente a $S_n$ può:
-iniziare con $0$ ed essere seguita da una sequenza di $S_{n-1}$ che non inizia con $0$;
-iniziare con $1$ o $2$ ed essere seguita da una qualunque sequenza di $S_{n-1}$.

Da queste due osservazioni ricaviamo $f(n)=g(n-1)+2f(n-1)$ e dalla seconda $g(n)=2f(n-1)$: per sostituzione segue immediatamente $f(n)=2f(n-1)+2f(n-2)$
Per trovare la formula generale dobbiamo risolvere l'equazione $x^2-2x-2=0$, che ci dà $x=1 \pm \sqrt{3}$, per cui si ha $f(n)=a(1+\sqrt{3})^n+b(1-\sqrt{3})^n$
A questo punto si impone $f(1)=3$ e $f(2)=8$ (valori che si trovano in modo quasi banale): abbiamo così un sistema di equazioni che ha come soluzione $a=\dfrac{3+2 \sqrt{3}}{6}$ e $b=\dfrac{3-2 \sqrt{3}}{6}$
"Bene, ora dobbiamo massimizzare [tex]\dfrac{x}{(x+100)^2}[/tex]: come possiamo farlo senza le derivate? Beh insomma, in zero fa zero... a $+\infty$ tende a zero... e il massimo? Potrebbe essere, che so, in $10^{24}$? Chiaramente no... E in $10^{-3}$? Nemmeno... Insomma, nella frazione c'è solo il numero $100$, quindi dove volete che sia il massimo se non in $x=100$..?" (da leggere con risatine perfide e irrisorie in corrispondenza dei puntini di sospensione)

Maledetti fisici! (cit.)

Hawk
Messaggi: 306
Iscritto il: 20 mag 2010, 19:16
Località: Roma

Re: Sequenze di elementi

Messaggio da Hawk » 30 set 2012, 19:14

Ecco, puoi spiegarmi come ricavi l'equazione?
« Due cose hanno soddisfatto la mia mente con nuova e crescente ammirazione e soggezione e hanno occupato persistentemente il mio pensiero: il cielo stellato sopra di me e la legge morale dentro di me. »

spugna
Messaggi: 421
Iscritto il: 19 mar 2009, 22:18
Località: Forlì

Re: Sequenze di elementi

Messaggio da spugna » 30 set 2012, 23:48

Hawk ha scritto:Ecco, puoi spiegarmi come ricavi l'equazione?
Non so quanto sia noto questo fatto: data una successione $a_1,a_2,a_3,...$ tale che $a_{n+1}=ha_n+ka_{n-1}$ dove $h$ e $k$ sono due costanti, esistono $\alpha,\beta,p,q$ tali che

$a_n=\alpha p^n+\beta q^n$ $\forall n \in \mathbb{N}^+$

Infatti sostituendo nella formula ricorsiva si ha

$\alpha p^{n-1} \cdot p^2+\beta q^{n-1} \cdot q^2=h(\alpha p^{n-1} \cdot p+\beta q^{n-1} \cdot q)+k(\alpha p^{n-1}+\beta q^{n-1})$

Ora si porta tutto al primo membro:

$\alpha p^{n-1}(p^2-hp-k)+\beta q^{n-1}(q^2-hq-k)=0$

A questo punto basta imporre che $p$ e $q$ siano le soluzioni dell'equazione $x^2-hx-k=0$ (nel nostro caso $h=k=2$)
"Bene, ora dobbiamo massimizzare [tex]\dfrac{x}{(x+100)^2}[/tex]: come possiamo farlo senza le derivate? Beh insomma, in zero fa zero... a $+\infty$ tende a zero... e il massimo? Potrebbe essere, che so, in $10^{24}$? Chiaramente no... E in $10^{-3}$? Nemmeno... Insomma, nella frazione c'è solo il numero $100$, quindi dove volete che sia il massimo se non in $x=100$..?" (da leggere con risatine perfide e irrisorie in corrispondenza dei puntini di sospensione)

Maledetti fisici! (cit.)

Rispondi