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

>Описиваются поняттяr-перестановок безлічі,r-сочетания, перестановки з повтореннями.

п.1.r- перестановки.

Визначення.r- перестановкою безлічі A називається кортеж зr попарно різних елементів безлічі A. Інодіr- перестановки називають розміщеннями без повторення.

Якщо (a, ..., a) єr- перестановка n- елементного безлічі, тоr n.

Позначення. ОзначимоP(n,r) кількість усіхr- перестановок n- елементного безлічі, де n,rN. ПоклавшиP(n, 0) = 1 дляnN0.

Теорему 1. Кількість всіхr- перестановок n- елементного безлічі, де

n,rN, обчислюється за такою формулою

>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,rN. Тоді кількість усіх ін'єкцій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,nN. Тоді кількість усіхбиекций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,rN. Справедливі затвердження:

1. Кількість всіхr- поєднань n- елементного безлічі одно .

2. Кількість всіхr-елементних підмножин n- елементного безлічі одно .

Доказ. Означимо K- кількість усіхr- поєднань n- елементного безлічі A. Кожнеr- елементне підмножина n- елементного безлічі A визначаєr! перестановок безлічі A, у своїй різні підмножини визначають різні перестановки. ТомуKr! - кількість усіх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 входить уt n раз, ..., a входить уt n раз, де n, ...,nN, .

Позначення. Означимо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, ...,nNполиномиальний коефіцієнт визначаєтьсяравенствами:

якщо 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 всім і = 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,

|>AA| = всім і j,

>A...A = U, одно.

Доказ. По теоремі 2 п.3 число таких кортежів одно

...= .

Список літератури

>Е.Е.Маренич, О.С.Маренич.Вводний курс математики.Учебно-методическое посібник. 2002

В.Є.Маренич. Журнал «Аргумент». Завдання з теорії груп.

>Кострикин А.І. Введення ЄІАС у алгебру.Ч.1 Основи алгебри. – М.:Физмат лит-ра, 2000

>Кострикин А.І. Введення ЄІАС у алгебру.Ч.2 Основи алгебри. – М.:Физмат лит-ра, 2000

>Кострикин А.І. Введення у алгебру.Ч.3 Основні структури алгебри. – М.:Физмат лит-ра, 2000

>Кострикин А.І. Збірник завдань із алгебрі. Вид. третє – М.:Физмат лит-ра, 2001

Для підготовки даної праці були використані матеріали із російського сайтуreferat/


Схожі реферати:

Навігація