Подстановки.

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

Определение 1: Биективное отображение конечного множества А на себя называется подстановкой множества А.

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

Определение 1’: Преобразование конечного множества А называется подстановкой множества А.

Если |A|=nÎ N, то можно решить вопрос о количестве различных подстановок множества А. Обозначим число таких подстановок через (читается: Р из n по n). Задачу построения биекции А на А можно рассматривать как задачу размещения n объектов (элементов множества А) по n ящикам, по одному в каждый ящик. Пронумеруем ящики от 1 до n. Порядок, в котором заполняются ящики, несуществен (любой другой порядок можно получить перемешиванием ящиков). Первый ящик может быть заполнен n способами, т.к. мы имеем свободный выбор из всего множества А. Убирая выбранный элемент из А, получим множество из n- 1 элементов. Следовательно, второй ящик может быть заполнен n- 1 способами, третий- n- 2 способами и т.д. Продолжая этот процесс, получим, что (n- 1)- й ящик может быть заполнен двумя способами, а ящик с номером n- единственным оставшимся элементом из А. Следовательно, число различных подстановок множества А равно n^.(n- 1)^.(n- 2)^....^.3^.2^.1. Это произведение называется факториалом числа n и обозначается n! Таким образом,

P_nⁿ= n! = 1^.2^.3^.... ^. (n- 1)^. n

Изучим теперь сами подстановки множества А и некоторые их свойства.

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

Пусть y подстановка на N_n. Тогда y можно определить как множество пар следующим образом:

y= {(1, x₁), (2, x₂),..., (n, x_n)}, где {x₁, x₂,..., x_n} = N_n.

Не обязательно, конечно, x₁= 1, x₂= 2 и т.д.

Подстановки удобно записывать следующим образом:

y = - здесь сразу видно какой элемент в какой переходит.

Пример 1: Пусть s- подстановка на N ₆:

s= . Тогда s(1) = 5, s(2) = 6, s(3) = 3 и т.д.

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

Пример 2: Пусть s подстановка из примера 1, а

r= . Вычислим r s: К каждому элементу N ₆ применим сначала s, а потом к результату применим r: s(1)= 5, r(5)= 4, значит r(s(1))=4; s(2)= 6, а r(6)= 5, значит r(s(2))= 5 и т.д. В конечном итоге получаем r s = .

Композицию подстановок можно построить и так: переставим в подстановке r столбцы так, чтобы ее первая строка была такой же как и вторая строка в подстановке s

r= и запишем их одна под другой:

s=

r= , тогда легко получаем

r s = .

s r = , значит r s ¹ s r.

Пример 3: Пусть s- подстановка из примера 1. Найти s¹⁰, т.е. s s s ... s - 10 раз.Для этого вовсе не обязательно находить десять раз образы каждого элемента. Замечаем, что s(1)= 5, s(5)= 4, s(4)= 1, значит s³(1)= 1, но s¹⁰= s s³ s³, значит s¹⁰(1)= 5. Далее:

s²(2)= 2 Þ s¹⁰(2)= 2,

s¹⁰(3)= 3,

s³(4)= 4 Þ s¹⁰(4)= 1,

s³(5)= 5 Þ s¹⁰(5)= 4,

s²(6)= 6 Þ s¹⁰(6)= 6.

В итоге получаем: s^{! 0}= .

Определение 2: Подстановка называется тождественной подстановкой и обозначается I_n (т.к. I _Nn -слишком громоздко).

Поскольку подстановка это биекция, имеет смысл говорить об обратной подстановке. Как построить обратную подстановку? Учитывая свойство биекции s s^-1 = I_n= s^-1 s: Если s переводит k в a_k, то s^-1 должна a_k перевести в k. Поэтому получаем правило построения s^-1 из s:

Подстановка s^-1 получается из s перестановкой строк.

Пример 4: Пусть r- подстановка из примера 2. Тогда

r^-1= . Перепишем ее в более удобном виде:

r^-1= . Тогда

r^-1 r = = = I₆.

r r^-1 = = = I_6.

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

