!!§!! Вспомогательная страница к разделу
☞
((:numtheory#каноническое_разложение_числа НАЧАЛА ТЕОРИИ ЦЕЛЫХ ЧИСЕЛ))
----
!!Т!! **Теорема.** //((:binomial#обобщение Мультиномиальный коэффициент))//
$$
\frac{n!}{n_1!\, n_2! \times \dots \times n_K!} \quad npu \quad
n_1+ n_2+\dots +n_K=n
$$
//является целым числом.//
**Доказательство.** Если $ p_{} $ --- простое число, то на основании ((:numtheory#каноническое_разложение_числа теоремы Лежандра))
оно входит в каноническое разложение числа $ n_{j}! $ с показателем
$$
\left\lfloor \frac{n_{j}}{p}\right\rfloor
+\left\lfloor\frac{n_{j}}{p^2}\right\rfloor+\left\lfloor\frac{n_{j}}{p^3}
\right\rfloor
+\dots
$$
Складывая эти суммы, вычисленные для всех $ j\in\{1,\dots,K\} $, получим показатель
вхождения $ p_{} $ в каноническое разложение знаменателя дроби для мультиномиального коэффициента.
Ввиду очевидного неравенства $ \left\lfloor A \right\rfloor+\left\lfloor B
\right\rfloor\le \left\lfloor A + B \right\rfloor $, следует:
$$ \sum_{j=1}^K \left\lfloor \frac{n_{j}}{p}\right\rfloor \le
\begin{array}{c}
\left\lfloor
\begin{array}{c}
\displaystyle \sum_{j=1}^K n_{j} \\
\hline
p
\end{array}
\right\rfloor
\\
\end{array}
= \left\lfloor\frac{n}{p}\right\rfloor \ ,
\quad
\sum_{j=1}^K \left\lfloor\frac{n_{j}}{p^2}\right\rfloor \le
\begin{array}{c}
\left\lfloor
\begin{array}{c}
\displaystyle \sum_{j=1}^K n_{j} \\
\hline
p^{2}
\end{array}
\right\rfloor
\\
\end{array}
= \left\lfloor\frac{n}{p^2}\right\rfloor
$$
и т.д., т.е. показатель вхождения $ p_{} $ в каноническое разложение числителя дроби
не меньше, чем показатель его вхождения в знаменатель.
Поскольку $ n\ge n_{j} $ при $ \forall j\in \{1,\dots,K\} $, то любое простое
$ p_{} $, входящее в каноническое разложение $ n_{j}! $, будет входить и в
разложение для $ n!_{} $.
♦