Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012



страница4/12
Дата26.07.2014
Размер1.15 Mb.
ТипУчебно-методическое пособие
1   2   3   4   5   6   7   8   9   ...   12

Перестановки


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

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

Например, дано множество А = {а, b}.

Перестановки этого множества: а, b и b, а.

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

Из всех возможных перестановок данного множества мы выбираем, по соглашению, одну перестановку, взаимное расположение элементов которой считаем «порядком» Тогда мы должны считать, что все прочие перестановки данного множества получены путем нарушения принятого нами «порядка» (путем инверсий).

Для каждой перестановки приписывается неотрицательное целое число, называемое числом инверсий. В частности, перестановке, взаимное расположение элементов в которой принято за «порядок», приписываем число инверсий, равное 0. Эта перестановка называется нормальной.

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



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

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

Число инверсий в перестановке определяют следующим образом:

1 шаг. Вычеркиваем в перестановке элемент, который в нормальной перестановке стоит на первом месте и подсчитываем число элементов, стоящих до этого вычеркнутого элемента.

2 шаг. Из перестановки вычеркиваем элемент, который в нормальной перестановке стоит на втором месте, и подсчитаем число элементов, стоящих до этого вычеркнутого элемента, не считая ранее вычеркнутого.

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

И т. д. Процесс конечный, т.к. число элементов в данной перестановке конечное.

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

Пример. Найти число инверсий в перестановке 2, 1, 5, 3, 4. Нормальной перестановкой является перестановка 1, 2, 3, 4, 5.

1 шаг: (2, 1, 5, 3, 4) → δ1 = 1

2 шаг: (2, 1, 5, 3, 4) → δ2 = 0

3 шаг: (2, 1, 5, 3, 4) → δ3 = 1

4 шаг: (2, 1, 5, 3, 4) → δ4 = 1

5 шаг: (2, 1, 5, 3, 4) → δ5 = 0

Число инверсий в перестановке 2, 1, 5, 3, 4 равно δ = δ1 + δ2 + δ3 + δ4 5 = 1 + 0 +1 + 1 + 0= 3.

Если число инверсий число четное, то перестановка называется четной.

Если число инверсий число нечетное, то перестановка называется нечетной.

Перечислим основные теоремы о перестановках.

Теорема 1. Всех перестановок n элементов будет

Теорема 2. Если поменять местами два элемента в перестановке (совершить одну транспозицию), то перестановка сменит свою четность на противоположную.

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



Теорема 3: При n ≥ 3 половина перестановок n элементов четная, половина нечетная. Заметим, нормальная перестановка - четная.

    1. Отображения множеств. Подстановки


Допустим, что мы имеем два непустых множества А и В.

Если по какому-либо закону каждому элементу х множества A подставляем в соответствие один и только один элемент у из множества В, а каждому элементу y из множества B соответствует, по крайней мере, один элемент х множества А, то в этом случае говорят, что множество А отображается на множество В и пишут:



АВ

ху

При этом элемент у называется образом элемента х, а элемент х – прообразом элемента у.

Заметим, что в этом случае образ у элемента х определяется однозначно, но элемент х элементом у может определяться неоднозначно.

Пример:


1. Пусть дано множество А всех вещественных чисел и множеств В всех неотрицательных вещественных чисел. Поставим каждому числу хА в соответствие число уВ по следующему закону: ху, где у = х². Таким образом, мы установили отображение множества А на множество В.

В самом деле, квадрат любого вещественного числа х существует и представляет собой неотрицательное вещественное число у, определяемое по данному х однозначно. Обратно, неотрицательное вещественное число у определяет, по крайней мере, одно вещественное число х, квадрат которого равен числу у.

2. Нам дано множество А всех целых чисел и множество В = {1, 1}. Поставим в соответствие каждому четному целому числу х число у = 1, а каждому нечетному целому числу x число y = –1 из множества В. Этим самым мы задали отображение множества А на множество В.

Отображение множества А на множество В называется взаимно однозначным, если каждому элементу уB соответствует единственный элемент xA.

Взаимно однозначное отображение множества А на множество В записывается так:

АВ

ху

Следовательно, при взаимно однозначном отображении множеств образ и его прообраз взаимно однозначно определяют друг друга.

Примеры:


    1. А = {a, b, c, d}, B = {1, 2, 3, 4}

Зададим отображение АВ

AB

а ↔ 1

b ↔ 2

c ↔ 3

d ↔ 4

Это отображение взаимно однозначное.



    1. Пусть множество А – множество пальцев на руке, В – множество «пальцев» на перчатке. При одевании перчатки на руку мы задаем взаимно однозначное отображение множества А на множество В.

    2. Нам дано множество А всех целых чисел и множество В целых чётных чисел. Если мы множество А отобразим на множество В по закону: ху = 2х, где хА, уВ, то это отображение будет взаимно однозначным.

    3. Нам дано множество А = {1, 2, 3} В = {1, 2, 3}. Если мы множество А отобразим на множестве В по закону:

1 ↔ 2

2 ↔ 3


3 ↔ 1,

то этим мы зададим взаимно однозначное отображение множества А на множество В.

Очевидно, можно говорить о взаимно однозначном отображении множества на себя.

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

Заметим, при этом множество может быть конечным, может быть бесконечным.

Мы остановимся на рассмотрении подстановок только конечных множеств.

При этом можно заметить, что множество можно взаимно однозначно отобразить на себя не единственным образом.

Например, множество А = {1, 2, 3} трех элементов можно взаимнооднозначно отобразить на себя различными способами:




