Найти количество отображений X в Y, таких что |f(X)|=3

[Unconnected]

Пусть $X,Y$ - множества, причем $|X|=m$, $|Y|=n$. Сколько существует отображений f: X->Y таких, что $|f(X)|=3$?

Отображение характеризуется элементами икс-игрик, которые в него входят.. т.е. просто наборами, два набора одного состава с разными соответствиями считаются одинаковыми. Так вот, нашел количество выборов 3х элементов из Y с возвращением (т.к. не обязательно биекция), и умножил на количество размещений 3х элементов в X. То есть:

$\binom{n+3-1}{3}\cdot\binom{m}{3}$
и опять незачет.. что не так?

[Whitaker]

Можете объяснить что значит $|f(X)|=3$?
Что-то я не догнал

[xmaister]

Whitaker в сообщении #505674 писал(а):

$|f(X)|=3$

Наверное, это значит, что образ $X$ содержит 3 элемента.

[ewert]

Во-первых, надо перебрать все образы; это $C_n^3$ варианта. Во-вторых, для каждого образа надо перебрать все отображения "на", т.е. все разбиения $X$ на три непустых подмножества, и это уже вовсе никакое не $C$, а...

[Whitaker]

Спасибо за информацию xmaister

[Unconnected]

Цитата:

Во-первых, надо перебрать все образы; это $C_n^3$ варианта.

1) Почему столько? Ведь все 3 икса могут отображаться в один элемент, или в два..
2) Разве $\binom{m}{3}$ может взять из Х пустые множества? Это ж сочетания..

[Whitaker]

Это число способов выбрать три элемента из $n$

[Unconnected]

Цитата:

Это число способов выбрать три элемента из $n$

А нужно ещё способы для 2 и 1 элемента посчитать..

[ewert]

Unconnected в сообщении #505678 писал(а):

Ведь все 3 икса

Разве где-то что-то говорилось о трёх именно иксах, хоть разок упоминалось?...

[svv]

Не могут, см. выше пояснение xmaister, заслуживающее того, чтобы его извлекли из оффтопа на поверхность.

[Unconnected]

Ну если |f(X)|=3, то наверное в прообразе три икса, или нет? O_o

[svv]

Прошу Вас, прочтите еще разик: образ содержит 3 элемента, и ничего сверх того.
А прообраз содержит $m$ элементов по условию задачи.

[ewert]

Unconnected в сообщении #505682 писал(а):

А нужно ещё способы для 2 и 1 элемента посчитать..

Какие ещё 2 и 1?... Читайте внимательнее:

ewert в сообщении #505676 писал(а):

Во-первых, надо перебрать все образы; это $C_n^3$ варианта.

По условию каждый образ должен содержать ровно три элемента; вот эти образы и перебираем. После чего для каждого варианта перебираем все разбиения на подмножества, а это не имеет ничего общего с сочетаниями.

[Unconnected]

А.. Значит, в прообразе может быть минимум 3 икса, да?
И вообще, если 3 икса отображаются в 1 элемент, в образе будет 3 элемента или один? Кажется, это очень важно)

[xmaister]

Unconnected в сообщении #505689 писал(а):

Значит, в прообразе может быть минимум 3 икса, да?

Знаете определение полного прообраза?