Мат. лінгвістика 1


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
МІНІСТЕРСТВО ОСВІТИ І НАУКИ
, МОЛОДІ ТА СПОРТУ
УКРАЇНИ

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







КОМБІНАТОРНІ МЕТОДИ
У
ЛІНГВІСТИЦІ



МЕТОДИЧНІ ВКАЗІВКИ

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

з дисципліни

Математична
структурна та прикладна
лінгвістика


для
студентів
напряму
Системи штучного інтелекту





Затверджено

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

Протокол №
14
від
1.05.0
1
р.




Львів

0
1





Комбінаторні методи
у лінгвістиці:
Методичні вказівки до лабораторної
роботи №1 / Укл.:
В.А.

В
исоцька,
Ю.В.

Нікольський,
Т.В.

Шестакевич
,

Ю.М.

Щербина.

Львів: Видавництво Національного університет
у
”Львівська
політехніка”, 0
1
.


4

с.


Укладачі


Висоцька В.А., асистент





Нікольський
Ю.
В
.,
д.т.н.
,
професор
.





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





Щербина Ю.М., к
.
ф.

м.н, доц
ент
.




Відповідальний за випуск

Жежнич

П
.
І
.,
д.т.н.
,
професор
.



Рецензенти

Берко

А
.
Ю
.,
д.т.н.
,
професор
.





Чирун Л.В.,
к

.н, доц
ент
.



3

ЗМІСТ


Вступ
................................
................................
................................
................................
...
4

1

ТЕОРЕТИЧНІ ВІДОМОСТІ
................................
................................
.....................
7

1.1

Елементи комбінаторного аналізу
................................
................................
...
7

1.1.1

Правило додав
ання
................................
................................
......................


1.1.

Правило добутку
................................
................................
..........................


1.1.3

Основне правило комбінаторики
................................
..............................
9

1.

Число різних k

елементних підмножин n

елементної множини
..............
10

1..1

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

1..

Розміщення без пов
торень
................................
................................
.......
11

1..3

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

1..4

Сполуки
................................
................................
................................
.......
1

1..5

Сполуки з
повтореннями
................................
................................
..........
13

1..6

Перестановки з повтореннями, мультимножини
................................
.
15

1.3

Впорядковане розбиття множин
................................
................................
....
16

1.4

Невпорядковане розбиття множин
................................
................................
17

1.5

Поліноміальна формула
................................
................................
...................
1

1.6

Біном Ньютона
................................
................................
................................
..
19

1.7

Інверсії
................................
................................
................................
................
0

1.

Зворотні перестановки
................................
................................
.....................




ВИСНОВКИ
................................
................................
................................
.............
3

3

КОНТРОЛЬНІ ПИТАННЯ
................................
................................
.....................
4

4

ЗАВДАННЯ
................................
................................
................................
..............
5

5

ЛІТЕРАТУРА
................................
................................
................................
...........
5

6

КОМБІНАТОРНІ СХЕМИ
................................
................................
.....................
6

7

ВИМОГИ ДО ЛАБОРАТОРНОЇ РОБОТИ
................................
..........................
7

ДОДАТОК
................................
................................
................................
........................



4


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

Вступ

Запровадження
інформаційних технологій
у сферу інтелектуальної
діяльності людини покликало до життя нову комунікативну систему людина


машина

людина, в межах якої функціонування природної мови відрізняється
від фу
нкціонування її в безпосередньому людському спілкуванні. Дослідження й
опис природної мови в нових комунікативних системах вимагає й нових методів
та підходів. Для розв’язування поставлених проблем прикладна лінгвістика
повинна, використовуючи власне лінгв
істичні дані, звертатися до багатьох
інших дисциплін

кібернетики, математики, психології, фізики, медицини. Цим
вона сприяє розширенню контактів мовознавчої науки з іншими науками і
збагаченню лінгвістики новими очними методами дослідження мови. До них
н
алежать: методи математичної статистики, математичного програмування,
булевої алгебри, імовірнісно

інформаційні методи, комбінаторні методи;
структурні методи.

У зв’язку з поширенням інтелектуальних інформаційних систем обробки
інформації та систем перекл
аду з однієї природної мови на іншу, зростає
необхідність підготовки інженерних кадрів, які володіють точними методами у
мовознавстві та можуть кваліфіковано та свідомо використовувати весь спектр
сучасного програмного забезпечення у цій галузі. Застосуван
ня математичних
методів у лінгвістиці обумовлено двома причинами.

По

перше, розвиток теорії і практики мовознавства вимагає введення все
більш точних і об’єктивних методів для аналізу мови і тексту. Разом з тим,
використання математичних прийомів при систе
матизації, вимірюванні та
інтерпретації лінгвістичного матеріалу у поєднанні з якісним аналізом
результатів дозволяє мовознавцям глибше проникнути у таємниці побудови
мови і утворення тексту.

По

друге, контакти мовознавства з іншими науками акустикою,
фіз
іологією вищої нервової діяльності, кібернетикою та обчислювальною
технікою тощо постійно розширюються і можуть існувати тільки при
використанні математичної мови, яка має високий ступінь загальності та
універсальності для різних гілок знань. Особливо нап
олегливо математизується

5

мовознавство у зв’язку з використанням природної мови в інформаційних і
управлінських системах людина

машина

людина. В існуючих системах
машинного перекладу, автоматичного анотування, людино

машинного діалогу
будь

яке повідомлення
на природній мові перекодовується в математичну мову
комп’ютера.

Застосування математичних методів у мовознавстві має на меті замінити
звичайно дифузну, інтуїтивно сформульовану і таку, що не має повного
розв’язку, лінгвістичну задачу однією або декількома
простішими, логічно
сформульованими математичними задачами, які мають
алгоритмічний

розв’язок. Таке розділення складної лінгвістичної проблеми на простіші задачі,
які алгоритмізуються, ми будемо називати
математичною експлікацією

лінгвістичного об’єкту аб
о явища.

Математична експлікація цікава не тільки з чисто пізнавальної і
теоретичної точки зору. Вона абсолютно необхідна при розв’язуванні
прикладних завдань, пов’язаних з аналізом і синтезом усної мови або
інформаційною обробкою текстів з використанням к
омп’ютера. Математична
експлікація лінгвістичних об’єктів застосовується не тільки при розв’язуванні з
допомогою комп’ютера нескладних, хоча і важливих задач такого типу, як
упорядкування частотних і алфавітних словників або послівного і пооборотного
машин
ного перекладу, але також при складанні і реалізації таких евристичних
алгоритмів штучного інтелекту, як семантичний переклад або тезаурусне
реферування тексту.

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

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


поняття предиката
.

Створення абстрактних моделей завжди було головним засобом
те
оретичного
вивчення мови. Але значення цього факту було усвідомлено лише
на початку XX століття, коли у працях основоположників так званої структурної
лінгвістики виникла концепція мови як абстрактної знакової системи, у якій
визначальна роль належить не м
атеріальній природі знаків, а співвідношенням

6

між ними. Тому засобом пізнання законів мови є побудова абстрактних моделей
її структури та їх вивчення.

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

це спеціальні р
ізновиди мови,
які вирізняються особливо чіткою структурою. Іншими словами, математика
може виявитись придатною
метамовою
для вивчення природних мов і тим
самим стати універсальною мовою лінгвістики. Саме це і відбулося з
виникненням математичної лінгвісти
ки.

У середині 50

х років XX століття визначились основні принципи
трактування лінгвістичних понять

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

З допомогою математичної лінгвістики можна вирішувати такі практичні
задачі прикладної лінгвістики:

1.

Створення і вдосконаленн
я писемності;

.

Дешифрування невідомих писемностей;

3.

Автоматичне розпізнавання та автоматичний синтез усної мови;

4.

Удосконалення засобів зв’язку шляхом оптимізації мовної
інформації;

5.

Автоматизований інформаційний пошук;

6.

Машинний переклад;

7.

Автоматичне обробленн
я текстів, записаних природними мовами;

.

Автоматичне реферування та автоматичне індексування тексту.






7


1


ТЕОРЕТИЧНІ ВІДОМОСТІ


1.1

Елементи комбінаторного аналізу


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

ти команд

уча
сниць фінальної групи? Задачі такого типу називаються
комбінаторними
, а
методи їх розв’язку


методами комбінаторного аналізу
. Оскільки
комбінаторика має справу зі скінченими множинами, то її часто називають
теорією скінчених множин
.

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

означає, що елемент
a
належить множині
A
. Множини будемо зображати переліком елементів та
розміщувати їх у фігурні дужки. Наприклад,
А
,,,
abxy
. Кількість елементів в
множині називається потужністю і записується як
A
; тут
A
4.

Нехай дано дві непорожні множини
A
і
B
. Розглянемо всі пари елементів
цих множин за умови, що перший елемент береться із множини
A
, а другий

із
множини
B
. Отримана таким чином множина називається прямим добутком
AB

множин
A
і
B
. Нагадаємо деякі властивості множин та операції над ними.

Скінчена множина

множина
зі скінченою
кількістю
елементів.




порожня множина.

U


універсальна множина.

/|
AUAxxA



доповнення множини.

,|,
ABabaAbB



прямий добуток множин.

|
ABxxAxB



об’єднання множин.

|
ABxxAxB



перетин множин.

/|
ABxxAxB



різниця множин.





1.1.1

Правило додавання

Нехай
A
і
B


скінчені множини такі, що
AB

,
Am

і
Bn

. Тоді
ABmn

.

Інтерпретація
. Якщо елемент
aA

можна вибрати
m
способами, а елемент
bB




n
способами, то вибір ел
емента
xAB

можна здійснити
mn


способами. Нехай
1
,,,
k
XXX



множини, що попарно не перетинаються,
ij
XX

, де
ij

. Тоді, відповідно, виконується рівніс
ть
1
1
k
k
ii
i
i
XX





.


1.1.

Правило добутку

Нехай
A
і
B


скінчені множини,
Am

і
Bn

, тоді
ABmn

.

Інтерпретація
. Якщо елемент
aA

можна вибрати
m
способами і якщо
після кожного такого вибору елемент
bB

можна вибрати
n
способами, то
вибір пари
,
abAB

у вказаному порядку мож
на здійснити
ABmn


способами. В цьому випадку говорять, що вибір елементів множини
A
не
залежить від способу вибору елементів множини
B
. Нехай тепер
1
,,,
k
XXX




будь

я
кі множини,
,1,
ii
Xnik

. Тоді





111
,,,|,1,.
kkiik
XXXxxxxXiknnn



Задача

Знайти кількість маршрутів із пункту
M
в пункт
N
через пункт
K
. Із
M
в
K
ведуть 5 доріг, із
K
в
N


3 дороги.

Розв’язок.
Введемо дві множини:
1345
,,,,
S



дороги із
M
в
K
,
13
,,
Tttt



дороги із
K
в
N
. Тепер дорогу із пункту
M
в пункт
N
через пункт
K
можна представити парою
,
ij
t
, де

1,,3,4,5;1,,3
ij

