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

3. Розглянемо множину M={a₁,a₂,a₃,...,a_n}. Розглянемо над цією множиною кортеж довжини k, де k=k₁+k₂+k₃+...+k_n, причому елемент a₁ - повторюється k₁ раз; елемент a₂ повторюється k₂ раз; елемент a₃ - k₃ раз; нарешті, елемент a_n - k_n разів. У комбінаториці такі кортежі називають перестановками з повтореннями, а їх число позначають символом Pk₁,k_2,k_3,…k_n i читають: число перестановок з повтореннями, в якій перший елемент повторюється k₁ раз, другий - k₂, третій - k₃, n-ий - k_n раз.

Означення: будь-який кортеж довжини k, де k=k₁+k₂+k₃+...+k_n над даною n елементною множиною М, в якому елемент a₁ - повторюється k₁ раз, елемент a₂ повторюється k₂ раз, елемент a₃ - k₃ раз, … елемент a_n - k_n разів називається перестановкою довжини k (k=k₁+k₂+k₃+...+k_n) з повтореннями.

Числом перестановок з перетвореннями обчислюють за формулою: Pk₁,k_2,k_3,…k_n =(k₁+k₂+k₃+...+k_n)!/(k₁!k₂!k₃!...k_n!). Застосування цієї формули покажемо на прикладі наступної задачі.

Задача: скільки чисел можна утворити з цифр 1, 2, 3, якщо 1 - повторюється три рази, 2 - два, 3 - оди раз.

Розв’язання.

У цій задачі є трьохелементна множина М={1, 2, 3}. Із елементів цієї множини потрібно утворити кортеж довжини k, що дорівнює k₁+k₂+k₃, де k₁=3, k₂=2, k₃=1. Отже, k=3+2+1=6, тобто треба утворювати кортежі довжини 6. Це означає, що нам потрібно обчислити число перестановок з повтореннями, в яких перший елемент повторюється три рази, другий - два рази, третій - один. Таким чином, Р_3,2,1=(3+2+1)!/(3!•2!•1!)=6!/(3!•2!•1!)=(1•2•3•4•5•6)/(1•2•3•1•2•1)=720:12=60. Отже, за допомогою цифр 1, 2, 3 можна записати 60 шестицифрових чисел, в яких цифра 1 буде повторюватися цифра 2 - два рази, цифра 3 - один раз.

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

Означення: перестановкою без повторень з даних n елементів даної n елементної множини М називають розміщення без повторень із даних n елементів по n елементів.

Як відомо, розміщення - це впорядкована підмножина, а тому одне розміщення без повторень вiдрiзняється від іншого або складом елементів, або порядком їх розташування, а перестановка із даних елементів відрізняється від іншої лише порядком розташування елементів. Число перестановок без повторень позначатимемо Р_n, а цей запис читають: число перестановок з n елементів.

Теорема: число перестановок із даних n елементів обчислюють за формулою: Р_n=n!=1•2•3•...•n.

Доведення.

Згідно із означенням перестановок без повторень Р_n=A_nⁿ. За формулою A_nⁿ=n!/(n-k)!. Отже, Р_n= A_nⁿ=n!/(n-n)!=n!/0!=n!/1=n! Формула доведена.

Задача: скільки п’ятицифрових чисел можна записати за допомогою цифр 1, 3, 5, 7, 9 якщо жодна із цифр не повторюється.

Розв’язання.

У задачі є п’ятиелементна множина М={1, 3, 5, 7, 9}. Із елементів цієї множини потрібно утворювати п’ятицифрові числа, причому жодна з цифр не повторюється, а оскільки одне п’ятицифрове число від іншого, утвореного з тих самих цифр буде відрізнятися навіть при переставлянні двох цифр, то нам слід утворювати перестановки без повторень із п’яти елементів. Отже у формулі: Р_n=n!, n=5. Р₅=5!=1•2•3•4•5=120. За допомогою п’яти цифр запишемо 120 чисел.

Комбiнацiї та їх властивості.

4. Розглянемо множину М={a₁, a₂, a₃,...,a_n}, де n(М)=n, i з’ясуємо, скільки k-елементних підмножин, де k≤n можна вибрати в цій множині М. Оскільки не вказано, що ці підмножини впорядковані, то одна підмножина повинна відрізнятися від другої принаймні одним елементом, а порядок розміщення елементів не має значення. В комбінаториці такі підмножини називаються комбінаціями із даних n елементів по k елементів, а їх число позначають символом С_n^k. Цей символічний запис читають так: число комбінацій із n елементів по k елементів.

