Matematyka dyskretna 1/Test 8: Funkcje tworzące w zliczaniu obiektów kombinatorycznych

From Studia Informatyczne

Liczby Catalana \displaystyle c_n spełniają zależność rekurencyjną:

\displaystyle c_n =\sum_{k=1}^{n-1} c_{k}

\displaystyle c_n =\sum_{k=1}^{n} c_{k}

\displaystyle c_n =\sum_{k=1}^{n-1} c_{k} c_{n-k}

\displaystyle c_n =\sum_{k=1}^{n} c_{k-1} c_{n-k}


\displaystyle n -ta liczba Catalana to:

\displaystyle {2n \choose n}

\displaystyle \frac{1}{n+1}{2n \choose n}

\displaystyle {1/2 \choose n}\left( -4 \right)^n

\displaystyle 2{1/2 \choose n+1}\left( -4 \right)^n


Niech \displaystyle t_{10} będzie liczbą drzew o wysokości \displaystyle 10 . Wtedy:

\displaystyle t_{10}\leq 2^{1023}

\displaystyle t_{10}\geq 2^{512}

\displaystyle t_{10}\leq 2^{10}

\displaystyle t_{10}\geq 2^{9}


Liczba podziałów liczby \displaystyle 16 na sumy złożone jedynie ze składników \displaystyle 1,2,4,8,16 wynosi:

\displaystyle 25

\displaystyle 26

\displaystyle 35

\displaystyle 165


Funkcja tworząca podziału liczby na sumy jest przedstawialna jako:

\displaystyle \prod_{k=1}^{\infty}\frac{1}{1-x^k}

\displaystyle \sum_{k=1}^{\infty}\frac{1}{1-x^k}

\displaystyle \sum_{n=0}^{\infty}\prod_{k=1}^{\infty}\frac{1}{1-x^{nk}}

\displaystyle \prod_{k=1}^{\infty}\sum_{n=0}^{\infty}x^{nk}


Funkcja tworząca \displaystyle s_n\!\left( x \right)=\left[\begin{array} {c}n\\ 0\end{array} \right]+\left[\begin{array} {c}n\\ 1\end{array} \right]x+\left[\begin{array} {c}n\\ 2\end{array} \right]x^2+\left[\begin{array} {c}n\\ 3\end{array} \right]x^3+\ldots, dla cyklowych liczb Stirlinga \displaystyle \left[\begin{array} {c}n\\ m\end{array} \right] , ma postać zwartą:

\displaystyle s_n\!\left( x \right)=x^{\overline{n}}

\displaystyle s_n\!\left( x \right)=\prod_{k=0}^{n-1}\left( x+k \right)

\displaystyle s_n\!\left( x \right)=x^{\underline{n}}

\displaystyle s_n\!\left( x \right)=1/\prod_{k=0}^{n-1}\left( 1-kx \right)


Podziałowe liczby Stirlinga spełniają zależność rekurencyjną:}

\displaystyle \left\{\begin{array} {c}n\\ k\end{array} \right\}=\left( n-1 \right)\left\{\begin{array} {c}n-1\\ k\end{array} \right\}+\left\{\begin{array} {c}n-1\\ k-1\end{array} \right\} , dla \displaystyle 0>k>n

\displaystyle \left\{\begin{array} {c}n+k\\ k\end{array} \right\}=\left\{\begin{array} {c}n+k-1\\ k\end{array} \right\}+k\left\{\begin{array} {c}n+k-1\\ k-1\end{array} \right\} , dla \displaystyle n>1,\ k>0

\displaystyle \left\{\begin{array} {c}n+k\\ k\end{array} \right\}=k\left\{\begin{array} {c}n+k-1\\ k\end{array} \right\}+\left\{\begin{array} {c}n+k-1\\ k-1\end{array} \right\} , dla \displaystyle n>1,\ k>0

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


Niech \displaystyle a_0=1 , \displaystyle a_1=0 oraz \displaystyle a_n=\frac{a_{n-2}}{n} . Funkcja tworząca \displaystyle A\!\left( x \right)=\sum_{n=0}^{\infty}a_n x^n ma postać zwartą:

\displaystyle A\!\left( x \right)=\sin x

\displaystyle A\!\left( x \right)=e^{x^2}

\displaystyle A\!\left( x \right)=e^{x^2/2}

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