![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Елементи комбінаторики
Комбінаторний аналіз займається вивченням об’єктів з деякої скінченної множини Дамо означення основних комбінаторних об’єктів.
Розміщенням елементів з множини У випадку, коли допускаються повторення одного і того ж елемента у розміщенні, число всеможливих розміщень з повтореннями з Перестановками називаються всі впорядковані підмножини з 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 вже зайнято. У три комірки, що залишилися, ми можемо покласти будь-які цифри із множини
|