Определение 3: Пусть A = {a_1, a₂,..., a_n} (т. е. элементы множества пронумерованы каким - то образом). Подстановку w называют циклом (циклической подстановкой), если ее можно представить в виде:

w = .

Предположим теперь, что AÍ B и |B|= m³ n. Зададим подстановку c на В, расширяя подстановку , так, что

c: x

Т.е. если B = {a_1, a_2, ..., a_n, a_n+1,..., a_m}, то c можно записать в виде:

c = (1)

Подстановка c, действуя на В, ведет себя как , во всех тех случаях, когда элементы В не остаются на месте. Можно сказать, что c передвигает элементы a_i циклическим образом («по кругу» см. рис.1).

Поскольку, как правило, множество, на котором действует подстановка известно (для c это В), то ее удобно записывать в следующей форме:

c= (a₁, a₂,..., a_n) (2)

Эта подстановка называется циклом длины n. Цикл длины 1 будем называть тривиальным циклом. Поэтому можно сказать, что (2) получена из (1) исключением циклов длины 1. С другой стороны если подстановка c задана в виде (2), то легко понять, как она действует на B (рис. 2).

И ее легко записать в виде (1). Т.е. при переходе от (2) к (1) мы добавляем циклы длины 1, если они есть.

Пример 5. Рассмотрим опять подстановку r = . Перепишем ее в виде (1) r = , т.е. эта подстановка является циклом длины 5 и ее можно представить в виде r = (1, 3, 6, 5, 4). Не все подстановки, конечно же, являются циклом, однако они все содержат циклы.

Пример 6. Подстановка s из примера 1 s = .

Ее можно представить в виде: s = . Как видно, она сама не является циклом, но содержит два нетривиальных цикла: (1, 5, 4) и (2, 6). Для того чтобы понять, что собой представляет s дополним каждый из этих циклов до преобразования N₆, не забыв о тривиальном цикле (3), и представим их в форме (1). А именно:

s₁= (1, 5, 4)= ; s₂ = (2, 6) = , тогда

s₂ s₁ = ; s₁ s₂ = . Мы видим, что s = s₁ s₂ = s₂ s₁ (_*)

Нам удалось представить подстановку множества, состоящего из шести элементов в виде композиции двух нетривиальных циклов. В этом случае будем говорить, что подстановка s представлена в виде произведения двух циклов и записывать s = (1, 5, 4) (2, 6).

Из того, что s- биекция и по основному свойству биекций:

f (X Ç Y) = f (X) Ç f (Y), можно сделать вывод, что циклы одной и той же подстановки не могут содержать общие элементы. Следовательно, подстановку s мы представили в виде произведения непересекающихся циклов.

C_n^r= C_n^n-r.

Доказательство:

C_n^n-r= = = C_n^r.

Комментарий: Если r- элементное подмножество В n- элементного множества А можно выбрать несколькими способами, то дополнение А\В можно выбрать таким же числом способов.

Свойство 2 (Правило Паскаля):

C_n+1^r = C_n^r + C_n^r-1.

Доказательство:

C_n^r + C_n^r-1= + = =

= =

Что и требовалось доказать.

Это дает рекуррентный способ построения чисел C_n^r. Только надо доопределить для r = 0: C_n⁰ = = 1= C_nⁿ (по свойству 1). Попробуем расположить наши результаты в виде таблицы. Будем располагать в n строках, т.е. номер строки равен n, а номер столбца равен r, а еще нулевой столбец и строку:

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

1 1

1 2 1

1 3 3 1

1 4 6 4 1

.............

Свойство 3(бином Ньютона). Для любых действительных чисел а и b и для любого натурального числа n имеет место формула:

.

Замечание: Если учесть, что C_n⁰ = C_nⁿ, и a ⁿ = C_n⁰ aⁿ b⁰,

bⁿ = C_nⁿ a⁰ bⁿ , то бином запишется так: (a + b) ⁿ = .

Доказательство (по индукции):

I шаг. При n= 1: a+ b= C₁⁰a+ C₁¹b= a+ b.

