Zadania - Matematyka Dyskretna

[Roghalik]

Otóż problem mam taki, że nie było mnie na tych lekcjach z powodu choroby i błądzę po internecie w poszukiwaniu informacji aczkolwiek i tak nie wiele rozumiem. Bardziej chciałbym poznać metode jak to rozwiązywać niż sam wynik. Gdyż są to zadania przykładowe i podobne się pojawią. Dacie mi jakieś skazówki a ja będę starał się to rozwiązywać. Pozdrawiam
1. Rozwiąż zależności rekurencyjne (podaj wzór lub regułą opisuj¡ca n-ty
wyraz bez użycia rekurencji):
\(\displaystyle{ a)a _{0} =1, a _{n} = \frac{3}{a _{n-1}}}\)
\(\displaystyle{ b) a _{1}=1, a _{n} =a _{n-1} +(-1) ^{n+1} *n}\)


2. Znajdź wzory na ciągi zadane równaniami rekurencyjnymi:

\(\displaystyle{ a)a _{1} =3, a _{n+1} =4a _{n} -5}\)
\(\displaystyle{ b)a _{0} = 2, a _{1} =5, a _{n+2} =3*a _{n+1} -2*a _{n}}\)
\(\displaystyle{ c)a _{0} = -2, a _{1} =6, a _{n+2}=6*a _{n+1} -9*a _{n}}\)








4. Na ile sposobów można przej±¢ najkrótszą drog¡ z dolnego lewego rogu
do prawego górnego rogu spaceruj¡c po siatce prostokąta o wymiarach
a) 2 na 3, b) 3 na 6, c) 4 na 5. Narysuj drog¦ odpowiadaj¡c¡ (odpowiednio
dla przypadków a) b) c)) zbiorom {1, 4}, {2, 4, 7}, {1, 5, 6, 8, 9}. Ile jest dróg
omijaj¡cych punkt (2, 3) dla przypadku b i c ?
5. Na ile sposobów można przejść najkrótszą drogą z dolnego, lewego, przedniego
rogu do prawego, górnego, tylnego rogu spaceruj¡c po siatce prostopadłościanu
o wymiarach 3 na 3 na 5 ?
6. Na ile sposobów można zapisać liczbę 7 jako sumę czterech liczb naturalnych?
Wa»na jest kolejno±¢ zapisu i zakładamy, »e zero jest liczb¡ naturalną
np 8 = 5 + 0 + 3 + 0. Jak rozwiązać zadanie jeżli przyjmiemy, »e zero nie jest
liczb¡ naturalną ? (Wsk. od każdego składnika sumy odejmij jeden).
7. Ile jest liczb podzielnych przez
(a) 2, 5, 7 w±ród liczb od 1 do 111 ? (b) 2, 3, 7 w±ród liczb od 37 do 222 ?
8. Ile jest liczb mniejszych od 500 zawieraj¡cych w zapisie cyfr¦ 4 ?
9. Oblicz ile jest totalnych nieporządków (tzn »adna liczba nie jest na swoim
miejscu) na zbiorze {1, 2, 3, 4, 5}.

[miodzio1988]

W pierwszym zacznij działać rekurencją i w ten sposób będziemy szukac rów rekurencyjnego

2 równanie charakterystyczne, znajdziesz topic na forum

Najpierw te zadania zrob

[Mariusz M]

1. b)
2.
Funkcje tworzące będą lepszym pomysłem

