Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

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




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

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

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

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

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

Доведення.

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

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

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

У задачі мова йде про 49 елементну множину, із якої треба вибрати шестиелементні підмножини, для яких порядок розміщення елементів немає значення, а тому нам потрібно обчислити число комбінацій із 49 елементів по 6, тобто С496=(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, то Сnknn-k.

Доведення.

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

Цією формулою зручно користуватися, коли верхнє число більше половини нижнього, наприклад: С10080100100-8010020. Покажемо це на наступному прикладі: обчислити С10096100100-961004=(100•99•98•97)/(1•2•3•4)=3921225.

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

Доведення.

Для доведення цієї властивості використаємо формулу для обчислення числа комбінацій i покажемо, що права частина рівності дорівнює лівій. Сn-1kn-1k-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-1kn-1k-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)!=Сnk. Властивість доведено.

Остання доведена теорема лежить в основі побудови, так званого, трикутника Паскаля, який дає можливість обчислювати значення Сnk, знаючи Сn-1k і Сn-1k-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. Трикутник Паскаля.

В цій таблиці у крайніх лівих і правих стовпцях стоять одиниці. У першому рядку записано С00=1, у другому - С00=1 і С00=1, у третьому – ліворуч С20=1, а праворуч С21=1, а тоді, щоб обчислити С21, необхідно додати числа, які стоять у попередньому рядку. Отже, С21=1+1=2. Аналогічно можна обчислювати інші значення числа комбінацій, наприклад С53= С4243=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. Побудуйте граф відношення «≥» між елементами множини Х та з’ясуйте його особливості.

Поделиться:





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





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



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...