4.2. Розміщення

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

У деяких задачах ставиться завдання визначити, скільки може існувати упорядкованих підмножин заданої множини. Якщо, наприклад, потрібно з’я-сувати, скількома способами у кооперативі з 25 членів можна обрати голову кооперативу, його заступника і скарбника, то мова йде про вибір упорядкованої трійки членів кооперативу.

Будь-яку упорядковану підмножину, що містить m елементів з даної n-елементної множини, де m  n, називають розміщенням з n елементів по m елементів.

Із цього означення можна дійти висновку, що різні розміщення з nелементів, узятих поm, відрізняються або складом елементів, які входять до них, або порядком їхнього розташування. Наприклад, із чотирьох буквА, Б, В, Гможна утворити 12 розміщень, що містять по 2 букви:

АБ,АВ,АГ,БВ,БГ,ВГ,

БА,ВА,ГА,ВБ,ГБ,ГВ.

Іноді потрібно порахувати кількість різних розміщень з nелементів, взятих поmелементів. Наприклад, у згаданій вище задачі про вибори правління кооперативу зрозуміло, що головою може бути будь-хто із членів колективу. Отже, його можна вибрати 25 способами. Тоді для вибору його заступника, якщо вже вибрали голову, залишається 24 можливості. Тому вибір голови та його заступника разом можна здійснити 25 · 24600 способами. Скарбником міг би бути хтось із решти 23 членів кооперативу. Тому існує 600 · 2313800 різних способів для розв’язання цієї прозаїчної задачі.

Кількість розміщень з nелементів поmпозначають символом(читається «а з ен по ем»).

Теорема 2. Кількість різних розміщень зnелементів поmдорівнює добуткуmпослідовних натуральних чисел, з яких найбільшим єn. Тобто:

■ Перший елементm-елементної підмножини можна вибрати nспособами, другий — (n– 1) способом. Упорядкована пара перших двох елементів вибираєтьсяn· (n– 1) способами. Упорядковану трійку елементів можна вибратиn (n– 1)(n – 2) способами. Продовжуючи ці міркування, бачимо, що ■

Виведену формулу можна записати так: . Справді,

Задача. Скільки різних трицифрових чисел можна записати за допомогою цифр 1, 2, 3, 4, 5 і 6, якщо жодна із цифр у записі будь-якого числа не буде повторюватися? Скільки таких чисел можна записати, використовуючи цифри 0, 1, 2, 3, 4, 5?

■ Зрозуміло, що в першому випадку шукане число дорівнює 6  5  4  120.

Для другого випадку відповідь така: — оскільки до кількості розміщеньтоді входитьрозміщень, у яких цифра 0 записана на першому місці. ■

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

4.3. Комбінації

Трапляються задачі, у яких потрібно визначити кількість різних підмножин, що містять kелементів, узятих з даноїn-елементної множини. Наприклад, нехай у класі є 25 учнів і потрібно вибрати трьох учнів, яким доручається провідати хворого. При відборі такої делегації немає істотного значення, в якому порядку будуть названі імена її членів. Делегація, до складу якої входить Іван, Оля та Наталка, — та ж сама, що й делегація, до складу якої ввійшли б Оля, Іван та Наталка, якщо тільки в класі немає кількох Іванів, Наталок чи Ольг і ніхто із цих учнів не замінений на свого тезку.

Нехай маємо множину М, що містить n елементів. Будь-яка підмножина заданої множини М, яка містить k елементів, де , називаєтьсякомбінацією з даних n елементів, взятих по k елементів.

Із цього означення випливає, що будь-які дві різні k-елементні комбінації відрізняються одна від одної принаймні одним елементом.

Кількість різних комбінацій з nелементів поkпозначають символом(читається «це з ен по ка»).

Кожна множина має дві тривіальні підмножини: однією з них є сама множина, а іншою — порожня множина. Тому іОчевидно також, щооскільки зnелементів можна утворити лишеnпідмножин, кожна з містить по одному елементу.

Перед тим, як вивести формулу для обчислення покажемо, що справджується рівність:

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

Таким чином, ми маємо таку теорему:

Теорема 3. Кількість усіх комбінацій зпелементів, взятих поk, привиражається формулою:

За допомогою методу математичної індукції можна дати ще одне доведення цієї теореми. При k0 теорема істинна, оскільки

Для обґрунтування індуктивного переходу доведемо таку формулу:

З цією метою спочатку зауважимо, що з кожної (k – 1)-елементної підмножини шляхом приєднання одного з решти n – (k – 1) елементів можна утворити n – k + 1 уже k-елементних підмножин. Оскільки, далі, усіх (k – 1)-елементнихпідмножин єа кожна з них породжуєn– k + 1k-елементних підмножин, то з усіх (k – 1)-елементних підмножин таким способом дістанемо (n – k + 1)· k-елементних підмножин. Однак слід зважити на те, що при цьому кожнаk-елементна підмножина враховуватиметьсяkразів. Справді, підмножину a₁ a₂ a₃ …а_k–1 а_k, наприклад, можна утворити k різними способами:

1-й раз, якщо до підмножини а₂а₃ …а_k–1а_kприєднати елемент а₁;

2-й раз, якщо до підмножини а₁а₃ …а_k–1а_kприєднати елемента₂;

…..............................................................................................................

нарешті, k-й раз, якщо до підмножиниа₁а₂ …а_k–1приєднати елемента_k.

Тому

Для завершення доведення теореми 3 методом математичної індукції, припустимо, що Спираючись на це припущення та виведену формулу, маємо:

Теорему доведено.

Тепер уже легко дати відповідь до задачі, умова якої наведена на початку цього пункту. Вибір трьох учнів для відвідування хворого можна здійснити способами.