Комб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. Цей трикутник представлено у наступній таблиці №2.

С00=1

С10=1

С11=1=1

С20=1

С21=2

С22=1

С30=1

С31=3

С32=3

С33=1

С40=1

С41=4

С42=6

С43=4

С44=1

С50=1

С51=5

С52=10

С53=10

С54=5

С55=1

С60=1

С61=6

С62=15

С63=20

С64=15

С65=6

С66=1

С70=1

С71=7

С72=21

С73=35

С74=35

С75=21

С76=7

С77=1

С80=1

С81=8

С82=28

С83=56

С84=70

С85=56

С86=28

С87=8

С88=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. Побудуйте граф відношення «≥» між елементами множини Х та з’ясуйте його особливості.

⇐ Предыдущая10111213141516171819Следующая ⇒

Поделиться:

Читайте также:

Відношення еквівалентності та порядку, їх властивості. Впорядковані множини. Зв'язок відношення еквівалентності з розбиттям множини на класи, що попарно не перетинаються.
Дільники і кратні. Спільні дільники і спільні кратні. Найбільший спільний дільник (НСД) і найменше спільне кратне (НСК), їх властивості.
Еліпс. Його властивості.
Еліпс. Канонічне рівняння, властивості.
Завдання 1. Прямокутні проекції основних геометричних фігур та їх властивості.
Невід’ємні раціональні числа та їх властивості.
Поняття числової функції, способи їх задання, графік та властивості.
Числові рівності та нерівності, їх властивості.

Воспользуйтесь поиском по сайту: