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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



3.Розглянемо множину M={a1,a2,a3,...,an}. Розглянемо над цією множиною кортеж довжини k, де k=k1+k2+k3+...+kn, причому елемент a1 - повторюється k1 раз; елемент a2 повторюється k2 раз; елемент a3 - k3 раз; нарешті, елемент an - kn разів. У комбінаториці такі кортежі називають перестановками з повтореннями, а їх число позначають символом Pk1,k2,k3,…kn i читають: число перестановок з повтореннями, в якій перший елемент повторюється k1 раз, другий - k2, третій - k3, n-ий - kn раз.

Означення: будь-який кортеж довжини k, де k=k1+k2+k3+...+kn над даною n елементною множиною М, в якому елемент a1 - повторюється k1 раз, елемент a2 повторюється k2 раз, елемент a3 - k3 раз, … елемент an - kn разів називається перестановкою довжини k (k=k1+k2+k3+...+kn) з повтореннями.

Числом перестановок з перетвореннями обчислюють за формулою: Pk1,k2,k3,…kn =( k1+k2+k3+...+kn)!/(k1!k2!k3!...kn!). Застосування цієї формули покажемо на прикладі наступної задачі.

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

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

У цій задачі є трьохелементна множина М={1, 2, 3}. Із елементів цієї множини потрібно утворити кортеж довжини k, що дорівнює k1+k2+k3, де k1=3, k2=2, k3=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=Ann. За формулою Ann=n!/(n-k)!. Отже, Рn= Ann=n!/(n-n)!=n!/0!=n!/1=n! Формула доведена.

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

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

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

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

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




Последнее изменение этой страницы: 2016-04-26; просмотров: 663; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.89.204.127 (0.008 с.)