7.5: Відмітні перестановки

Last updated
Save as PDF

Page ID: 58801

\( \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}}\)

Якщо є колекція з 15 кульок різних кольорів, то кількість перестановок в підкладці куль вгору в ряд дорівнює\(_{15} P_{15}=15 !\). Якби всі кулі були одного кольору, була б лише одна помітна перестановка в вишикуванні їх в ряд, тому що самі кулі виглядали б однаково незалежно від того, як вони були розташовані.

Якби 10 кульок були жовтими, а інші 5 кульок різного кольору, скільки помітних перестановок було б?

Як би не були розташовані кулі, адже 10 жовтих кульок не відрізняються один від одного, їх можна було б міняти місцями без будь-яких відчутних змін в загальному розташуванні. В результаті кількість помітних перестановок в цьому випадку буде\(\frac{15 !}{10 !},\) так як є\(10 !\) перестановки жовтих куль для кожного фіксованого положення інших куль.

Загальне правило для такого типу сценаріїв полягає в тому, що, враховуючи\(n\)\(n_{1}\) об'єкти, в яких є об'єкти одного виду, які не відрізняються,\(n_{2}\) об'єкти іншого роду, які не відрізняються і так далі, то кількість помітних перестановок буде дорівнює:
\ [
\ begin {масив} {c}
n! \\
\ гідророзриву {n} {n_ {1}! * n_ {2}! * n_ {3}! *\ cdots * n_ {k}!} \
\ text {з} n_ {1} +n_ {2} +n_ {3} +\ cdots+n_ {k} =n
\ end {array}
\]
Приклад
Знайдіть кількість способів розміщення 12 куль в ряд, враховуючи, що 5 червоні, 3 зелені та 4 жовті.
Це буде\(\frac{12 !}{5 ! 3 ! 4 !}=\frac{12 * 11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1}{5 * 4 * 3 * 2 * 3 * 2 * 4 * 3 * 2}\)
\ [
\ begin {масив} {l}
=\ frac {12 * 11 * 10 * 9 * 8 * 7 * 6} {3 * 2 * 4 * 3}\\
=27,720
\ end {масив}
\]

Ще один спосіб подумати над цією проблемою - вибрати п'ять з дванадцяти просторів, в яких розміщувати червоні кулі - оскільки порядок вибору не важливий, є\(_{12} C_{5}\) способи зробити це. Потім з решти 7 наявних місць нам потрібно вибрати три з них, в яких помістити зелені кульки. Є\(_{7} C_{3}\) способи зробити це. Потім чотири жовті кульки поміщаються в решту чотирьох пробілів.

Результатом цього процесу є те, що існують\(_{12} C_{5}\) способи вибору місць для червоних куль та\(_{7} C_{3}\) способи вибору місць для зелених куль, в результаті чого:
\ [
_ {12} C_ {5} *_ {7} C_ {3} =\ frac {12!} {5! 7!} *\ гідророзриву {7!} {3! 4!} =\ гідророзриву {12!} {5! 3! 4!}
\]
Це призводить до тієї ж відповіді, що і коли ми підійшли до проблеми як перестановки. Розгляд проблеми таким чином допомагає нам вирішувати проблеми, які передбачають призначення завдань групам осіб.
Приклад
Чотирнадцять будівельних робітників повинні бути призначені для трьох різних завдань. Шість робочих потрібні для змішування цементу, п'ять - для кладки цегли і три - для перенесення цегли до цегляних шарів. Скільки різних способів можуть бути призначені працівники для виконання цих завдань?

Це теж проблема помітної перестановки. Хоча порядок працівників тут не важливий, результат той же:
\ [
\ frac {14!} {6! 5! 3!}
\]
Ще один спосіб думати про проблеми такого типу полягає в тому, що вони є комбінаційними проблемами, оскільки порядок, в якому призначаються працівники, не важливий. У такому випадку нам потрібно вибрати шість з чотирнадцяти робочих для змішування цементу, п'ять для укладання цегли і трьох для перенесення цегли.
Вибрати шість робітників для змішування цементу:\(\quad_{14} C_{6}=\frac{14 !}{6 ! 8 !}\)
Вибрати п'ять робітників (з решти 8) для укладання цегли:\(\quad_{8} C_{5}=\frac{8 !}{5 ! 3 !}\)
вибрати трьох робітників (з решти трьох) нести цеглу: 1

Якщо є\(\frac{14 !}{6 ! 8 !}\) способи вибрати цементна бригада і\(\frac{8 !}{5 ! 3 !}\) способи вибору мулярів з решти восьми робочих, далі буде:
\ [
\ frac {14!} {6! 8!} *\ гідророзриву {8!} {5! 3!} =\ гідророзриву {14!} {6! 5! 3!}
\]
способи доручення працівників до цих завдань.

Вправи 7.5
Знайдіть кількість помітних перестановок заданих букв.
1)\(\quad A A A B B C\)
2)\(\quad A A A B B B C C C\)
3)\(\quad A A B C D\)
4)\(\quad A B C D D D E E\)
5) Скільки способів можна розташувати поспіль два синіх кульки і чотири червоні кульки?
6) Скільки способів можна розташувати в ряд п'ять червоних кульок, дві білі кульки та сім жовтих куль?
7) Скільки різних способів можна розташувати в ряд чотири копійки, три нікеля, дві копейки і три чверті?
8) Скільки способів можуть бути розташовані букви слова ELEEMOSYNARY?
9) Чоловік купив три конуси ванільного морозива, два шоколадні конуси, чотири полуничні конуси і п'ять ірискотч-шишок для 14 дітей. Скільки способів він може розподілити шишки серед дітей.
10) Коли сімеро студентів вирушають у подорож, вони знаходять готель з трьома доступними кімнатами - кімнатою для однієї людини, кімнатою для двох осіб і кімнатою на трьох осіб. Скільки різних способів можуть бути віднесені учні до цих кімнат? (Один студент буде спати в машині)
11) Вісім робітників прибирають великий будинок. П'ять потрібні для очищення вікон, два для чищення килимів і один для очищення решти будинку. Скільки різними способами ці завдання можуть бути покладені на вісім працівників?