У п’ятому заняттi розглядаються комбiнацiї C
k
n
з n елементiв по k еле-
ментiв. Комбiнаторний змiст чисел C
k
n
такий: це число способiв вибору iз n
елементної множини k елементної пiдмножини. В цьому ж заняттi наводяться
рiзнi рекурентнi формули i спiввiдношення для чисел C
k
n
. При розв’язаннi вiд-
повiдних задач необхiдно оволодiти рiзними методами доведення цих тото-
жностей: аналiтичним (за допомогою арифметичних операцiй над числовими
значеннями C
k
n
), комбiнаторним (за допомогою iнтерпретацiї цих спiввiдно-
шень як числа способiв вибору елементiв iз рiзних множин), геометричним
(за допомогою iнтерпретацiї шляхами шахового мiста). Також у п’ятому за-
няттi розглядається одне iз найбiльш важливих комбiнаторних спiввiдношень
– бiном Ньютона та його застосування.
Заняття 6 присвячене комбiнацiям та перестановкам з повтореннями. У
попереднiх заняттях розглядався випадок, коли елементи, якi брали участь у
перестановках чи комбiнацiях, всi були рiзнi. Якщо ж деякi елементи однаковi,
то отримуємо менше комбiнацiй чи перестановок, бо деякi з них збiгаються.
При розв’язаннi вiдповiдних задач необхiдно звернути увагу на метод заши-
фрування комбiнацiй з повтореннями за допомогою послiдовностей з нулiв та
одиниць (елементи позначаються одиницями, а рiзнi типи вiдокремлюються
один вiд одного нулем).
Заняття 7 призначене для оволодiння методом включень i виключень.
Нехай є N предметiв, деякi з яких мають властивостi a
1
, ..., a
n
. При цьому
кожний предмет може або не мати жодної з цих властивостей, або мати одну
чи кiлька властивостей. Позначимо N(a
j
a
i
...a
k
) – кiлькiсть предметiв, якi
мають властивостi a
j
,a
i
, ..., a
k
(i, можливо, ще деякi з iнших властивостей).
Тодi кiлькiсть M предметiв, якi не мають жодної iз вказаних властивостей,
дорiвнює
M = N −
1≤i
1
<i
2
<...<i
k
≤n
(−1)
k
N(a
i
1
a
i
2
...a
i
k
).
У заняттi 8 запропонованi задачi на отримання та застосування рiзнома-
нiтних формул обертання. При розв’язаннi задач цього заняття слiд прагнути
користуватись двома методами. Перший полягає у пiдстановцi виразiв для
вiдповiдних коефiцiєнтiв у праву частину рiвностi i отримання тотожностi.
Другий – у зведеннi певними замiнами пар взаємно обернених спiввiдношень,
якi доводяться, до вже вiдомих.
У заняттi 9 розглядаються задачi, якi можна звести до деякого випадково-
го блукання. Основним при їх розв’язаннi є геометрична iнтерпретацiя задачi
як деякої ламаної на координатнiй площинi. Розглядається клас ламаних з
обмеженнями. Принцип дзеркального вiдображення полягає у симетричному
вiдображеннi деякої частини ламаної вiдносно вiдповiдної прямої i у вста-
новленнi взаємно однозначної вiдповiдностi мiж класом утворених ламаних i
початковим класом. Кiлькiсть вiдображених ламаних легко порахувати, так
5