Число сюръекций

[vadimm]

Сколько существует отображений из $n$ элементного множества в $m$ элементное $(m < n)$, чтобы у каждого элемента было не менее $k < n$ прообразов?

То есть, если я правильно понимаю, нужно найти число сюръекций. Но не всех, а таких, где у каждого элемента не менее $k$ прообразов. Знаю, что число всех отображений будет $m^n$. Поэтому требуемое число сюръекций должно быть меньше. Думаю, что это задача с комбинаторной интерпретацией. Имеется $n$ шаров, которые нужно разложить по $m$ ящикам, чтобы в каждом ящике оказалось не менее $k$ шаров. Так?

[svv]

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

[vadimm]

Хороший вопрос. Думаю, что шары одинаковые. Если взять конкретный пример. Ну, например, сколько существует отображений из 4 элементного множества в 2 элементное, чтобы у каждого элемента было не менее 2 прообразов. Как мне кажется, это то же самое, что и сколькими способами можно разложить 4 одинаковых шара по 2-м различным ящикам так, чтобы в каждом ящике оказалось не менее двух шаров? Так же?

[svv]

Рассмотрим отображения множества $\{1,2\}$ на себя.
Ну разве отображения
$1\mapsto 1,\; 2\mapsto 2$
и
$1\mapsto 2,\; 2\mapsto 1$
совпадают? А на языке ящиков и шаров — это в обоих случаях один шар в первом ящике и один шар во втором ящике.

[iifat]

Имхо, при любом ответе на вопрос svv стоит начать с более простого случая: $n=km$, а дальше уж посмотреть.
Upd: не, ерунду написал.

[vadimm]

Да. Спасибо. Действительно, скорее всего это похоже на размещение $n$ различных шаров по $m$ различным ящикам, чтобы в них лежало $k_1, k_2, \dots, k_m$ шаров. В таком случае число таких размещений будет $\frac{n!}{k_1!~\dots~k_m!}$. Верно? Но плохо понимаю, что будет в случае, если шаров в каждом ящике не менее $k$?

[vadimm]

UPD. Я проверил. Сколько существует отображений из 4 элементного множества в 2 элементное, чтобы у каждого элемента было не менее 2 прообразов? Тогда существует единственное разбиение множества из 4 элементов по двум "ящикам". Это в каждом ящике ровно по 2 элемента. То есть $k_1=2$ и $k_2 = 2$. Воспользуемся формулой $\frac{4!}{2!2!}=6$. Другой пример. Сколько имеется таких отображений 5 элементного множества в 2 элементное, чтобы у каждого элемента было не менее 2 прообразов? Пять элементов можно разбить таким образом по двум "ящикам" только как по: 2, 3. По формуле получаем $\frac{5!}{2!3!}=10$. Вроде так и есть. Формула работает.

[nnosipov]

vadimm
Напишите Ваш ответ для $k=1$ (и произвольных $m$ и $n$).

[vadimm]

Затрудняюсь написать.

[nnosipov]

Тогда думайте дальше. Уже случай $k=1$ вполне интересен.

[vadimm]

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

скорее всего это похоже на размещение $n$ различных шаров по $m$ различным ящикам, чтобы в них лежало $k_1, k_2, \dots, k_m$ шаров. В таком случае число таких размещений будет $\frac{n!}{k_1!~\dots~k_m!}$.

А это направление мысли верно?

[nnosipov]

Не уверен, но настаивать не буду (мало ли сколь замысловатым путем можно прийти к правильному решению). Когда я сам решал задачу про число сюръективных отображений, я составил и затем решил некую систему линейных уравнений.

[iifat]

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

Пять элементов можно разбить таким образом по двум "ящикам" только как по: 2, 3

Напоминаю: ящики различимы. Ещё 3 и 2.

[vadimm]

iifat в сообщении #1475912 писал(а):

Напоминаю: ящики различимы. Ещё 3 и 2.

То есть в формуле нужен множитель $m!$ ?