Розв’язання

.

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

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

...

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

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

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

.

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

Розв’язання

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



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

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

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

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

.

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

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

.

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

.

Доведення

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

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

Розв’язання

Кількість пар вершин в п-кутнику, серед яких одні визначають діагональ, а інші – сторону п-кутника дорівнює:

.

Оскільки всіх сторін п, кількість діагоналей визначатимемо так:

.

Приклад. Скільки натуральних дільників має число 2310=235711?

Розв’язання

Кожен дільник, який не дорівнює одиниці, має вигляд: , де .

Оскільки порядок множників у добутку – неістотний, то кожен дільник задається комбінацією з 5 по k, де . Всього дільників буде:

.

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

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

Теорема 4.1.8. Кількість різних комбінацій з повтореннями з елементів по , де і – довільні натуральні числа дорівнює:

.

Приклад. У кондитерський відділ завезли 4 види тістечок. Скількома способами можна купити 7 тістечок?

Розв’язання

.

4.1.6. Біном Ньютона. Трикутник Паскаля. Властивості біноміальних коефіцієнтів

З елементарної математики відомі формули скороченого множення:

.

Ці формули можна записати і так:

.

Очевидно, існує загальна закономірність.

Теорема 4.1.9. Справедлива рівність:

.

Цю рівність називають біномом Ньютона.

Біноміальні коефіцієнти можна подати у вигляді трикутної таблиці, яку називають трикутником Паскаля:

1						1						п=1
1					2		1					п=2
1			3			3			1			п=3
1		4			6		4			1		п=4
1	5			10		10		5			1	п=5
...

У п-му рядку трикутника Паскаля кожен коефіцієнт розкладу, крім двох крайніх, що дорівнюють 1, – це сума відповідних коефіцієнтів із попереднього рядка.

Узагальненням бінома Ньютона є наступна теорема:

Теорема 4.1.10 (поліноміальна теорема). Справедлива рівність:

,

де .

Числа називають біноміальними коефіцієнтами.

Властивості біноміальних коефіцієнтів:

1. (випливає з теореми 4.1.6, якщо замінити у формулі k на (n–k), то (n–k) заміниться на (n– (n–k))=k).

2. (формула симетрії).

3. (формула додавання).

4. ( – кількість всіх розміщень з повтореннями з елементів 2-х типів).

5. (формула винесення за дужки).

6. .

7. .