Означення: будь-яка k елементна підмножина АÌМ даної n елементної множини М називається комбінацією із n елементів по k.

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

Теорема: число комбінацій із даних n елементів по k елементів (k≤n) дорівнює дробові, чисельник якого дорівнює добутку k послідовних натуральних чисел, із яких найбільшим є n, а знаменник дорівнює добутку перших k натуральних чисел.

Символічно формула для обчислення числа комбінацій із даних n елементів по k елементів запишеться так: С_n^k=(n•(n-1)•(n-2)•...•(n-k+1))/(1•2•3•...•k)=n!/((n-k)!k!).

Доведення.

Виберемо в множині М={a₁, a₂, a₃,...,a_n} деяку k елементну підмножину А, де k≤n. Оскільки множина А містить k елементів, то із елементів цієї множини можна утворити k! перестановок. Як відомо i розміщення, i комбiнацiї являють собою підмножини даної множини, тільки розміщення - це впорядковані підмножини. Тоді розміщень із даних k елементів можна утворити більше в стільки разів, скільки можна утворити перестановок із даних k елементів. Число розміщень позначається А_n^k, число комбінацій С_n^k, число перестановок Р_n. Отже, А_n^k=С_n^k•Р_n. Звідси С_n^k=А_n^k/Р_n. Підставляючи значення числа розміщень і перестановок, одержимо дві формули для обчислення числа комбінацій із даних n е лементів по k елементів: 1) С_n^k=(n•(n-1)•(n-2)•...•(n-k+1))/(1•2•3•...•k); 2) С_n^k=n!/((n-k)!•k!). Теорему доведено.

Задача: скільки грошей потрібно витратити, щоб закупити таку кiлькiсть карточок спортлото 6 із 49, щоб, перебравши всі можливі комбiнацiї, точно вгадати 6 номерів.

Розв’язання.

У задачі мова йде про 49 елементну множину, із якої треба вибрати шестиелементні підмножини, для яких порядок розміщення елементів немає значення, а тому нам потрібно обчислити число комбінацій із 49 елементів по 6, тобто С₄₉⁶=(49•(49-1)•(49-2)•(49-3)•(49-4)•(49-5))/(1•2•3•4•5•6)=(49•48•47•46•45•44)/(1•2•3•4•5•6)=13983816. Щоб визначити необхідну кількість грошей, слід 13983816 помножити на ціну однієї карточки.

Для того, щоб спростити обчислення числа комбінацій, використовують властивості комбінацій, які спрощують ці обчислення.

Властивість 1: якщо 0<k≤n, то С_n^k=С_n^n-k.

Доведення.

Для доведення цієї властивості використаємо формулу С_n^k=n!/((n-k)!•k!) i покажемо, що права частина властивості дорівнює лівій. С_n^n-k=n!/((n-k)!•(n-(n-k))!)=n!/((n-k)!•(n-n+k)!)=n!/((n-k)!•k!)=С_n^k. Властивість доведено.

Цією формулою зручно користуватися, коли верхнє число більше половини нижнього, наприклад: С₁₀₀⁸⁰=С₁₀₀^100-80=С₁₀₀²⁰. Покажемо це на наступному прикладі: обчислити С₁₀₀⁹⁶=С₁₀₀^100-96=С₁₀₀⁴=(100•99•98•97)/(1•2•3•4)=3921225.

Властивість 2: якщо 0<k≤n, то для будь-яких k i n С_n^k=С_n-1^k+С_n-1^k-1.

Доведення.

