Лабораторна робота №4

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ

НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ ”ЛЬВІВСЬКА ПОЛІТЕХНІКА”

Комбінаторні схеми методичні вказівки

до лабораторної роботи №4

з дисципліни ”Аналітико-синтетична переробка інформації. Частина 1”

для студентів базового напряму ”Культура”

Затверджено

на засіданні кафедри інформаційних систем та мереж

Протокол №14 від 18.05.2007р.

Львів-2008

Комбінаторні схеми: Методичні вказівки до лабораторної роботи №4 / Укл.: В.В.Литвин, Н.О.Думанський, Т.В. Шестакевич. – Львів: Видавництво Національного університету ”Львівська політехніка”, 2008. – 13 с.

Укладачі Литвин В.В., канд. техн. наук, доц.

Думанський Н.О., асистент

Шестакевич Т.В., асистент

Відповідальний за випуск Пасічник В.В., доктор техн. наук., проф.

Рецензенти Верес О.М., канд. техн. наук, доц.

Мета роботи: В даній роботі зроблений огляд типових задач комбінаторики. Знання та розуміння комбінаторних схем, вміння їх застосувати є важливим при для теоретичного аналізу текстів.

1 Теоретичні відомості

1.1Комбінаторні схеми

1.Розміщення. Нехай є алфавіт, який складається з елементів. З цих елементів складаються -членні комбінації, причому кожний з елементів може входити в комбінацію не більше одного разу і порядок елементів істотний. Такий тип комбінацій називається розміщенням. Кількість розміщень з елементів по визначається за формулою

. (1.1)

Знайдемо розміщення по два елементи, якщо алфавіт задано так: . Кількість таких розміщень знаходимо за формулою, тут : . Випишемо усі розміщення: .

2. Розміщення з повтореннями. Знову візьмемо алфавіт з елементів і будемо утворювати -членні комбінації, допускаючи повторення кожного елемента від 0 до разів. Порядок елементів залишається істотним. Такі комбінації елементів називаються розміщеннями з повтореннями, їх загальна кількість знаходиться за формулою

. (1.2)

Знайдемо розміщення з повтореннями по два елементи, якщо алфавіт задано так: . Кількість таких розміщень з повторенням знаходимо за формулою, тут : . Випишемо усі розміщення з повтореннями: .

3. Переставлення (перестановки). Нехай розміщення з різних елементів взяті по елементів, тобто кожне розміщення містить всі елементів алфавіту і відрізняється від інших тільки порядком цих елементів. Такі розміщення називаються переставленнями. Тоді з формули (1.1) можна отримати формулу для знаходження кількості переставлень. Для цього потрібно замінити на і врахувати, що . Дійсно,

. (1.3)

Знайдемо переставлення з трьох елементів, якщо алфавіт задано так: . Кількість таких переставлень знаходимо за формулою, тут : . Зауважимо, що оскільки переставлення є частинним випадком розміщень, то порядок елементів істотний. Випишемо усі переставлення: .

4. Переставлення з повтореннями. У тих випадках, коли проміж елементів, що утворюють переставлення є однакові, одержуються комбінації, які називаються переставленнями з повтореннями. Кількість цих переставлень обчислюється за формулою

, (1.4)

де – загальна кількість елементів, що входять у переставлення, а , , ..., – кількість однакових елементів відповідно першого, другого, ..., -го типів.

Визначимо, наприклад, кількість переставлень з повтореннями, які можна одержати з букв, що утворюють словоформу математика.

.

5. Сполуки. У розміщеннях з елементів по комбінації різняться або елементами, або порядком їхнього запису, або і елементами і порядком. Якщо порядок елементів не враховувати, то отримаємо сполуки з елементів по . Очевидно, що з кожної такої сполуки можна отримати розміщень, які складаються з однакових елементів і відрізняються тільки порядком елементів. Звідси та з формули (1.1), випливає, що кількість сполук з елементів по дорівнює

. (1.5)

Знайдемо сполуки по два елементи, якщо алфавіт задано так: . Кількість таких сполук знаходимо за формулою, тут : . Випишемо усі сполуки:.

6. Сполуки з повтореннями. Сполуками з елементів по з повтореннями називаються такі комбінації, які включають з різних елементів за умови, що один і той самий елемент може включатись у комбінацію декілька разів. Порядок елементів неістотний. Кількість сполук елементів по з повтореннями визначається за формулою

. (1.6)

Знайдемо сполуки з повтореннями по два елементи, якщо алфавіт задано так: . Кількість таких сполук з повтореннями знаходимо за формулою, тут : . Випишемо усі сполуки з повтореннями: .

Узагальнимо комбінаторні схеми в таблиці

№ п/п	Назва	Алфавіт	Комбінації	Порядок	Повтор.	Формула
1	Розміщення	n	m	Іст.	–
2	Розміщення з повторенням	n	m	Іст.	+
3	Перестановки	n	n	Іст.	–
4	Перестановки з повторенням	n	n	Іст.	+
5	Сполуки	n	m	Не іст.	–
6	Сполуки з повторенням	n	m	Не іст.	+