Matematyka dyskretna 1/Test 7: Funkcje tworzące

From Studia Informatyczne

Na ile sposobów można rozmienić \displaystyle 25 centów za pomocą monet \displaystyle 1 , \displaystyle 5 , \displaystyle 10 oraz \displaystyle 25 centowych?

\displaystyle 6

\displaystyle 12

\displaystyle 13

\displaystyle 49


Funkcja tworząca postaci \displaystyle G\!\left( x \right)=g_0+g_1x+g_2x^2+g_3x^3+\ldots ma odwrotną względem mnożenia (splotu), tzn. istnieje funkcja tworząca \displaystyle U\!\left( x \right) taka, że \displaystyle U\!\left( x \right)G\!\left( x \right)=1:

jeśli \displaystyle g_0\neq 1

jeśli \displaystyle g_0\neq 0

jeśli wszystkie \displaystyle g_i\neq0

wtedy i tylko wtedy, gdy \displaystyle g_0\neq0


Funkcja \displaystyle G\!\left( x \right) spełniająca \displaystyle G\!\left( x \right)=\left( \sum_{n=0}^{\infty}x^n \right)\cdot\left( 1+xG\!\left( x \right) \right) jest funkcją tworzącą:

ciągu \displaystyle 1,1,2,4,8,16,32,\ldots, 2^{n-1},\dots

ciągu geometrycznego \displaystyle g_n=2^n

nie ma takiego ciągu

nie istnieje taka funkcja tworząca


Funkcja \displaystyle G\!\left( x \right) spełniająca \displaystyle G\!\left( x \right)=G'\!\left( x \right) oraz \displaystyle G\!\left( 0 \right)=1 jest funkcją tworzącą ciągu:

\displaystyle g_n=\frac{1}{n}

\displaystyle g_n=\frac{1}{n!}

\displaystyle g_n=1

\displaystyle g_0=1 oraz \displaystyle g_n=0 dla \displaystyle n>1


Niech \displaystyle G\!\left( x \right)=\left( 1+x \right)^y , gdzie \displaystyle y jest liczba rzeczywistą. Jeśli \displaystyle G\!\left( x \right)=\sum_{n=0}^{\infty}g_n x^n , to:

\displaystyle g_n=\frac{\left( y+n \right)^{\underline{n}}}{n}

\displaystyle g_n=\frac{y^n}{n!}

\displaystyle g_n={ y+n \choose n }=\frac{\left( y+n \right)^{\underline{n}}}{n!}

\displaystyle g_n={ y \choose n }=\frac{y^{\underline{n}}}{n!}


Suma \displaystyle \sum_{k=0}^{n}\left( 3k^2-3k+1 \right) wynosi:

\displaystyle 2n^3+3n+n ,

\displaystyle n^3 ,

\displaystyle \left( 2n^3+3n+n \right)/{6} ,

\displaystyle 3n^3-3n^2+n


Niech \displaystyle a_0=2 , \displaystyle a_1=3 , \displaystyle a_2=5 , oraz \displaystyle a_{n+3}=7a_{n+2}-16a_{n+1}+12a_n . Wtedy:

\displaystyle a_n=\left( 1-n \right)2^n+3^n

\displaystyle a_n=\frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2} \right)^{n+3}-\left( \frac{1-\sqrt{5}}{2} \right)^{n+3} \right)

\displaystyle a_n=\frac{1}{\sqrt{5}}\left( \left( \frac{1+\sqrt{5}}{2} \right)^{n}-\left( \frac{1-\sqrt{5}}{2} \right)^{n} \right)

żadna z pozostałych odpowiedzi nie jest prawidłowa