. Відповідно,
ST




це множина всіх доріг із
M
в
N
, кількість яких рівна
5315
ST

.

K
N
M

9


1.1.3

Основне правило комбінаторики

Розглянемо наступну зада
чу. Нехай з пункту
A
міста Києва в пункт
B

можна дістатись трьома видами транспорту: тролейбусом Т, автобусом А і
метро М, а з пункту
B
в пункт
C


ли
ше двома видами транспорту:
тролейбусом Т і автобусом А. Скількома способами можна доїхати з пункту
A
в пункт
C
міста Києва? Розв’язок цієї задачі зводиться, очевидно, до
підрахунку числа елементів в де
картовому добутку множин А, Т, М

А, Т.
Число таких елементів, як ми знаємо, дорівнює добутку числа елементів першої
множини на число елементів другої множини, тобто в нашому випадку
36

.
Отже, існує шість
способів доїхати із пункту
A
в пункт
C
. Виявляється, що за
цією простою задачею стоїть правило, яке називається
основним правилом
комбінаторики
.

Нехай необхідно виконати послідовно
k
дій. Якщо першу дію можна
виконати
1
n
способами, другу



n
способами і так далі до
k

ї дії, яку можна
виконати
k
n
способами, то всі
k
дій можна виконати
1
k
nnn


способами.


Приклади

1.

Скількома способами на першості світу з футболу можуть
розподілитися медалі, якщо у фінальній частині грають 4 команди?

Розв’язок
. Золоту медаль може одержати будь

яка з 4

х команд, т
обто
маємо 4 можливості. Срібну медаль може виграти одна з 3

х команд, а
бронзову

одна з 

х команд. За основним правилом комбінаторики, загальне
число способів розподілу медалей
431144

.

.

Скільки тризначних чисел можна скласти з циф
р
0,1,,3,4,5
, якщо:

a.

Цифри можуть повторюватися;

b.

Ні одна з цифр не повторюється двічі;

c.

Цифри непарні і можуть повторюватися.

Розв’язок

a.

Першою цифрою може бути одна із цифр
1,,3,4,5
, оскільки 0 не
може бути першою цифрою, бо
в такому випадку число не буде тризначним
буде двозначним. Якщо перша цифра вибрана, то друга може бути вибрана
шістьма способами, як і третя цифра. Отже, загальне число тризначних цифр
56610

.


10

b.

Першою цифрою може бути одна із п’яти ц
ифр


1,,3,4,5
; якщо
перша цифра вибрана, то другою може бути теж одна з п’яти цифр тут уже
враховується 0, а третя може бути вибрана чотирма способами з чотирьох цифр,
що залишилися. Отже, загальна кількість таких тризначних чисел
554100

.

c.

Першою цифрою може бути одна з трьох цифр:
1,3,5
. Другою теж
може бути одна з цих трьох цифр. Аналогічно і третя цифра може бути вибрана
трьома способами. Таким чином, загальна кількість таких чисел дорівнює
3337

.


1.

Число різних
k

елементних підмножин
n

елементної множини

Розглянемо тепер, скільки існує різних підмножин із
k
елементів в
множині, що має
n
елементів


kn

.

Т
еорема 1.
Число різних
k

елементних підмножин
n

елементної множини
становить




!
!!
k
n
n
C
knk


,

1


де функція


!131
nnn


називається
факторіалом числа n

читається
n

факторіал.


1..1

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

Задача формулюється наступним чином. Є елементи
n
різноманітних видів
1
,,...,
n
aaa
. Із них складають всі можливі комбінації довжини
k
, прич
ому
елементи в комбінації можуть повторюватись. Наприклад,
133431
aaaaaaaa



комбінація довжини . Такі комбінації називаються розміщеннями з
повторенням із
n
по
k
елементи одного виду можуть по
вторюватись.
Знайдемо загальну кількість розміщень, серед яких два розміщення вважаються
відмінними, якщо вони відрізняються один від одного чи виглядом в них
елементів, чи порядком їх слідування. При утворенні вказаних розміщень
довжини
k
на кожне місце можна поставити елемент будь

якого вигляду.
Розглянемо множини
1
,,...,
k
XXX
такі, що
11
...,,...,
kn
XXXaaa

. Тоді всі
розміщення з повтореннями складають множину
1
...
k
XXX

. За правилом
прямого доб
утку отримуємо, що загальна кількість розміщень з повтореннями із
n
по
k
дорівнює
1
...
k
k
XXXn

.


11

Задача
. Знайти кількість всіх п’ятизначних чисел.

Розв’язок
. Введемо п’ять множин:
3451
0,1,...,9,1,,...9
AAAAA

. Тоді
всі п’ятизначні числа складають прямий добуток вказаних множин
1345
AAAAA

. Згідно правила прямого добутку, кількість елементів в
множині
1345
AAAAA

складає
91010101090000

.

1..

Розміщення без повто
рень

Розглянемо
n
різних елементів
1
,,...,
n
aaa
. Скільки комбінацій довжиною
k

можна скласти з них, якщо повторення не дозволяються?. Такі розміщення
називаються розміщеннями без повторень, а
їх кількість позначають
k
n
A
два
розміщення вважаються різними, якщо вони відрізняються виглядом складових
або порядком їх розташування. При складанні таких комбінацій на перше місце
можна поставити будь

який із
n
елементів. На друге місце тепер можна
поставити лише будь

який із
1
n

елементів і т. д. Нарешті, на
k

те місце

будь

який із
1
nk

елементів. За правилом прямого добутку отримаємо
, що загальна
кількість розміщень без повторень із
n
по
k
дорівнює
1...1!/!
k
n
Annnknnk

. Нагадаємо, що
!1...1
nnn

та
0!1

.

Задача
. В хокейному турнірі беруть учас
ть 17 команд. Розігруються золота,
срібна та бронзова медалі. Скількома способами можуть бути розподілені
медалі?

Розв’язок
. 17 команд претендують на 3 місця. Тоді трійку призерів можна
вибрати способами
3
17
17!
171615400
14!
A

.

1..3

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

При утворен
ні розміщень без повторень із
n
по
k
ми отримали комбінації,
які відмінні одна від одної або складом, або порядком елементів. Але якщо
розглядати розміщення, які містять всі
n
елеме
нтів, то вони можуть відрізнятись
один від одного лише порядком розташування цих елементів. Такі розміщення
називаються перестановками із
n
елементів, а їх кількість позначається
n
P
.
Відповідно, кількість пе
рестановок дорівнює
!
n
nn
PAn

. Перестановки
1
,,...,
n


елементів
1,,...,
n
записують і в матричній формі
1
1...
...
n
n






, де верхній рядок

це порядкові номери
1,,...,
n
позицій

елементів в перестановці; нижній рядок

той же набір чисел
1,,...,
n
, взятих в
певному порядку,
j



номер елемента на
j

му місці перестановки. Порядок

1

стовпців в перестановках, записаних
в матричній формі, не є суттєвим, оскільки
в цьому випадку номер позиції кожного елементу в перестановці вказується
явно в верхньому рядку. Наприклад, перестановка


3,,4,1
із чотирьох елементів
може бути записана як
134314143
,,
341431314



і т.д.

Задача
. Скількома способами можна розставити на шаховій дошці  тур,
щоб вони не могли бити одна одну?

Розв’язок
. Умова “не могли бити” означає, що на кожній горизонталі та
вертикалі може стояти лише одна тура. Тому кожному розміщенню тур на д
ошці
відповідає перестановка
1
1...
...






. Верхній рядок перестановки

це
номери горизонталей, нижній

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

елементів:

!
P

.

1..4

Сполуки

В тих випадках, коли нас не цікавить порядок елементів в розміщенні, а
цікавить лише його склад, говорять про сполуки. Сполуками із
n
різноманітних
елементів по
k
називають всі можливі розміщення довжини
k
, утворені із цих
елементів і відмінні один від одного складом, порядок елементів не суттєвий.
Загальну кількість сполук позначають через
k
n
C
або
n
k



. Визначимо це число.
Складемо всі сполуки із
n
по
k
. Потім переставимо в кожній сполуці елементи
всіма можливими способами. Тепер ми отримали розміщення без повторень із
n

по
k
. Їх кількість дорівнює
k
n
A
. Враховуючи, що кожна сполука дає
!
k

розміщень, за правилом добутку можна записати
!
kk
nn
CkA

. Тоді
1...1
!
k
n
nnnk
C
k


або
!
!!
k
n
n
C
knk


і
knk
nn
CC


.

Задача
. Скільки різних прямокутників можна вирізати із клітинок дошки,
розмір якої
mn

?

1



3

...

n







3





...





m






13


Розв’язок
. Прямокутник однозначно визначається положенням його сторін.
Горизонтальні сторони можуть займати будь

яке із
1
m

положень. Тоді
кількість способів їх вибору дорівнює

1
m
C

. Вертикальн
і сторони можна вибрати

1
n
C

способами. За правилом прямого добутку отримаємо, що кількість
прямокутників дорівнює

11
mn
CC


.

1..5

Сполуки з повтореннями

Розглянемо елементи
n
різних видів. Кількіс
ть елементів кожного виду
необмежена. Скільки існує розміщень довжини
k
, якщо не брати до уваги
порядок елементів? Такі розміщення називаються сполуками з повтореннями,
кількість та позначення яких наступне:
1
11
knk
nnknk
HCC



. Виведемо дану
формулу.

Нехай
,,,...,
abcd


це вхідні різні типи елементів, кількість яких
n
.
Розглянемо сполуку з повтореннями
...
cbbcaccdaddaccbbb
із даних типів елементів.
Оскільки порядок елементів в сп
олуках не враховується, то розміщення можна
записати і так:
...|...|...|...|...
aaabbbcccddd
, де елементи кожного із типів
впорядковані та закінчуються вертикальною рискою, за виключенням останньої
серії елементів. Довжина такого розміщення з урахуванням вертика
льних ліній
складає
11
knnk

, де
k


кількість елементів в розміщенні;
1
n




кількість вертикальних ліній. Очевидно, що будь

яке таке
розміщення
можна
задати вибором із
1
nk

місця
1
n

місця для положення вертикальних ліній. Це
можна зробити
1
1
n
nk
C


способами. Проміжні місця між лініями заповнюються
відповідними типами елементів.

Задача
. Троє хлопців зібрали в саду 63 яблука. Скі
лькома способами вони
можуть їх розділити між собою?

Розв’язок
. Поставимо у відповідності кожному поділу яблук між хлопцями
сполуку з повтореннями наступним чином. Типами елементів в нашому випадку
будуть хлопці. Таким чином, маємо три типи елементів
,,
abc

3
n

, із яких
необхідно скласти всі можливі
розміщення
довжиною
63
k

. Наявність в
розміщенні якогось із елементів
,,
abc
відповідає приналежності даного яблука
відповідно
му хлопцеві. Порядок елементів в такому розміщені не істотний. При
поділі яблук між хлопцями не важливо, яке з них попаде тому чи іншому

14

