Witam,
Pełna treść zadania: Ile jest wyrazów złożonych z n liter należących do 25-literowego alfabetu łacińskiego, zawierających parzystą liczbę liter a?
Do czego doszedłem:
\(\displaystyle{ a_{0}=1\\
a_{1}=24\\
a_{n+1}=24 \cdot a_{n}}\)
To jest jeżeli chcę dodać 1 literę (nie a), ale nie wiem co zrobić, jeżeli chciałbym dodać 1 literę 'a' do zbioru, w którym występuje nieparzysta liczba liter.
Ile jest wyrazów n-literowych z parzystą liczbą a
Ile jest wyrazów n-literowych z parzystą liczbą a
Ostatnio zmieniony 8 sty 2012, o 18:08 przez Anonymous, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
abc666
Ile jest wyrazów n-literowych z parzystą liczbą a
Oznaczmy sobie przez \(\displaystyle{ a_{n}}\) liczbę słów \(\displaystyle{ n}\)-literowych o parzystej liczbie liter \(\displaystyle{ a}\). Przez \(\displaystyle{ b_{n}}\) analogicznie, ale o nieparzystej liczbie a. Teraz dostawiamy z prawej strony kolejne literki
\(\displaystyle{ a_{n}=b_{n-1}+24\cdot a_{n-1}}\)
możemy albo dostawić literkę \(\displaystyle{ a}\) ciągu z nieparzystą liczbą \(\displaystyle{ a}\), lub jedną z \(\displaystyle{ 24}\) pozostałych literek do tego z parzystą.
Analogicznie
\(\displaystyle{ b_{n}=24\cdot b_{n-1}+a_{n-1}}\)
Teraz pomnóżmy pierwsze równanie przez \(\displaystyle{ 24}\) dostaniemy
\(\displaystyle{ 24a_{n}=24b_{n-1}+576a_{n-1}\\
b_{n}=24\cdot b_{n-1}+a_{n-1}}\)
odejmujemy stronami i mamy
\(\displaystyle{ 24a_{n}-b_{n}=575a_{n-1}}\)
skąd
\(\displaystyle{ b_{n}=24a_{n}-575a_{n-1}}\)
podstawiamy to do pierwszej równości i mamy
\(\displaystyle{ a_{n}=24a_{n-1}-575a_{n-2}+24a_{n-1}=48a_{n-1}-575a_{n-2}}\)
Oraz
\(\displaystyle{ a_{0}=1\\
a_{1}=24}\)
Teraz wystarczy rozwiązać tą rekurencję np. z wykorzystaniem r. charakterystycznych.
\(\displaystyle{ a_{n}=b_{n-1}+24\cdot a_{n-1}}\)
możemy albo dostawić literkę \(\displaystyle{ a}\) ciągu z nieparzystą liczbą \(\displaystyle{ a}\), lub jedną z \(\displaystyle{ 24}\) pozostałych literek do tego z parzystą.
Analogicznie
\(\displaystyle{ b_{n}=24\cdot b_{n-1}+a_{n-1}}\)
Teraz pomnóżmy pierwsze równanie przez \(\displaystyle{ 24}\) dostaniemy
\(\displaystyle{ 24a_{n}=24b_{n-1}+576a_{n-1}\\
b_{n}=24\cdot b_{n-1}+a_{n-1}}\)
odejmujemy stronami i mamy
\(\displaystyle{ 24a_{n}-b_{n}=575a_{n-1}}\)
skąd
\(\displaystyle{ b_{n}=24a_{n}-575a_{n-1}}\)
podstawiamy to do pierwszej równości i mamy
\(\displaystyle{ a_{n}=24a_{n-1}-575a_{n-2}+24a_{n-1}=48a_{n-1}-575a_{n-2}}\)
Oraz
\(\displaystyle{ a_{0}=1\\
a_{1}=24}\)
Teraz wystarczy rozwiązać tą rekurencję np. z wykorzystaniem r. charakterystycznych.