Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Елементи комбінаторики
Комбінаторний аналіз займається вивченням об’єктів з деякої скінченної множини та їх властивостей. У ролі об’єктів використовуються підмножини множини . Дамо означення основних комбінаторних об’єктів.
Розміщенням елементів з множини по називається впорядкована підмножина з елементів множини . Впорядкованість означає, що суттєвим є порядок слідування елементів у множині і не допускається повторення елементів. Число всеможливих розміщень з елементів множини по позначається і обчислюється за формулою: У випадку, коли допускаються повторення одного і того ж елемента у розміщенні, число всеможливих розміщень з повтореннями з елементів множини по обчислюється: Перестановками називаються всі впорядковані підмножини з n елементів множини . Очевидно, що перестановки це частковий випадок розміщень при . Число можливих перестановок елементів множини потужності :
Сполуками (числом комбінацій або вибірками) з елементів множини називають її невпорядковані підмножини (підмножини у класичному розумінні) потужності . Число можливих сполук з n елементів множини по позначають або і формула їх обчислення: Сполуками з повторенням n елементів множини по називаються невпорядковані множини з елементів множини , які можуть повторюватись. Число всеможливих сполук із повтореннями з елементів множини по дорівнює:
Приклади застосування комбінаторики: 1. Обчислення коефіцієнтів бінома Н’ютона: . 2. Обчислення кількості членів у канонічному представленні многочлена n -го степеня від змінних: . 3. Визначення коефіцієнтів многочлена степеня від змінних на підставі, так званої, поліноміальної формули: , де . 4. Визначення знаку елемента суми при обчисленні визначника матриці n -го порядку: , де – деякий добуток елементів матриці, взятих по одному з кожного рядка і кожного стовпця; у випадку, якщо перестановка парна і , якщо перестановка є непарною.
Наведемо приклади розв'язування задач із застосуванням комбінаторики.
Приклад 1. Скільки існує варіантів вибору 5 телефонних номерів із 10 запропонованих. Розв’язування. За умовою задачі зрозуміло, що несуттєвим є порядок вибору телефонного номеру, а також неможливо вибрати один і той же номер більше одного разу. Отож, результат даної задачі буде описувати комбінаторний об'єкт, у якому неважливим є місце елемента у комірці, а також неможливі повторення одного елемента в декількох комірках. Тобто це будуть вибірки без повторень із множини 10 елементів у 5 комірок. .
Приклад 2. Скільки можна утворити телефонних номерів, що складаються із 4 цифр. Розв’язування. Для утворення телефонного номера використовують цифри {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}. Будемо вважати теоретично можливим телефонний номер із будь-яких 4 цифр. Отже, кожен номер буде містити 4 цифр із 10 можливих. За умовою задачі зрозуміло, що важливим є порядок цифр у номері, а також можливо вибрати одну й ту ж цифру більше одного разу. Отже, результат даної задачі буде описувати комбінаторний об'єкт, у якому важливим є місце елемента у комірці, а також можливі повторення одного елемента в декількох комірках. Тобто це будуть розміщення з повтореннями із множини 10 елементів у 4 комірки. Зауваження. Оскільки першою цифрою телефонного номера не може бути цифра 0, а лише будь-яка із дев’яти інших, тоді реальна кількість чотирицифрових телефонних номерів визначатиметься так:
Приклад 3. Задано множину . Встановити, скільки існує вибірок без повторень із елементів цієї множини у 5 комірок за умови, що кожна вибірка повинна містити цифри 7 і 13. Розв’язування. Оскільки кожна вибірка повинна містити цифри 7 і 13, отже дві комірки із 5 вже зайнято. У три комірки, що залишилися, ми можемо покласти будь-які цифри із множини . Оскільки необхідно визначити кількість вибірок, то неважливим є місце цифр 7 і 13 у комірках, а тому результат будемо знаходити так: .
|