хлопчикові. Тоді кількість способів поділити яблука між хлопцями дорівнює
6363
336313631
6564
00

HCC



.

Задача
. Знайти кі
лькість цілочисельних розв’язків системи
1
...
n
xxxk

,
0
k

,
0
j
x

,
1,,...,;1
jnn

.

Розв’язок
. Розглянемо наступну інтерпретацію розв’язку рівняння. Кожне
значення
11...1
jjjj
x

представимо як суму одиниць, кількість яких
j
x
. Індекс
у
1
j
відмічає її належність до розкладу числа
j
x
. Таким чином, ми ввели
n
типів
різних елементів
1
1,1,...,1
n
, значення кожного із них дорівнює одиниці. Тепер
будь

який розв’язок вхідного рівняння можна представити як суму, складену із
k
вибіркових одиниць множини
1
1,1,...,1
n
. Сумуючи подібні одиниці
1
j
з
однаковими індексами, можна скласти відповідні складові
j
x
розв’язку вхідного
рівняння. Дана відповідність є взаємно однозначною, звідки і випливає, що
кількість розв’язків системи рівна кількості сполук
з повтореннями
1
11
knk
nnknk
HCC



.

Задача
. Знайдемо кількість невід’ємних цілих розв’язків рівняння
13
11
xxx

.

Розв’язок
. Безпосереднє використання формули для сполук з повтореннями
дає

111111
3311113
13!113
7
11!!
HCC



.

Кількість невід’
ємних цілих розв’язків рівняння
1
...

xxxn

може бути
визначена й у випадку, коли на змінні накладено певні обмеження.

Задача
. Знайдемо кількість невід’ємних цілих розв’язків рівняння
13
11
xxx

за умов
13
1,,3
xxx

.

Розв’язок
. Очевидно, що ця задача є еквівалентною знаходженню розв’язка
рівняння у невід’ємних цілих числах
13
5
xxx

уже без обмежень. Справді,
потрібно врахувати щонайменше 1 елемент першого типу,  елементи другого
типу та 3 елеме
нти третього типу

разом
136

фіксованих елементів; отже,
1165

елементів залишиться для вільного вибору,

555
33517
7!67
1
5!!
HCC



.

Задача
. Визначимо кількість розв’язків у невід’ємних цілих числах
нерівності
13
11
xxx

.


15

Розв’язок
. Уведемо допоміжну змінну
4
x
, яка може набувати цілі невід’ємні
значення, і перейдемо до еквівалентної задачі: визначимо кількість розв’язків у
невід’ємних цілих числах рівняння
134
11
xxxx

. Отже,

111111
4411114
14!11314
364
11!3!3
HCC




.

1..6

Перестановки з повтореннями, мультимножини

Задача формулюється наступним чином. Розглядаються елементи
k
різних
видів. Скільки існує перестановок із
1
n
елементів
першого типу,

n
елементів
другого типу, ...,
k
n
елементів
k

го типу? Розглянемо, наприклад,
мультимножину

,,,,,,,,,
Maaabbcdddd

, в якому є 3 елементи
a
,
 елементи
b
, 1 елемент
c
та 4 елементи
d
. Мультимножина

це те ж саме, що і множина,
але в ній допускаються однакові елементи. Повторення елементів можна вказати
і наступним чино
м:
3,,1,4
Mabcd

. Таким чином, перестановки з
повтореннями

це перестановки елементів мультимножини. Якщо б ми
розглядали всі елементи множини
M
як різні, позначивши їх
1311134
,,,,,,,,,
aaabbcdddd
, то отримали б
10!
перестановок, але після відкидання
індексів частина з них були б однаковими. Фактично, кожна перестановка
множини
M
зустрілась би рівно
3!!1!4!

разів, оскільки в будь

якій
перестановці
M
індекси при літерах
a
можна розташувати
3!
способами, при
b



!
способами, при
c


одним способом, а при
d
, відповідно,
4!
способами.
Тому кількість перестановок множини
M
дорівнює
10!
3!!1!4!

. При застосуванні
до загального випадку ті ж викладки доводять, що кількість перестан
овок будь

якої мультимножини перестановок з повтореннями рівна поліноміальному
коефіцієнту

1
1
1
!
,,...,
,,...,
!!...!
k
k
k
n
n
Pnnn
nnn
nnn




,

де
1
...
k
nnnn



загальна кількість елементів.

Перестановки з повтореннями мають тісний зв’язок зі сполуками.
Визначимо
кількість цих перестановок наступним чином. Із всіх
n
місць
перестановки
1
n
місце займають елементи першого типу. Вибір місць для них
можна зробити
1
n
n
C
способами. Із інших
1
nn

місць елементи другого типу
займають

n
місця, які можна обрати

1
n
nn
C

способами. Ті ж пояснення показують,

16

що елементи
k

го типу можна розмістити в перестановці
11
...
k
k
n
nnnn
C


способами.
Згідно правила прямого добутку, кількість перестановок з повтореннями
дорівнює

1
111
1...
1
!
,,...,...
!!...!
k
k
n
nn
knnnnnn
k
n
PnnnCCC
nnn



.

Задача
. Скільки існує різних перестановок із букв слова “Уссурі”?

Розв’язок
.
6!
,1,1,10
!1!1!!
P
уірс


.


1.3

Впорядковане ро
збиття множин

Підрахуємо кількість розбиттів скінченої множини
S
, де
||
Sn

, на
k
різних
підмножин
1
...
k
SSSS

, які в свою чергу попарно не перетинаються,
||,1,,...,
ii
Snik

та
1
k
i
i
nn



. Послідовність різних підмножин
1
,,...,
k
SSS

розглядається як впорядкована послідовність. При формуванні впорядкованої
послідовності
1
,,...,
k
SSS
підмножину
1
S
мож
на обрати
1
n
n
C
способами,
підмножину

S
можна обрати із
1
nn

елементів

1
n
nn
C

способами і т. д., множину
k
S
можна обрати із
11
...
k
nnnn


елементів
11
...
k
k
n
nnn
C


способами. За правилом
прямого добутку отримаємо, що загальна кількість впорядкованих розбиттів
множини
S
на
k
підмножин рівна

1
111
...
1
!
...
!!...!
k
k
n
nn
nnnnnn
k
n
CCC
nnn



,

що спів
падає з кількістю
1
,,...,
k
Pnnn
перестановок з повтореннями.

Впорядковане розбиття множини
S
на підмножини
1
...
k
SSSS

, що
не перетинаються, допускає інтерпретацію в термінах “кошиків” та “шарів”.
Позна
чимо елементи вхідної множини
||
Sn

“шарами”. Під розбиттям вхідної
множини тепер множини шарів на різні
i
S
впорядковані підмножини будемо
розуміти розкладання шарів по
k
різним кошика
м впорядковані підмножини
1
,,...,
k
SSS
:
1
n
шарів покласти в кошик
1
S
,

n
шарів покласти в кошик

S
і т.д.,
k
n

покласти в
кошик
k
S
, де
1
...
k
nnnn

. Як встановлено, кількість таких
розкладень дорівнює
1
111
...
1
!
...
!!...!
k
k
n
nn
nnnnnn
k
n
CCC
nnn



.


17

Задача
. В студентській групі, яка складається із 5 людей, при виборі
старости за висунуту кандидатуру проголо
сували 19 людей, проти

3,
утримались

3. Скількома способами може бути проведено таке голосування?

Розв’язок
. Маємо три різні кошика: “за”, “проти” та “утримались”, в які
необхідно розкласти 5 шарів, відповідно 19

в першу, 3

в другу, 3

в третю.
Кількість таких розкладень визначається виразом
1933
563
5!01345
354000
19!3!3!33
CCC



.


1.4

Невпорядковане розбиття множин

Підрахуємо, скількома способами можна розбити множину
S
, де
||
Sn

, на
підмножини, серед яких для кожно
го
1,,...,
in

є
0
i
m

підмножин з
i

елементами. Тоді вірно, що
1
n
i
i
imn



. Дане розбиття дозволяє представити
вихідну множину наступним чином:
1
1
11111
...
ni
mm
mm
n
jjnjij
jjjij
SSSSS



, де
підм
ножини
ij
S


попарно не перетинаються і
1
||||...||
i
iiim
SSSi

для кожного
1,,...,
in

. Порядок підмножин в розбитті не є суттєвим. Так, наприклад,
розбиття множини


1,,3,4,5
S

вигляду

























1,3,4,5;
1,3,5,4;
5,1,3,4;
4,1,3,5

вважаються однаковими.

Позначимо кількість невпорядкованих розбиттів множини
S
через
1
,,...,
n
Nmmm
. Розглянемо схему формування впорядкованого розбиття для
представлення
1
1...
n
nmmnm

:

111111
1
3
1
1
1133
11111111...1
.........
!!
1!1!...1!!!...!...!!...!1!!...!

n
n
n
n
n
nnnmnmnmmnmmnmmnm
m
mm
m
m
mm
mmm
CCCCCCC
nn
nnnn








.

Скористаємось інтерпретацією формування впорядкованого розбиття як
розкладання
n
різних шарів по різних
1
...
n
mmm

кошиках так, що в кожний

1

із
i
m
кошик кладуть
i
шарів. Тепер відмовимось від впорядкування підмножин в
розбитті. Нехай всі кошики мають різну кількість шарів, такі кошики можна
розглядати як різні вони відрізняються кількістю шарів. В цьому випадку
впорядковані та невпорядковані розби
ття співпадають. Нехай тепер в розбитті
існує
i
m
кошиків з однаковим числом шарів. При впорядкованому розкладанні
такі кошики розглядаються як різні. Але при невпорядкованому розбитті обмін
шарами таких кошиків можна розглядати як в
ідповідну перестановку вказаних
кошиків, що не приводить до нових розкладань. Якщо кількість кошиків з
однаковим числом шарів дорівнює
i
m
, то невпорядкованих розбиттів буде в
!
i
m

раз менше, ніж впорядкованих.
Тоді загальна кількість невпорядкованих
розбиттів буде в
1
!!...!
n
mmm
разів менша, ніж кількість впорядкованих.
Відповідно,

1
1
1
!
,,...,
1!!...!!!...!
n
n
m
mm
n
n
Nmmm
nmmm

.

Задача
. Скількома способами із групи 17 людей можна сформувати 6
коаліцій по  людини і 1
коаліцію із 5 людей?

Розв’язок
. Необхідно розбити множину із 17 людей на невпорядковані
групи, що не перетинаються. Звідки шукана кількість становить

13456717
61
17!
0,6,0,0,1,0,0,...,0
!5!6!1!
N

.

Задача
. Скількома способами можна розділити колоду із 36 карт навпіл так,
щоб
в кожній пачці було по два тузи?

Розв’язок
. 4 тузи можна розбити на

4!
3
!!

різні коаліції по дві карти в
кожній невпорядковане розбиття, тобто тільки 3 способами можна розділити
тузи пополам. Далі, кожна половина будь

