Учебное пособие: Елементи комбінаторики. Початки теорії ймовірностей

Застосуємо метод математичної індукції. Припустимо, що для А² _n правильною є формула (1). Розміщення з п елементів по k + і можна розглядати як пару: на першому місці будь-яке розміщення з п елементів по k(їх кількість А^k _n ), на другому - будь-який елемент з решти п - kелементів. За правилом добутку дістанемо

А_n ^{k +1} = А_n ^k (n-k). (2)

Користуючись формулою (1), маємо

А_n ^{k +1} =п(п-1)(п-2)...(п-(k-і))(п-k) = = n(n- 1)(n - 2)...(n- (k-1))(n-(k +1-1)).

Оскільки

то формулу (1) можна записати ще так:

. (3)

Приклад 1. Скількома способами можна вибрати з 10 кандидатів три особи на три різні посади?

Для розв'язування задачі треба знайти число розміщень з 10 елементів по три. Отже, за формулою (1) маємо

A³ ₁₀ =10•9•8 = 720.

Приклад 2. Скільки трицифрових чисел з різними цифрами можна утворити з цифр 0, 1,2, 3, 4?

Загальна кількість трицифрових чисел з різними цифрами є кількістю

розміщень з 5 елементів по три, тобто А³ ₅ = 5 • 4 • 3 = 60. Проте із загальної кількості чисел треба відкинути числа, що починаються з нуля. Таких чисел стільки, скільки можна утворити розміщень з чотирьох цифр по два без нуля, тобто А² ₄ =4•3 = 12. Отже, шукана кількість трицифрових чисел дорівнює 60 - 12 = 48 .

§ 4. Комбінації

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

З одного елемента можна утворити тільки одну комбінацію. З двох елементів а і bможна утворити дві комбінації по одному елементу і тільки одну комбінацію з двох елементів.

З трьох елементів a, b, cможна утворити такі комбінації:

{a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}.

Комбінації з п елементів даної множини по kможна також розглядати як розміщення з п елементів по k, які відрізняються принаймні одним елементом. Виникає запитання, як визначити кількість комбінацій з n елементів по k. Число комбінацій з п по kпозначається С^k _n . Доведемо, що

. (1)

Розглянемо множину, яка складається з п елементів, і комбінації, які складаються з kелементів. Всього комбінацій С^k _n . Якщо з кожної такої комбінації утворити всі можливі перестановки (їх буде Р_k = k!), то дістанемо всі можливі розміщення з п елементів по к, тобто число А^k _n . Отже,

А^k _n = Р_k •С^k _n , (2)

звідки

Зауважимо, що за означенням покладають 0! = 1. Тому неважко помітити, що С¹ ₁ =1і Сⁿ _n = 1.

Приклад. Збори з 30 осіб вибирають трьох делегатів на конференцію. Скількома способами це можна зробити?

Із множини у 30 осіб треба вибрати підмножину з трьох осіб. Цеможна зробити способами .

§ 5. Властивості комбінацій