v1 · padrão canônico

Lição 37 — Permutações e arranjos

Permutação total Pn = n!. Arranjo A(n,p). Quando a ordem importa.

Used in: 1.º ano EM (15 anos) · Equiv. Math A japonês · Equiv. Klasse 10 alemã

P_n = n!, \qquad A_n^p = \frac{n!}{(n-p)!}

Choose your door

Rigorous notation, full derivation, hypotheses

Определения и доказательства

Факториал

"Факториал числа $n$ определяется как $n! = n(n-1)(n-2) \cdots 2 \cdot 1$ для $n \geq 1$ , и $0! = 1$ ." — OpenStax Algebra and Trigonometry 2e, §11.7

Рост факториала:

Сверхэкспоненциальный рост n!. Формула Стирлинга: n! ≈ √(2πn)·(n/e)ⁿ.

Перестановка с повторением

Для $n$ объектов, где $n_1$ объектов типа 1, $n_2$ объектов типа 2, ..., $n_k$ объектов типа $k$ (где $n_1 + n_2 + \cdots + n_k = n$ ):

P_n^{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1! \cdot n_2! \cdots n_k!}

what this means · Делим на n_i!, потому что перестановка равных элементов типа i между собой не даёт новую конфигурацию.

Анаграммы слова "ARARA" (3 буквы A, 2 буквы R): $5!/(3! \cdot 2!) = 10$ .

"Число различимых перестановок $n$ объектов, где есть $n_1$ одинаковых объектов типа 1, $n_2$ объектов типа 2, ..., и $n_r$ объектов типа $r$ , равно $\frac{n!}{n_1! n_2! \cdots n_r!}$ ." — OpenStax Algebra and Trigonometry 2e, §11.7

$n$ объектов в круге: $(n-1)!$ . Причина: "первая позиция" произвольна — повворот всех объектов вместе не даёт новую конфигурацию. Формально: зафиксируйте один объект на позиции; остальные $n-1$ переставляются свободно.

Решённые примеры

Example— 1· Прямое вычисление размещения

Задача: Вычислите $A_8^3$ — число способов выбрать и упорядочить 3 объекта из 8 доступных.

Стратегия: Применить формулу $A_n^p = n!/(n-p)!$ , или эквивалентно $A_n^p = n(n-1)\cdots(n-p+1)$ ( $p$ убывающих множителей начиная с $n$ ).

Решение:

Факториальная форма: $A_8^3 = \dfrac{8!}{(8-3)!} = \dfrac{8!}{5!} = \dfrac{8 \cdot 7 \cdot 6 \cdot 5!}{5!} = 8 \cdot 7 \cdot 6$ .
Умножение: $8 \cdot 7 = 56$ и $56 \cdot 6 = 336$ .
Результат: $A_8^3 = 336$ .

Проверка: Прямым подсчётом через принцип произведения (1-я позиция: 8 вариантов; 2-я: 7; 3-я: 6) получаем $8 \cdot 7 \cdot 6 = 336$ . Согласуется.

Источник. OpenStax Algebra and Trigonometry 2e §11.7 — лицензия CC-BY 4.0.

Example— 2· Анаграммы с повторяющимися буквами

Задача: Сколько различных анаграмм можно составить из слова "BANANA"?

Стратегия: Слово содержит 6 букв с повторениями: 3 буквы A, 2 буквы N и 1 буква B. Применить формулу перестановки с повторением.

Решение:

Определить кратности: $n = 6$ , $n_A = 3$ , $n_N = 2$ , $n_B = 1$ .
Применить формулу: $P_6^{3,2,1} = \dfrac{6!}{3! \cdot 2! \cdot 1!}$ .
Вычислить: $6! = 720$ , $3! = 6$ , $2! = 2$ , $1! = 1$ . Значит $720/(6 \cdot 2 \cdot 1) = 720/12 = 60$ .

Проверка: Без деления на повторения получили бы $6! = 720$ перестановок, но перестановки между 3 одинаковыми A'ми не дают новый анаграмм ( $3! = 6$ одинаковых перестановок), и перестановки между 2 N'ми дают $2! = 2$ одинаковых перестановок. $720/(6 \cdot 2) = 60$ .

Источник. Wikilivros — Matemática elementar / Combinatória — лицензия CC-BY-SA.

Example— 3· Циклическая перестановка с ограничением

Задача: 8 человек сидят вокруг круглого стола. Двое из них, Анна и Борис, хотят сидеть рядом. Сколько различных конфигураций?

Стратегия: Рассмотрите Анну и Бориса как один блок. Тогда остаётся 7 "объектов" для размещения вокруг круглого стола: $(7-1)! = 6!$ . Внутри блока Анна и Борис могут поменяться местами: $2!$ способов.

Решение:

Блок "AB" + 6 других человек = 7 объектов вокруг круглого стола: $(7-1)! = 6! = 720$ .
Внутренняя перестановка блока: $2! = 2$ (AB или BA).
Итого: $720 \cdot 2 = 1\,440$ .

