7. комбінаторика icon

7. комбінаторика




Скачати 39.71 Kb.
Назва7. комбінаторика
Дата22.06.2012
Розмір39.71 Kb.
ТипДокументи

7. КОМБІНАТОРИКА


У цім розділі вирішуються деякі задачі, пов'язані з розглядом різних комбінацій з елементів кінцевих множин М. Наприклад, якщо взяти 10 різних цифр 0, 1, 2, ... , 9 і утворювати з них комбінації, то будемо одержувати різні числа, наприклад 345, 534, 1036, 5472, 45, 54 і т.п.

Видно, що деякі з таких комбінацій відрізняються тільки порядком цифр (наприклад 345 і 534), інші - вхідними в них цифрами (наприклад 1036 і 5472), треті - розрізняються і порядком і числом цифр (наприклад 345 і 54).

Отримані комбінації задовольняють різним умовам. Залежно від правил їх утворення можна виділити три типи комбінацій: перестановки, розміщення, сполучення. Розглянемо їх окремо.


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

Визначення 7.1. Комбінації з n елементів, які відрізняються друг від друга тільки порядком елементів, називаються перестановками.

Перестановки позначаються символом Рn, де n — число елементів, що входять у кожну перестановку.

Приклад 7.1. Нехай множина М містить три букви А, В, С. Складемо всі можливі комбінації із цих букв: АВС, АСВ, ВСА, CAB, CBA, ВАС (усього 6 комбінацій). Видно, що вони відрізняються друг від друга тільки порядком розташування букв.

Дійсно, на перше місце в комбінації (перестановці) можна поставити три букви. На друге місце вже можна поставити тільки дві букви із трьох (одна посіла перше місце), а на третьому виявиться тільки одна (та, що залишилася). Виходить, 3 · 2 · 1 = 6 = P3 , але 1 · 2 · 3 = 3! Прийшли до відомого у математиці поняттю факторіала.

Визначення 7.2. Добуток всіх натуральних чисел від 1 до n включно називають n-факторіалом і пишуть: n!= 1 · 2 · 3 · ... · (n - 1) · n. Вважають, що 0! = 1 і . Основна властивість факторіала: (n + 1)! = (n +1) · n!.

Отже, число перестановок обчислюємо за формулою: Рn = n! (7.1)


7.2. Розміщення

Визначення 7.3. Комбінації з n елементів по m елементів, які відрізняються друг від друга або самими елементами або порядком елементів, називаються розміщеннями.

Розміщення позначаються символом , де n - число всіх наявних елементів, m - число елементів у кожній комбінації. Число розміщень можна обчислити по формулі:

, де 0 ? m ? n; m, nN. (7.2)

Вважають, що .

Приклад 7.2. Нехай множина M містить чотири букви А, В, С, D. Склавши всі комбінації тільки із двох букв, одержимо: АВ, AC, AD, ВА, ВР, BD, СА, СВ, CD, DA, DB, DC.

Видно, що всі отримані комбінації (їх 12) відрізняються або буквами, або їхнім порядком (комбінації ВА і АВ вважаються різними).

За формулою (7.2) , що збігається з результатом наведеного приклада. Тут кожен рядок відповідає однієї із всіх наявних букв (n=4), а число стовпців відповідає іншим буквам (n-1=3) , усього 4 · 3=12 різних комбінацій.

Формулу (7.2) можна записати у факторіальній формі:

. (7.3)

Основні властивості розміщень: 1) ; 2) .


7.3. Сполучення

Визначення 7.4. Сполученнями називаються всі можливі комбінації з n елементів по m, які відрізняються друг від друга принаймні хоча б одним елементом ( m, nN і n m).

У загальному випадку число сполучень із n елементів по m дорівнює числу розміщень з n елементів по m, діленому на число перестановок з m елементів: . Використовуючи для чисел розміщень і перестановок факторіальні формули і , одержимо формулу числа сполучень у вигляді: . (7.4)

Основні властивості сполучень: ; .

Приклад 7.3. Множина М утворена з чотирьох букв А, В, С, D. Скласти комбінації з двох букв, що відрізняються друг від друга хоча б одним елементом.

Маємо АВ, AC, AD, ВР, BD, CD. Виходить, що число сполучень з чотирьох елементів по двоє дорівнює 6. Це коротко записується так: .


^ 7.4. Розміщення з повтореннями

Розміщення з n елементів по k зображують упорядковані комбінації різних елементів множини М, |М|= n. Часто доводиться робити упорядковані комбінації з повтореннями деяких елементів. Наприклад, з множини М = {A, Б} можна зробити вісім комбінацій з трьох елементів: ААА, ААБ, АБА, БАА, БАБ, ББА, АББ, БББ. Тут n = 2, k = 3. Такі упорядковані k-комбінації називають кортежами довжини k. Два кортежі (тобто дві загальні комбінації) вважаються однаковими, якщо вони мають однакову довжину і на місцях з однаковими номерами стоять однакові елементи.

Визначення 7.5. Розміщенням з повтореннями з n елементів по k називається кортеж довжини k з n елементів.

Кількість кортежів обчислюється за формулою: . (7.5)

Розглянутий вище приклад обчислюється за формулою (7.5) .

Дійсно, після заповнення першого місця кортежу довжиною k одним з n елементів (що можливо зробити n варіантами) заповнити друге місце кортежу можна знову будь-яким елементом з усієї множини (повторюючи в одному з варіантів елемент, який знаходиться на першому місці), і так далі k разів. За правилом добутку одержимо, що .

Вправи

1. Спростити: а) ; б) .

2. Обчислити: а) 7! – 5!; б) .

3. Скільки різних варіантів хокейної команди можна скласти з 9 нападаючих, 5 захисників і 3 воротарів, якщо до складу команди повинно ввійти 3 нападаючих, 2 захисника і воротар?

4. З 10 студентів призначають двох чергових. Скількома способами можна це зробити, якщо:

1) один із призначених стає старшим;

2) старших немає?

5. Побудувати різні перестановки по 2 і по 3 елементи множини М = {1,2,3}.

6. У футбольному чемпіонаті беруть участь 15 команд вищої ліги. За умовою, що 2 останні команди її залишають, скільки варіантів завершення чемпіонату?

7. Скільки кортежів довжини 4 можна одержати з елементів множини

М = {1, 2, 3, 4}.





Схожі:

7. комбінаторика iconПроректор з навчальної роботи
Політична теорія, політична детермінанта, політичний детермінізм. Основи вивчення політичної теорії. Прояв політичної теорії в політичній...
7. комбінаторика iconРобоча програма з дисципліни Історія зарубіжних політичних вчень для студентів спеціальності
Політична теорія, політична детермінанта, політичний детермінізм. Основи вивчення політичної теорії. Прояв політичної теорії в політичній...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи