Элементы комбинаторики. Отображение называется инъективным, если , т.е

Перестановки. Пусть .

Отображение называется инъективным, если , т.е. разные элементы переходят в разные.

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

Биекция – взаимно однозначное отображение, биекция – это одновременно инъективное и сюръективное отображение.

Определение: множества называются равномощными, если между ними можно установить биекцию.

Так как множество и отрезок нельзя привести в биективное отношение, то мощность отрезка будет больше мощности натурально ряда . Такая мощность называется – мощностью континуума.

Проблема континуума: Есть ли мощность промежуточная между мощностью континуума и мощностью счетных множеств?

Действительная прямая удовлетворяет множеству аксиом. И из множества аксиом не следует, что такое подмножество есть и не следует, что такого подмножества нет.

Теорема Бернштейна: если А – множество, то некоторое множество всех его подмножеств имеет мощность больше, чем мощность самого А.

Определение: отображение множества А на себя, являющееся биекцией, называется перестановкой, относительно суперпозиции отображение множеств перестановок является группой, где нейтральный элемент – это тождественная перестановка, которая .

Перестановка, обратная перестановке А будет обратным отображением. группа перестановок на множестве А. Если множество А конечное, то вместо пишут .

Сколько разных перестановок на ?

НАПРИМЕР:

Формула приближенного вычисления . Формула Стирлинга.

Число называется трансцендентными, если не являются корнями никакого многочлена с целыми коэффициентами.

Определение: Размещением из n по m, называется любое упорядоченное подмножество из m – элементов, взятое из множества, содержащего n элементов.

Определение: Сочетанием из n по m называется любое неупорядоченное подмножество, содержащее m элементов, взятое из множества, содержащего n элементов.

Очевидно, что множество из m можно упорядочить m! способами. Значит m! размещений дают одно и то же сочетание.

Если у нас есть n сортов предметов и каждый из сортов неограничен в количестве и нам нужно выбрать неупорядоченное подмножество из m элементов, причем нет ограничений на количество элементов данного сорта. (Сочетание с повторением) это

Формула Бинома-Ньютона.

Одночлен получается, когда из i скобок мы берем элемент , а изо всех остальных берем элемент . Так как порядок этих скобок неважен, то их множество неупорядоченное. Всего n – скобок, а выбрать из них I – неупорядоченных – это сочетание из n по i, значит коэффициенты .