Проверка: Без ограничения 8 человек вокруг круглого стола дают $7! = 5\,040$ конфигураций. Учитывая позицию Анны, Борис имеет 2 возможных соседа из 7 оставшихся мест — доля $2/7$ . $5\,040 \cdot 2/7 = 1\,440$ . Согласуется.

Источник. Wikilivros — Matemática elementar / Combinatória — лицензия CC-BY-SA.

Example— 4· Решение факториального уравнения

Задача: Найдите значение $n \in \mathbb{N}$ , удовлетворяющее $\dfrac{(n+2)!}{n!} = 56$ .

Стратегия: Упростить факториальное частное, используя $(n+2)! = (n+2)(n+1) \cdot n!$ , приводя к полиномиальному уравнению в $n$ .

Решение:

Упростить: $\dfrac{(n+2)!}{n!} = \dfrac{(n+2)(n+1) \cdot n!}{n!} = (n+2)(n+1)$ .
Уравнение: $(n+2)(n+1) = 56$ , или $n^2 + 3n + 2 = 56 \Rightarrow n^2 + 3n - 54 = 0$ .
Формула Бхаскары: $n = \dfrac{-3 \pm \sqrt{9 + 216}}{2} = \dfrac{-3 \pm 15}{2}$ . Решения: $n = 6$ или $n = -9$ .
Поскольку $n \in \mathbb{N}$ , отбросьте $n = -9$ . Ответ: $n = 6$ .

Проверка: $(6+2)!/6! = 8!/6! = 8 \cdot 7 = 56$ . Верно.

Источник. Stitz–Zeager Precalculus §9.5 — лицензия CC-BY-NC-SA.

Example— 5· Пароли с позиционным ограничением

Задача: Пароль содержит 5 символов, все разные, выбранные из алфавита $\{A, B, C, \ldots, Z\}$ (26 букв). По требованию первый символ должен быть гласной ( $A, E, I, O, U$ ). Сколько различных паролей существует?

Стратегия: По принципу произведения: считайте первую позицию (гласная) и затем размещение 4 оставшихся позиций среди 25 оставшихся букв.

Решение:

Первый символ: 5 вариантов (гласные).
Следующие 4 позиции: размещение $A_{25}^4 = 25 \cdot 24 \cdot 23 \cdot 22$ , так как без повторения.
Вычисление: $25 \cdot 24 = 600$ , $600 \cdot 23 = 13\,800$ , $13\,800 \cdot 22 = 303\,600$ .
Итого: $5 \cdot 303\,600 = 1\,518\,000$ .

Проверка: Без ограничения $A_{26}^5 = 26 \cdot 25 \cdot 24 \cdot 23 \cdot 22 = 7\,893\,600$ . Доля паролей, начинающихся с гласной, $5/26$ . $7\,893\,600 \cdot 5/26 = 1\,518\,000$ . Согласуется.

Источник. OpenStax Algebra and Trigonometry 2e §11.7 — лицензия CC-BY 4.0.

Exercise list

46 exercises · 11 with worked solution (25%)

Application 32Understanding 4Modeling 8Challenge 1Proof 1

