8.3: Перестановки

\(A\)Дозволяти бути кінцевий набір з\(n\) елементами. Для\(1\le r\le n\), \(\mathbf{r}\)-перестановка\(A\) - це впорядкований вибір\(r\) різних елементів з\(A\). Іншими словами, це лінійне розташування\(r\) різних об'єктів\(a_1a_2\ldots a_r\), де\(a_i\in A\) для кожного\(i\). Число\(r\) -перестановок\(n\) множини -елементів позначається символом\(P(n,r)\). Він також фігурує в багатьох інших формах і іменах.

• Кількість перестановок\(n\) об'єктів, прийнятих за\(r\) один раз без заміни.
• Кількість способів розстановки\(n\) предметів (в послідовності), прийнятих\(r\) за один раз без заміни.

Всі вони відносяться до одного числа\(P(n,r)\). Ключові слова:

1. «Перестановка» або «розташування», обидва з яких припускають, що порядок має значення.
2. «Без заміни» означає, що записи в перестановці/розташуванні є різними.

У деяких підручниках позначення\(P(n,r)\) також пишеться як\(P_r^n\) або\(_nP_r\).

Приклад\(\PageIndex{1}\label{eg:perm-01}\)

1-перестановки\(\{a,b,c,d\}\) є

\[\begin{array}{llll} a, & b, & c, & d. \end{array} \nonumber\]

Отже,\(P(4,1)=4\). 2-перестановки\(\{a,b,c,d\}\) є

\[\begin{array}{lll} ab, & ac, & ad, \\ ba, & bc, & bd, \\ ca, & cb, & cd, \\ da, & db, & dc. \end{array} \nonumber\]

Отже,\(P(4,2)=12\). Що таке 3-перестановки та 4-перестановки\(\{a,b,c,d\}\)? Чи можете ви пояснити, чому числа 3-перестановок і 4-перестановок рівні?

Обчислити значення\(P(n,r)\) нескладно. Ми хочемо розташувати\(r\) об'єкти в послідовності. Ці\(r\) об'єкти повинні бути обрані з пулу\(n\) елементів. Звідси є\(n\) способи заповнити першу позицію. Після того, як ми погоджуємося з першою позицією, все, що ми туди поставимо, не можна використовувати знову. Нам залишається\(n-1\) вибір на другу позицію. Так само, як тільки він буде заповнений, є лише\(n-2\) вибір для третьої позиції. Тепер зрозуміло, що\(P(n,r)\) це добуток\(r\) чисел виду\(n\),\(n-1, n-2, \ldots\,\). Який останній номер в цьому списку? Перед ним стоять\(r-1\) цифри, так воно і повинно бути\(n-(r-1)=n-r+1\).

Теорема\(\PageIndex{1}\)

Для всіх цілих чисел\(n\) і\(r\) задовольняє\(1 \leq r \leq n\),\[P(n,r) = n(n-1)\cdots(n-r+1) = \frac{n!}{(n-r)!}. \nonumber\]

Хоча формулу\(P(n,r) = \frac{n!}{(n-r)!}\) досить легко запам'ятати, інша форма\[P(n,r) = \underbrace{n(n-1)\cdots(n-r+1)}_r \nonumber\] насправді більш корисна в числових обчисленнях, особливо коли це робиться вручну. Ми\(n\) множимо на наступне менше ціле число\(n-1\), а потім наступне менше ціле\(n-2\), і так далі, поки ми не отримаємо добуток\(r\) послідовних множників. Наприклад,\[P(4,2) = 4\cdot3 = 12, \qquad\mbox{and}\qquad P(9,3) = 9\cdot 8\cdot 7 = 504. \nonumber\] Як щодо\(P(n,1)\) і\(P(n,2)\)?

Приклад\(\PageIndex{2}\label{eg:perm-02}\)

Як би ви обчислили значення\(P(278,3)\) вручну, або якщо ваш калькулятор не має цієї\(_nP_r\) кнопки?

Рішення

Знаходимо\(P(278,3) = 278\cdot277\cdot276 = 21253656\).

практичні вправи\(\PageIndex{1}\label{he:perm-01}\)

Обчислення\(P(21,4)\) вручну.

Зауваження

