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

[svv]

Whitaker
Если $x\in M$ -- элемент, то $y=f(x)$ -- элемент, образ элемента $x$.
Если $X$ -- множество, то $f(X)$ -- тоже множество, образ множества $X$, т.е. множество всех образов $x\in X$.
Ну, а $|f(X)|$ -- количество содержащихся в нем элементов (мы с Вами точно такое обозначение недавно использовали ).
Так как $f: X \to Y$ -- не обязательно сюръекция, $|f(X)|$ не обязательно равно $|Y|=n$.

[Joker_vD]

Блин, вот вам $X=\mathbb R$, $Y = \mathbb C$, и отображение $f\colon X \to Y$ действующее по правилу: $f(1)=1$, $f(2)=2$ и $f(x)=3$ если $x\ne1,2$. Как ни странно, это $f$ удовлетворяет условию задачи.

[Whitaker]

А теперь последуйте совету ewert.
Сколькими способами можно разбить множества $X$ на три подмножества так чтобы в каждой было хотя бы один элемент?

[ewert]

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

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

Вы совершенно не в ту сторону думаете. Вам нужно найти количество способов разбить прообразы на три непустых подмножесва. Если бы пустые подмножества допускались, то эта подзадача была бы стандартной. Ну так просто выкиньте лишнее.

[Unconnected]

Ааа, кажется начинаю понимать, что имелось в виду.. я раньше считал, что если какие-то иксы отображаются в 3 одинаковых элемента из игрик, то значит мощность уже равна 3.

Чтобы разбить так.. Возможно, если представить n элементов, то нужно количество способов расставить 3 перегородки между ними, для всех расстановок иксов.. $\binom{n+1}{3}\cdot n!$ ?

[Whitaker]

Неправильно

[Unconnected]

А, ещё перегородки не должны стоять рядом. $\binom{n-2}{3}\cdot n!$ , иначе не знаю..

[ewert]

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

Возможно, если представить n элементов, то нужно количество способов расставить 3 перегородки между ними, для всех расстановок иксов.. $\binom{n+1}{3}\cdot n!$ ?

Невозможно. Не при чём тут вообще перегородки. Забудьте пока про непустоту и подсчитайте количество способов разбить на любые три подмножества (возможно, и пустые). Или, что то же, количество всех вообще отображений (не обязательно "на") из $m$ элементов в $3$ элемента. Это -- совершенно стандартная и очень простая формула, Вы обязаны её знать.

[Whitaker]

Сколькими способами можно положить $n$ различных предметов в $m$ различных ящиков так, чтобы в каждом ящике лежал хотя бы один предмет.
Вы знаете формулу включений-исключений?

[Unconnected]

Знаю размещения и сочетания и ещё пару тривиальных, а это не проходили..

[ewert]

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

и ещё пару тривиальных,

Вот это и есть одна из тривиальных.

[Whitaker]

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

[Unconnected]

$m^n$ ?
Принцип включений-исключений нагуглил, но не понял, как его сюда приплести.

[ewert]

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

Принцип включений-исключений нагуглил, но не понял, как его сюда приплести.

Вычтите отсюда все отображения, в которых образы состоят не более чем из двух элементов.

[Whitaker]

Сколькими способами можно положить $n$ предметов в $m$ ящиков при условии что один ящик должен быть полностью пустым (остальные как угодно)?