Цело ли данное число, как догадаться?

[vadimm]

Будет ли целым число $\frac{1000!}{100!^{10}}$?

Тут вот, что интересует.

Число, по видимому, целое. Известно, что это значение мультиномиального коэффициента в разложении $(x_1 + x_2 + \dots + x_{10})^{1000}$ по одночленам $x_1^{100}x_2^{100} \dots ~x_{10}^{100}$.

А как об этом догадаться, когда первый раз видишь такую задачу? Об этом просто нужно знать? Ведь не зная, понять, что это число является значением мультиномиального коэффициента в разложении чего-там и т.д. и т.п., практически кажется не реальным. И еще вопрос странный, конечно, почему коэффициент обязан всегда быть целым? Понятно, что идут подобные слагаемые, которых целое число, но ведь у какого-то произвольного многочлена могут быть и не целые коэффициенты?

[alisa-lebovski]

Коэффициент обязан быть целым потому, что он получается сложением и умножением из целых чисел.

Если не знать, что это коэффициент, можно поискать в 1000! такие 10 различных наборов множителей, каждый из которых делится на 100!.

[nnosipov]

На тот случай, когда комбинаторное происхождение подобных чисел неизвестно: можно воспользоваться формулой Лежандра для показателя, с которым простое число $p$ входит в каноническое разложение числа $n!$.

[alisa-lebovski]

nnosipov в сообщении #1475383 писал(а):

На тот случай, когда комбинаторное происхождение подобных чисел неизвестно: можно воспользоваться формулой Лежандра для показателя, с которым простое число $p$ входит в каноническое разложение числа $n!$.

Да, но придется проверять все простые числа до 100, в каких степенях они у 100! и 1000!. Или нет?

[nnosipov]

alisa-lebovski в сообщении #1475402 писал(а):

Да, но придется проверять все простые числа до 100, в каких степенях они у 100! и 1000!.

Ничего страшного: в данном случае это можно сделать в "буквенном" виде, с помощью оценок. Вот еще один пример задачи, где эта технология вполне себя оправдывает:

Докажите, что при $u \geqslant v \geqslant 1$ число

$$\frac{(2u)!v!}{u!(2v)!(u-v)!}$$

является целым.

Таких примеров (лежащих вне комбинаторики?) довольно много.

[mihaild]

Общий вид задачи, видимо, такой: пусть $a_1 + \ldots a_n = b_1 + \ldots + b_m$. При каких условиях $\frac{\prod_{i=1^n} a_i!}{\prod_{i=1^m} b_i!}$ целое?
Из комбинаторики получаем что при $n = 1$ точно целое. Из формулы Лежандра вроде бы получается такое условие: если отсортировать эти последовательности вместе, и в любом префиксе получившейся последовательности членов числителя не больше, чем членов знаменателя, то число целое (на самом деле там должно быть что-то более сильное, но не соображу что). Для задачи nnosipov этого, впрочем, недостаточно.

[nnosipov]

Вот такая тема на тему была: topic53833.html

[alisa-lebovski]

Мне кажется, здесь общий вид задачи, что целое

$$\frac{(ab)!}{(a!)^b},\quad a>b>1.$$

[StaticZero]

И я подозреваю, что при $a \gg b$ ответ всегда утвердительный...

[nnosipov]

alisa-lebovski в сообщении #1475474 писал(а):

Мне кажется, здесь общий вид задачи

Можно даже пойти чуть дальше: вот такое число тоже целое:

$$\frac{(kn)!}{k!^nn!}.$$

-- Чт июл 23, 2020 22:01:05 --

StaticZero
Там при любых верно: это же частный случай полиномиального коэффициента.

[StaticZero]

nnosipov, ага, уже увидел...

[ИСН]

nnosipov в сообщении #1475480 писал(а):

Можно даже пойти чуть дальше: вот такое число тоже целое

А это коэффициент из формулы Фаа ди Бруно (ну, почти).

[nnosipov]

ИСН в сообщении #1475585 писал(а):

А это коэффициент из формулы Фаа ди Бруно (ну, почти).

Почему почти? Один из, насколько я понял.

[ИСН]

Ну да, можно сказать и так.

[Andrey A]

vadimm в сообщении #1475369 писал(а):

Число, по видимому, целое... А как об этом догадаться, когда первый раз видишь такую задачу? Об этом просто нужно знать?

Достаточно знать, что $\dfrac{(A+B)!}{A!B!}$ целое. Тогда произведение целых $\dfrac{(A+B+C)!}{A!(B+C)!} \cdot \dfrac{(B+C)!}{B!C!}=\dfrac{(A+B+C)!}{A!B!C!}$ тоже целое. В том числе и $\dfrac{1000!}{100!^{10}}=\dfrac{(100+100+...+100)!}{100! \cdot 100! \cdot ... \cdot 100!}.$