7.3: Перестановки
- Page ID
- 66907
У цьому розділі ви навчитеся
- Підрахуйте кількість можливих перестановок (впорядкованого розташування) n елементів, прийнятих r за один раз
- Підрахуйте кількість можливих перестановок, коли є умови, накладені на домовленості
- Виконуйте розрахунки за допомогою факторіалів
У прикладі 7.2.6 розділу 7.2 нам було запропоновано знайти послідовності слів, утворені за допомогою букв {A, B, C}, якщо жодна буква не повинна повторюватися. Деревоподібна діаграма дала нам наступні шість домовленостей.
ABC, ACB, BAC, BCA, CAB та CBA.
Такі домовленості, де порядок важливий і жоден елемент не повторюється, називаються перестановками.
Перестановка набору елементів - це впорядкована композиція, де кожен елемент використовується один раз.
Скільки трилітерних послідовностей слів можна сформувати за допомогою букв {A, B, C, D}?
Рішення
Існує чотири варіанти для першої літери нашого слова, три варіанти для другої літери та два варіанти для третьої.
| 4 | 3 | 2 |
Застосовуючи аксіому множення, отримуємо\(4 \cdot 3 \cdot 2 = 24\) різні аранжування.
Скільки перестановок букв слова ARTICLE мають приголосні в першій і останній позиціях?
Рішення
У слові СТАТТЯ є 4 приголосні.
Оскільки перша буква повинна бути приголосної, у нас є чотири варіанти для першої позиції, і як тільки ми використовуємо приголосний, залишається лише три приголосні для останнього місця. Ми показуємо наступним чином:
| 4 | 3 |
Оскільки обмежень більше немає, ми можемо піти вперед і зробити вибір для решти позицій.
Поки ми використали 2 літери, отже, п'ять залишаються. Отже, для наступної позиції є п'ять варіантів, для позиції після цього є чотири варіанти, і так далі. Ми отримуємо
| 4 | 5 | 4 | 3 | 2 | 1 | 3 |
Таким чином, загальні перестановки є\(4 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 \cdot 3 = 1440\).
Дано п'ять літер {A, B, C, D, E}. Знайдіть наступне:
- Кількість послідовностей слів з чотирьох букв.
- Кількість трилітерних послідовностей слів.
- Кількість дволітерних послідовностей слів.
Рішення
Завдання легко вирішується аксіомою множення, і відповіді такі:
- Кількість послідовностей слів з чотирьох букв дорівнює\(5 \cdot 4 \cdot 3 \cdot 2 = 120\).
- Кількість трилітерних послідовностей слів дорівнює\(5 \cdot 4 \cdot 3 = 60\).
- Кількість дволітерних послідовностей слів дорівнює\(5 \cdot 4 = 20\).
Ми часто стикаємося з ситуаціями, коли у нас є набір n об'єктів і ми вибираємо r об'єктів для формування перестановок. Ми називаємо це перестановками n об'єктів, прийнятих r за один раз, і ми пишемо це як nPR.
Тому на вищевказаний приклад також можна відповісти, як зазначено нижче.
- Кількість чотирибуквенних послідовностей слів дорівнює 5P4 = 120.
- Кількість трилітерних послідовностей слів дорівнює 5П3 = 60.
- Кількість дволітерних послідовностей слів дорівнює 5P2 = 20.
Перш ніж дати формулу для NPR, ми хотіли б ввести символ, який ми будемо використовувати багато в цьому, а також у наступному розділі.
\[\mathrm{n} !=\mathrm{n}(\mathrm{n}-1)(\mathrm{n}-2)(\mathrm{n}-3) \cdots 3 \cdot 2 \cdot 1 \nonumber \]
де\(n\) - натуральне число.
\[0! = 1 \nonumber \]
Тепер визначаємо NPR.
Кількість перестановок n об'єктів, прийнятих r за один раз
\[\mathrm{nPr}=\mathrm{n}(\mathrm{n}-1)(\mathrm{n}-2)(\mathrm{n}-3) \cdots(\mathrm{n}-\mathrm{r}+1) \nonumber \]
або
\[\mathrm{nPr}=\frac{\mathrm{n} !}{(\mathrm{n}-\mathrm{r}) !} \nonumber \]
де\(n\) і\(r\) є натуральними числами.
Читач повинен ознайомитися з обома формулами і повинен відчувати себе комфортно в застосуванні.
Обчислити наступне за допомогою обох формул.
- 6П3
- 7П2
Рішення
Ми будемо виявляти\(n\) і\(r\) в кожному конкретному випадку і вирішувати, використовуючи надані формули.а. 6Р3 =\(6 \cdot 5 \cdot 4 = 120\), по черзі
\[ 6 \mathrm{P} 3=\frac{6 !}{(6-3) !}=\frac{6 !}{3 !}=\frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{3 \cdot 2 \cdot 1}=120 \nonumber \]
б. 7Р2 =\(7 \cdot 6 = 42\), або
\[7 \mathrm{P} 2=\frac{7 !}{5 !}=\frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}=42 \nonumber \]
Далі ми розглянемо ще деякі проблеми перестановки, щоб отримати подальше розуміння цих понять.
Скільки по-різному можна посадити 4 людини по прямій, якщо двоє з них наполягають на сидінні поруч?
Рішення
Давайте припустимо, що у нас є чотири людини A, B, C і D. Далі припустимо, що A і B хочуть сидіти разом. Заради аргументу зв'язуємо А і Б разом і ставимося до них як до однієї людини.Чотири людини -\(\boxed{AB}\) компакт-диск. Оскільки\(\boxed{AB}\) розглядається як одна людина, ми маємо наступні можливі домовленості.
\[ \boxed{AB} CD, \boxed{AB} DC, C \boxed{AB}D, D\boxed{AB}C, CD \boxed{AB}, DC\boxed{AB} \nonumber \]
Зауважте, що є ще шість таких перестановок, оскільки A і B також можуть бути пов'язані в порядку BA. І вони
\[ \boxed{BA}CD, \boxed{BA} DC, C\boxed{BA}D, D\boxed{BA}C, CD\boxed{BA}, DC \boxed{BA} \nonumber \]
Таким чином, в цілому є 12 різних перестановок.
Давайте тепер зробимо задачу, використовуючи аксіому множення.
Після того, як ми зв'яжемо двох людей разом і ставимося до них як до однієї людини, ми можемо сказати, що у нас всього три людини. Аксіома множення говорить нам, що три людини можуть сидіти в 3! способи. Так як двох людей можна зв'язати разом 2! способів, є 3! 2! = 12 різних домовленостей
У вас є 4 книги з математики та 5 книг з історії, щоб покласти на полицю, яка має 5 слотів. Скільки способів можна відкласти книги, якщо перші три слоти заповнені книгами з математики, а наступні два слоти заповнені книгами історії?
Рішення
Спочатку ми робимо задачу за допомогою аксіоми множення.
Оскільки математичні книги йдуть у перші три слоти, є 4 варіанти для першого слота,
3 варіанти для другого та 2 варіанти для третього.
Четвертий слот вимагає книги історії, і має п'ять варіантів. Після того, як цей вибір зроблений, залишилося 4 книги історії, і, отже, 4 варіанти для останнього слота. Вибір наведено нижче.
| 4 | 3 | 2 | 5 | 4 |
Тому кількість перестановок є\(4 \cdot 3 \cdot 2 \cdot 5 \cdot 4 = 480\).
По черзі ми можемо бачити, що\(4 \cdot 3 \cdot 2\) це дійсно те ж саме, що 4P3, і\(5 \cdot 4\) є 5P2.
Таким чином, відповідь можна записати як (4P3) (5P2) = 480.
Зрозуміло, що це має сенс. Для кожної перестановки трьох математичних книг, розміщених у перших трьох слотах, є 5P2 перестановки книг історії, які можуть бути розміщені в останніх двох слотах. Звідси застосовується аксіома множення, і ми маємо відповідь (4P3) (5P2).
Узагальнюємо поняття цього розділу:
1. Перестановки
Перестановка набору елементів - це впорядкована композиція, де кожен елемент використовується один раз.
2. Факторіал
\[\mathrm{n} !=\mathrm{n}(\mathrm{n}-1)(\mathrm{n}-2)(\mathrm{n}-3) \cdots 3 \cdot 2 \cdot 1 \nonumber \]
Де\(n\) - натуральне число.
\[0! = 1 \nonumber \]
3. Перестановки n об'єктів, взятих або за один раз
\[\mathrm{nPr}=\mathrm{n}(\mathrm{n}-1)(\mathrm{n}-2)(\mathrm{n}-3) \cdots(\mathrm{n}-\mathrm{r}+1) \nonumber \]
або
\[\mathrm{nPr}=\frac{\mathrm{n} !}{(\mathrm{n}-\mathrm{r}) !} \nonumber \]
де\(n\) і\(r\) є натуральними числами.