bulgakov

18. Итог раздела: какую формулу выбрать

Почти любая задача на подсчёт решается тремя вопросами: что именно считаем (слово, набор, раздачу), важен ли порядок и можно ли повторять. Ответы выбирают формулу; если есть ограничения, задача разбивается на шаги и случаи.

Что пригодится из прошлого: всё предыдущее: правила суммы и произведения, виды выборок, размещения, перестановки, перестановки с повторяющимися элементами, сочетания, сочетания с повторениями, число решений уравнения. Эта глава ничего не добавляет к теории: она собирает формулы в одну схему и тренирует главное умение — выбирать нужную.

Схема выбора

Схема
Что считаем?
│
├─ ВСЕ N элементов в ряд
│   ├─ все разные
│   │     N!
│   └─ k видов: d₁, …, d_k штук
│         N! / (d₁! · … · d_k!)
│
└─ выбираем r элементов из n
    Важен ли порядок?
    ├─ ДА (места, должности)
    │   Можно ли повторять?
    │   ├─ да  → nʳ
    │   └─ нет → n(n−1)…(n−r+1)
    │
    └─ НЕТ (комиссия, набор)
        Можно ли повторять?
        ├─ да  → C(n+r−1, r)
        └─ нет → C(n, r)

Сводка по видам

  • размещения с повторениями — [n]~r=nr\widetilde{[n]}_r=n^r; код, пароль, слово; при n=3n=3, r=2r=2 — 9;
  • размещения без повторений — [n]r=n!(n−r)![n]_r=\dfrac{n!}{(n-r)!}; призовые места, должности; при n=3n=3, r=2r=2 — 6;
  • сочетания без повторений — (nr)=n!r!(n−r)!\dbinom nr=\dfrac{n!}{r!(n-r)!}; комиссия, команда, лотерея; при n=3n=3, r=2r=2 — 3;
  • сочетания с повторениями — (nr)~=(n+r−1r)\widetilde{\dbinom nr}=\dbinom{n+r-1}{r}; набор пирожных, раздача одинаковых предметов; при n=3n=3, r=2r=2 — 6;
  • перестановки — n!n!; расстановка всех nn предметов;
  • перестановки с повторяющимися — N!d1!⋯dk!\dfrac{N!}{d_1!\cdots d_k!}; слова из букв данного слова (NN — длина слова, kk — число разных букв).

Как действовать

  1. Переведите условие на язык слов. Что здесь «слово» (какая позиция что получает), что «набор» (кто вошёл, а кто нет), что «раздача» (сколько кому)?
  2. Задайте два вопроса: порядок важен? повторения разрешены?
  3. Если есть дополнительные условия, разбейте задачу. «И затем» — шаги, перемножаем. «Или» — случаи, складываем. Нарисуйте ячейки.
  4. Проверьте на маленьком примере. Пересчитайте формулу для двух-трёх элементов вручную — как с A={a,b,c}A=\{a,b,c\} в главе про виды выборок.
  5. Проверьте на здравый смысл. Ответ — целое неотрицательное число. Сравните его с числом всех вариантов без ограничений: ответ не может быть больше.

Тренируемся выбирать

1. Восемь бегунов; нужно определить золото, серебро и бронзу.

Решение

Награды разные — порядок важен; один бегун не может получить две награды — без повторений. Размещение: [8]3=8⋅7⋅6=336[8]_3=8\cdot7\cdot6=336.

2. Из тех же восьми бегунов нужно выбрать троих в сборную (без ролей).

Решение

Порядок не важен, повторять нельзя. Сочетание: (83)=56\dbinom83=56. Это число призовых троек 336336, делённое на 3!=63!=6: каждую сборную мы посчитали шесть раз — по числу способов раздать награды.

3. Сколько существует пятизначных кодов (цифры от 00 до 99, повторять можно)?

Решение

Порядок важен, повторения разрешены: 105=100 00010^5=100\,000.

4. Сколько слов можно получить перестановкой букв слова «БАНАН»?

Решение

Есть одинаковые буквы: Б — 11, А — 22, Н — 22. 5!1! 2! 2!=30\dfrac{5!}{1!\,2!\,2!}=30.

5. В магазине четыре вида пирожных. Сколько способов купить шесть (одинаковые разрешены)?

Решение

Порядок покупки не важен, повторения разрешены: сочетание с повторениями, n=4n=4, r=6r=6: (4+6−16)=(96)=84\dbinom{4+6-1}{6}=\dbinom96=84.

6. Сколько существует целых неотрицательных решений уравнения x1+x2+x3=7x_1+x_2+x_3=7?

Решение

Раздача 77 одинаковых единиц трём переменным, то есть сочетание с повторениями: (7+3−17)=(97)=(92)=36\dbinom{7+3-1}{7}=\dbinom97=\dbinom92=36.

7. Из 1010 мальчиков и 1212 девочек нужно выбрать делегацию из двух мальчиков и трёх девочек.

Решение

Два шага подряд: мальчики и девочки. (102)⋅(123)=45⋅220=9900\dbinom{10}{2}\cdot\dbinom{12}{3}=45\cdot220=9900.

8. Пароль — четыре различные латинские буквы (2626 букв), порядок важен. Сколько паролей?

Решение

Размещение без повторений: [26]4=26⋅25⋅24⋅23=358 800[26]_4=26\cdot25\cdot24\cdot23=358\,800.

9. В группе 1212 человек; каждый пожал руку каждому. Сколько рукопожатий?

Решение

Рукопожатие — пара людей без порядка и без повторений: (122)=66\dbinom{12}2=66.

10. Сколько существует четырёхзначных кодов (цифры 00–99), в которых хотя бы одна цифра повторяется?

Решение

Проще посчитать противоположное событие. Всего кодов 104=10 00010^4=10\,000. Кодов без повторов (все цифры разные): 10⋅9⋅8⋅7=504010\cdot9\cdot8\cdot7=5040. Значит, кодов, где хоть одна цифра повторяется,

10 000−5040=4960.10\,000-5040=4960.

Приём «все минус неподходящие» полезен, когда прямой подсчёт распадается на много случаев.

Частые ошибки выбора формулы

  • Должности выдали, а считали сочетание. Если в условии есть слова «первый, второй, третий», «староста», «председатель», «на каждое место» — это порядок.
  • Считали размещения, хотя порядок не важен. Слова «команда», «комиссия», «набор», «лотерея», «пара» — порядка нет.
  • Не заметили, что можно повторять. «Купить пирожные» с одинаковыми — повторения есть; «выбрать людей» — повторений нет.
  • Не разбили сложное условие. Если условий несколько, разбейте на шаги или случаи вместо поиска «волшебной формулы».

Итог

  • Три вопроса: что считаем? важен ли порядок? можно ли повторять?
  • Формулы: nrn^r, [n]r[n]_r, (nr)\dbinom nr, (n+r−1r)\dbinom{n+r-1}{r}, n!n!, N!d1!⋯dk!\dfrac{N!}{d_1!\cdots d_k!}.
  • Условия «и затем» дают произведение, «или» — сумму; иногда проще посчитать противоположное.
  • После ответа проверьте себя на маленьком примере.
ПрактикаЗагружаем тест…