Skip to main content
LibreTexts - Ukrayinska

7.4: Кругові перестановки та перестановки з подібними елементами

  1. Last updated
  2. Save as PDF
  • Page ID
    66934

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Цілі навчання

    У цьому розділі ви навчитеся

    1. Підрахуйте кількість можливих перестановок елементів, розташованих по колу
    2. Підрахуйте кількість можливих перестановок, коли є повторювані елементи

    У цьому розділі ми розглянемо наступні дві проблеми.

    1. Скільки різних способів п'ять чоловік можуть сидіти по колу?
    2. Скільки різних способів можуть бути розташовані букви слова МІССІСІПІ?

    Перша проблема підпадає під категорію кругових перестановок, а друга - під перестановками зі схожими елементами.

    Циркулярні перестановки

    Припустимо, у нас є три людини на ім'я A, B і C. Ми вже визначили, що їх можна посадити по прямій лінії в 3! або 6 способів. Наша наступна проблема полягає в тому, щоб побачити, скільки способів цих людей можна посадити в коло. Малюємо схему.

    Розділ 7.4 PNG

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

    Визначення: Кругові перестановки

    Кількість перестановок\(n\) елементів в колі дорівнює\((n-1)!\)

    Приклад\(\PageIndex{1}\)

    Скільки різних способів п'ять людей можуть сидіти за круглим столом?

    Рішення

    Ми вже визначили, що перша людина - це всього лише власник місця. Тому є лише один вибір для першого місця. У нас є

    1 4 3 2 1

    Отже, відповідь 24.

    Приклад\(\PageIndex{2}\)

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

    Рішення

    Знову підкреслимо, що перша людина може сидіти де завгодно, не впливаючи на перестановку.

    Таким чином, є тільки один вибір для першого місця. Припустимо, чоловік сів першим. Стілець поруч з ним повинен належати жінці, і є 4 варіанти. Наступний стілець належить чоловікові, тому є три варіанти вибору і так далі. Ми перерахуємо варіанти нижче.

    1 4 3 3 2 2 1 1

    Отже, відповідь 144.

    ПЕРЕСТАНОВКИ З ПОДІБНИМИ ЕЛЕМЕНТАМИ

    Визначимо кількість помітних перестановок букв ELEMENT.

    Припустимо, ми робимо всі літери різними, позначаючи літери наступним чином.

    \[E_1LE_2ME_3NT \nonumber \]

    Так як всі букви тепер різні, їх 7! різні перестановки.

    Давайте тепер розглянемо одну таку перестановку, скажімо

    \[LE_1ME_2NE_3T \nonumber \]

    Припустимо, ми формуємо нові перестановки з цього розташування лише переміщенням E. Зрозуміло, що їх 3! або 6 таких домовленостей. Перерахуємо їх нижче.

    \ почати {вирівняний} &\ математика {LE} _ {1}\ математика {ME} _ {2}\ математика {NE} _ {3}\\
    &\ математика {LE} _ {1}\ математика {ME} _ {3}\ Mathrm {2} _ {2}\
    &\ mathrm {LE} _ {2} ME} _ {1}\ математика {NE} _ {3}\ математика {T}\\
    &\ математика {LE} _ {2}\ математика {ME} _ {3}\ mathrm {NE} _ {1}\ mathrm {T}\\
    &\ математика {LE} _ {3}\ математика {ME} _ {2}\ математика {NE} _ {1}\ математика {T}\\
    &\ mathrm {LE} _ {3}\ mathrm {ME} _ {I}\ mathrm {NE} _ {2}\ mathrm {T}\ кінець {вирівняний}

    Оскільки Е не відрізняються, є тільки один розташування LEMENET, а не шість. Це вірно для кожної перестановки.

    Припустимо, що існує n різних перестановок букв ELEMENT.

    Потім йдуть\(n \cdot 3!\) перестановки букв\(E_1LE_2ME_3NT\).

    Але ми знаємо, що їх 7! перестановки букв\(E_1LE_2ME_3NT\).

    Тому,\(n \cdot 3! = 7!\)

    Або\(n = \frac{7!}{3!}\).

    Це дає нам метод, який ми шукаємо.

    Визначення: Перестановки з подібними елементами

    Кількість перестановок n елементів, прийнятих\(n\) за один раз, з\(r_1\) елементами одного роду,\(r_2\) елементами іншого роду і так далі, дорівнює

    \[\frac{n !}{r_{1} ! r_{2} ! \ldots r_{k} !} \nonumber \]

    Приклад\(\PageIndex{3}\)

    Знайти кількість різних перестановок букв слова MISSISSIPPI.

    Рішення

    Слово Міссісіпі має 11 букв. Якби листи були всі різні, було б 11! різні перестановки. Але Міссісіпі має 4 S, 4 я, і 2 P, які схожі.

    Отже, відповідь є\(\frac{11!}{4!4!2!} = 34,650\).

    Приклад\(\PageIndex{4}\)

    Якщо монета кидається шість разів, скільки різних результатів, що складаються з 4 голів і 2 хвостів є?

    Рішення

    Знову ж таки, у нас є перестановки з подібними елементами.

    Шукаємо перестановки для букв HHHHTT.

    Відповідь є\(\frac{6!}{4!2!} = 15\).

    Приклад\(\PageIndex{5}\)

    Скільки різних способів можна розташувати в ряд 4 нікеля, 3 діми, і 2 чверті?

    Рішення

    Якщо припустити, що всі нікелі схожі, все діми схожі, а всі чверті схожі, у нас є перестановки з подібними елементами. Тому відповідь така

    \[\frac{9 !}{4 ! 3 ! 2 !}=1260 \nonumber \]

    Приклад\(\PageIndex{6}\)

    Фондовий брокер хоче призначити 20 нових клієнтів однаково 4 своїм продавцям. Скільки різних способів це можна зробити?

    Рішення

    Це означає, що кожен продавець отримує 5 клієнтів. Проблему можна розглядати як проблему впорядкованих розділів. У такому випадку за допомогою формули ми отримуємо

    \[\frac{20 !}{5 ! 5 ! 5 ! 5 !}=11,732,745,024 \nonumber \]

    Приклад\(\PageIndex{7}\)

    Торговий центр має прямий ряд з 5 флагштоків біля площі головного входу. Він має 3 однакових зелених прапорців та 2 однакових жовтих прапорців. Скільки різних композицій прапорів на флагштоках можливі?

    Рішення

    Проблема може розглядатися як різні перестановки букв GGGYY; тобто розташування з 5 букв, де 3 літери схожі, а решта 2 літери схожі:

    \[ \frac{5 !}{3 ! 2 !} = 10 \nonumber \]

    Просто щоб надати трохи більше розуміння рішення, ми перерахуємо всі 10 різних перестановок:

    GGGY, GGGY, GYGG, GYGGY, GYGG, GYGG, YGGG, YGGG, YGGG

    Підсумовуємо.

    Резюме

    1. Циркулярні перестановки

    Кількість перестановок n елементів у колі дорівнює

    \[(n -1)! \nonumber \]

    2. Перестановки зі схожими елементами

    Кількість перестановок n елементів, взятих n за один раз, з\(r_1\) елементами одного роду,\(r_2\) елементами іншого роду і так далі, такі,\(\mathrm{n}=\mathrm{r}_{1}+\mathrm{r}_{2}+\ldots+\mathrm{r}_{\mathrm{k}}\) що

    \[\frac{n !}{r_{1} ! r_{2} ! \dots r_{k} !} \nonumber \]

    Це також називають упорядкованими перегородками.