II шаг. Пусть (a+ b)^k= - верно. Тогда (a+b)^k+1= (a+b)^k(a+b)= ^. (a+b)= a + b= a^k+1 + (C_k⁰+ C_k¹)a^kb + (C_k¹+ C_k²)a^k-1b² +...+ (C_k^s+ C_k^s+1)a^k-sb^s+...+ b^k+1, получаем (по свойству 2: C_k^s+C_k^s+1= C_k+1^s+1):

(а+ b)^k+1= a^k+1+ C_k+1¹a^kb+ C_k+1²a^k-1b²+...+ C_k+1^s+1a^k-sb^s+1+...+ b^k+1. Ч.т.д.

Поэтому числа C_n^r называются биномиальными коэффициентами.

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

Рассмотрим некоторые такие задачи (на конкретных множествах).

Пример 1: Клавиатура пианино содержит 88 клавиш. Сколько различных музыкальных фраз можно составить из 6 нот, если не допускать в одной фразе одинаковых звуков?

P₈₈⁶= 88^.87^.86^.85^.84^.83= 390 190 489 920.

Специально было сказано: «без повторений». Это словосочетание уже звучало в определениях 1 и 2. Попробуем отказаться от него.

Пример 2: Сколько различных музыкальных фраз можно составить из 6 нот, допуская повторение одних и тех же звуков?

Эта задача тоже на построение кортежа длины 6. Но отличается от предыдущей тем, что после выбора первой ноты для выбора второй имеется снова 88 возможностей. Таким образом общее число фраз равно

88⁶= 464 404 086 784= R₈₈⁶.

В общем виде эту задачу можно сформулировать так: |A|= n. Сколько кортежей с повторениями длины k можно составить из элементов А? Эта задача равносильна следующей: Найти |A^k|, если |A|= n. По теореме о мощности прямого произведения |A^k|= n^k. Т.е. число размещений с повторениями из n элементов по k равно R_n^k= n^k.

Пример 3: В университете есть 60 человек играющих в футбол. Из них надо составить 3 команды, т.е. отобрать 33 человека. Остальные 27 человек будут в запасе.

Решение: С₆₀³³ = С₆₀²⁷ - это более, чем миллиард миллиардов.

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

Принцип умножения: Пусть некоторый выбор может быть сделан в точности r различными способами; для каждого их этих способов некоторый второй выбор может быть сделан в точности s различными способами; для каждой пары первых двух выборов некоторый третий выбор может быть сделан в точности t способами и т.д. Тогда число способов для последовательности этих выборов получается перемножением соответствующих чисел, т.е. равно r ^. s ^. t×....

(Можно проверить на множестве, состоящем из 3 или 4 элементов).

Прежде чем привести следующий пример, дадим удобное определение.

Определение: Размещение из n элементов по n будем называть перестановкой n- элементного множества. Другими словами, перестановка- это образ n- элементного множества А при подстановке на А.

Число перестановок из n по n равно числу подстановок n- элементного множества, т.е. P_nⁿ= n! = P_n.

Пример 4: (перестановки с повторениями). Имеется 3 одноцветные пешки и 2 одноцветных коня. Сколькими способами можно их расставить в ряд?

Наклеим на фигуры разноцветные ярлыки и будем временно считать все фигуры различными. Тогда число способов расстановки в ряд пяти фигур будет P₅= 5! Но если теперь снять ярлыки, то среди 5! перестановок будут совпадающие. Совпадающими будут перестановки, отличающиеся порядком пешек, их всего P₃= 3!, и порядком коней- их P₂= 2! Значит общее число способов расстановки в ряд трех одноцветных пешек и 2 одноцветных коней равно = 10.

Можно обобщить эту задачу и показать, что число различных расположений n объектов, среди которых имеется n₁ неразличимых объектов типа 1, n₂ объектов типа 2 и т.д., n_r объектов типа r равно:

P_n(n₁, n₂,..., n_r)= = , где n₁+ n₂+...+ n_r= n.

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