якого із цих тр
ьох розбиттів тузів
виконує роль різних двох “кошиків”, куди необхідно розкласти інші 3 карти.
Розкладання 3 інших карт вже буде впорядкованим, а оскільки “кошики” різні,
то число розкладань дорівнює
3!
16!16!
. Згідно правила прямого доб
утку, загальна
кількість варіантів поділу колоди пополам дорівнює

4!3!33!
!!16!16!16!16!



.


1.5

Поліноміальна формула



19

Формула

1
1
11
...
1
!
......
!!...!
k
k
n
nn
n
kk
nnnn
k
n
xxxxxx
nnn







називається поліноміальною, де сумування виконується за всіма розв’язкам
рівняння
1
...
k
nnnn

в цілих невід’ємних числах,
0,1,,...,
i
nik

. Для
доведення виконаємо множення









1111
...............
n
kkkk
n
xxxxxxxxxxxx


.

Щоб привести подібні доданки в отриманому виразі, необхідно підрахувати
кількість одночленів виду
1
1
...
k
n
nn
k
xxx
к
ожного розбиття
1
...
k
nnnn

. Для
отримання ж одночлена
1
1
...
k
n
nn
k
xxx
необхідно обрати
1
x
в якості множника в
1
n

дужках при розкритті виразу


1
...
n
k
xxx

. Це можна зр
обити
1
n
n
C
способами. Із
інших
1
nn

не розкритих дужок необхідно вибрати

x
в якості множника в

n

дужках. Це можна зробити

1
n
nn
C

способами і т
.д. Тоді кількість одночленів
1
1
...
k
n
nn
k
xxx
при розкритті дужок виразу







111
............
kkk
n
xxxxxxxxx



буде рівна числу
1
111
...
1
!
...
!!...!
k
k
n
nn
nnnnnn
k
n
CCC
nnn



впорядкованих розбиттів.


1.6

Біном Ньютона

Частковий випадок поліноміальної формули :




0
n
n
kknk
n
k
abCab





3


називається біномом Ньютона.

Розглянемо декілька задач, в основі розв’язування яких лежить біном
Ньютона.

Задача
. Довести рівність
0

n
kn
n
k
C



.


0

Розв’язок
. Використаємо формулу 3 бінома Ньютона, в якій покладемо
1
a

та
1
b

, тоді


0
1111
n
n
kknk
n
k
C




.

Задача
. Довести рівність


0
1
n
nk
kn
n
k
Cmm




.

Розв’язок
. Використаємо формулу 3, де покладемо
1
a

та
1
bm

.


Задача
. Дове
сти рівність

11
01

nn
kkn
nn
kk
CC







.

Розв’язок
. Використаємо формулу 3 бінома Ньютона, в якій покладемо
1
a

та
1
b

, тоді




0
1110
n
nk
k
n
k
C



. Групуючи додатні та від’ємні члени
рівності, встановимо


1
01
nn
kk
nn
kk
CC







. Оскільки

1
010

nn
n
kkkn
nnn
kkk
CCC







, то
кожен із доданків


0
n
k
n
k
C





та

1
1
n
k
n
k
C






складає половину числа

n
.

Задача
. Довести рівність
1
0

n
kn
n
k
kCn




.

Розв’язок
. Використаємо формулу 3 бінома Ньютона, із якої, поклавши
1
a

та
bx

, отримаємо


0
1
n
n
kk
n
k
xCx



. Диференціювання останньої рівності
дає


1
1
0
1
n
n
kk
n
k
nxkCx





. Нехай
1
x

, тоді


1
1
0
111
n
n
kk
n
k
nkC





, що доводить
задану рівність.



1.7

Інверсії


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

Нехай


1
,,...,
n
aaa


перестановка елементів множини


1,,...,
n
. Якщо
ij

, а
ij
aa

, то пара


,
ij
aa
називається інверсією перестановки. Наприклад,

1

перестановка
314
має три інверсії






3,1,3,,4,
. Кожна інверсія

це пара
елементів, які “порушують порядок”; відповідно, єдина перестановка, яка не ма
є
інверсій,

це відсортована перестановка


1,,...,
n
.

Таблицею інверсії перестановки


1
,,...,
n
aaa
називається послідовність
1
...
n
ddd
, де
j
d


кількість елементів, більших за
j
, що знаходяться зліва від
j
.
Іншими словами,
j
d


кількість інверсій, в якій другий елемент рівний
j
.
Наприклад, таблиця інверсій перестановки
5916473
буде
364010
, оскільки 5 і
9 знаходься лівіше 1; 5,9,

лівіше  і т. д. Всього 0 інверсій. За визначенням,

1
01,
dn


1
0,...,01,0
nn
dndd


.

М. Холл встановив, що таблиця інверсій єдиним чином визначає відп
овідну
перестановку. Із будь

якої таблиці інверсій
1
...
n
ddd
можна однозначно відновити
перестановку, котра породжує дану таблицю, шляхом послідовного визначення
відносного розкладу елементів
,1,...,1
nn

в цьому порядку. Н
априклад,
перестановку, що відповідає таблиці інверсій


1345679
,3,6,4,0,,,1,0
ddddddddd

,
можна побудувати наступним чином: випишемо число 9; так як

1
d

, то  стоїть
відносно 9 справа. Оскільки
7

d

, то 7 стоїть направ
о від  і 9. Так як
6

d

, то
6 стоїть направо відносно двох вже виписаних чисел; таким чином, отримали
розташування 9,,6,7. Припишемо тепер 5 зліва, так як
5
0
d

; розміщуємо 4
після вже виписаних чисел, 3

піс
ля шести виписаних чисел тобто в правий
кінець і отримаємо 5,9,,6,4,7,3. Розмістивши аналогічним чином  і 1,
прийдемо до перестановки


5,9,1,,,6,4,7,3
.

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


1,,...,
n
? Відповідь повинна бути рівна кіл
ькості можливих таблиць інверсій, а
їх легко перерахувати, оскільки
1
d
можна вибрати
n
різними способами,

d

можна незалежно від
1
d
вибрати
1
n

способами і т. д.,
n
d


одним способом.
Тоді різних таблиць інверсій
1...1!
nnn

. Таблиці інверсій перерахувати досить
легко, оскільки всі
j
d
незалежні, в той же час як елементи
j
a
перестановки
повинні всі бути різними.





1.

Зворотні перестановки

Не треба плутати інверсії перестановок із зворотними перестановками.
Звернемося знову до термінології „шарів та кошиків”. Нехай
1
,,...,
n
aaa


різні
шари, індек
си яких поєднано з їх номерами. Тоді вихідний розклад шарів
однозначно визначається відповідною перестановкою


1,,...,
en

. Нехай


1
,,...,
n




деяка перестановка номерів
1,,...,
n
, де
k



номер шару на
k

му місці. Така перестановка відповідає розташуванню шарів
1
,,...,
n
aaa

.
Згадаємо, що перестановка
1
1...
...
n
n






може бути записана в матричному
вигляді. Дана форма запису дозволяє розг
лядати перестановку в якості
оператора, котрий заміняє старі номери шарів

верхній рядок матриці

на нові
номери

нижній рядок матриці. Тоді результат двох послідовних змін


1
,,...,
n


і


1
,,...,
n


вхідної послідовності
1,,...,
n
номерів шарів
можна розглядати як операцію множення перестановок

11
1...1...
......
nn
nn






.

Впорядкуємо стовпці перестановки

у відповідності з перестановкою


1
,,...,
n


,
тобто

1
1
1
...
1...
...
...
n
n
n
n












.
Тоді

можна

записати
,
що
1
1
1
11
...
1...
1...1...
...
...
......
n
n
n
nn
n
nn

















.
Цій перестановці відповідає розташування шарів
1
,,...,
n
aaa

, де значення
k
k





це номер шару на
k

му місці.

Зворотною до пере
становки
1
1...
...
n
n






називається перестановка
1
1
111
1
1...
...
1...
...
n
n
n
n












, яка отримується, якщо в кінцевій
перестановці поміняти місцями рядки, а потім впорядкувати стовпці в
зростаючому порядку за верхніми елементами, тобто


1111
1
,,...,
n



. Ясно,
що послідовна зміна порядку шарів згідно перестановкам


1
,,...,
n


та

3

зворотної


1111
1
,,...,
n



приводить до їх вихідного розкладу, тобто до
відповідної перестановки

1
1
1...
...
1...
1...
1...
...
n
n
n
n
e
n
n












.

Наприклад, зворотною до перестановки


5,9,1,,,6,4,7,3
буде перестановка


3,5,9,7,1,6,,4,
, оскільки
59164731345679
13456793597164




.





ВИСНОВКИ


Виділимо шість основних комбінаторних схем.

.1. Розміщення.
Нехай є алфавіт, який складається з
n
елементів. З цих
елементів складаються
m

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

елементів по
m
визначається за формулою:











!
!
1

1
m
n
n
m
n
n
n
n
A
m
n








.

4

.. Розміщення з повтореннями.
Знову візьмемо алфавіт з
n
елементів і
будем
о утворювати
m

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



m
m
n
n
A

~
.

5

.3. Перестановки.
Нехай розміщення з
n
різних елементів взяті по
n

елементів, тобто кожне розміщення містить всі
n
елементів алфавіт
у і
відрізняється від інших тільки порядком цих елементів. Такі розміщення
називаються
перестановками
. Тоді з формули 4 можна отримати формулу для
знаходження кількості перестановок. Для цього потрібно замінити
m
на
n
і
врахувати, що
1
!
0

. Дійсно,





!
!
!
n
n
n
n
A
P
n
n
n




.

6


4

Визначимо, наприклад, скільки речень можна скласти з трьох слів:
сьогодні, іде, дощ. Кількість речень тут дорівнює кількості перестановок з трьох
елементів:
6
3

3



P
.

Зауважимо, що оскільки перестановка є частинним випадком розміщень, то
порядок елементів істотний.

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




!
!
!
!
,
,
,

1

1
k
k
n
n
n
n
n
n
n
n




,

7

де
n


загальна кількість елементів, що входять у перестановку, а
1
n
,

n
, ...,
k
n


кількість однакових елементів відповідно першого, другого, ...,
k

го типів.

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



00
151
10
9

7
6
5
!

!

!
3
!
10
1
,
1
,
1
,

,

,
3
10










P
.

.5. Сполуки.
У розміщеннях з
n
елементів по
m
комбінації різняться або
елементами, або порядком їхнього запису, або і елементами і порядком. Якщо
порядок елементів не враховувати, то отримаємо
сполуки
з
n
елементів по
m
.
Очевидно, що з кожної такої сполуки можна отримати
!
m
P
m

розміщень, які
складаються з однакових елементів і відрізняються тільки порядком елементів.
Звідси та з формули .1,
випливає, що кількість сполук з
n
елементів по
m

дорівнює





m
n
n
m
n
C
m
n
m
n
C




!
!
!
.



.6. Сполуки з повтореннями.

Сполуками
з
n
елементів по
m

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



m
m
n
m
n
C
H
1



.

9


3

КОНТРОЛЬНІ ПИТАННЯ



