Инструменты сайта


§

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


Т

Теорема. Мультиномиальный коэффициент $$ \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!_{} $.

numtheory/vspom1.txt · Последние изменения: 2021/09/06 17:37 — au