УказательРазделыОбозначенияАвторО проекте


§

Вспомогательная страница к разделу ☞ НАЧАЛА ТЕОРИИ ЦЕЛЫХ ЧИСЕЛ


Т

Теорема. Мультиномиальный коэффициент

\frac{n!}{n_1!\, n_2! \times \dots \times n_K!} \quad npu \quad n_1+ n_2+\dots +n_K=n

является целым числом.

Доказательство. Если p_{} — простое число, то на основании теоремы Лежандра оно входит в каноническое разложение числа 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!_{}.


2011/04/12 11:37 редактировал au