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

Скачать 1.15 Mb.

Название	Учебно-методическое пособие для студентов гуманитарных направлений Саранск 2012 содержание
страница	5/16
Дата публикации	01.07.2013
Размер	1.15 Mb.
Тип	Учебно-методическое пособие

100-bal.ru > Математика > Учебно-методическое пособие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Похожие:

	Учебно-методическое пособие для самостоятельной работы студентов... М 545 Методология сравнительного правоведения: учебно-методическое пособие для самостоятельной работы студентов [Текст] / сост. И....		Учебно-методическое пособие по педагогической (методической) практике... Учебно-методическое пособие по педагогической (методической) практике, для студентов 4-го и 5-го курсов отделения романо-германской...
	Информационные технологии в музее (методическое пособие) Методическое пособие для бакалавров музеологов, обучающихся по направлению 030300 и студентов гуманитарных отделений		Учебно-методическое пособие Тольятти 2011 удк ббк ахметжанова Г.... Учебно-методическое пособие предназначено для студентов магистров, обучающихся на педагогическом факультете тгу по направлению «Педагогика»....
	Министерство образования и науки федеральное агентство по образованию Учебно-методическое пособие для студентов гуманитарных и экономических специальностей		Учебно-методическое пособие для студентов факультета «Финансы и кредит» Учебно-методическое пособие предназначено для студентов дневной формы обучения в помощь для эффективной подготовки к семинарским...
	Учебно-методическое пособие адресовано студентам очной формы обучения... Кискин Е. В., Ахмедова А. К. Юридическое делопроизводство: Учебно-методическое пособие для студентов очной и заочной формы обучения....		Учебно-методическое пособие для студентов специальность 050144 Дошкольное... Данное учебно-методическое пособие адресовано студентам педагогического колледжа и имеет цель оказать помощь в подготовке к зачету...
	Учебно-методическое пособие по дисциплине «пропедевтика внутренних болезней» Учебно-методическое пособие предназначено для студентов 3 курса медико-профилактического факультета кгму		Учебно-методическое пособие по дисциплине «пропедевтика внутренних... Учебно-методическое пособие предназначено для студентов 2-3 курсов лечебного факультета кгму
	Учебно-методическое пособие по дисциплине «формирование здорового образа жизни у детей» Учебно-методическое пособие предназначено для студентов 1-3 курсов педиатрического факультета кгму		Учебно-методическое пособие по дисциплине «пропедевтика внутренних... Учебно-методическое пособие предназначено для студентов 2-3 курсов педиатрического факультета кгму
	Учебно-методическое пособие для подготовки к семинарским занятиям... Поликарпова Е. В. Философские проблемы науки и техники. Учебно-методическое пособие для подготовки к семинарским занятиям. – Таганрог:...		Учебно-методическое пособие для подготовки к семинарским занятиям... Поликарпова Е. В. Философские проблемы науки и техники. Учебно-методическое пособие для подготовки к семинарским занятиям. – Таганрог:...
	Учебно-методическое пособие Учебно-методическое пособие предназначено для студентов дневной, вечерней и заочной форм обучения		Учебно-методическое пособие для бакалавров направления 080100. 62... Учебно-методическое пособие предназначено для студентов очного и заочного отделения с целью организации и обеспечения учебного процесса...

Школьные материалы