Наприклад, для n = 7 і k = 3 розподілу (5, 1, 1) (5 предметів у першій урні та по одному предмету в другій і третій) відповідає кортеж
(1, 1, 1, 1, 1, 0, 1, 0, 1),
а розподілу (0, 4, 3) – кортеж
(0, 1, 1, 1, 1, 0, 1, 1, 1).
У свою чергу, кортеж
(1, 1, 1, 0, 0, 1, 1, 1, 1)
–це запис розподілу, за яким у першій урні міститься 3, у другій
–0 і в третій – 4 предмети.
Кількість кортежів, що складаються з n одиниць і k – 1 нулів, обчислити неважко. Вона дорівнює кількості способів обрання n позицій серед n + k – 1 координат цих кортежів, на які буде записано одиниці (на всі інші автоматично записуються нулі). Отже, шукана кількість дорівнює C(n + k – 1, n).
До запропонованої моделі зводяться й задачі, у яких накладено певні умови на розподіли n однакових предметів по k урнах. Наприклад, якщо потрібно, щоб у результаті розподілу кожна урна містила не менше ніж t предметів (t ≥ 1), то спочатку слід у кожну урну покласти по t предметів, потім n – tk предметів, що залишились, розподіляти так як раніше. У цьому разі кількість різних розподілів
C(n – tk + k – 1, n – tk) або C(n – tk + k – 1, k – 1).
Зокрема, якщо накладено умову, щоб при кожному розподілі жодна з урн не залишилася порожньою (тобто t = 1), то кількість способів дорівнюватиме
C(n – 1, n – k) або C(n – 1, k – 1).
Урнову модель можна також використати для визначення кількості невід'ємних цілих розв'язків рівняння
x1 + x2 + … + xk = n,
де k і n – фіксовані натуральні числа. Кожному із розв'язків (t1, t2, …, tk) цього рівняння поставимо у відповідність певний розподіл n однакових предметів по k урнах, а саме розподіл, за яким у першу урну потрапило t1 предметів, у другу – t2 предметів і т. д., в останню – tk предметів. Отже, шукана кількість роз- в'язків дорівнюватиме C(n + k – 1, n).
Приклад 3.10.
1. Скількома способами можна розкласти 12 однакових куль по п'яти різних пакетах, якщо жоден пакет не має бути порожнім?
157
За наведеною вище формулою ця кількість становить
C(12 – 1, 5 – 1) = C(11, 4).
2. Скільки є способів розміщення 57 пасажирів у 5 вагонах поїзда, якщо рівно 2 вагони виявляться порожніми?
Кількість варіантів обрати 2 вагони, що будуть порожніми, дорівнює С(5, 2). А способів розміщення 57 пасажирів у 3 вагонах поїзда так, щоб серед них не було порожніх, дорівнює C(56, 2). Отже, за правилом множення шукана кількість дорів-
нює С(5, 2) C(56, 2).
3.Скількома способами можна розкласти 15 однакових куль по 5 урнах так, щоб виявилося не більше двох порожніх урн?
Множину варіантів розподілу слід розбити на ситуації, коли порожніми є дві, одна або жодна з урн.
C(5, 2)C(14, 2) + C(5, 1)C(14, 3) + C(5, 0)C(14, 4) = 3731.
Зауважимо, що C(5, 0) = 1.
4.Довести, що кількість розв'язків рівняння
x1 + x2 + … + xm = n
у натуральних числах дорівнює C(n – 1, m – 1).
Ця кількість збігається із кількістю розподілів n предметів по m урнах за умови, що жодна з урн не залишається порожньою (тут xi – кількість предметів, що потрапили в урну з номером i).
5. Скількома способами4 червоні, 4 біліта4 синікуліможнарозкластив6 різнихпакетів(деякіпакетиможутьбутипорожніми)?
Кількість способів розподілити 4 кулі одного кольору по 6 пакетах дорівнює C(9, 5), тому за правилом множення шукана кількість – (C(9, 5))3. ◄
Нехай задано n груп (сортів) елементів, кожна з яких складається з однакових між собою елементів. Сполукою (або комбі нацією) з n по k елементів із повтореннями називають невпо-
рядкований набір, що містить k елементів, причому кожний із цих елементів належить до однієї із заданих n груп.
Наприклад, якщо n = 2 і перша група елементів складається з літер a, а друга – з літер b, то з елементів цих двох груп можна утворити такі чотири сполуки по 3 елементи з повтореннями: aaa, aab, abb, bbb (підкреслимо, що у сполуках порядок розташування елементів неістотний).
158
Кількість сполук з n по k елементів з повтореннями позначатимемо C(n, k). Задачу визначення цієї кількості можна також звести до урнової моделі, а саме до задачі розподілу k однакових предметів по n урнах. Зв'язок між сполуками й розподілами встановимо таким чином. Кожному розподілу (m1, m2, …, mn) предметів по урнах поставимо у відповідність сполуку з повтореннями, що містить m1 елементів першої групи, m2 предметів другої групи і т. д., mn елементів n-ї групи. Отже,
C(n, k) = C(n + k – 1, k) = C(n + k – 1, n – 1). (3.10)
Аналогічно задачам розподілу з накладеними на них додатковими умовами можна розв'язувати й задачі обчислення кількостей сполук із повтореннями, для яких мають виконуватися певні умови. Наприклад, такою умовою може бути вимога, щоб у кожну зі сполук гарантовано входило принаймні по одному елементу з t фіксованих груп тощо.
Приклад 3.11.
1.Скількома способами можна вибрати 5 тістечок (однакових або різних) у кондитерській, де є 11 різних сортів тістечок?
За (3.10) ця кількість становить
C(11 + 5 – 1, 11 – 1) = C(15, 10).
2.Скількома способами можна вибрати 7 тістечок у кондитерській, де є 12 різних сортів тістечок за умови, що серед кожних семи обраних буде щонайменше 2 тістечка певного фіксованого сорту?
Отримавши 2 тістечка певного сорту, нам залишається вибрати ще 5, що можна зробити C(18, 11) способами. Остання кількість і буде шуканою. ◄
Завдання для самостійної роботи
1.Скількома способами можна розкласти 17 однакових куль по 6 різних пакетах, якщо жоден пакет не має бути порожнім?
2.Скільки є способів розміщення k пасажирів у n вагонах поїзда, за яких рівно m вагонів виявиться порожніми?
3.Скількома способами можна розкласти:
(а) 19 однакових куль по 7 урнах так, щоб виявилося не більше двох порожніх урн;
159
(б) 20 однакових куль по 5 урнах так, щоб у кожній урні виявилося не менше двох куль?
4. Довести, що кількість розв'язків рівняння
x1 + x2 + … + xm = n
у невід'ємних цілих числах дорівнює кількості розв'язківрівняння x1 + x2 + … + xm = n + m
унатуральних числах.
5.Скількома способами 5 червоних, 7 білих і 9 синіх куль можна розкласти в 6 різних пакетів (деякі пакети можуть бути порожніми)?
6.Скількома способами можна розмістити n білих, m червоних і k синіх куль по p урнах? Скільки є таких розміщень, де в першій урні міститься l1 білих, l2 червоних і l3 синіх куль?
7.У 2n урнах розподілено n білих і n чорних однакових куль, причому в кожній урні є принаймні одна куля. Скількома різними способами можна це зробити?
8.Скількома способами можна укласти букет з 11 квіток, якщо квітковий магазин пропонує 25 різних сортів квітів? Скільки існує таких способів, щоб у кожному букеті було обов'язково щонайменше три троянди?
9.Скількома способами можна вибрати k тістечок у кондитерській, де є n різних сортів тістечок, так, щоб серед обраних k
тістечок обов'язково були тістечка кожного із n сортів (k ≥ n)? 10. Скількома способами можна вибрати 5 літер з набору? (а) а, а, а, а, а, б, б, б, б, б; (б) а, а, а, а, а, б, б, б, б, б, в, в, в, в, в; (в) а, а, а, а, а, б, б, в, в, в.
160
Розділ 4 ТЕОРІЯГРАФІВ
Роком виникнення теорії графів вважають 1736, коли Леонард Ейлер опублікував розв'язання задачі про кенігсберзькі мости, а також знайшов загальний критерій існування ейлерового циклу в графі (див. п. 4.10). Картинка у вигляді набору точок на площині та ліній, проведених між деякими з них, стала зручною й наочною формою зображення найрізноманітніших об'єктів, процесів і явищ (див. п. 4.12). Нині теорія графів – важливий розділ дискретної математики.
4.1. Поняття графа. Способи задання графів
Нехай V – непорожня скінченна множина, а V (2) – множина всіх двохелементних підмножин (невпорядкованих пар різних елементів) множини V.
Графом (неорієнтованим графом) G називають пару множин
(V, E), де E − довільна підмножина множини V (2) (E V (2)); позначають G = (V, E).
Елементи множини V називають вершинами графа G, а елементи множини E − його ребрами. Відповідно V називають
множиною вершин, а E − множиною ребер графа G.
Традиційно ребра {v,w} записують за допомогою круглих дужок (v, w) (іноді просто vw).
Граф, що складається з однієї вершини, називають тривіаль ним, а граф G = (V, ) – порожнім.
Нехай задано граф G = (V, E). Якщо (v, w) Е, то кажуть, що
вершини v i w суміжні, інакше вершини v i w несуміжні. Якщо
е = (v, w) − ребро графа, то вершини v i w називають кінцями ребра е. У цьому разі кажуть також, що ребро е з'єднує вершини v i w. Вершину v і ребро е називають інцидентними, якщо v – кінець ребра е. Два ребра називають суміжними, якщо вони мають спільну вершину.
Існує кілька способів задання графів.