Matematyka dyskretna 1/Test 6: Permutacje i podziały

From Studia Informatyczne

Niech \displaystyle n_{\pi},n_{\sigma},n_{\rho} będą kolejno liczbami permutacji w \displaystyle S_7 tego samego typu co, odpowiednio, \displaystyle \pi=(14)(26)(357), \displaystyle \sigma=(1357)(246), \displaystyle \rho=(12)(34)(56)(7). Wtedy:

\displaystyle n_{\pi}\leqslant n_{\rho}\leqslant n_{\sigma}

\displaystyle n_{\sigma}\leqslant n_{\pi}\leqslant n_{\rho}

\displaystyle n_{\rho}\leqslant n_{\pi}\leqslant n_{\sigma}

\displaystyle n_{\pi}\leqslant n_{\sigma}\leqslant n_{\rho}

Dla sprzężonych permutacji \displaystyle \pi,\sigma\in S_{13} zachodzi:

\displaystyle \pi i \displaystyle \sigma mają tyle samo cykli \displaystyle 4-elementowych

elementy \displaystyle 1 i \displaystyle 2 albo są w tym samym cyklu w obu permutacjach, albo nie są w tym samym cyklu w obu permutacjach

\displaystyle \pi i \displaystyle \sigma mają ten sam typ

\displaystyle \pi i \displaystyle \sigma mają ten sam znak

Dla \displaystyle n\geqslant 2, podziałowa liczba Stirlinga \displaystyle \left\{\begin{array} {c}n\\ 2\end{array} \right\} wynosi:

\displaystyle \sum_{k=1}^{n-1}{n\choose k}k!=\sum_{k=1}^{n-1}\frac{n!}{k!}

\displaystyle n!\sum_{k=1}^{n-1}\frac{1}{k(n-k)}

\displaystyle n!\sum_{k=1}^{n-1}\frac{1}{k(n-k)}

\displaystyle \frac{n!}{2}\sum_{k=1}^{n-1}\frac{1}{k(n-k)}

Średnia liczba cykli permutacji \displaystyle n-elementowej (czyli stosunek sumarycznej liczby cykli we wszystkich permutacjach \displaystyle n-elementowych do liczby cykli \displaystyle n-elementowych) to:

\displaystyle 2n

\displaystyle \left\lfloor \frac{n}{\lg{n}} \right\rfloor+1

\displaystyle \sum_{k=1}^n \frac{1}{k}

\displaystyle \frac{n}{2}

Podziałowa liczba Stirlinga\displaystyle \left\{\begin{array} {c}7\\ 4\end{array} \right\} wynosi:

\displaystyle 90

\displaystyle 140

\displaystyle 301

\displaystyle 350

Jednomian \displaystyle x^n jest równy:

\displaystyle \sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}x^{\underline{i}}

\displaystyle B_nx^{\underline{n}}, gdzie \displaystyle B_n jest \displaystyle n-tą liczbą Bella

\displaystyle \sum_i\left[\begin{array} {c}n\\ i\end{array} \right]x^{\overline{i}}

\displaystyle \sum_i\left\{\begin{array} {c}n\\ i\end{array} \right\}(-1)^{n-i}x^{\overline{i}}

Na ile sposobów można rozłożyć \displaystyle a rozróżnialnych obiektów do dokładnie \displaystyle b rozróżnialnych szuflad, tak by każda szufladka była niepusta?

\displaystyle b^a

\displaystyle \left\{\begin{array} {c}a\\ b\end{array} \right\}

\displaystyle b!\left\{\begin{array} {c}a\\ b\end{array} \right\}

\displaystyle {a-1\choose b-1}

Na ile sposobów można rozłożyć \displaystyle a nierozróżnialnych obiektów do co najwyżej \displaystyle b rozróżnialnych szuflad?

\displaystyle {a-1\choose b-1}

\displaystyle {b+a-1\choose b-1}

\displaystyle \left\{\begin{array} {c}a\\ b\end{array} \right\}

\displaystyle \sum_{i=1}^b\left\{\begin{array} {c}a\\ i\end{array} \right\}

Gdy \displaystyle P(n,k) jest liczbą rozkładów liczby \displaystyle n na sumy dokładnie \displaystyle k nieujemnych całkowitych składników, to \displaystyle \lim_{n\rightarrow\infty}\frac{P(n,k)}{n^k} wynosi:

\displaystyle 0

\displaystyle \frac{1}{k!(k-1)!}

\displaystyle \frac{1}{k}

\displaystyle 1

Na ile sposobów można podzielić zbiór \displaystyle a elementowy na \displaystyle b+c bloków, przy czym \displaystyle b bloków jest wyróżnionych?

\displaystyle \left\{\begin{array} {c}a\\ b+c\end{array} \right\}{b+c\choose b}

\displaystyle \sum_k{a\choose k}\left\{\begin{array} {c}k\\ b\end{array} \right\}\left\{\begin{array} {c}a-k\\ c\end{array} \right\}

\displaystyle \left\{\begin{array} {c}a\\ b\end{array} \right\}\left\{\begin{array} {c}a-b\\ c\end{array} \right\}

\displaystyle \left\{\begin{array} {c}a\\ b+c\end{array} \right\}b!