Перестановки и сочетания
| English | Русский |
|---|---|
| permutation/ˌpɜːmjuːˈteɪʃn/ | перестановка |
| combination/ˌkɒmbɪˈneɪʃn/ | комбинации |
| factorial/fækˈtɔːrɪəl/ | факториал |
| multiplication principle/ˌmʌltɪplɪˈkeɪʃn ˈprɪnsɪpl/ | правило умножения |
Сколько способов расставить книги на полке?
- У вас есть 10 книг, и вы хотите выбрать 3 для экспозиции. Сколькими способами это можно сделать? Если порядок имеет значение, это перестановка. Если вам нужны любые 3, это сочетание.
- Комбинаторные методы являются основой теории вероятностей — они встречаются повсюду, от лотерейных шансов до безопасности паролей.
Лабораторная работа по перестановкам и сочетаниям
Определите, имеет ли значение порядок в задаче на подсчет.
Перестановки (порядок имеет значение)
- Перестановка — это расположение, где порядок имеет значение: ${}^nP_r = \dfrac{n!}{(n-r)!}$.
- Пример: размещение 3 книг из множества 10: ${}^{10}P_3 = \dfrac{10!}{7!} = 10 \times 9 \times 8 = 720$.
Разобранный пример. Сколько кодов из 3 букв можно составить из алфавита 26 букв (без повторений)? Ответ: ${}^{26}P_3 = 26 \times 25 \times 24 = 15\,600$.
Перестановки: 3 книги можно расположить в 3 × 2 × 1 = 6 различных порядках
В сочетании порядок выбранных элементов:
Сочетания игнорируют порядок; перестановки учитывают порядок.
Сколькими способами можно расставить 3 книги из 10 на полке (¹⁰P₃)?
¹⁰P₃ = 10!/(10-3)! = 10!/7! = 10 × 9 × 8 = 720.
Сочетания (порядок не имеет значения)
- Сочетание — это выбор, где порядок не имеет значения: ${}^nC_r = \dbinom{n}{r} = \dfrac{n!}{r!\,(n-r)!}$.
- Пример: выбор 3 книг из 10: ${}^{10}C_3 = \dfrac{10!}{3!\,7!} = \dfrac{720}{6} = 120$.
Перестановка против сочетания. Выбор комитета из 3 человек из 10 — это сочетание (порядок не важен). Выбор президента, вице-президента и секретаря из 10 человек — это перестановка (порядок важен — роли различны).
Для перестановки порядок имеет значение, но не для сочетания
Сколькими способами можно выбрать 2 из 5 (⁵C₂)?
⁵C₂ = 5!/(2!3!) = 120/(2×6) = 10.
⁵P₃ больше, чем ⁵C₃.
⁵P₃ = 60 (порядок важен), ⁵C₃ = 10 (порядок не важен). Перестановки всегда ≥ сочетаний.
Расстановки с повторениями
- Чтобы расположить слово с повторяющимися буквами, разделите факториал на факториал каждого количества повторений.
- Пример: NEEDLESS содержит 8 букв, из которых 3 буквы E и 2 буквы S: количество расстановок $= \dfrac{8!}{3!\,2!} = \dfrac{40320}{12} = 3360$.
Сколькими способами можно расставить буквы слова NEEDLESS? (8 букв: E×3, S×2 → 8!/(3!2!))
8!/(3!2!) = 40320/(6×2) = 40320/12 = 3360.
Правило умножения
- Если один выбор можно сделать $m$ способами, а другой $n$ способами, то оба вместе можно сделать $m \times n$ способами.
- Пример: 3 рубашки и 4 брюк → $3 \times 4 = 12$ комплектов одежды.
У вас есть 3 рубашки и 4 брюки. Сколько комплектов одежды можно составить?
3 × 4 = 12 комплектов (правило умножения).
Вы поняли
- Перестановка (порядок имеет значение): ${}^nP_r = \dfrac{n!}{(n-r)!}$
- Сочетание (порядок не имеет): ${}^nC_r = \dfrac{n!}{r!(n-r)!}$
- Повторяющиеся буквы: разделить $n!$ на факториал каждого повторения (NEEDLESS → $\dfrac{8!}{3!\,2!}$)