Здравствуй, лор.
Есть вот такое известное тождество.
\begin{equation} \label{STIREQ1} {n+1\brack m+1}=\sum_{k=m}^{n}{n\brack k}*{k\choose m} \end{equation} (Напомним, что символом ${n\choose k}$ обозначается биномиальный коэффициент $\frac{n!}{k!*(n-k)!}$)
Проверь, пожалуйста, доказательство на наличие косячков. Я в неадеквате.
В заключение докажем тождество (\ref{STIREQ1}). Рассмотрим множество всех циклических представлений множества $X=\{1,\ldots,n\}.$ Это множество распадается на различные классы, соответствующие разным подмножествам множества $X$, которые являются циклами, содержащими элемент $n$. Отметим, что для каждого $b$-элементного подмножества $B\subseteq X,$ содержащего элемент $n,$ существует в точности ${n-1\brack m-1}$ разбиений множества $X$ на $m$ циклов, содержащих $B$ в качестве цикла. Действительно, каждое такое разбиение однозначно соответствует разбиению множества $X\backslash B$ на $m-1$ блоков. $b$-элементное множество $B\subseteq X,$ содержащее элемент $n,$ можно выбрать ${n-1\choose b-1}$ способами. Таким образом, $${n\brack m}=\sum_{b=1}^{n-(m-1)}{n-1\choose b-1}*{n-b\brack m-1} =\sum_{b=1}^{n-(m-1)}{n-1\choose n-b}*{n-b\brack m-1} =\sum_{k=m-1}^{n-1}{n-1\choose k}*{k\brack m-1} $$ Соответственно, $${n+1\brack m+1}=\sum_{k=m}^{n}{n\choose k}*{k\brack m}
Если что, за основу взят В. Липский, "Комбинаторика для программистов".