5

4.1

Що називається перестановкою
n

елементної множини?

4.

Що називається сполученням з
n
е
лементів по
m
елементів?

4.3

Що називається розміщенням з
n
елементів по
m
елементів?

4.4

Скількома способами можна розмістити три книжки на
книжковій полиці?

4.5

Скількома способами на перш
ості світу з футболу можуть
розподілитися медалі, якщо у фінальній частині грають 4 команди?

4.6

Збірна команда університету з волейболу налічує 15 чоловік.
Скільки різних варіантів повинен розглянути тренер перед грою, щоб заявити
список гравців на гру?

4.7

Скіл
ьки різних слів можна побудувати перестановкою букв в
слові “лаваш”?

4.

Студенту необхідно скласти три екзамени протягом семи днів.
Скількома способами це можна зробити?

4.9

Скількома різними способами можна розмістити п’ять
студентів в аудиторії, яка має 0 місц
ь?


4


ЗАВДАННЯ


Розв’язати завдання
, подані у додатку,

відповідно до свого порядкового
номеру у списку групи. При оформленні лабораторної роботи дотримуватись
вимог, які наведені в методичних вказівках. Оцінювання виконаної лабораторної
роботи проводиться з
гідно кількості правильно розв’язаних завдань з
відповідного варіанту. Завдання лабораторної роботи мають три рівня
складності. Оцінювання виконання завдань першого рівня в п’ятибальній
системі відповідає оцінці “задовільно”, другий рівень

“добре”, треті
й


“відмінно”.

5


ЛІТЕРАТУРА


1.

Капітонова Ю.В., Кривий С.Л., Летичевський О.А., Луцький Г.М.,
Печурін М.К. “Основи дискретної математики”, Київ: Наукова думка, 00.

.

Нікольський Ю.В., Пасічник В.В., Щербина Ю.М. “Дискретная
математика”, Львів: “Магнолія Плюс
”, 005.

3.

Нікольський Ю.В., Щербина Ю.М. “Збірник задач з дискретної
математики”, Львів: Видавничий центр Львівського державного університету ім.
І. Франка, 199.


6

6


КОМБІНАТОРНІ СХЕМИ



п/
п

Назва

Алфа

віт

Комбі

нації

Поря

док

Повтор.

Формула

1

Розміщення

n

m

Іст.





!
!
m
n
n
A
m
n





Розміщення з
повторенням

n

m

Іст.



mm
n
An



3

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

n

n

Іст.



!
n
P
n


4

Перестановки
з
повторенням

n

n

Іст.





!
...
!
!
!
...,
,
,

1

1
k
k
n
n
n
n
n
n
n
n
P





5

Сполуки

n

m

Не іст.





!
!
!
m
n
m
n
C
m
n



6

Сполуки з
повторенням

n

m

Не іст.



1
mm
nnm
HC



7

Впорядковане
розбиття
множин

n

m

Іст



1
111
...
1
!
...
!!...!
k
k
n
nn
nnnnnn
k
n
CCC
nnn






Непорядкова

не розбиття
множин

n

m

Не іст



1
1
1
!
,,...,
1!!...!!!...!
n
n
m
mm
n
n
Nmmm
nmmm


9

Поліноміаль

на формула

n

m

Іст



1
1
11
...
1
!
......
!!...!
k
k
n
nn
n
kk
nnnn
k
n
xxxxxx
nnn




10

Біном
Ньютона

n

m

Іст





0
n
n
kknk
n
k
abCab







7

7

ВИМОГИ ДО ЛАБОРАТОРНОЇ РОБОТИ


1.

Кожен студент отримує набір завдань відповідно до свого
порядкового номеру у списку групи або відповідно до номеру залікової книжки.

.

Звіт про в
иконання роботи оформля
є
ться у вигляді завдань
, програм

та розв’язку до них.

3.

Звіт акуратно оформляється на аркушах А4 та скріпля
є
ться
скріпкою
.

4.

Звіт про виконання лабораторної роботи необхідно захистити у
строго визначені терміни.

5.

Загальний принцип оформле
ння титульного листа лабораторної
роботи:



МІНІСТЕРСТВО ОСВІТИ І НАУКИ
, МОЛОДІ ТА СПОРТУ
УКРАЇНИ

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


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


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


на тему


КОМБІНАТОРНІ МЕТОДИ У ЛІНГВІСТИЦІ


Ви
конав

студент групи
СШІ

%%

Прізвище та ініціали студента


Прийняв

п
осада

Прізвище та ініціали викладача




Львів

0
1
%






ДОДАТОК

Завдання до лабораторної роботи № 1

Варіант № 1


Перший рівень

1.

Зобразити на координатній площині декартовий добуток множин
AB

та
BA

. У
задачі

b
виписати також всі елементи декартового добутку.
:,35,:,36
:,35,:,36
aAxxRxBxxRx
bAxxZxBxxZx



.

Український алфавіт складається з 33 букв. Скільки ланцюжків з


m
бук
в можна
утворити з букв цього алфавіту, якщо повторення букв дозволені? Розв’язати цю
задачу також для
3

m
.

3.

Дані натуральні числа від 1 до 0. Скількома способами можна вибрати з них 4 числа
так, щоб їх сума була парним числом?

4.

Побудуват
и розклад

а


5
xy

;
б


5
xy

; в


6
xy

; г


6
xy

.

Другий рівень

5.

Скількома способами можна поселити 1 студентів у 4 кімнати гуртожитку, поселяючи
по 3 студенти у кожній?

6.

Довести комбінаторними міркуваннями тобто використовуючи тільки визначену
кількість сполук рівн
і
ст
ь
1
11
kkk
nnn
CCC



.

7.

Яка кількість матриць можна скласти із
n
рядків та
m
стовпців з елемента
ми із
множини


0,1
?

.

Довести, що непарна кількість предметів можна обрати із
n
предметів
1

n

способами.


Третій рівень

9.

Поїзду, в котрому знаходиться
n
пасажир
ів, треба зробити
m
зупинок. Скількома
способами можуть розподілитися пасажири між цими зупинками?

10.

Скількома способами можна розділити колоду із 36 карт пополам так, щоби в кожній
пачці було по два тузи?

11.

Скількома способами можна
скласти триколірний прапор, якщо є матеріал 5 різних
кольорів? Та ж задача, якщо одна зі смуг повинна бути червоною.

1.

Запрограмувати
всі
із
перелічених вище
задач на мові
Сі або С
.



9

Завдання до лабораторної роботи № 1

Варіант № 

Перший рівень

1.

Нехай
,,,,,0,1
AabcBxyC

. Визначити:

;
;
;
.
aABC
bCBA
cCAB
dBBB





.

Український алфавіт складається з 33 букв. Скільки ланцюжків з


m
букв можна
утворити з букв цього алфавіту, якщо повторення букв не дозволені? Розв’язати цю
задачу також для
3

m
.

3.

Дані натуральні числа від 1 до 40. Скількома способами можна вибрати з них 4 числа
так, щоб їх сума була непарним числом?

4.

Визначити коефіцієнт

а при
5
xy
у розкладі


13
xy

;

б при
1411
xy
у р
озкладі


5
xy

.


Другий рівень

5.

Скількома способами можна поселити 1 студентів у 3 кімнати гуртожитку, поселяючи
по 4 студенти у кожній?

6.

Визначити
кількість
розв’язків рівняння
13
1
xxx

у невід’ємних цілих числах при
обмеженнях
13
1;;3
xxx

.

7.

Скількома способами можна скласти трьохкольоровий прапор, якщо є матеріал 5
різних кольорів? Та же задача, якщо одна із смуг повинна бути червоною.

.

Скількома способами можна посадити рядом 3 англійців, 3 французів та
3 німців так,
щоби ніяких три співвітчизника не сиділи разом?


Третій рівень

9.

Скільки можна скласти перестановок із
n
елементів, в яких дані
m
елементів не
стоять поряд в будь

якому порядку?

10.

Скількома спо
собами можна розкласти 10 книг в 5 бандеролей по  книги в кожну
порядок бандеролей не приймається до уваги?

11.

Скільки учасників у шаховому турнірі, якщо відомо, що кожний учасник зіграв з
кожним з решти, а всього було зіграно 10 партій?

1.

Запрограмувати
вс
і
із перелічених вище задач на мові
Сі або С
.




30


Завдання до лабораторної роботи № 1

Варіант № 3

Перший рівень

1.

Нехай
,,,,,,,,,,,,
AabcdeBabcdefgh

. Визначити:

;
;
/;
/.
aAB
bAB
cAB
dBA



.

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

3.

Скільки можна утворити чисел з простих дільників числа 310, які мають  різні прості
дільники?

4.

Скільки членів у розкладі


100
xy

?


Другий рівень

5.

Скількома способами можна поділити 0 спортсменів на 4 ко
манди з баскетболу по 5
чоловік у кожній?

6.

Розв

язати систему:






.
153
;


x
y
x
y
x
C
C
C

7.

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

який лист можна передати з будь

яким із 3 кур’єрів?

.

В колоді 5 карти. В скількох вип
адках при виборі із колоди 10 карт серед них будуть:

a.

рівно один туз;

b.

хоча би один туз;

c.

не менше двох тузів;

d.

рівно два тузи?


Третій рівень

9.

Скільки бітових рядків можна утворити з 4 одиниць та 1 нулів, якщо кожний рядок
обов’язково повинен починатись з 1 і
після кожної 1 має бути принаймні два 0?

10.

Скількома способами можна розкласти 9 книг в 4 бандеролі по  книги і в 1 бандероль
1 книгу порядок бандеролей не приймається до уваги?

11.

Скільки учасників у шаховому турнірі, якщо відомо, що кожний учасник зіграв
з
кожним з решти, а всього було зіграно 10 партій?

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.


31


Завдання до лабораторної роботи № 1

Варіант № 4


Перший рівень

1.

Знайти множини
A
та
B
, я
кщо
/1,5,7,;/,10;3,6,9
ABBAAB

.

.

Англійський алфавіт складається з 6 букв. Скільки ланцюжків з


m
букв можна
утворити з букв цього алфавіту, якщо повторення букв дозволені? Розв’язати цю
задачу також для
3

m
.

3.

Скільки
можна утворити чисел з простих дільників числа 460, які мають  прості
дільники?

4.

Скільки п

ятизначних чисел можна скласти з цифр 0, 1, , 3, 4, 5, якщо:



перша та остання цифри

парні;



цифри не можуть повторюватись
.

Другий рівень

5.

Визначити кількість розв
’язків рівняння
1345
1
xxxxx

, де
1345
,,,,
xxxxx



невід’ємні цілі числа такі, що:

а
1
1;
x


б
1
1,,3,4,5;
x
дляj


в
1
010;
x


6.

Доведіть:
m
n
m
n
mC
nC



1
1
.

7.

В одного студента 7 книг
, у іншого 9 різних книг. Скількома способами вони можуть
обміняти одну книгу одного на одну книгу іншого?

.

