Sottosequenze generalizzate

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Rispondi
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Sottosequenze generalizzate

Messaggio da Boll »

Generalizzazione del Problema 7 del Giornalino 17

Problema
Sia $ a_1,\dots, a_k $ una sequenza finita di interi non negativi. Diciamo che essa è alternante se è crescente e se numeri consecutivi hanno parità opposta (cioè si alternano numeri pari e dispari). Dato $ n\in\mathbb{N} $,trovare il numero $ A(n) $ delle sequenze alternantitali che $ a_i\le n $ per ogni $ i $

EDIT: what aveva perfettamente ragione
Ultima modifica di Boll il 24 apr 2005, 20:37, modificato 1 volta in totale.
Avatar utente
what
Messaggi: 158
Iscritto il: 01 gen 1970, 01:00
Località: roma

Re: Sottosequenze generalizzate

Messaggio da what »

Boll ha scritto:Problema
Sia $ a_1,\dots, a_k $ una sequenza finita di interi. Diciamo che essa è alternante se è crescente e se numeri consecutivi hanno parità opposta (cioè si alternano numeri pari e dispari). Dato $ n\in\mathbb{N} $,trovare il numero $ A(n) $ delle sequenze alternantitali che $ a_i\le n $ per ogni $ i $
Uhm... non capisco.
Consideriamo la successione
$ a_1=n-k+1 $
$ a_{i+1}=a_i+1 \textrm{ con } 1\leq i\leq k $.
Essa è alternante, ed inoltre $ a_i\leq n $ per ogni $ i $.
Se pongo $ b_i:=a_i-h $ con $ h $ intero positivo, allora anche la sequenza $ b_1,\dots,b_k $ è alternante e soddisfa le condizioni del problema.
Ma $ h $ può assumere infiniti valori, e quindi $ A(n) $ è sempre infinito...
Dove sbaglio?? :oops:
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Scusa what mancava un ipotesi... Hai perfettamente ragione, solo che nel Giornalino partendo da 1 non si ponevano il problema. Cambio il testo :D:P
Igor
Messaggi: 108
Iscritto il: 01 gen 1970, 01:00

Messaggio da Igor »

Per ogni n, definiamo :
P(n) :numero di sequenze alternanti valide(tali che $ a_i\leq n $ per ogni i) e tali che l’ultimo numero della sequenza sia pari
D(n) : numero di sequenze alternanti valide e tali che l’ultimo numero della sequenza sia dispari.
Quindi A(n) = P(n) + D(n).

Ora, se n è pari, avremo che:
P(n) = P(n-1)+D(n-1)+1, perché, alle sequenze P(n-1), si devono sommare quelle D(n-1), alle quali viene aggiunto n,ed aggiungere anche la sequenza composta solo da n.
D(n) = D(n-1)

Allo stesso modo, se n è dispari, avremo :
P(n) = P(n-1)
D(n) = P(n-1)+D(n-1)+1

Dimostriamo ora che A(n+2)=A(n+1)+A(n)+2

Se n è dispari:
P(n+1)=P(n)+D(n)+1 D(n+1)=D(n)
P(n+2)=P(n)+D(n)+1 D(n+2)=P(n+1)+D(n+1)+1=P(n)+2D(n)+2

A(n)=P(n)+D(n)
A(n+1)=P(n)+2D(n)+1
A(n+2)=2P(n)+3D(n)+3=A(n)+A(n+1)+2

Se n è pari:
P(n+1)=P(n) D(n+1) = P(n)+D(n)+1
P(n+2)=2P(n)+D(n)+2 D(n+1) = P(n)+D(n)+1

A(n)=P(n)+D(n)
A(n+1)=2P(n)+D(n)+1
A(n+2)=3P(n)+2D(n)+3=A(n)+A(n+1)+2

Quindi:
A(1)=3
A(2)=6
A(n)=A(n-1)+A(n-2)+2

Ora bisogna solo trovare la formula esplicita per A(n), che dovrebbe essere decisamente 'brutta'.Se la soluzione è giusta, magari faccio i conti e la scrivo.
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Pare proprio tutto perfetto, la mio soluzione era leggermente diversa... Riguardo alla formula è sicuramente una cosa tanto brutta quanto famosa ;)
Igor
Messaggi: 108
Iscritto il: 01 gen 1970, 01:00

Messaggio da Igor »

Beh, in effetti si tratta di una formula famosa.
Indicato con F(k) il k-esimo numero di Fibonacci, abbiamo che:

$ \begin{displaystyle}A(n)=F(n+4)-2=\frac{\left(\frac{1+\sqrt{5}}{2}\right)^{n+4}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+4}}{\sqrt{5}}-2\end{displaystyle} $
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Ezzi, 7 punti per Igor :D:D

La famosa formula di Binet, detta anche "se non vedi che funziona non ci credi"
Rispondi