Для доведення цієї властивості використаємо формулу для обчислення числа комбінацій i покажемо, що права частина рівності дорівнює лівій. С_n-1^k+С_n-1^k-1=((n-1))!/(k!•(n-k-1)!)+((n-1)!)/((k-1)!•(n-k)!). Зведемо ці два дроби до спільного знаменника, враховуючи, що (n-k)!=1•2•3•...•(n-k-1)•(n-k) i (n-k-1)!=1•2•3•...•(n-k-1). Верхній i нижній факторіали вiдрiзняються лише тільки одним множником - (n-k), так само k! i (k-1)! вiдрiзняються лише одним множником k, а тому спільним знаменником для двох дробів буде k!•(n-k)!, тоді маємо: С_n-1^k+С_n-1^k-1=((n-1)!•k+(n-1)!)/((k-1)!•(n-k)!•k)=((n-1)!(k+n-k))/(k!•(n-k)!)=((n-1)!•n)/(k!•(n-k)!)=n!/(k!•(n-k)!=С_n^k. Властивість доведено.

Остання доведена теорема лежить в основі побудови, так званого, трикутника Паскаля, який дає можливість обчислювати значення С_n^k, знаючи С_n-1^k і С_n-1^k-1. Цей трикутник представлено у наступній таблиці № 1.2.

 

С0^0=1

С1^0=1

С1^1=1=1

С2^0=1

С2^1=2

С2^2=1

С3^0=1

С3^1=3

С3^2=3

С3^3=1

С4^0=1

С4^1=4

С4^2=6

С4^3=4

С4^4=1

С5^0=1

С5^1=5

С5^2=10

С5^3=10

С5^4=5

С5^5=1

С6^0=1

С6^1=6

С6^2=15

С6^3=20

С6^4=15

С6^5=6

С6^6=1

С7^0=1

С7^1=7

С7^2=21

С7^3=35

С7^4=35

С7^5=21

С7^6=7

С7^7=1

С8^0=1

С8^1=8

С8^2=28

С8^3=56

С8^4=70

С8^5=56

С8^6=28

С8^7=8

С8^8=1

Таблиця № 1.2. Трикутник Паскаля.

В цій таблиці у крайніх лівих і правих стовпцях стоять одиниці. У першому рядку записано С₀⁰=1, у другому - С₀⁰=1 і С₀⁰=1, у третьому – ліворуч С₂⁰=1, а праворуч С₂¹=1, а тоді, щоб обчислити С₂¹, необхідно додати числа, які стоять у попередньому рядку. Отже, С₂¹=1+1=2. Аналогічно можна обчислювати інші значення числа комбінацій, наприклад С₅³= С₄²+С₄³=6+4=10. Напрямок руху можна показати стрілками.

 

Запитання для самоконтролю та завдання для самостійної роботи студентів за модулем 1.

1. Чому не можна дати означення поняттю „множина”?

2. Як позначають множини?

3. Як називають предмети з яких складаються множини і як їх позначають?

4. Чому множина відноситься до неозначуваних понять?

5. Як позначають множини?

6. Як називають об’єкти множин? Як вони позначаються?

7. Які існують способи задання множин?

8. Задайте переліком п’ять множин.

9. Задайте п’ять множин за допомогою характеристичної властивості.

10. Записати десять довільних множин.

11. Записати десять порожніх множин.

12. Яка множина називається підмножиною даної множини? Як це записати?

13. На які дві групи поділяються підмножини?

14. Які існують відношення між множинами? Як вони зображаються?

15. Які дві множини називаються рівними? Як це довести?

16. За якою формулою знаходиться число підмножин даної множини?

17. Що називається геометричною фігурою, колом, відрізком?

18. Чи можуть елементами множин бути множини?

19. Задайте п’ять множин і вкажіть до кожної із них підмножину.

20. Записати всі підмножини множини А={1, 2, 3, 4, 5}.

21. Задайте дві множини і утворіть їх об’єднання.

22. Утворити об’єднання множин А та В, якщо: а) А={1,2,3,4,5}, а В={а,в,с}; б) А={1, 3, 5, 7}, а В={1, 2, 3, 4, 5, 6, 7}.

23. Задайте дві множини і утворіть їх перетин.

24. Утворіть перетин множин А={1, 2, 3, 4, 5} і В={1, 2, 4, 6,}.

25. Задайте чотири множини і утворіть їх перетини.

26. Довести А Ç В = В Ç А.

27. Доведіть закони операцій об’єднання і перетину за допомогою діаграм Ейлера-Венна чи міркуваннями.

28. Знайти різницю множин: а) А={а, в, с, d, t}, В={ а, в, t}; б) А={m,n,p,k,l}, В={а, в, с, k,l}; в) Z \ N; г) А={х/х=2 n, nÎN}, В={х /х=5n, n Î N}.

29. Довести кожен закон операцій над множинами одним із способів (міркуваннями чи за допомогою діаграм Ейлера-Венна).

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

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

32. Що таке впорядкована пара? Як вона позначається? Як називаються елементи, із яких складаються пари? Які пари називаються рівними?

33. Запишіть приклади впорядкованих пар, трійок.

34. Що називається кортежем довжини к? Як їх позначають? Які кортежі називаються рівними?

35. Що називається декартовим добутком множин Х і У? Як він позначається? Як його можна задавати?

36. Утворити Х´Х, якщо Х={а,в,с}.

37. Довести самостійно властивості 3-6, які пов’язують операції об’єднання, перетину, різниці та декартового добутку множин.

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

39. Побудуйте граф відношення «менше» на множині Х={2, 3, 6, 7, 8} та з’ясуйте особливості цього графа.

40. Побудуйте граф відношення «≥» між елементами множини Х та з’ясуйте його особливості.