Комбінації. Комбінації з повтореннями

Розв’язання

Розв’язання

.<

Означення 4.1.5. Нехай . Перестановкою з повтореннями з п елементів називають будь-яке впорядковання п -множини, серед елементів якої є однакові. Якщо серед елементів множини М є елементів першого типу,

елементів другого типу,

...

елементів k- го типу ,

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

Теорема 5.1.5. Має місце формула:

.

Приклад. Скільки перестановок можна зробити з літер слова “Міссісіпі”?

Оскільки літера “м” входить до слова 1 раз, літера “і” – 4 рази, “с” – 3 рази, “п” – 1 раз, а всіх літер у слові 9, то

<

У тих випадках, коли нас не цікавить порядок елементів у розміщення, а лише його склад, вводять поняття комбінації..

Означення 5.1.6. Нехай , тобто множина складається з елементів, . Комбінацією без повторень з елементів по називають довільну k - підмножину множини , всі елементи якої різні.

Кількість різних комбінацій з елементів по без повторень позначають:

.

Отже, комбінація не є впорядкованою множиною, на відміну від розміщення, тобто дві різні комбінації відрізняються хоча б одним елементом.

Теорема 5.1.6. Для довільних натуральних чисел і має місце формула:

.

Теорема 5.1.7. Для виконується рівність:

.

Доведення

Серед розміщень з елементів по можна виділити класи впорядкованих k -множин, які відрізняються лише порядком розміщення одних і тих самих елементів. У кожному класі таких множин буде , а кількість різних класів – . Отже, .<

Приклад. Скільки діагоналей у правильному п -кутнику?

Дата добавления: 2014-10-17