Putnam 2004 B2 Доказать неравенство

[artempalkin]

Пусть $m$ и $n$ положительные целые числа. Докажите, что

$$\frac {(m+n)!}{(m+n)^{m+n}}<\frac {m!}{m^m}\frac {n!}{n^n}$$

Задача несложно решается индукцией по $n$ при закрепленном $m$. Но, мне кажется, если более изящное комбинаторное решение, т.к можно переформулировать ее как $C_{n+m}^nm^mn^n<(m+n)^{m+n}$. Справа - количество $m+n$-буквенных слов в $m+n$-буквенном алфавите. А вот слева не совсем понятно, что... То есть понятно: берем $n$ букв и составляем из них $n$-буквенное слово, из оставшихся $m$ букв составляем $m$-буквенное слово. Потом, скажем, склеиваем их вместе. Слов будем меньше, потому что в первой и второй части слова буквы не могут повторяться, но зато сами слова будут повторяться... в общем, неочевидно.

[zykov]

artempalkin в сообщении #1602833 писал(а):

А вот слева не совсем понятно, что...

Одно из слагаемых при разложении правой части в бином Ньютона.

[worm2]

artempalkin в сообщении #1602833 писал(а):

То есть понятно: берем $n$ букв и составляем из них $n$-буквенное слово, из оставшихся $m$ букв составляем $m$-буквенное слово. Потом, скажем, склеиваем их вместе. Слов будем меньше, потому что в первой и второй части слова буквы не могут повторяться, но зато сами слова будут повторяться... в общем, неочевидно.

А по-моему, это и есть полное решение. Ну, может быть, чуть-чуть слов добавить/переставить и будет полное (на апелляции сообщить, что вы именно это имели в виду, и я бы, например, полный балл поставил).
$C_{n+m}^n m^m n^n$ — это число всех $(m+n)$-буквенных слов, у которых ровно $m$ букв из первой ($m$-буквенной) части алфавита, а остальные $n$ букв — из второй ($n$-буквенной) части. Это довольно очевидно. Ясно, что таких слов будет меньше, чем вообще всех слов (без ограничений).

[artempalkin]

zykov в сообщении #1602885 писал(а):

Одно из слагаемых при разложении правой части в бином Ньютона

Это гениально и это, конечно, самое простое решение в полстроки

-- 29.07.2023, 11:55 --

worm2 в сообщении #1602920 писал(а):

Это довольно очевидно. Ясно, что таких слов будет меньше, чем вообще всех слов (без ограничений).

Ну все же не особо очевидно, надо признать. Различных слов меньше, но слова будут повторяться. И непонятно, что победит.
Например, $\{1,2\}$ и $\{3,4\}$ дадут слово $1144$, но и наборы $\{1,3\}$ и $\{2,4\}$ дадут это слово.