Скількома способами можна обрати 6 карт із колоди, що має 5 карти, так, щоби серед
них були карти кожної масті?

Третій рівень

9.

Визначити 5

й член ро
зкладу бінома
n
ax
a
x





, якщо відношення коефіцієнта 3

го
члена до коефіцієнта 

го члена дорівнює
11

.
У задачі члени бінома нумеруються від 1
до
1
n

:


1
0
n
n
j
j
xyT




, де


1
1
j
jnjj
jn
TCxy




10.

Скількома способами можна розкласти 9 книг в 3 бандеролі по 3 книги в кожну
порядок бандеролей не приймається до уваги?

11.

Довести, що наступні числа:


3!
3
nn
n
,



!
n
n
n
є цілими.

1.

Запрограмувати
всі
із
перелічених вище задач на мові
Сі або С
.



3


Завдання до лабораторної роботи № 1

Варіант № 5

Перший рівень

1.

A
та
B


множини. Довести
\
ABAB

.

.

Англійський алфавіт складається з 6 букв. С
кільки ланцюжків з


m
букв можна
утворити з букв цього алфавіту, якщо повторення букв не дозволені? Розв’язати цю
задачу також для
3

m
.

3.

Скількома способами можна поставити на полицю 10 книжок, якщо:

а серед них є од
ин тритомник та всі томи тритомника повинні стояти поруч у
довільному порядку?

б всі томи тритомника повинні стояти поруч у порядку зростання номерів томів?

4.

Скільки
різних рядків можна утворити з слова MISSISSIPPI, використовуючи всі
літери? Скільки з
цих
рядків починаються та закінчуються літерою
S
? У скількох таких
рядках всі 4 літери
S
стоять поруч?


Другий рівень

5.

Визначити кількість додатних цілих чисел менших за 1.000.000 таких, що сума їх цифр
дорівнює 19.

6.

Скількома способами можна скласти триколірни
й прапор, якщо є матеріал 5 різних
кольорів? Та ж задача, якщо одна зі смуг повинна бути червоною.

7.

Скільки різних словників потрібно видати, щоби можна було переводити з будь

якої із
даних
n
мов на будь

яку іншу мову цієї ж множин
и?

.

На залізо дорожній станції є
m
світлофорів. Скільки може бути подано різних
сигналів, якщо кожний світлофор має три стани: червоний, жовтий та зелений?


Третій рівень

9.

В розіграші першості світу по футболу беруть участь 0 коман
д. Яку найменшу
кількість ігор повинно бути зіграно, щоби серед будь

яких трьох команд знайшлись
дві, вже які зіграли між собою?

10.

На перші дві лінії шахової дошки виставляють білі та чорні фігури по два коня, два
слона, дві лад’ї, ферзя і короля кожного ко
льору. Скількома способами можна це
зробити.

11.

Довести, що наступні числа:


!

n
n
,




!
!1!
n
nn

є цілими.

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.




33


Завдання до лабораторної роботи № 1

Варіант №
6

Перший рівень

1.

A
та
B


множини. Довести




ABABA

.

.

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

3.

Скільки учасників у шаховому турнірі, якщо відомо, що кожний учасник зіграв з
кожним з решти, а всього було зіграно 10 партій?

4.

Із міста
A
в місто
B
ведуть сім шляхів, а із міста

B
в місто
C


три дороги. Скільки
можливих маршрутів ведуть із
A
в
C
через місто
B
?


Другий рівень

5.

Скількома способами із кол
оди 5 карт можна вийняти 10 карт, щоб серед цих карт
був:

а точно один туз?

б принаймні один туз?

в не менше двох тузів?

6.

Розв

язати рівняння:


.

7

1
3
1





x
C
C
x
x

7.

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

.

Є 17 пар різних предметів. Знайти повну кількість вибірок із цих предметів. Кожна
пара може брати участь у вибірці так, щоби або пропонувати будь

який із двох її
елементів, або н
е брати участь. Вибірки рахуються різними, якщо відрізняються один
від одного своїм складом; порядок предметів у вибірці не враховується.


Третій рівень

9.

Деяка комісія збиралась 40 разів. Кожний раз на засіданнях були присутні по 10 людей,
причому ніякі дво
є із її членів не були на засіданнях разом більше одного разу.
Довести, що кількість членів комісії більше 60.

10.

Скількома способами можна розташувати в 9 лузах 7 білих кулі та  чорних кулі?
Частина луз може бути порожніми, та лузи рахуються різними.

11.

Знайти
число цілих позитивних чисел, які не більше за 1000 і не діляться ні на одне з
чисел 6, 10 і 15.

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.





34


Завдання до лабораторної роботи № 1

Варіант № 7

Перший рівень

1.

Нехай
A
,
B
та
C


множини. Довести:

;
;
;
.
aABCABC
bABCABC
cABCABAC
dABCABAC





.

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

3.

Скількома способами можна вибрати пару однакових карт з колоди у 36 карт?

4.

Скільки слів з 7 букв, які починаються з послідовності of, можна утворити в
англійському алфавіті?


Другий рівень

5.

Скількома способами можна з
 кісток доміно можна утворити пари кісток, які можна
докласти одна до другої за правилами доміно?

6.

Знайти кількість підмножин множини


1
,,...,
n
Maaa

.

7.

У мами 5 яблук, 7 груш та 3 апельсини. Кожний день під час 15 днів підряд вона видає
синові
по одному фрукту. Скількома способами це може бути зроблено?

.

Знайти кількість способів розкладень
n
різних шарів по
m
різним кошикам.


Третій рівень

9.

В деякому закладі 5 співробітників. Довести, що із них
не можна скласти більше 30
комісій по 5 людей в кожній так, щоби ніякі дві комісії не мали більше одного
загального члена.

10.

В ліфт сіли  людей. Скількома способами вони можуть вийти на чотирьох поверхах
так, щоби на кожному поверсі вийшла принаймні одна л
юдина?

11.

Поїзду, в котрому знаходиться
n
пасажирів, треба зробити
m
зупинок. Скількома
способами можуть розподілитися пасажири між цими зупинками?

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або
С
.





35


Завдання до лабораторної роботи № 1

Варіант № 

Перший рівень

1.

Нехай
A
,
B
та
C


множини. Довести:






\\\\\
ABCACBC

.

.

Скільки слів з 7 букв, які починаються з пос
лідовності
of
, можна утворити в
англійському алфавіті? Використовуючи словник вияснити, скільки з них допущені
нормами англійської мови.

3.

Дані натуральні числа від 1 до 60. Скількома способами можна вибрати з них 6 числа
так, щоб їх сума була парним число
м?

4.

Скількома способами можна розташувати білі фігури:  коня,  слона,  тури, ферзя та
короля на першій лінії шаховій дошці?



Другий рівень

5.

Визначити кількість додатних цілих чисел менших за 1.000.000, що мають точно одну
цифру 9 і сума всіх цифр дорівню
є 13.

6.

Скількома способами можна скласти триколірний прапор, якщо є матеріал 5 різних
кольорів? Та ж задача, якщо одна зі смуг повинна бути червоною.

7.

У мами
m
яблук та
n
груш. Кожний день під час
nm

днів підряд вона видає синові
по одному фрукту. Скількома способами це можна зробити?

.

Знайти кількість способів розкладень
n
однакових шарів по
m
різним кошикам.


Третій рівень

9.

В змаган
нях по гімнастиці дві команди мали однакову кількість учасників. В
результаті, загальна сума балів, отриманих всіма учасниками, рівна 156. Скільки було
учасників, якщо кожний із них отримав оцінки тільки  або 9 балів?

10.

Визначити кількість розв’язків рівнян
ня
13
1
xxx

у невід’ємних цілих числах при
обмеженнях
13
1;;3
xxx

.

11.

Скількома способами можна поставити на полицю 10 книжок, якщо:

а серед них є один тритомник та всі томи тритомника повинні стояти поруч у
довільному поря
дку?

б всі томи тритомника повинні стояти поруч у порядку зростання номерів томів?

13.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.



36

Завдання до лабораторної роботи № 1

Варіант № 9

Перший рівень

1.

Нехай


0,,4,6,,10
A

,


0,1,,3,4,5,6
B

,


4,5,6,7,,9,10
C

. Знайти:





;
;
;
.
aABC
bABC
cABC
dABC





.

Нехай
1,,3,4,5
S

. Виписати всі розміщення з S по 3 елементи. Виписати всі
сполуки з S по 3 елементи.

3.

Скількома способами можна вибрати пару з колоди у 36 карт
і одного джокера?
Джокер утворює пару з будь

якою картою.

4.

Обчислити, скільки слів в українській мові з семи букв починаються на “за”.

Другий рівень

5.

Скількома способами можна поселити 9 студентів у 3 кімнати гуртожитку, поселяючи
по 3 студенти у кожній?

6.

Скількома способами 3 людини можуть розділити між собою 6 однакових яблук, 1
апельсин, 1 сливу, 1 лимон, 1 грушу, 1 айву і 1 фінік?

7.

Нехай задано слово КОЛОССЯ. Обчислити:

o

Скільки різних рядків можна утворити з букв слова, використовуючи усі літери?

o

Скільк
и з цих рядків не починаються літерою О?

o

У скількох рядках не стоїть разом буквосполучення ЯС?

o

Скільки з цих рядків починаються буквосполученням СО і закінчуються буквою Я?

.

Скількома способами можна розмістити
n
однакових шарів
по
m
різним кошикам при
наступних умовах:

a.

порожніх кошиків немає;

b.

в другому кошику
k
шарів;

c.

в перших
k
кошиків відповідно
1
,,...,
k
aaa
шарів?

Третій рівень

9.

Група і
з 41 студента успішно здала сесію із трьох екзаменів. Можливі оцінки: 5, 4, 3.
Довести, що, хоча б 5 студентів здали сесію з однаковими оцінками.

10.

Скількома способами можна розкласти
n
різних куль по
k
різ
них кошикам так, щоби
в перший кошик попало
1
n
куль, в другий кошик попало

n
куль і т. д., в
k

й кошик
попало
k
n
куль, де
1
...
k
nnnn

?

11.

Скі
льки тризначних чисел можна скласти з цифр
0,1,,3,4,5
, якщо:

a.

Цифри можуть повторюватися;

b.

Ні одна з цифр не повторюється двічі;

c.

Цифри непарні і можуть повторюватися.

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.



37


Завдан
ня до лабораторної роботи № 1

Варіант № 10

Перший рівень

1.

Симетричною різницею двох множин
A
та
B
називається множина, яка визначається
формулою




/
ABABAB

.

а нехай




1,3,5;1,,3
AB

. Знайти
AB

;

b нехай
A
та
B


довільні множини. Довести, що




\\
ABABBA

.

.

Обчислити кількість перестановок множини
,,,,,,
Xabcdefg

, що закінчуються
літерою
а.

3.

Скількома способами можна вибрати 5 невпорядкованих елементів з множини 3
елементів, якщо повторення дозволені?

4.

Обчислити кількість слів з 9 букв у англійській мові, які починаються з “t”.