З першого варіанту формули випливає, що\(P(n,n)=n!\). Друга версія зводиться до\[n! = P(n,n) = \frac{n!}{0!}. \nonumber\] Отже, щоб друга версія працювала, ми повинні визначити\(0!=1\).

Зауваження

У ваших домашніх завданнях, вікторини, тести та підсумковий іспит цілком нормально використовувати позначення\(P(n,r)\) у своїх відповідях. Насправді, залишаючи відповіді з точки зору\(P(n,r)\) дає іншим підказку про те, як ви отримали відповідь.

Часто це простіше і менш заплутано, якщо ми використовуємо принцип множення. Як тільки ви зрозумієте\(P(n,r)\), що відповідь передбачає, це не важко з'ясувати значення\(n\) і\(r\). Хороший початок, перш ніж стрибати в будь-який розрахунок, - запитати себе, як би ви перерахували можливі домовленості? Також спробуйте побудувати деякі приклади. Вони можуть дати вам уявлення про те, скільки варіантів у вас є в кожній позиції.

Приклад\(\PageIndex{3}\label{eg:perm-03}\)

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

Рішення

Уявіть, що ви офіцер, який розкладає завдання. Ви повинні призначити когось до першого округу, а потім ще одного офіцера до другого округу і так далі.

\[ \begin{array}{cccccc} \text{district:} & \text{first} & \text{second} & \text{third} & \text{fourth} & \text{fifth} \\ \text{choices:} & \text{any officer} & \text{another officer} & \text{another different officer} & \cdots & \cdots \\ & - & - & - & - & - \\ \text{# of choices:} & 12 & 11 & 10 & 9 & 8 \end{array} \nonumber\]

Є 12 варіантів для першого округу, 11 для другого і т.д. принцип множення має на увазі\(12\cdot11\cdots\), що відповідь є, який у вигляді\(P(n,r)\). Так як твір починається з 12, а нам потрібен добуток 5 послідовних чисел, відповідь є\(P(12,5)\).

практичні вправи\(\PageIndex{2}\label{he:perm-02}\)

Школа відправляє команду з шести бігунів на естафету. Скільки способів їх можна відібрати для участі в\(4 \times 100\) м естафеті?

Приклад\(\PageIndex{4}\label{eg:perm-04}\)

З колекції з 10 прапорів різних візерунків, скільки сигналів з трьома прапорами ми можемо поставити на стовп?

Рішення

Оскільки прапори розташовані на прапорці, порядок важливий. Є 10 варіантів для верхнього прапора, 9 для другого і 8 для третього. Тому можуть формуватися\(10\cdot9\cdot8 = P(10,3)\) різні сигнали.

Приклад\(\PageIndex{5}\label{eg:perm-05}\)

Визначте кількість функцій,\(f:{\{1,3,4,7,9\}}\to{\mathbb{Z}_{22}}\) якщо

1. Обмежень немає.
2. \(f\)один до одного.
3. \(f\)знаходиться на.

Рішення

Щоб відрізнити одну функцію від іншої, ми повинні порівняти їх зображення. Отже, функція повністю визначається її зображеннями (здивування: не своєю формулою!). Зрештою, ми можемо навіть не знати формулу, що стоїть за функцією, тому ми не можемо і не повинні покладатися лише на формулу.

Щоб визначити, скільки функцій є від\(\{1,3,4,7,9\}\) до\(\mathbb{Z}_{22}\), ми повинні визначити кількість способів присвоєння значень\(f(1)\),\(f(3)\)\(f(4)\),\(f(7)\) і\(f(9)\).

\[ \begin{array}{cccccc} \text{images:} & f(1) & f(3) & f(4) & f(7) & f(9) \\ \text{choices:} \\ & - & - & - & - & - \\ \text{# of choices:} \end{array} \nonumber\]

1. Якщо немає обмежень, у нас є 22 варіанти вибору для кожного з цих п'яти зображень. Звідси і є\(22\cdot22\cdot22\cdot22\cdot22 = 22^5\) функції.
2. Якщо\(f\) це один на один, ми не можемо дублювати зображення. Таким чином, у нас є 22 варіанти для\(f(1)\), 21 для\(f(3)\), і так далі. Існують функції\(P(22,5)\) «один-на-один».
3. Існує не більше п'яти чітких зображень, але\(\mathbb{Z}_{22}\) має 22 елементи, тому принаймні 17 з них залишаться невикористаними. Отже, ніколи не\(f\) може бути на. Таким чином, кількість функцій onto дорівнює нулю.

практичні вправи\(\PageIndex{3}\label{he:perm-03}\)

Скільки функцій є від\(\{2,4,6,8,10\}\) до\(\mathbb{Z}_{15}\)? Скільки з них один до одного?

Приклад\(\PageIndex{6}\label{eg:perm-06}\)

\(B\)Дозволяти\(A\) і бути кінцевими множинами, з\(|A|=s\) і\(|B|=t\). Визначте кількість функцій один до одного від\(A\) до\(B\).

Рішення

Як ми можемо придумати функцію один до одного від\(A\) до\(B\)? Ми повинні вказати зображення кожного елемента в\(A\). Є\(t\) вибір для першого елемента. Оскільки повторювані зображення не допускаються, ми маємо лише\(t-1\) вибір для зображення другого елемента в\(A\), і\(t-2\) вибір для третього зображення тощо. Відповідь є\(P(t,s)\).

Що робити, якщо\(t<s\)? Ми знаємо, що в такому випадку не існує жодної функції один\(A\) до одного,\(B\) тому що не вистачає чітких зображень. Чи\(P(t,s)\) все ще має сенс? Твір версії формули говорить про те, що\(P(t,s)\) є добутком\(s\) послідовних чисел. Звідси, наприклад,\[P(3,6) = 3\cdot2\cdot1\cdot0\cdot(-1)\cdot(-2) = 0, \nonumber\] що означає, що немає функції один-на-один від\(A\) до\(B\).

Не всі проблеми використовують\(P(n,r)\). У багатьох ситуаціях доводиться використовувати\(P(n,r)\) разом з іншими числами. Найбезпечніший підхід - покладатися на принципи додавання і множення.

Приклад\(\PageIndex{7}\label{eg:perm-07}\)

Скільки чотиризначних цілих чисел, які не містять повторюваних цифр?

Рішення

Є 10 варіантів для кожної цифри, але відповідь не є\(P(10,4)\), тому що ми не можемо використовувати 0 як першу цифру. Щоб у нас вийшло чотиризначне ціле число, перша цифра повинна бути ненульовою. Це залишає нам вибір 9 для першої цифри. Тоді у нас є 9 варіантів для другої цифри, 8 і 7 для наступних двох. Відповідь є\(9\cdot9\cdot8\cdot7\).

Приклад\(\PageIndex{8}\label{eg:perm-08}\)

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

Рішення

Відповідь не\(P(12,9)\) тому, що будь-яка позиція може бути першою позицією в круговій перестановці. Важливим є відносне розміщення обраних об'єктів, все, що нас хвилює, це хто поруч з ким сидить. Правильну відповідь можна знайти в наступній теоремі.

Теорема\(\PageIndex{1}\label{thm:circperm}\)

Число кругових\(r\) -перестановок\(n\) множини -елементів дорівнює\(P(n,r)/r\).

Доказ

Порівняйте кількість кругових\(r\) -перестановок з кількістю лінійних\(r\) -перестановок. Починаємо в будь-якому положенні по круговій\(r\) -перестановці, і йдемо за годинниковою стрілкою; отримуємо лінійну\(r\) -перестановку. Оскільки ми можемо почати з будь-якої з\(r\) позицій, кожна кругова\(r\) -перестановка виробляє\(r\) лінійні\(r\) -перестановки. Це означає, що існує\(r\) раз стільки кругових\(r\) перестановок, скільки є лінійних\(r\) -перестановок. Тому число кругових\(r\) -перестановок є\(P(n,r)/r\).

Альтернативний доказ

\(A\)Дозволяти бути множиною всіх лінійних\(r\) -перестановок\(n\) об'єктів, і нехай\(B\) бути множиною всіх кругових\(r\) -перестановок. Визначте функцію від\(A\) до\(B\) наступним чином. З огляду на будь-яку\(r\) -перестановку, сформуйте її образ, з'єднавши її «голову» до свого «хвоста». Стає зрозумілим, використовуючи той самий аргумент у доказі вище, що\(f\) є функцією\(r\) to-one,\(f\) що означає\(r\) відображення різних елементів від\(A\) до одного зображення в\(B\). Тому\(A\) має\(r\) в рази стільки елементів, скільки в\(B\). Це означає\(|A| = r\cdot|B|\). Так як\(|A|=P(n,r)\), знаходимо\(|B|=P(n,r)/r\).

практичні вправи\(\PageIndex{4}\label{he:perm-04}\)

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

практичні вправи\(\PageIndex{5}\label{he:perm-05}\)

Скільки способів ми можемо сформувати намисто з восьми намистин різного кольору?

Зауваження: Коли намисто перевертається, це все те саме намисто. Таким чином, орієнтація намиста не має значення: ми можемо вважати намистини за годинниковою стрілкою, або проти годинникової стрілки.

Приклад\(\PageIndex{9}\label{eg:perm-09}\)

Скільки способів ми можемо влаштувати 20 лицарів за круглим столом? Що робити, якщо двоє з них відмовляються сидіти поруч один з одним?

Рішення

Без будь-яких обмежень існують\(20!/20 = 19!\) способи розсадити 20 лицарів. Для вирішення другої проблеми використовують комплемент. Якщо два з них завжди сидять разом, ми фактично розташовуємо 19 об'єктів по колу. Між собою цих двох лицарів можна посадити двома способами, в залежності від того, хто сидить зліва. Отже, є\(2\cdot 19!/19=2\cdot18!\) способи посадити 20 лицарів, причому два з них завжди разом. Тому остаточну відповідь на другу проблему є\(19!-2\cdot18!\).

Резюме та огляд

• Використовуйте перестановку, якщо порядок має значення: розташування ключових слів, послідовність та порядок припускають, що ми повинні використовувати перестановку.
• Часто ефективніше використовувати принцип множення безпосередньо.
• Кількість способів розташування\(n\) об'єктів лінійно є\(n!\), а кількість способів їх розташувати по колу -\((n-1)!\).

Вправа\(\PageIndex{1}\label{ex:perm-01}\)

Скільки восьмизначних паролів можна сформувати з 26 букв англійського алфавіту, кожна з яких може бути прописною або малим, а 10 цифр? Скільки з них не мають повторюваного характеру?

Вправа\(\PageIndex{2}\label{ex:perm-02}\)

Скільки функцій є від\(\mathbb{Z}_6\) до\(\mathbb{Z}_{12}\)? Скільки з них один до одного?

Вправа\(\PageIndex{3}\label{ex:perm-03}\)

Шкільна рада шкільного округу налічує 14 членів. Скільки способів можна вибрати крісло, перший заступник голови, другий заступник голови, скарбник та секретар?

Вправа\(\PageIndex{4}\label{ex:perm-04}\)

Збірні з боротьби двох шкіл мають вісім і 10 членів відповідно. Скільки способів між ними можна скласти три матчі?

Вправа\(\PageIndex{5}\label{ex:perm-05}\)

Команди з боротьби трьох шкіл мають сім, 10 і 11 членів відповідно. Кожна школа матиме три матчі проти кожної з двох інших школи. Скільки способів можуть бути влаштовані ці сірники?

Вправа\(\PageIndex{6}\label{ex:perm-06}\)

Вчитель бере свій клас обчислення AP з 8 студентів на обід. Вони сидять навколо круглого обіднього столу.

1. Скільки можливих місць для розсадження?
2. Скільки розсаджень існує, якщо вчителю доводиться сидіти на стільці, найближчому до фонтану з газованою водою?
3. Серед учнів один набір трійок. Скільки місць для сидіння там без всіх трьох з них сидять разом?

Вправа\(\PageIndex{7}\label{ex:perm-07}\)

Одинадцять студентів йдуть на обід. В обідньому залі два круглих столи, один вміщує 7 осіб, інший вміщує 4. Скільки способів їх можна посадити?

Вправа\(\PageIndex{8}\label{ex:perm-08}\)

П'ять пар відвідують весільний банкет. Їх садять на довгий стіл. Скільки розсаджень, які чергують чоловіків і жінок? Що робити, якщо стіл має круглу форму?