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

Liczby Catalana $\displaystyle c_{n}$ spełniają zależność rekurencyjną:

$\displaystyle c_{n}=\sum _{k=1}^{n-1}c_{k}$ Źle

$\displaystyle c_{n}=\sum _{k=1}^{n}c_{k}$ Źle

$\displaystyle c_{n}=\sum _{k=1}^{n-1}c_{k}c_{n-k}$ Źle

$\displaystyle c_{n}=\sum _{k=1}^{n}c_{k-1}c_{n-k}$ Dobrze

$\displaystyle n$ -ta liczba Catalana to:

$\displaystyle {2n \choose n}$ Źle

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

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

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

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

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

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

$\displaystyle t_{10}\leq 2^{10}$ Źle

$\displaystyle t_{10}\geq 2^{9}$ Źle

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$ Źle

$\displaystyle 26$ Źle

$\displaystyle 35$ Dobrze

$\displaystyle 165$ Źle

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

$\displaystyle \prod _{k=1}^{\infty }{\frac {1}{1-x^{k}}}$ Dobrze

$\displaystyle \sum _{k=1}^{\infty }{\frac {1}{1-x^{k}}}$ Źle

$\displaystyle \sum _{n=0}^{\infty }\prod _{k=1}^{\infty }{\frac {1}{1-x^{nk}}}$ Źle

$\displaystyle \prod _{k=1}^{\infty }\sum _{n=0}^{\infty }x^{nk}$ Dobrze

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}}$ Dobrze

$\displaystyle s_{n}\!\left(x\right)=\prod _{k=0}^{n-1}\left(x+k\right)$ Dobrze

$\displaystyle s_{n}\!\left(x\right)=x^{\underline {n}}$ Źle

$\displaystyle s_{n}\!\left(x\right)=1/\prod _{k=0}^{n-1}\left(1-kx\right)$ Źle

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$ Źle

$\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$ Źle

$\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$ Dobrze

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

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$ Źle

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

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

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