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
Sottosequenze generalizzate
Sottosequenze generalizzate
Ultima modifica di Boll il 24 apr 2005, 20:37, modificato 1 volta in totale.
Re: Sottosequenze generalizzate
Uhm... non capisco.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 $
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??
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.
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.