Множество инъективных отображений Множество биективных отображений

Определение 1.27. Пусть X и Y непустые множества. Отображение f : X → Y называется иньективным, если из условия х1 ≠ х2 (х1, х2 - любые элементы множества X) следует, что f{x1) ≠ f(x2).
Множество всех инъективных отображений обозначим InYX
Теорема 1.28. Пусть X uY - конечные непустые множества. Тогда l)InYX ≠ Ø тогда и только тогда, когда |Y| > |Х|; 2) если |Х| = |Y|, то InYX = BiYX.
Доказательство. Пусть X = {x1,x2 ,…,хт} и Y = {y1,y2 ,…,ym}.
Докажем =>. Итак, InYx ≠ Ø. Тогда существует инъективное отображение f : X → У.
Следовательно f(X) = {f(x1), f(x2),…, f(xm)} Y и |f(Х)| = |Х| < |У|. Заметим, что мы использовали инъективность отображения f : f(xi) ≠ f(xj), если xi ≠ xj.
Пусть теперь п > т. Тогда мы можем построить такое отображение из множества X в множество Y: f(xi) = уi если i {1,2,...,m}. Так как f InYX, то InYX Ø.
2)Очевидно, что, если п = m, то любое инъективное отображение будет биективным.
Теорема 1.29. Пусть X ,Y - конечные непустые множества и |Y| > |Х|. Пусть |Х| = т, |Y| = п. Тогда
|InYX| =n ∙ (п- 1) ∙ ... ∙ (п – т + 1)
Доказательство. Пусть X = {х1,х2,... ,хт}, Y = {у1, y2,,…, уп}. Любое отображение f : X → Y определяется тем, куда попадет каждый элемент множества X, то есть набором элементов {f(x1), f(x2),..., f(xm)} из множества Y. При этом отображения f и g различны, если f(xi) ≠ g(xi) хотя бы для одного i {1, 2,..., m}. Будем считать элементы множества Y ячейками.
Так как мы рассматриваем инъективные отображения множества X в множество Y, то два разных элемента множества X при любом отображении попадут в две разные ячейки. Задача о нахождении InYX превращается в задачу о нахождении количества способов размещения элементов {х1,х2 ,..., хт} по п различным ячейкам. Зафиксируем элемент х1.
Существует п различных способов размещения этого элемента, так как он может попасть в любую из ячеек {y1, у2 ,...,уп}. Предположим, что элемент х1 в ячейку yj. Тогда элемент x2 может попасть при размещении в любую ячейку, за исключением уj. Таким образом получаем п ∙ (п — 1) различных способов размещения элементов {х1,x2}. При размещении элементов {х1, x2, х3} мы получаем п ∙ (п — 1) ∙ (п — 2) различных способа размещения, так как элемент x3 можно разместить в любой из (п — 2) ячеек (две ячейки уже заняты элементами х1 и x2). Продолжая этот процесс, получаем, что число различных размещений т элементов по п ячейкам вычисляется по формуле: n ∙ (п- 1) ∙ ... ∙ (п – т + 1).
В комбинаторике это число обозначается и называется числом размещений длины т на множестве из п элементов (число ячеек). Итак, мы доказали, что |InYX| = = n ∙ (п- 1) ∙ ... ∙ (п – т + 1) =n!/(n-m)!.
Следствие. Пусть X и Y такие множества, что |Х| = |Y|. Если обозначить BiYX множество всех биективных отображений из множества X в множество Y, то |BiY X| = n!
Доказательство. Действительно, если существует биективное отображение из множества X в множество Y, то |Х| = |У| = n |BiY X |= n!/(n-m)! = п!. Заметим, что в этом случае BiYX = InYX.
Каждое биективное отображение множества X = {х1,х2,..., хп} в множество Y = {y1,y2,,…, уп} является некоторым размещением элементов {x1, x2,..., хп} по ячейкам {у1, у2,..., уп}, то есть некоторой перестановкой элементов множества X. Число всех перестановок п различных элементов обозначают Рп, таким образом Рп = п!.
Задача. В кабину лифта девятиэтажного дома вошли 4 пассажира. Сколько существует способов разгрузки лифта, если каждый пассажир может выйти на любом из 8 этажей, но при этом на любом этаже может выйти не более одного человека?
Решение. Пусть X - множество пассажиров, Y - множество этажей. Каждый способ разгрузки лифта в нашей задаче - это некоторое инъективное отображение множества X в множество Y: два разных пассажира обязательно выйдут на двух разных этажах. Следовательно число различных способов разгрузки лифта совпадает с числом различных инъективных отображений из множества X в множество Y и равно |InYX|=8!/(8-4)!= 8∙7∙6∙5= 1680.
Задача. В аудитории 50 мест. Сколько существует способов размещения в аудитории 1) студенческой группы из 25 человек; 2) студенческого потока из 50 человек?
Решение. Пусть X - множество студентов, Y - множество мест в аудитории. Тогда в случае 1) количество различных способов размещения студентов в аудитории равно |InYX| =50!/25!. В случае 2) количество различных способов размещения студентов в аудитории равно |BiYX| = 50!.
Рассмотрим следующую задачу: сколькими способами из конечного множества X такого, что |Х| = п, можно выбрать m-элементные подмножества (m < п)?
Пусть X = {х1,х2,..., хп}. Рассмотрим множество Т = {1,2,..., m} и множество всех инъективных отображений из Т в X. Количество таких отображений равно |InYX| = n!/(n-m)!. Заметим, что каждое инъективное отображение f : Т → X выделяет некоторое подмножество множества X. А именно, если f(j) = xij при j Т, то Xf = {хi1, хi2,..., хim} - выделенное подмножество. С другой стороны по каждому подмножеству А = {хj1, хj2,..., хjm} можно построить отображение f : Т → X такое, что f(k) = xjk для к Т. Будет ли число различных m-элементных подмножеств множества X совпадать с |InYX|? Ответ на этот вопрос отрицательный. Действительно, подмножество Хо = {хi1, хi2,..., хim} совпадает с подмножеством Х1 = {хi2, хi3,..., хim, xi1}, однако fx0 ≠ fx1. Количество различных инъективных отображений, соответствующих подмножеству Хо, совпадает с числом различных перестановок элементов множества Хо и равно га!. Заметим, что это утверждение верно для любого m-элементного подмножества множества X. Таким образом, получаем, что число различных m-элементных подмножеств множества X равно

Powered by Drupal - Design by artinet