Другий рівень

5.

Скільки різних рядків можна утворити з слова MI
SSISSIPPI, використовуючи всі
літери? Скільки з цих рядків починаються та закінчуються літерою S? У скількох таких
рядках всі 4 літери S стоять поруч?

6.

Доведіть:
1
1
1





m
n
m
n
m
n
mA
A
A
.

7.

В англійців прийнято давати дітям декілька імен. Скількома способами мо
жна назвати
дитину, якщо їй дають не більше трьох імен, а загальна кількість імен рівна
m
?

.

Скількома способами можна розмістити
1
n
червоних,

n
жовтих та
3
n
зелених шарів
по
m
різним урнам?


Третій рівень

9.

Вступник у вищий учбовий заклад повинен здати чотири іспити. Він рахує, що для
поступлення буде достатньо набрати 17 балів. Скількома способами він зможе здати
іспити, набравши не
менше 17 балів та не отримавши ні одної двійки.

10.

Скільки бітових рядків можна утворити з 4 одиниць та 1 нулів, якщо кожний рядок
обов’язково повинен починатись з 1 і після кожної 1 має бути принаймні два 0?

11.

Скільки чотиризначних чисел можна скласти з цифр
0, 1, , 3, 4, 5, якщо:



жодна цифра не повторюється більше 1 разу;



цифри можуть повторюватись;



всі цифри непарні;

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.



3


Завдання до лабораторної роботи № 1

Варіант № 11

Перший рівень

1.

Чи можна ст
верджувати, що
AB

, якщо
,,
ABC


множини, такі, що:

;
;
.
aACBC
bACBC
cACBC




.

Обчислити:
3559
1
5
610
;;;;;
AAAAAA
.

3.

Скількома способами можна вибрати 3 невпорядкованих елементи з множини 5
елементів, якщо повто
рення дозволені?

4.

Довести тотожність Паскаля
1
11
kkk
nnn
CCC



на основі алгебраїчних перетворень.


Другий рівень

5.

Множина S містить 100 елементів. Підрахувати кількість підмножин цієї множини, що
містять більше одного елемента.

6.

Скільки бітових рядк
ів можна утворити з 6 одиниць та  нулів?

7.

Скількома способами можна розташувати білі фігури:  коня,  слона,  лад’ї, ферзя та
короля на першій лінії шаховій дошці?

.

Скількома способами 3 людини можуть розділити між собою 6 однакових яблук, 1
апельсин, 1 с
ливу, 1 лимон, 1 грушу, 1 айву і 1 фінік?


Третій рівень

9.

Яких чисел більше серед першого мільйона: тих, в записі яких зустрічається 1, чи тих,
в записі яких її немає?

10.

Скільки існує натуральних
n


значних чисел, у яких цифри розта
шовані в не
спадаючому порядку?

11.

На лавці сидить 14 чоловік, серед яких три сім’ї: Петренки 4 чол., Васюки 3 чол. та
Качконоси 5 чол.. Скільки способів розсадити всіх так, щоб:



Васюки сиділи поруч у довільному порядку?



Всі родини сиділи разом, кожні з
членів родин

в довільному порядку?



Качконоси сиділи розташовані за віком?

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.


39


Завдання до лабораторної роботи № 1

Варіант № 1

Перший рівень

1.

Маємо універсальну множину
U


латинський алфавіт 6 літер
та цифри 0

9
.
Нехай


0,,4,6,,10,,,
Aabc

,


0,1,,3,4,5,6,,,
Bcdx

,


4,5,6,7,,9,10,,,
Cxyz

, D1, ,
u , j.


Знайти





;
;
;
.
aAB
bAB
cADBC
dABCD





.

Обчислити:
306
14
55
1
;;;;;
CCCCCC
.

3.

Скільки можна утворити р
ізних рядків з 6 літер з множини 6 літер, якщо повторення
дозволені?

4.

Обчислити кількість перестановок множини
,,,,,,
Xabcdefg

, що закінчуються
літерою а.


Другий рівень

5.

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

6.

Скільки учасників у шаховому турнірі, якщо відомо, що кожний учасник зіграв з
кожним з решти, а всього було зіграно 10 партій?

7.

Скількома способами можна розташувати
k
лад’їв на шаховій дошці розміром
nm


так, щоби вони не загрожували один одному, тобто так, щоби ніякі дві із них не стояли
на одній вертикалі чи горизонталі?

.

Поїзду, в котрому знаходиться
n
пасажир
ів, треба зробити
m
зупинок. Скількома
способами можуть розподілитися пасажири між цими зупинками?


Третій рівень

9.

Нехай
M


скінчена множина. Довести, що кількість підмножин цієї множини з
парним числом ел
ементів дорівнює кількості підмножин з непарним числом елементів.

10.

Скільки існує натуральних чисел, які не перевищують
10
n
, у яких цифри розташовані в
не спадаючому порядку?

11.

Визначити кількість цілочисельних розв’язків системи
13
40
xxx

,
1
3
x

,

0
x

,
3

x

.

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.


40

Завдання до лабораторної роботи № 1

Варіант № 13

Перший рівень

1.

Зобразити на коор
динатній площині декартовий добуток множин
AB

та
BA

. У
задачі

b
виписати також всі елементи декартового добутку.
:,1315,:,1316
:,1315,:,1316
aAxxRxBxxRx
bAxxZxBxxZx



.

Скількома способами можуть бути визначені п
ризові місця перше, друге, третє у
забігу 1 коней?

3.

Визначити кількість розв’язків рівняння
13
13
xxx

у невід’ємних цілих числах.

4.

Міста А та В з’єднані чотирма різними дорогами. Скількома способами можна
здійснити круговий рейс від А до
В і від В до А, якщо у рейсі від В до А обов’язково
вибирати нову дорогу?


Другий рівень

5.

Скільки бітових рядків можна утворити з 4 одиниць та 1 нулів, якщо кожний рядок
обов’язково повинен починатись з 1 і після кожної 1 має бути принаймні два 0?

6.

Дані нат
уральні числа від 1 до 30. Скількома способами можна вибрати з них 3 числа
так, щоб їх сума була парним числом?

7.

Скількома способами можна посадити
n
чоловіків та
n
жінок за круглий стіл так,
ніякі дві осо
би одного полу не сиділи рядом? Та же задача, але стіл може обертатися та
способи, які переходять при обертанні один в одне, рахуються однаковими.

.

Скількома способами можна розфарбувати квадрат, який розділений на чотири
частини, п’ятьма кольорами:

a.

припуст
ивши розмалювання різних частин в один колір;

b.

якщо різні частини розмальовувати різними кольорами?


Третій рівень

9.

Скільки слів з 7 букв, які починаються з послідовності of, можна утворити в
англійському алфавіті?

10.

Скількома способами можна розташувати
n
нулів та
k
одиниць так, щоби ніякі дві
одиниці не стояли поруч?

11.

В колоді 5 карти. В скількох випадках при виборі із колоди 10 карт серед них будуть:

а рівно один туз;

б хоча би один туз;

в не менше дво
х тузів;

г рівно два тузи?

14.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.





41


Завдання до лабораторної роботи № 1

Варіант № 14

Перший рівень

1.

Нехай
,,,,,,,0,1,
AabcdBxyzC

. Визначити:

;
;
;
.
aABC
bCBA
cCAB
dBBB





.

У групі є n чоловіків та n жінок. Скількома спо
собами вони можуть бути вишикувані у
колону так, щоб чергувались чоловік і жінка?

3.

Визначити кількість розв’язків рівняння
134
17
xxxx

у невід’ємних цілих числах.

4.

Скількома способами можуть бути визначені призові місця перше, друге, третє у

забігу 1 коней?


Другий рівень

5.

Скільки бітових рядків можна утворити з 6 одиниць та  нулів, якщо кожний рядок
обов’язково повинен починатись з 1 і після кожної 1 має бути принаймні три 0?

6.

Скількома способами можна поселити 9 студентів у 3 кімнати гурто
житку, поселяючи
по 3 студенти у кожній?

7.

На шкільному вечері присутні 1 дівчат та 15 хлопців. Скількома способами можна
обрати із них 4 пари?

.

Скількома способами можна обрати 5 номерів із 36?


Третій рівень

9.

Яка таблиця інверсій для перестановки
7145936
?

10.

Нехай задано слово ТРОТУАР. Обчислити:

o

Скільки різних рядків можна утворити з букв слова, використовуючи усі літери?

o

Скільки з цих рядків не починаються літерою О?

o

У скількох рядках разом стоїть буквосполучення ТТ?

o

У скількох рядках ра
зом стоїть буквосполучення ТУР?

o

Скільки з цих рядків не починаються буквосполученням ТТ?

11.

Компанія, яка складається із 10 сімейних пар, розбивається на 5 груп по 4 людини для
катання на шлюпці. Скількома способами можна розбити їх так, щоби в кожній
шлюпці
були два чоловіка і дві жінки?

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.





4


Завдання до лабораторної роботи № 1

Варіант № 15

Перший рівень

1.

Нехай
,,,,,,,,,,,,,,,,,,
AabcdefghBabcdefghxyz

. Визначити:

;
;
/;
/.
aAB
bAB
cAB
dBA



.

У групі є n хлопців
, m дівчат та k гуманоїдів. Скількома способами вони можуть бути
вишикувані у колону так, щоб чергувались гуманоїд, хлопець і дівчина? 
nmk



3.

Визначити кількість розв’язків рівняння
13
1
xxx

у невід’ємних цілих числ
ах при
обмеженнях
13
1;;3
xxx

.

4.

Визначити кількість членів доданків у розкладі


1
...
n
k
xxx

.


Другий рівень

5.

Скількома способами число
11
n
можна представити у вигляді трьох співмножників
представлення,
що відрізняється порядком співмножників, рахувати різними;
0
11



співмножник?

6.

Довести тотожність
0

n
kn
n
k
C



.

7.

Нехай



nn

людей садять за круглий стіл, який обертається. Два розміщення
будемо р
ахувати такими, що співпадають, якщо кожна людина має одних і тих же
сусідів в обох випадках. Скільки існує способів сісти за стіл?

.

В скількох випадках при грі в “Спортлото” вгадування 5 номерів із 36 будуть
правильно обрані:

a.

рівно 3 номера;

b.

не менше 3 н
омерів?


Третій рівень

9.

Скількома способами можна розташувати білі фігури:  коня,  слона,  тури, ферзя та
короля на першій лінії шаховій дошці?

10.

На шкільному вечері присутні 1 дівчат та 15 хлопців. Скількома способами можна
обрати із них 4 пари?

11.

Маємо
n
предметів, розміщених в ряд. Скількома способами можна обрати із них три
предмета так, щоби не брати ніяких двох сусідніх елементів?

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.




43


Завдання до лабораторної роб
оти № 1

Варіант № 16

Перший рівень

1.

Знайти множини
A
та
B
, якщо
/0,1,5,7,;/,4,10;3,6,9
ABBAAB

.

.

