Описуються поняття r-перестановок множини, r-поєднання, перестановки з повтореннями.
п.1. r-перестановки.
Визначення. r-перестановкою множини A називається кортеж з r попарно різних елементів множини A. Іноді r-перестановки називають розміщеннями без повторення.
Якщо (a, ..., a) є r-перестановка n- елементного безлічі, то r ВЈ n.
Позначення. Позначимо P (n, r) число всіх r- перестановок n-елементного безлічі, де n, rГЋN. Покладемо P (n, 0) = 1 для nГЋN0.
Теорема 1. Число всіх r-перестановок n-елементного множини, де
n, rГЋN, обчислюється за формулою
P (n, r) = n = n (n -1) ... (n - r + 1). (1)
Доказ. Перша координата r-перестановки n- елементного безлічі може бути обрана n способами, якщо перша координата обрана, то друга координата може бути обрана n-1 способами, якщо обрані перші дві координати, то третя координата може бути обрана n-2 способами і т.д. до r-ої координати включно, яка може бути обрана n-r +1 способами. З теореми 2, п.3, слід рівність (1).
Слідство 1. Нехай A і B-кінцеві множини, | A | = n, | B | = r, де
n, r ГЋN. Тоді число всіх ін'єкцій f: B В® A одно P (n, r) = n.
Доказ. Позначимо B = {b, ..., b}, ін'єкція f: B В® A може бути записана в табличній формі
,
де кортеж є r-перестановка безлічі A. Тому шукане число дорівнює P (n, r).
Визначення. Нехай A є n-елементне безліч. Перестановкою множини A називається n-перестановка безлічі A. Іншими словами, перестановка множини A це кортеж містить всі елементи множини A по одному разу.
Наслідок 2. Число всіх перестановок n-елементного безлічі одно n!.
Доказ. Шукане число дорівнює P (n, n) = n = n (n-1) ... (n-n +1) =
= n!.
Наслідок 3. Нехай A і B-кінцеві множини, | A | = | B | = n, nГЋN. Тоді число всіх Бієкція f: B В® A одно n!.
Доказ. Т.к. | A | = | B |, то кожна Бієкція f: B В® A є ін'єкцією і навпаки. По слідству 1, шукане число дорівнює P (n, n) = n!.
п.2. r-елементні підмножини (r - поєднання).
Визначення. Нехай A-кінцеве безліч. r- поєднанням безлічі A називається будь r-елементне підмножина безлічі A.
Теорема 1. Нехай A є n-елементне безліч, n, rГЋN. Справедливі твердження:
1. Число всіх r-сполучень n-елементного безлічі одно.
2. Число всіх r-елементних підмножин n-елементного безлічі одно.
Доказ. Позначимо K-число всіх r-сполучень n-елементного безлічі A. Кожне r-елементне підмножина n-елементного множини A визначає r! перестановок множини A, при цьому різні підмножини визначають різні перестановки. Тому K Г— r! - Число всіх r-перестановок множини A, рівне n. Звідси випливає, що K = n/r! ==.
Приклад 1. Кожен кортеж N, де, кодується k-елементним підмножиною множини. Тому, при фіксованому k, число всіх кортежів N, де, одно.
Приклад 2. Перерахування заворушень ступеня n. Позначимо U-множина всіх перестановок ступеня n,. Будемо вважати, що елементами перестановок є числа. Перестановка ступеня n називається безладом, якщо для всіх.
Існує тільки один безлад ступеня 2.
Існує тільки два безладу ступеня 3.
Для позначимо множину всіх перестановок ступеня n таких, що. Число всіх заворушень ступеня n дорівнює числу всіх перестановок ступеня n не належать безлічі. Позначимо число всіх заворушень ступеня n. За формулою включення-виключення
, (1)
де підсумовування ведеться по всіх кортежам Nтакім, що
. Легко бачити, що для будь-якого кортежу N, де справедливо рівність
.
При фіксованому k число всіх кортежів N, де, одно. З рівності (1) випливає, що
.
Тому
.
п.3. Перестановки з повтореннями.
Визначення. Кортеж t = (b, ..., b) називається перестановкою з повтореннями складу (n, ..., n) множини {a, ..., a}, якщо елемент a входить в tn раз, ..., a входить в tn раз, де n, ..., nГЋN,.
Позначення. Позначимо P (n, ..., n) число всіх перестановок з повтореннями складу (n, ..., n) деякого k - елементного множини, де n == n + ... + n.
Теорема 1. Для будь-якого (n, ..., n) ГЋN
P (n, ..., n) = n!/n! ... n! , Де n = n + ... + n.
Доказ. Перестановка (b, ..., b) складу (n, ..., n) множини {a, ..., a} кодується кортежем довжини k: на першому місці кортежу записано безліч тих місць в перестановці на яких розташований елемент; на другому місці кортежу записано безліч тих місць в перестановці, на яких розташований елемент; ...; на k - му місці кортежу записано безліч тих місць в перестановці, на яких розташований елемент. Перший елемент кортежу може бути вибраний способами; якщо перший елемент обраний, то другий можна вибрати способами; ...; якщо перші елементів обрані, то k-ий елемент може бути вибраний способами. За правилом твори отримуємо, що число всіх перестановок з повтореннями складу (n, ..., n) з {a, ..., a} дорівнює
P (n, ..., n) = ... =
=
Позначення. Для "n, ..., nГЋN поліноміальний коефіцієнт визначається рівностями:
якщо n + ... + n = n, то;
якщо n + ... + n В№ n, то.
Слідство 1. Нехай A і B-кінцеві безлічі такі, що | A | = n, | B | = k, (n, ..., n) ГЋN, n + ... + n = n, B = {b, ..., b}. Тоді число всіх функцій
f: A В® B таких, що | f (b) | = n для всіх i = 1, ..., k, одно.
Доказ. Нехай A = {a, ..., a}. Запишемо функцію f: A В® B в табличному вигляді.
Кортеж (f (a), ..., f (a)) є перестановка з повтореннями складу (n, ..., n) множини {b, ..., b}.
Наслідок 2. Нехай U-кінцеве безліч, | U | = n. Тоді число кортежів множин (A, ..., A) таких, що
| A | = n, ..., | A | = n,
| AГ‡A | = Г† для всіх i В№ j,
AГ€ ... Г€A = U, одно.
Доказ. По теоремі 2 п.3 число таких кортежів дорівнює
... =.
Список літератури
Е.Е. Маренич, А.С. Маренич. Вступний курс математики. Навчально-методичний посібник. 2002
В.Є. Маренич. Журнал В«АргументВ». Задачі з теорії груп.
Кострикін А.І. Введення в алгебру. Ч.1 Основи алгебри. - М.: фізмат літ-ра, 2000
Кострикін А.І. Введення в алгебру. Ч.2 Основи алгебри. - М.: фізмат літ-ра, 2000
Кострикін А.І. Введення в алгебру. Ч.3 Основні структури алгебри. - М.: фізмат літ-ра, 2000
Кострикін А.І. Збірник задач з алгебри. Вид. третє - М.: фізмат літ-ра, 2001
Для підготовки даної роботи були використані матеріали з сайту referat.ru/
