Задачка на отображения

[Orkimed]

Здравствуйте. Нашёл книжку Преобразования и перестановки Л.А Калужина, начал решать.
Поставила в ступор одна задачка. Решение разбираю уже пару часов.
Найти, сколько существует m-элементных подмножеств множества из n элементов.
Предлагаю воспользоваться решением предыдущего упражнения. Оно про количество инъектвных отображений. Оно равно $A_{a}^{b}$ убывающему факториалу.
В ответах приведено решение:
Пусть B есть n-элементное множество. Зафиксируем произвольное множество A, $|A|=m.$
Образ множества А при инъективном отображении $A\to B$ будет некоторым m-элементным подмножеством B. Множество А будет иметь тот же самый образ $A' \subset B$ при разных инъекциях тогда и только тогда, когда они будут отличаться на некоторую биекцию множества А в себя. Поскольку $|A|=m$ , то существует $m!$ различных биекций А на себя. А поэтому есть $C_n^m=\frac{(n-m+1)!}{m!}$ различных m-элементных подмножеств множества B.
Вопрос:
Что значит "отличаться на некоторую биекцию..." ?

Я предположил, что количество этих подмножеств будет равно $ С_{n}^{m} = \frac{(n-m+1)!}{m!(n-1)!}$ ( число сочетаний c повторениями) ,но в числителе не сходится. Вид дроби сходен, но почему нет коэффициента, я не понимаю. Количество инъекций равно $(n-m+1)!$ или $A_{n}^{m}=\frac{n!}{(n-m)!}$ . Я догадываюсь, что понимание придёт тогда, когда мне кто-нибудь доступно разъяснит мой вопрос.

[Slow]

Orkimed в сообщении #1113036 писал(а):

$C_n^m=\frac{(n-m+1)!}{m!}$

А если $n=m$?
Теперь насчет биекции:
Пусть $f:A \to A$-биекция, $g:A \to B$ - инъекция. А теперь рассмотрим образ $g$ и образ суперпозиции $f$ и $g$, что о них можно сказать?

[VAL]

Понятно ли Вам, что количество размещений (т.е. упорядоченных наборов неповторяющихся элементов) из n элементов по m равно $n(n-1)(n-2)\dots (n-m+1) = \frac{n!}{(n-m)!}$ ?

[Orkimed]

VAL
Понятно. Две эквивалентные формулы.

-- 07.04.2016, 18:09 --

Slow
Если n=m получается дробь $\frac{1}{m!}$. Что это значит? А вроде должна же получиться 1,т.е сводиться к количеству сочетаний без повторений ?
Они должны совпадать. Биекция не вносит никаких изменений в отображение.

[VAL]

Orkimed в сообщении #1113053 писал(а):

VAL
Понятно. Две эквивалентные формулы.

А понятно, что элементы m-элементного множества можно упорядочить $m!$ способами?

[Orkimed]

VAL
Это же следует из формулы $A_n^m $? Я когда выводил её, то как раз пользовался этим.

-- 07.04.2016, 19:37 --

Нашёл нормальные лекции по Комбинаторике.
$C_n^m=\frac{A_n^m}{m!},$ то есть общее количество различных наборов при выборе $m$ элементов из $n$ без возвращения и без учета порядка.
Теперь осталось разобраться откуда берётся $m!$ число биекций. Точнее как придти логически к их использованию в доказательстве.

[VAL]

Orkimed в сообщении #1113077 писал(а):

VAL
Это же следует из формулы $A_n^m $? Я когда выводил её, то как раз пользовался этим.

Я, признаться, поленился прочесть весь Ваш стартовый пост

Мне представляется, что формула $A_n^m=n(n-1)(n-2)\dots (n-m+1)$ очевидна сама по себе и не требует вывода с использованием подсчета количества перестановок.

А именно: На первое можно поставить любой из $n$ элементов. Это $n$ способов.
На второе место можно поставить любой из $n-1$ оставшихся элементов. Итого упорядоченный набор из 2-х элементов можно получить $n(n-1)$ способами.
И т.д.

А формула для числа перестановок просто частный случай формулы для размещений при $m=n$.

Вас такой подход чем-то не устраивает?

[Orkimed]

VAL
Всем устраивает. Я немного запутался и теперь распутался.

[Orkimed]

Slow
Так откуда берётся в доказательстве биективность? Почему образ всегда должен быть один и тот же $A'$? Как логически до этого дойти? Не могли бы вы привести пример?
А то я примерное понимаю что и как,но вот пример у меня для окончательного понимания не получается подобрать. С множествами из чисел.

[provincialka]

"Биективное отображение" и "перестановка элементов" для конечного множества -- одно и то же. Только звучит по-загадочнее.

[Slow]

Orkimed в сообщении #1113053 писал(а):

Если n=m получается дробь $\frac{1}{m!}$. Что это значит?

Я думаю это значит что формула неправильная.

Orkimed в сообщении #1113053 писал(а):

Они должны совпадать. Биекция не вносит никаких изменений в отображение.

Это вы поняли? Если да, тогда не совсем понятно в чем затруднение:

Orkimed в сообщении #1113143 писал(а):

Так откуда берётся в доказательстве биективность? Почему образ всегда должен быть один и тот же $A'$? Как логически до этого дойти? Не могли бы вы привести пример?

Сформулируйте лучше, а то я не совсем понимаю в чем именно проблема.

[Brukvalub]

Как во множестве из $n$ элементов выделить $m\le n$ элементов? Можно организовать отдельное множество $M$ из $m$ элементов и инъективно отобразить его в то множество, где выделяются элементы. Образ инъекции и есть выделенное множество. Что будет, если инъекция будет другая, но образ останется прежним? Выделится то же самое множество. Как это отразить в рассуждении? Вот как: если сделать сначала биекцию $M$ на себя, а затем применить ту же, что и ранее, инъекцию в множество, где выделяются элементы, то выделяемое множество не изменится. Поэтому в книге и написано :

Orkimed в сообщении #1113036 писал(а):

Множество А будет иметь тот же самый образ $A' \subset B$ при разных инъекциях тогда и только тогда, когда они будут отличаться на некоторую биекцию множества А в себя.

[Orkimed]

Slow
То что формула неправильная я уже понял. Если её вычислить при $n=4$ и $m=2$, то получается 3. Абсурд. 3 подмножества из 2 элементов в 4 элементном множестве. Какие нужно внести коррективы в формулу, чтобы она работала корректно?
С биекцией я разобрался. За ночь мысли сформировались. Немного подкорректировал этот процесс пост Brukvalub. Огромное ему за это спасибо.

[Slow]

Orkimed
Забудьте вы эту неправильную формулу. У вас есть количество ВСЕХ инъекций, при этом различных с точностью до биекции инъекциий там одинаковое количество(какое?). Как найти число этих самых различных инъекций?

[Orkimed]

Slow
Общее количество всех инъекций $A_{n}^{m}=(n-m+1)! =\frac{n!}{(n-m)!}$
Естественно это должна быть дробь. $C_{n}^{m}=\frac{n!}{m!(n-m)!}?$
А вот как вычленить все различные инъекции я не знаю. Курс комбинаторики мне еще не читали.