Міста А та В з’єднані трьома різними дорогами. Скількома способами можна
здійснити круговий рейс від А до В і від В
до А, якщо у рейсі від В до А обов’язково
вибирати нову дорогу?

3.

Визначити кількість розв’язків у невід’ємних цілих числах нерівності
13
15
xxx

.

4.

Довести, що


,

nn
CPn

.


Другий рівень

5.

Нехай множина
1,,3,...,100
S

.

а Скільки існує розміщень елементів цієї множини по 4 елементи,
що
містять 47?

б Скільки існує розміщень по 4 елементи, які одночасно містять числа 17 та 47?

в Скільки існує розміщень по 4 елементи, які містять одночасно числа 17, 47 та 73?

г Скільк
и існує розміщень по 4 елементи, які містять одночасно 17, 47, 73 та 97?

6.

Скільки чотиризначних чисел можна скласти з цифр 0, 1, , 3, 4, 5, якщо:



жодна цифра не повторюється більше 1 разу;



цифри можуть повторюватись;



всі цифри непарні;

7.

Хор складається із
10 учасників. Скількома способами можна під час трьох днів
вибрати по 6 учасників, так, щоби кожний день були різні склади хору?

.

Скільки існує різних комбінацій із 30 купюр вартістю 1,  та 5 гривень?


Третій рівень

9.

Доведіть:
1
1
1





m
n
m
n
m
n
mA
A
A
.

10.

Скільк
и слів з п’яти букв можна скласти з елементів множини


d
c
b
a
X
,
,
,

, якщо
буква
а
зустрічається у слові не більше  раз, буква
b


не більше 1 разу, буква
с


не
більше трьох раз.

11.

Нехай задано слово КОЛОССЯ. Обчислити:

o

Скільки різних рядків можна
утворити з букв слова, використовуючи усі літери?

o

Скільки з цих рядків не починаються літерою О?

o

У скількох рядках не стоїть разом буквосполучення ЯС?

o

Скільки з цих рядків починаються буквосполученням СО і закінчуються буквою Я?

1.

Запрограмувати
всі
із п
ерелічених вище задач на мові
Сі або С
.





44


Завдання до лабораторної роботи № 1

Варіант № 17

Перший рівень

1.

Нехай


0,,4,6,,10,,,
Aabc

,


0,1,,3,4,5,6,,,
Bcdx

,


4,5,6,7,,9,10,,,
Cxyz

.
Знайти:





;
;
;
.
aABC
bABC
cABC
dABC





.

Скількома способами м
ожна розмістити 6 осіб за круглим столом?

3.

Скільки бітових рядків можна утворити з 6 одиниць та  нулів?

4.

Скільки слів з 7 букв, які починаються з послідовності of, можна утворити в
англійському алфавіті?


Другий рівень

5.

З цифр 1, , 3, 4, 5, не повторюючи
їх, склали всі можливі п’ятицифрові числа. Скільки
серед цих чисел таких, які:

а починаються цифрою 3?

б не починаються цифрою 5?

в починаються з 54?

г не починаються з 543?

6.

Хор складається із 10 учасників. Скількома способами можна під час трьох днів
фестивалю вибрати по 6 учасників, так, щоб кожен день виступали різні склади хору?

7.

Скількома способами можна розподілити
3
n
різних предметів між трьома людьми та,
щоби кожний отримав
n
предметів?

.

Скількома
способами можна розфарбувати квадрат, що розділений на дев’ять частин,
чотирма кольорами таким чином, щоби в перший колір були розфарбовані 3 частини, в
другий

, в третій

3, в четвертий

1 частина?


Третій рівень

9.

Нехай задано слово ТРОТУАР. Обчислит
и:

a.

Скільки різних рядків можна утворити з букв слова, використовуючи усі літери?

b.

У скількох рядках разом стоїть буквосполучення ТУР?

c.

Скільки з цих рядків не починаються буквосполученням ТТ?

10.

Маємо
m
різних кульок та
k
різних кошиків. Скількома способами можна розмістити
предмети по кошикам, дозволяючи порожні кошики?

11.

Маємо
n
однакових речей і ще
n
різних речей. Скількома способами можна обрати із
них
n
речей? Скількома способами можна впорядкувати всі

n
речей?

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.



45


Завдання до лабораторної роботи № 1

Варіант № 1

Перший рівень

1.

Симетричною різ
ницею двох множин
A
та
B
називається множина, яка визначається
формулою




/
ABABAB

.

а нехай




1,3,5,7,9;1,,3,6,9
AB

. Знайти
AB

;

b нехай
A
та
B


довільні множини. Довести, що




\\
ABABBA

.

.

У спортивному клубі, що нараховує 0 членів, потрібно сформувати команду з 4
чоловік для бігу на дистанцію 1000 метрів.

а Скількома способами це можна зробити?

б
Скіль
ко
ма способами можна вибрати у цьому клубі 4 чоловіки для участі в естафеті
10000300500 м? черговість бігунів в естафеті важлива

3.

Із міста
A
в місто
B
ведуть сім шляхів, а із міста
B
в місто
C


три дороги. Скільки
можливих маршрутів ведуть із
A
в
C
через місто
B
?

4.

Записати розклад


4
xyz

.


Другий рівень

5.

Ро
зв’язати систему:






.
153
;


x
y
x
y
x
C
C
C

6.

Нехай задано слово КОЛОССЯ. Обчислити:

o

Скільки різних рядків можна утворити з букв слова, використовуючи усі літери?

o

Скільки з цих рядків не починаються літерою О?

o

У скількох рядках не стоїть разом буквосполучення
ЯС?

7.

Є
n
абонентів. Скількома способами можна одночасно з’єднати три пари?

.

Визначити коефіцієнт
c
в одночлені
343
13
cxxx
після розкладань виразу


10
13
xxx

та
приведення
подібних членів.


Третій рівень

9.

Скількома способами можна розподілити
3
n
різних книг між трьома людьми так,
щоби числа книг утворювали арифметичну прогресію?

10.

Маємо
m
різних кульок та
k
різних кошиків. Скількома способами можна розмістити
предмети по кошикам, не дозволяючи порожні кошики? 
Вказівка: Скористатися
правилом включення та виключення.


11.

В шаховій олімпіаді беруть участь представники
n
країн по 4
представника від кожної
країни. Скількома способами вони можуть встати в ряд так, щоби рядом з кожним був
би представник той же країни?

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.



46

Завдання до лабораторної роботи № 1

Варіант № 19

Перш
ий рівень

1.

Маємо універсальну множину
U


латинський
алфавіт 6 літер і набір цифр, а також
її підмножини:
Аg, h, , d, b, , 6, ; Bh, j, k, l, , e, w, , 3, 4, 5; Cb, m , d, h, e, f,
, 9; D1, , 3, 4, 5, 6, 7, .

З
найти





;
;
;
.
aAB
bAB
cADBC
dABCD





.

Скількома способами можна вибрати 5 невпорядкованих елементів з множини 3
елементів, якщо повторення дозволені?

3.

Скільки можна утворити різних рядків з  літер з множини 6 літер, якщо повторення
дозволені?

4.

Визначити коефіці
єнт при
35
xyz
у розкладі


10
xyz

.


Другий рівень

5.

Скільки слів з двох та трьох букв можна утворити в українському алфавіті?

6.

Дані натуральні числа від 1 до 30. Скількома способами можна вибрати з них 3 числа
так, щоб
їх сума була парним числом?

7.

Скількома способами можна скласти три пари із
n
шахістів?

.

На лавці сидить 14 чоловік, серед яких три сім’ї: Петренки 4 чол., Васюки 3 чол. та
Качконоси 5 чол.. Скільки способів розсадити всіх так,
щоб:



Васюки сиділи поруч у довільному порядку?



Всі родини сиділи разом, кожні з членів родин

в довільному порядку?



Качконоси сиділи розташовані за віком?


Третій рівень

9.

Розглядаються можливі розбиття
nk
елементів на
n
груп по
k
елементів в кожній,
причому розбиття, які відрізняються один від одного тільки порядком елементів
всередині груп та порядком розташування груп, рахуються такими, що співпали.
Скільки існує різних таких ро
збиттів?

10.

Знайти кількість способів розкладення
m
кульок по
k
кошиках так, щоб

кошиків
залишились порожніми. 
Вказівка: Скористатися правилом включення та
виключення.


11.

Дані

n
різних предметів
11
,,,,...,,
nn
aaaaaa
. Скільки існує перестановок із цих

n

предметів, в яких не стоять рядом однакові елементи?

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.



47


Зав
дання до лабораторної роботи № 1

Варіант № 0

Перший рівень

1.

Маємо універсальну множину
U


ук
раїнський алфавіт 33 літери та її підмножини:

Аа, б, с, д, е, р, ф, ш; Ва, н, о, в, м, ь, ш, д, ж; Сф, і, в, п, н, г, ш, щ; D
а, о, л,
ж, й, н, о,т
.

Знайти





;
;
;
.
aAB
bAB
cADBC
dABCD





.

Дані натуральні числа від 1 до 50. Скількома способами можна вибрати з них 3 числа
так, щоб їх сума була непарним числом?

3.

Скільки можна утворити різних рядків з 6 літер з множини 6 літер, якщо повт
орення
не дозволені?

4.

Скільки членів доданків у розкладі


100
xyz

?


Другий рівень

5.

Скількома способами число
11
n
можна представити у вигляді двох співмножників
представлення, що відрізняється порядком співмножникі
в, рахувати різними;
0
11



співмножник?

6.

Довести комбінаторними міркуваннями тобто використовуючи тільки визначену
кількість сполук рівність
1
11
kkk
nnn
CCC



;

7.

Розглядаються можливі розбиття

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

.

Скільки учасників у шаховому турнірі, якщо відомо, що
кожний учасник зіграв з
кожним з решти, а всього було зіграно 10 партій?

Третій рівень

9.

Скількома способами можна розбити 30 робітників на 3 бригади по 10 людей в кожній
бригаді? На 10 груп по 3 людини в кожній групі?

10.

Знайти число перестановок
m
шарів, в яких рівно

елементів залишаються на місці.
Вказівка: скористатися правилом включення і виключення.

11.

Знайти число способів розподілу

n
однакових шарів по двом не відмінних кошика
х.

1.

Запрограмувати
всі
із перелічених вище задач на мові
Сі або С
.



4

НАВЧАЛЬНЕ ВИДАННЯ



КОМБІНАТОРНІ МЕТОДИ У ЛІНГВІСТИЦІ


МЕТОДИЧНІ ВКАЗІВКИ

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

з дисципліни Математична структурна та прикладна лінгвістика

для студентів напряму 
Системи штучного інтелекту



Укладачі


Висоцька В.А., асистент





Нікольський
Ю.
В
.,
д.т.н.
,
професор
.





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





Щербина Ю.М., к
.
ф.

м.н, доц
ент
.


Редактор


Комп’ютерн
е
верст
ання








Приложенные файлы

  • pdf 1182316
    Размер файла: 574 kB Загрузок: 0

Добавить комментарий