\(\displaystyle{ a)
a _{1} =3, a _{n+1} =4a _{n} -5\\
A\left( x\right)= \sum_{n=1}^{ \infty }{a_{n}x^{n}} \\
a_{n}=4a_{n-1} -5\\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}=\sum_{n=2}^{ \infty }{4a_{n-1}x^{n}}+ \sum_{n=2}^{ \infty }{-5x^n} \\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}=4x\sum_{n=2}^{ \infty }{4a_{n-1}x^{n-1}}- \frac{5x^2}{1-x} \\
\sum_{n=1}^{ \infty }{a_{n}x^{n}}-3x=4x\sum_{n=1}^{ \infty }{4a_{n}x^{n}}- \frac{5x^2}{1-x} \\
A\left( x\right)-3x=4xA\left( x\right) -\frac{5x^2}{1-x}\\
A\left( x\right)-4xA\left( x\right)=3x-\frac{5x^2}{1-x}\\
A\left( x\right)\left( 1-4x\right)=\frac{3x-8x^2}{1-x}\\
A\left( x\right)=\frac{3x-8x^2}{\left( 1-4x\right)\left( 1-x\right) } \\
\frac{3x-8x^2}{\left( 1-4x\right)\left( 1-x\right) }=\frac{Ax}{1-4x}+\frac{Bx}{1-x}\\
Ax\left( 1-x\right)+Bx\left( 1-4x\right)=x\left( 3-8x\right)\\
A-Ax+B-4Bx=3-8x\\
\begin{cases} A+B=3 \\ -A-4B=-8 \end{cases} \\
\begin{cases} A=3-B \\ 3B=5 \end{cases}\\
\begin{cases} 3A=9-3B \\ 3B=5 \end{cases}\\
\begin{cases} 3A=4 \\ 3B=5 \end{cases}\\
A\left( x\right)= \frac{1}{3} \cdot \frac{4x}{1-4x}+\frac{5}{3} \cdot \frac{x}{1-x}\\
A\left( x\right)= \frac{1}{3}\left( \sum_{n=1}^{ \infty }{4^nx^n} \right)+\frac{5}{3}\left( \sum_{n=1}^{ \infty }{x^n} \right) \\
a_{n}=\frac{1}{3} \cdot 4^n+\frac{5}{3}}\)
\(\displaystyle{ b)
a _{0} = 2, a _{1} =5, a _{n+2} =3*a _{n+1} -2*a _{n}\\
a_{n}=3a_{n-1}-2a_{n-2}\\
A\left( x\right)= \sum_{n=0}^{ \infty }{a_{n}x^{n}}\\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}= \sum_{n=2}^{ \infty }{3a_{n-1}x^n}+ \sum_{n=2}^{ \infty }{-2a_{n-2}x^{n}}\\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}= 3x\sum_{n=2}^{ \infty }{a_{n-1}x^{n-1}}-2x^2 \sum_{n=2}^{ \infty }{a_{n-2}x^{n-2}}\\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}= 3x\sum_{n=1}^{ \infty }{a_{n}x^{n}}-2x^2 \sum_{n=0}^{ \infty }{a_{n}x^{n}}\\
\sum_{n=0}^{ \infty }{a_{n}x^{n}}-5x-2= 3x\left(\sum_{n=0}^{ \infty }{a_{n}x^{n}}-2\right)-2x^2 \sum_{n=0}^{ \infty }{a_{n}x^{n}}\\
A\left( x\right)-5x-2=3x\left( A\left( x\right)-2 \right)-2x^2A\left( x\right) \\
A\left( x\right)-5x-2=3xA\left( x\right)-6x-2x^2A\left( x\right) \\
A\left( x\right)=3xA\left( x\right)-x+2-2x^2A\left( x\right) \\
A\left( x\right)-3xA\left( x\right)+2x^2A\left( x\right)=-x+2\\
A\left( x\right)\left( 1-3x+2x^2\right)=-x+2\\
A\left( x\right)=\frac{-x+2}{\left( 1-2x\right)\left( 1-x\right) }\\
\frac{-x+2}{\left( 1-2x\right)\left( 1-x\right) }=\frac{A}{1-2x}+\frac{B}{1-x} \\
A\left( 1-x\right)+B\left( 1-2x\right)=-x+2\\
A-Ax+B-2Bx=-x+2\\
\begin{cases} -A-2B=-1 \\ A+B=2 \end{cases} \\
\begin{cases} B=-1 \\ A=3 \end{cases} \\
A\left( x\right)=\frac{3}{1-2x}- \frac{1}{1-x} \\
A\left( x\right)=3\left( \sum_{n=0}^{ \infty }{2^nx^n} \right) -\left( \sum_{n=0}^{ \infty } {x^n}\right) \\
a_{n}=3 \cdot 2^n-1\\}\)

\(\displaystyle{ a)a _{0} =1, a _{n} = \frac{3}{a _{n-1}}\\
a_{0}=1\\
a_{1}=\frac{3}{1}=3\\
a_{2}=\frac{3}{3}=1\\}\)

Równoważne równanie rekurencyjne

\(\displaystyle{ \begin{cases} a_{0}=1\\a_{1}=3 \\ a_{n}=a_{n-2} \end{cases}}\)
i teraz stosując funkcję tworzącą można otrzymać wzór jawny

\(\displaystyle{ \begin{cases} a_{0}=1\\a_{1}=3 \\ a_{n}=a_{n-2} \end{cases}\\
A\left( x\right)=\sum_{n=0}^{ \infty }{a_{n}x^{n}}\\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}=\sum_{n=2}^{ \infty }{a_{n-2}x^{n}}\\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}=x^2\sum_{n=2}^{ \infty }{a_{n-2}x^{n-2}}\\
\sum_{n=2}^{ \infty }{a_{n}x^{n}}=x^2\sum_{n=0}^{ \infty }{a_{n}x^{n}}\\
\sum_{n=0}^{ \infty }{a_{n}x^{n}}-3x-1=x^2\sum_{n=0}^{ \infty }{a_{n}x^{n}}\\
A\left( x\right) -3x-1=x^2A\left( x\right)\\
A\left( x\right)-x^2A\left( x\right)=3x+1\\
A\left( x\right)\left( 1-x^2\right)=3x+1\\
A\left( x\right)=\frac{3x+1}{1-x^2}\\
A\left( x\right)=\frac{2\left( 1+x\right)-\left( 1-x\right) }{\left( 1-x\right)\left( 1+x\right) } \\
A\left( x\right) =\frac{2}{1-x}-\frac{1}{1+x}\\
A\left( x\right)=2\left( \sum_{n=0}^{ \infty } {x^n}\right) -\left( \sum_{n=0}^{ \infty }{\left( -1\right)^{n}x^{n} } \right) \\
a_{n}=2-\left( -1\right)^{n}}\)

[a4karo]

Ad 1. po prostu wypisz sobie kilka początkowych wyrazów i zaobserwuj prawidłowość. Stąd łatwo wydedukujesz wzór.