Ex. 37.1Application
Вычислите $5!$ .
Solve online
Ex. 37.2Application
Вычислите $8!/5!$ .
Solve online
Ex. 37.3ApplicationAnswer key
Сколько анаграмм слова "MAR" существует?
Solve online
Ex. 37.4Application
Сколько анаграмм слова "CASA" существует?
Solve online
Ex. 37.5Application
Сколько анаграмм слова "MISSISSIPPI" существует?
Solve online
Ex. 37.6ApplicationAnswer key
Вычислите $A_5^3$ .
Solve online
Ex. 37.7Application
Вычислите $A_8^2$ .
Solve online
Ex. 37.8ApplicationAnswer key
Сколько рядов из 4 человек можно составить из 7 кандидатов?
Solve online
Ex. 37.9Application
Награждение 1-е, 2-е, 3-е место среди 12 спортсменов. Сколько различных пьедесталов возможно?
Solve online
Ex. 37.10Application
Сколько трёхзначных чисел с различными цифрами можно составить из $\{1, 2, 3, 4, 5\}$ ?
Solve online
Ex. 37.11ApplicationAnswer key
Проверьте равенство $7!/(7-3)! = 7 \cdot 6 \cdot 5$ .
Solve online
Ex. 37.12Application
Решите $n! = 720$ .
Solve online
Ex. 37.13Application
Решите $A_n^2 = 30$ для $n \in \mathbb{N}$ .
Solve online
Ex. 37.14ApplicationAnswer key
Сколько анаграмм слова "CIDADE" существует?
Solve online
Ex. 37.15Application
Сколько анаграмм слова "BANANA" существует?
Solve online
Ex. 37.16ApplicationAnswer key
Сколько паролей из 5 различных цифр можно составить из цифр $\{0, 1, \ldots, 9\}$ ?
Solve online
Ex. 37.17Application
Сколькими способами 6 различных книг можно расставить на 3 полки (по 2 на каждую), учитывая порядок на каждой полке?
Solve online
Ex. 37.18Application
8 человек за круглым столом. Сколько различных конфигураций?
Solve online
Ex. 37.19Understanding
Объясните, почему циклическая перестановка $n$ человек равна $(n-1)!$ , а не $n!$ .
Solve online
Ex. 37.20Application
Сколько анаграмм слова "AMOR" начинаются с буквы A?
Solve online
Ex. 37.21Application
Сколько анаграмм слова "MATEMATICA" существует?
Solve online
Ex. 37.22Application
Сколько анаграмм слова "PROVA" начинаются с согласной?
Solve online
Ex. 37.23Application
Анаграммы слова "AMOR" где A и O рядом в этом порядке (блок "AO" неразделимый).
Solve online
Ex. 37.24ApplicationAnswer key
10 студентов сидят на 10 стульях в ряду. 2 друга хотят сидеть рядом. Сколько конфигураций?
Solve online
Ex. 37.25Application
8 человек за круглым столом; 2 хотят сидеть вместе. Сколько конфигураций?
Solve online
Ex. 37.26Application
Анаграммы слова "LIVRO" начинающиеся с гласной.
Solve online
Ex. 37.27ApplicationAnswer key
Сколько четырёхзначных чисел с различными цифрами можно составить из цифр $\{1, \ldots, 9\}$ ?
Solve online
Ex. 37.28Application
Сколько чётных четырёхзначных чисел с различными цифрами можно составить из цифр $\{1, 2, 3, 4, 5\}$ ?
Solve online
Ex. 37.29Application
Решите $n!/(n-3)! = 60$ для $n \in \mathbb{N}$ .
Solve online
Ex. 37.30Application
Решите $(n+1)!/n! = 5$ .
Solve online
Ex. 37.31Application
На гонке с 10 спортсменами, сколько различных пьедесталов (1-е, 2-е, 3-е место) возможно?
Solve online
Ex. 37.32Application
Сколько анаграмм слова "FATORIAL" существует (все буквы различные)?
Solve online
Ex. 37.33Application
Пять карт выбраны и упорядочены в ряд из 7 различных карт — сколько конфигураций?
Solve online
Ex. 37.34Understanding
Проверьте рекуррентное соотношение $A_n^p = n \cdot A_{n-1}^{p-1}$ для $n = 6, p = 3$ .
Solve online
Ex. 37.35Modeling
Футбольная команда: 11 игроков занимают 11 различных позиций на поле. Сколько расстановок с позиционированием существует?
Solve online
Ex. 37.36Modeling
Пароли из 8 строчных букв без повторения. Сколько различных паролей существует?
Solve online
Ex. 37.37ModelingAnswer key
В логистике, каково число возможных порядков доставки 10 различных пакетов на 10 адресов?
Solve online
Ex. 37.38Modeling
В карточной игре, сколько различных конфигураций колоды из 52 карт существует после тасования?
Solve online
Ex. 37.39Modeling
В ДНК, последовательность 8 оснований (A, T, C, G) где каждое основание появляется ровно 2 раза. Сколько различных последовательностей существует?
Solve online
Ex. 37.40Modeling
В популяционной генетике, сколько возможных порядков существует для упорядочения 4 различных аллелей в цепи?
Solve online
Ex. 37.41Modeling
В машинном обучении, важность признака через перестановку тасует признак над $N$ образцами и измеряет потерю в предсказании. Сколько возможных перестановок $N$ образцов существует?
Solve online
Ex. 37.42Modeling
В компьютерной графике, сколько порядков рендеринга существует для 100 полигонов?
Solve online
Ex. 37.43Understanding
Докажите, что $A_n^p = n \cdot A_{n-1}^{p-1}$ .
Solve online
Ex. 37.44UnderstandingAnswer key
Покажите, что $P_n = A_n^n$ .
Solve online
Ex. 37.45Challenge
Сколько анаграмм слова "AMOR" начинаются с согласной и заканчиваются гласной?
Solve online
Ex. 37.46ProofAnswer key
Докажите, что $A_n^p = n!/(n-p)!$ используя Принцип Фундаментального Подсчёта.
Solve online

Источники

Только книги, которые питали непосредственно текст и упражнения.

OpenStax Algebra and Trigonometry 2e — Jay Abramson et al. · 2022, 2nd ed · EN · CC-BY 4.0 · §11.7 Counting Principles. Первичный источник.
Wikilivros — Matemática elementar / Combinatória — коллективный · PT-BR · CC-BY-SA · перестановки, размещения, анаграммы. Исходный источник на португальском.
Stitz–Zeager Precalculus — Carl Stitz, Jeff Zeager · 2013, v3 · EN · CC-BY-NC-SA · §9.5 Counting.
Book of Proof — Richard Hammack · 2018, 3rd ed · EN · CC-BY-ND · cap. 3.

Lição 37 — Permutações e arranjos

Определения и доказательства

Факториал

Простая перестановка

Перестановка с повторением

Простое размещение

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

Решённые примеры

Exercise list

Источники