Елементи комбінаторики

Приклад

Скільки парних п’ятизначних чисел можна утворити з цифр 0, 1, 2, 3, 4 так, щоб усі числа були різними?

♦ Парними будуть числа, що закінчуються на 0, 2, 4. Кількість чисел, які закінчуються нулем дорівнює  числу перестановок з чотирьох цифр (1, 2, 3, 4), тобто Р4.

Числа, що закінчуються на 2, утворюються із цифр 0, 1, 3, 4 їх різноманітними перестановками, кількість яких  Р4. Проте цифра нуль не може стояти на першому місці. Тому з  Рвилучаєсо кількість чисел які утворюються із цифр 1, 3 та 4, тобто  Р3

Аналогічно можна знайти кількість числе, що закінчуються  на 4. 

Отже, всього парних п’ятизначних чисел можна утворити n = 3 Р– 2 Р3 = 3·4! – 2·3! = 60.♦

Приклад

Команда з “Клубу знавців” у складі шести осіб займає місця за круглим столом. Скільки є можливих варіантів розміщення гравців? Скільки таких варіантів у випадку, коли два провідних члени команди повинні сісти поруч?

♦ У першому випадку кількість способів розміщення гравців дорівнює числу перестановок з 6 елементів, тобо Р6 = 6! = 720. У другому випадку для двох виділених осіб є  шість різних сусідніх пар місць, на кожному з яких ці дві особи можуть сісти двома способами (один біля одного ліворуч або праворуч). Отже, посадити їх можна 12 способами. На місця, що залишаться, решту членів команди можна розсадити Р4 способами. За правилом добутку дістаємо кількість усіх варіантів розміщень: 12·4!=288.♦

Приклад

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

♦ Позначимо через n число учасників турніру. Оскільки три з них вибуло, зігравши в сумі 1 + 2 + 3 = 6 партій, то в останніх 84 – 6 = 78 партіях взяло участь n – 3 учасники. Отже,  78=C_{n-3}^{2} , тобто  \frac{(n-3)(n-4)}{2!}=78 , або  n^{2}-7n-144=0 , звідки дістаємо один додатний корінь n = 16. ♦

Приклад

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

♦ Кількість таких способів дорівнює числу розміщень  з 8 елементів по 3, тобто  A_{8}^{3}=8\cdot 7\cdot 6=336  .♦

Приклад

Обчислити:

а)  \frac{A_{8}^{4}+A_{6}^{3}}{A_{5}^{2}} ;

б)  \frac{P_{4}-P_{3}}{3!}  ;

в)   C_{6}^{4}+C_{3}^{2}\; i\; C_{6}^{2}+C_{3}^{1} .

♦ а) Користуючись формулою 

 A_{n}^{k}=n(n-1)(n-2)...(n-k+1)=\frac{n!}{(n-k)!},0\leq k\leq n, ,

маємо  \frac{A_{8}^{4}+A_{6}^{3}}{A_{5}^{2}}=\frac{8\cdot 7\cdot 6\cdot 5+6\cdot 5\cdot 4}{5\cdot 4}=90 .

б) За формулою   P_{n}=A_{n}^{n}=n!

отримаємо  \frac{P_{4}-P_{3}}{3!}=\frac{4!-3!}{3!}=\frac{3!(4-1)}{3!}=3 .

в) За властивістю  C_{n}^{k}=C_{n}^{n-k},\; C_{n+1}^{k+1}=C_{n}^{k+1}+C_{n}^{k},\; k\in \bar{0,n}

та формулою  C_{n}^{k}=\frac{A_{n}^{k}}{P_{k}}=\frac{n(n-1)...(n-k+1)}{k!}=\frac{n!}{k!(n-k)!},\; 0\leq k\leq n

дістаємо  C_{6}^{4}+C_{3}^{2}= C_{6}^{2}+C_{3}^{1} =\frac{6\cdot 5}{2!}+\frac{3}{1!}=18. ♦

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *