1.4. Преобразования и подстановки

Произведение преобразований g и g множества X определено для любого xX равенством: gg(x)=g(g(x)), то есть gg - также преобразование множества X. Операция возведения в степень преобразования g определяется индуктивно:

g⁰=е, g^t=g(g^t-1), t=1,2,...

Элемент xX называется неподвижным элементом преобразования g, если g(x)=x. Если x - неподвижный элемент преобразований g и g, то x - неподвижный элемент и их произведения.

Пусть g(X) образ множества X относительно преобразования g. Числа g(X) и X-g(X) называются соответственно рангом преобразования g и дефектом преобразования g, обозначаются rang(g) и def(g). Для произведения любых преобразований g и g множества X выполнено:

rang(gg)min{rang(g),rang(g)}. (1.1)

Теорема 1.2. Биективность преобразования конечного множества равносильна его инъективности (сюръективности).

Биективное преобразование п-множества X называется подстановкой на множестве X, п – степенью подстановки, т.е. подстановка степени п – это преобразование п-множества, имеющее ранг п и дефект 0.

Множество S(X) всех подстановок степени п образует относительно умножения группу порядка п!, умножение определено, как в общем случае для функций. Группа S(X), называемая симметрической группой подстановок степени п, есть максимальная подгруппа обратимых элементов моноида (X). Обычно вместо множества X удобно рассматривать множество {1,…,n}. Соответствующие симметрические полугруппа и группа степени п обозначаются _n и S_n.

Каноническое табличное задание подстановки gS_n имеет вид:

g = = ,

где (i₁,…,i_n) – перестановка чисел (1,…,n). Каноническая таблица обратной подстановки g^-1 получается после перестановки в таблице g верхней и нижней строк и переупорядочения вертикальных пар по элементам верхней строки.

Между множеством подстановок степени n и множеством перестановок множества {1,…,n} имеется биекция, ставящая в соответствие подстановке g перестановку нижнего ряда канонической таблицы подстановки g. Данная биекция порождает соответствие многих понятий для подстановок и перестановок.

Теорема 1.3. Произведение g₁…g_t преобразований множества X есть подстановка  g_i - подстановка множества X, i=1,…,t, где t>1.

t Для t=2 теорема вытекает из равенства (1.1). Отсюда, применяя метод математической индукции, получаем теорему для t>2. u

Лекция № 2. Схемы и методы комбинаторики

2.1. Основные правила перечисления

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

Подмножества множества (мультимножества) X в комбинаторике часто называют выборками из множества (мультимножества) X. Пусть требуется посчитать число различных выборок, обладающих определенными свойствами. Для решения таких задач используются следующие правила.

Правило суммы: если число различных выборок со свойством 1 равно n₁, и число различных выборок со свойством 2 равно n₂, и при этом ни одна выборка не обладает свойствами 1 и 2 одновременно, то число различных выборок, обладающих свойством 1 или свойством 2, равно n₁+n₂.

Правило произведения: если число различных выборок Y со свойством 1 равно n₁, и число различных выборок Z со свойством 2 равно n₂ (свойства 1 и 2 могут совпадать), то число различных пар выборок (Y,Z) таких, что Y обладает свойством 1 и Z обладает свойством 2, равно n₁n₂.

Пример 2.1. Правило суммы. В студенческой группе число «отличников» равно 5, число «хорошистов» равно 10. Тогда число студентов, которые учатся не ниже, чем на «четыре», равно 15.

Правило произведения. а) Число 7-значных телефонных номеров равно 10⁷.

б) Число 7-значных телеф. номеров, начинающихся не с «нуля», равно 910⁶.

в) Число способов, которыми можно переставить n предметов (число перестановок n элементов, n - натуральное) равно n!.

г) число строк длины n, состоящих из «нулей» и «единиц», равно 2ⁿ. w