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

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

$c_n=\sum _{k=1}^{n-1}{c}_k$ Źle

$c_n=\sum _{k=1}^n{c}_k$ Źle

$c_n=\sum _{k=1}^{n-1}{c}_k{c}_{n-k}$ Źle

$c_n=\sum _{k=1}^n{c}_{k-1}{c}_{n-k}$ Dobrze

$n$ -ta liczba Catalana to:

$(\genfrac{}{}{0ex}{}{2n}{n})$ Źle

$\frac{1}{n+1}(\genfrac{}{}{0ex}{}{2n}{n})$ Dobrze

$(\genfrac{}{}{0ex}{}{1/2}{n}){(-4)}^n$ Źle

$2(\genfrac{}{}{0ex}{}{1/2}{n+1}){(-4)}^n$ Dobrze

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

$t_{10}\le 2^{1023}$ Dobrze

$t_{10}\ge 2^{512}$ Dobrze

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

$t_{10}\ge 2^9$ Źle

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

$25$ Źle

$26$ Źle

$35$ Dobrze

$165$ Źle

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

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

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

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

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

Funkcja tworząca $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+\dots ,$ dla cyklowych liczb Stirlinga $\left[\begin{array}{c}n\\ m\end{array}\right]$ , ma postać zwartą:

$s_n\left(x\right)=x^{\bar{n}}$ Dobrze

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

$s_n\left(x\right)=x^{\underset{\_}{n}}$ Źle

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

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

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

$\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 $n>1,k>0$ Źle

$\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 $n>1,k>0$ Dobrze

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

Niech $a_0=1$ , $a_1=0$ oraz $a_n=\frac{a_{n-2}}{n}$ . Funkcja tworząca $A\left(x\right)=\sum _{n=0}^{\mathrm{\infty }}{a}_n{x}^n$ ma postać zwartą:

$A\left(x\right)=\sin x$ Źle

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

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

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