1) 1 ↔ 1

2 ↔ 2


3 ↔ 3,

2) 1 ↔ 2


2 ↔ 1

3 ↔ 3,


3) 1 ↔ 2

2 ↔ 3


3 ↔ 1,

4) 1 ↔ 3


2 ↔ 2

3 ↔ 1,


5) 1 ↔ 3

2 ↔ 1


3 ↔ 2,

6) 1 ↔ 1


2 ↔ 3

3 ↔ 2.



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

Чтобы решить задачу о количестве подстановок множества длины n, введем сначала некоторые обозначения и определения.

Во-первых, подстановки удобнее записывать несколько в ином виде. Например, подстановку 1 ↔ 2, 2 ↔ 3, 3 ↔ 1 запишем в виде и обозначим ее какой-нибудь буквой, например, α. Читаем эту запись сверху вниз так: подстановка α переводит: 1 в 2, 2 в 3, 3 в 1.

Итак, эту подстановку можно кратко записать в следующей форме , которая по существу, означает запись перестановки В = (2, 3, 1) под перестановкой А = (1, 2, 3). Следовательно, для этого чтобы получить подстановку n элементов, мы должны взять две перестановки n элементов и отобразить их друг на друге взаимно однозначно. При этом, верхняя строка будет состоять из прообразов, а нижняя строка – из их образов при данном отображении. Другими словами, каждый столбик подстановки представляет собой запись связи прообраза х с его образом у согласно заданному отображению.

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

Например, подстановки α = и β = – равны.

Пусть дано множество М длины n. Рассмотрим всевозможные подстановки этого множества. Запишем их так, чтобы верхняя строка (строка прообразов) представляла собой нормальную перестановку. Тогда все различные подстановки будут отличаться только нижней строчкой, которых должно быть n! (как различных перестановок n элементов). Отсюда следует

Теорема 3. Подстановок n элементов равно n!.

Например, для множества М = {1} подстановок будет 1! = 1, для множества М = {1, 2}подстановок будет 2! = 1·2 = 2, для множества М = {1, 2, 3} подстановок будет 3! = 1·2·3 = 6, для множества М = {1, 2, 3, 4} подстановок будет 4! = 1·2·3·4 = 24 и т.д.

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

Например, подстановка α = нечетная, т.к. верхняя строка четная (0 инверсий), а нижняя – нечетная (т.к. она получена из верхней строки путём одной транспозиции – перемены мест двух элементов).



Теорема 4. Если поменять местами два столбика в подстановке, то ее четность не изменится.

Действительно, при перемене мест двух столбиков происходит одна транспозиция в верхней строке и одна транспозиция в нижней. От этого четность верхней строки и нижней строки изменится на противоположную. Но при этом, если строки имели одинаковую четность, они такими же и останутся, если они имели разную четность, то такими же и останутся. Т.е. четность подстановки при одной транспозиции столбцов не изменится.

Запишем все подстановки n элементов так, чтобы верхняя строка была в них нормальной перестановкой. Тогда четность подстановок будет зависеть только от четности нижних строк, в которой ½ n! четных и ½ n! нечетных при n ≥ 2

Отсюда следует



Теорема 5. При n ≥ 2 половина подстановок n элементов четная, половина – нечетная.

Замечаем, что в дальнейшем множество подстановок n элементов мы будем обозначать символом Sn.


1   2   3   4   5   6   7   8   9   ...   12

Похожие:

Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов-заочников направлений и специальностей Института информационных технологий и коммуникаций
Учебно- методическое пособие для студентов-заочников направлений и специальностей Института информационных технологий и
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие по Новой истории стран Азии и Африки Брянск, 2008 Сагимбаев Алексей Викторович. Учебно-методическое пособие по курсу «Новая история стран Азии и Африки»
Учебно-методическое пособие предназначено для студентов дневного отделения Исторического факультета, обучающихся по специальности...
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов педагогических колледжей. Предлагаемый практикум является учебно-методическим пособием нового типа. Он активизирует познавательную деятельность обучаемого
Педагогика: практикум. Учебно-методическое пособие для студентов педагогических колледжей
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие по неорганической химии Алт гос техн ун-т им. И. И. Ползунова, бти. Бийск
Учебно-методическое пособие предназначено для студентов всех форм обучения, изучающих курс "Неорганическая химия"
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов физико-математических специальностей вузов Балашов 2009 удк 004. 43 Ббк 32. 97
Данное учебно-методическое пособие состоит из лабораторных работ, которые условно можно разбить на несколько частей
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов отделений журналистики и филологии Новосибирского госуниверситета Новосибирск 1999
Учебно-методическое пособие предназначено для студентов третьего курса отделения журналистики Новосибирского госуниверситета, изучающих...
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов отделений журналистики и филологии Новосибирского госуниверситета Новосибирск 1999
Учебно-методическое пособие предназначено для студентов третьего курса отделения журналистики Новосибирского госуниверситета, изучающих...
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов 4 курса (озо, одо) специальности 050602. 65 «Изобразительное искусство»
О. А. Бакиева. Народный костюм Севера: Учебно-методическое пособие для студентов 4 курса очной и заочной формы обучения специальности...
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для преподавателей и студентов санкт-Петербург 2008 г
Данное учебно-методическое пособие мы рассматриваем как одно из средств, способствующих конструированию новой образовательной среды,...
Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 iconУчебно-методическое пособие для студентов, обучающихся по специальности «Информатика»
Учебно-методическое пособие предназначено для студентов, обучающихся по специальности «информатика», а также может использоваться...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org