Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
дискретка_1.DOC
Скачиваний:
4
Добавлен:
01.03.2025
Размер:
6 Мб
Скачать
☆

Розміщення і функціональні відображення

Позначимо через Y* множину всіх відображень f: XY.

Твердження 1. Нехай |X| = r, |Y| = n. Тоді

|Y*| = U(n, r) = nr = |Y||x|. (1)

Нехай X = {x1, ..., xr}. Тоді будь-яке відображення f: XY можна подати у вигляді впорядкованої послідовності <f(x1), ..., f(x2)> значень функції f у точках X, де f(xi)  Y. Очевидно, що цим самим установлено взаємно однозначну відповідність між множиною функціональних відображень та множиною впорядкованих вибірок із повторенням обсягу r із множини Y обсягом n (тобто множиною r-перестановок з n елементів із повторенням). Звідси випливає правильність рівності (1).

Твердження 2. Нехай |X| = r, |Y| = n. Тоді кількість всіх ін’єктивних відображень вигляду f: XY дорівнює P(n, r) = .

Наслідок 1. Для Sn – множини всіх бієктивних відображень n-елементної множини в себе маємо |Sn| = = P(n, n) = n!.

Приклад 2. Задано квадрат, розділений на чотири частини:

1

2

4

3

Скількома способами можна розфарбувати квадрат п’ятьма кольорами, якщо: а) допускається фарбування різних частин в один колір; б) різні частини зображаються різними кольорами?

Для розв’язання будемо розглядати кожне розфарбування як функціональне відображення множини номерів квадрата X = {1, 2, 3, 4} у множину кольорів Y, де |Y| = 5. Тоді використовуючи твердження 1, 2, маємо: а) 54 = 625; б) = 5! = 120.

Приклад 3. Знайти, скількома способами можна вибрати 5 номерів із 36. Розв’язком буде число (36,5)-сполучень: = 376992.

Приклад 4. У скількох випадках при грі “Спортлото” (угадування 5 номерів з 36) будуть правильно вибрані: а) рівно 3 номери; б) рівно 4 номери; в) рівно 5 номерів; г) не менше як 3 номери.

Маємо: а) 3 правильні номери із 5 можна вибрати способами, а 2 неправильних номери, що залишилися, – способами. Далі за правилом множення визначаємо, що шукана кількість дорівнює  = = 4650. В інших випадках відповідно знаходимо: б) = 155; в) 2; г) 4650 + 155 + 1 = 4806.

Розбиття

Підрахуємо кількість розбиттів скінченної множини X, де |X| = n, на k підмножин X1, ..., X­k (k  1), де = n, таких, що кожне Xi містить ni елементів, тобто

= X, Xi Xj =  при ij, |Xi| = ni, i = 1, 2, ..., k. (2)

Нехай для деяких номерів i матимемо Xi = . Кількість зазначених розбиттів при фіксованих ni­ позначимо через .

У цьому випадку набір підмножин множини X у розбитті є впорядкованим (тобто X1, ..., Xk – впорядкована послідовність множин).

Справджується рівність = .

Для утворення сполучення, що відповідає множині X1, можуть бути використані всі елементи множини X, тобто множина X1 може бути вибрана способами. Після вибору X1 множина X2 може бути вибрана способами (оскільки X2 є підмножиною множини X \ X1 та |X \ X1| = n – n1) і для будь-якого i, де 2  ik, після вибору множин X1, ..., Xi – 1 множина Xi може бути вибрана способами.

... = ... =

= = = .

Приклад. У студентській групі, яка складається з 25 осіб, при виборі старости за висунену кандидатуру проголосували 12 чоловік, проти – 10, утрималися – 3. Скількома способами могло бути проведене таке голосування?

Розв’язування. Нехай X – множина студентів у групі: X1 – множина студентів, які проголосували за висунену кандидатуру; X2 – множина студентів, які проголосували проти; X3 – множина студентів, які утрималися від голосування. Тоді |X| = 25, |X1| = 12, |X2| = 10, |X3| = 3, X = X1 X2 X3, Xi Xj = , ij, а, отже, шукана кількість дорівнює = = 1487285800.

Кількість , де ni  0, = n, дорівнює числу Pn(n1, ..., nk) переставлень n елементів зі специфікацією {n1, n2, ..., n­k}, серед елементів яких міститься n1 елементів першого типу, n2 елементів другого типу і т.д., аж до елементів k-го типу.

Підрахуємо тепер, скількома способами можна розбити множину X, де |X| = n, на підмножини, серед яких для кожного i = 1, 2, ..., n існують mi  0 підмножин з i елементами, де = n. При цьому набір множин не є впорядкованим. Так розбиття множини X = {1, 2, 3, 4, 5} вигляду

{1, 3}, {4}, {2, 5}; {4}, {2, 5}, {1, 3}; {2, 5}, {4}, {1, 3}

вважають однаковими. Позначимо кількість невпорядкованих розбиттів множини X через N(m1, ..., mn).

Справедлива рівність

N(m1, ..., mn) = .

Кожне з невпорядкованих розбиттів, розглянутих при визначені величини N(m1, ..., mn), можна, нумеруючи множини в цьому розбитті, привести m1! ... mn! способами до впорядкованих розбиттів вигляду

X1, ..., , , ..., , ..., , ..., , (1)

де

|X1| = ... = | | = 1, | | = ... = | | = 2, ...,

| =... = | | = n. (2)

При цьому об’єднанні попарно непересічних множин число розбиттівдорівнює

N(m1, ..., mn) = .

Приклад. Скількома способами з групи 25 чоловік можна сформувати 5 коаліцій по 5 чоловік.

Розв’язування. Нехай X – множина людей у групі, mi – кількість коаліцій по i осіб, де i = 1, 2, ..., 25. Тоді за умовою задачі |X| = 25, m5 = 5, mi = 0, i  {1, 2, ..., 25} \ {5}, а отже, шукана кількість дорівнюватиме N(0, 0, 0, 0, 5, 0, ..., 0) = = .