9 класс Вероятность и статистика Элементы комбинаторики

Комбинаторное правило умножения

Содержание

В уроке «Монета и кубик: равновозможные исходы» мы перечисляли исходы деревом и таблицей $6 \times 6$. Когда вариантов сотни и тысячи, перечислять их долго. В этом уроке научимся считать способы выбора без перечисления — по комбинаторному правилу умножения — и применим его к числам, кодам и вероятностям.

Вопрос, на который ответим в разделе о кодах. На номере легкового автомобиля стоят буква, три цифры и еще две буквы, например А 123 ВС, а справа — код региона. Букв разрешено всего 12: А, В, Е, К, М, Н, О, Р, С, Т, У, Х. Цифры — от 001 до 999. Сколько разных номеров можно выдать с одним кодом региона?

Два шага выбора — два яруса дерева

В кафе к обеду предлагают одно блюдо — суп, салат или кашу — и один напиток — чай или сок. Сколько разных комплектов «блюдо и напиток» можно составить? Вообразавр советует: представьте выбор деревом. Из корня выходят 3 ветви — это первый шаг, выбор блюда. От конца каждой из них отходят 2 ветви — второй шаг, выбор напитка.

Дерево выбора обеда: 3 блюда и 2 напитка; 6 листьев разбиты на 3 группы по 2, комплектов 3 · 2 = 6 — Каждая из 3 ветвей-блюд продолжается 2 ветвями-напитками: листьев $3 \cdot 2 = 6$ — шесть комплектов

Каждый комплект — это путь от корня до листа: «суп и чай», «суп и сок», «салат и чай», «салат и сок», «каша и чай», «каша и сок». Те же шесть комплектов можно записать таблицей: строки — блюда, столбцы — напитки, в каждой клетке — один комплект.

Блюдо	Чай	Сок
Суп	суп и чай	суп и сок
Салат	салат и чай	салат и сок
Каша	каша и чай	каша и сок

Листья не нужно пересчитывать по одному. Они разбиты на 3 одинаковые группы — по одной на каждое блюдо, — и в каждой группе 2 листа. Три группы по два листа — это $3 \cdot 2 = 6$. В таблице то же самое: 3 строки по 2 клетки.

Определение

Дерево выборов — схема, в которой каждый шаг выбора изображен ярусом ветвей, а каждый способ выбора — путем от корня до листа. Число способов равно числу листьев.

{"questions":[{"content":"У Ани 4 футболки и 3 пары шорт. Сколько разных комплектов «футболка и шорты» она может составить?[[choice-1]]","widgets":{"choice-1":{"type":"choice","options":["$19$","$7$","$12$","$3$"],"explanations":["Это $4 \\cdot 3 + 4 + 3$: комплект — только пара «футболка и шорты», отдельные вещи комплектом не считаются","Это $4 + 3$: сложение считает отдельные вещи, а не пары «футболка и шорты»","","Так считают шорты к одной футболке, а каждая из 4 футболок тоже сочетается с любыми шортами"],"answer":[2]}},"hints":["Комплект — пара из двух выборов: футболка и шорты.","Каждую футболку можно надеть с любыми из 3 шорт.","$4 \\cdot 3 = 12$."],"step":1},{"content":"Чтобы найти число путей в дереве выбора, числа ветвей на ярусах [[fill_choice-1]].","widgets":{"fill_choice-1":{"type":"fill_choice","options":["делят","складывают","вычитают","перемножают"],"answer":3}},"instruction":"Выберите слово","hints":["Каждая ветвь яруса продолжается всеми ветвями следующего яруса.","Поэтому число путей растет умножением: ярус за ярусом."],"step":1}],"mix":1}

С каждым ярусом число путей умножается

Добавим третий шаг: к обеду можно взять десерт — мороженое или яблоко. Теперь каждый из 6 листьев разветвляется еще на 2 ветви, и листьев становится $6 \cdot 2 = 12$. Рисовать все 12 путей не обязательно: хватит одного пути и числа ветвей на каждом ярусе.

Свернутое дерево трех шагов: один путь обед — суп — чай — мороженое, у остальных ветвей короткие отростки; путей 3 · 2 · 2 = 12 — Один путь из двенадцати: на ярусах 3, 2 и 2 ветви, путей $3 \cdot 2 \cdot 2 = 12$

Так устроен любой выбор в несколько шагов. Если из каждого конца предыдущего яруса выходит одинаковое число ветвей, то на каждом ярусе число путей умножается на число ветвей этого яруса.

Правило

Комбинаторное правило умножения: если первый выбор можно сделать $n_1$ способами, второй — $n_2$, …, то все выборы подряд — $n_1\cdot n_2\cdot\ldots$ способами.

$$N = n_1 \cdot n_2 \cdot \ldots \cdot n_k$$

Здесь $k$ — число шагов. Важно, чтобы число вариантов на каждом шаге не зависело от того, что выбрали раньше.

Ошибка

Решавр считает комплекты «блюдо и напиток» так: «Блюд 3, напитков 2, значит, комплектов $3 + 2 = 5$».

Проверим перечислением. У одного только супа два комплекта: «суп и чай», «суп и сок». У салата и у каши — тоже по два. Всего 6, а не 5.

Где сломалось рассуждение: $3 + 2 = 5$ — это число предметов в меню: суп, салат, каша, чай, сок. Решавр сосчитал предметы, а комплект — это путь от корня до листа. Каждое блюдо входит в столько комплектов, сколько напитков, поэтому нужно умножать.

Ошибка Решавра: сумма 3 + 2 = 5 считает предметы меню, а комплект — путь в дереве; путей 6 — Решавр сосчитал 5 предметов меню. Комплектов столько, сколько путей от корня до листьев: 6

derevo-vyborov

Сложение тоже бывает нужно — когда выбирают одно из двух. Из города $A$ в город $C$ можно доехать через город $B$: из $A$ в $B$ ведут 3 дороги, из $B$ в $C$ — 2 дороги. Кроме того, из $A$ в $C$ ведут 2 прямые дороги.

Маршруты из A в C: через B дороги перемножаются, 3 · 2 = 6; напрямую 2; наборы складываются, 6 + 2 = 8 — Через $B$ — $3 \cdot 2 = 6$ маршрутов, напрямую — 2. Маршрут идет либо через $B$, либо напрямую: $6 + 2 = 8$

Маршрут через $B$ — два шага подряд: дорога до $B$ и дорога от $B$. Это выбор «и», числа перемножаем: $3 \cdot 2 = 6$. Прямой маршрут — другой набор, и путник выбирает либо его, либо маршрут через $B$. Это выбор «или», числа складываем: $6 + 2 = 8$.

Правило

«И» или «или». Шаги, которые делают один за другим (и то, и другое), — числа вариантов перемножают. Если выбирают одно из разных наборов (или то, или другое), числа вариантов складывают.

{"questions":[{"content":"У Пети 2 куртки и 5 шапок. Решавр посчитал комплекты «куртка и шапка» так: $2 + 5 = 7$. В чем ошибка?[[choice-1]]","widgets":{"choice-1":{"type":"choice","options":["Он сосчитал вещи, а не пары: каждая куртка идет с любой из 5 шапок, комплектов $2 \\cdot 5 = 10$","Он не возвел в степень: комплектов $5^2 = 25$","Ошибки нет: комплектов 7","Он не учел, что шапок больше, чем курток: комплектов $5-2=3$"],"explanations":["","Степень нужна, когда один и тот же набор выбирают дважды, а здесь куртки и шапки — разные наборы","На дереве 10 листьев: например, «куртка 1 и шапка 2» и «куртка 2 и шапка 2» — разные комплекты, а в 7 они не учтены","Разность ничего не считает: с одной только первой курткой уже 5 комплектов"],"answer":[0]}},"hints":["Нарисуйте дерево: от каждой из 2 курток отходят 5 ветвей-шапок.","Листьев $2 \\cdot 5 = 10$: комплектов 10, а не 7."],"step":1},{"content":"Распределите задачи по группам: где числа вариантов перемножают, а где складывают.[[grouper-1]]","widgets":{"grouper-1":{"type":"grouper","labels":["Перемножаем: шаги «и»","Складываем: выбор «или»"],"items":[["Выбрать суп и напиток к нему","Проехать из $A$ в $C$ через $B$","Составить код из двух цифр"],["Взять одну книгу: роман или сборник стихов","Уехать одним рейсом: автобусом или поездом","Выбрать один подарок: игру или книгу"]]}},"instruction":"Распределите задачи по группам","hints":["Если выбор состоит из нескольких шагов подряд (и то, и другое) — это ярусы дерева, числа перемножают.","Если выбирают один предмет из одного набора или из другого — дерево с одним ярусом, ветви складывают.","Ответ: перемножают — суп и напиток, путь через $B$, код из двух цифр; складывают — одна книга, один рейс, один подарок."],"step":1},{"content":"Из города $A$ в город $B$ ведут 3 дороги, из $B$ в $C$ — 4 дороги, из $C$ в $D$ — 2 дороги. Сколько существует маршрутов из $A$ в $D$ через $B$ и $C$? [[input-1]]","widgets":{"input-1":{"type":"input","answer":"24"}},"hints":["Маршрут — это три выбора подряд: дорога $A \\to B$, затем $B \\to C$, затем $C \\to D$.","Числа способов на шагах перемножают: $3 \\cdot 4 \\cdot 2$.","Ответ: 24 маршрута."],"step":1}],"mix":1}

Запрет вычеркивает ветви, а строгий шаг идет первым

Составим двузначные числа из цифр $0, 1, 2, 3$ так, чтобы цифры не повторялись. Без ограничений на первом месте стояла бы любая из 4 цифр, на втором — любая из 3 оставшихся: $4 \cdot 3 = 12$. Но число не может начинаться с нуля: запись $03$ — не двузначное число.

Дерево чисел из разных цифр 0–3 без нуля впереди: ветвь «0» вычеркнута, остается 3 · 3 = 9 чисел, а не 12 — Ветвь «0» на первом ярусе вычеркнута вместе с ее листьями: остается $3 \cdot 3 = 9$ путей, а не 12

На дереве запрет виден сразу: ветвь «0» первого яруса вычеркиваем вместе со всеми ее листьями. Остаются 3 ветви — цифры $1$, $2$, $3$. Из каждой выходят 3 ветви: любая цифра, кроме уже поставленной, и ноль теперь разрешен. Чисел $3 \cdot 3 = 9$: $10$, $12$, $13$, $20$, $21$, $23$, $30$, $31$, $32$.

На втором ярусе у разных ветвей разные цифры, но их число одинаковое — 3. Поэтому правило умножения работает. Запрет удобнее всего учесть в самом начале: шаг, на который наложен запрет, ставим первым.

Ошибка

Решавр считает трехзначные числа, у которых все цифры разные: «Первая цифра — 10 способов, вторая — 9, третья — 8, всего $10 \cdot 9 \cdot 8 = 720$».

Проверим тем же способом на цифрах $0, 1, 2, 3$: по схеме Решавра двузначных чисел было бы $4 \cdot 3 = 12$, а на дереве их 9. Лишние записи — $01$, $02$, $03$.

Где сломалось рассуждение: Решавр не вычеркнул ветвь «0» на первом ярусе. Верно так: первая цифра — любая, кроме нуля, 9 способов; вторая — любая, кроме первой, 9 способов (ноль теперь можно); третья — 8 способов. Чисел $9 \cdot 9 \cdot 8 = 648$. Лишние $720-648 = 72$ записи Решавра начинаются с нуля, например $012$.

Алгоритм

Разбейте выбор на шаги: например, первая, вторая и третья цифры числа.
Начните с самого строгого шага — того, на который наложен запрет.
Для каждого следующего шага посчитайте, сколько вариантов осталось после уже сделанных выборов.
Перемножьте числа вариантов всех шагов.
Если число вариантов какого-то шага зависит от того, что выбрали раньше, разбейте задачу на случаи, в каждом случае перемножьте, а результаты сложите.

Пример 1

Задача. Сколько существует трехзначных четных чисел, у которых все цифры разные?

Решение. Запретов два: первая цифра не $0$, последняя — четная, то есть $0$, $2$, $4$, $6$ или $8$. Самый строгий шаг — последняя цифра. Но от нее зависит первая: если последняя цифра $0$, ноль уже занят и на первое место подходят 9 оставшихся цифр; если последняя $2$, $4$, $6$ или $8$, на первое место нельзя ни ее, ни ноль — остается 8 цифр. Дерево неравномерное, поэтому разберем два случая.

Случай 1: последняя цифра $0$ — 1 способ, первая — 9 способов, средняя — любая из 8 оставшихся: $1 \cdot 9 \cdot 8 = 72$.

Случай 2: последняя цифра $2$, $4$, $6$ или $8$ — 4 способа, первая — 8 способов, средняя — любая, кроме двух уже поставленных, 8 способов: $4 \cdot 8 \cdot 8 = 256$.

Число оканчивается либо нулем, либо другой четной цифрой — это выбор «или», складываем: $72 + 256 = 328$. Одним произведением $5 \cdot 8 \cdot 8 = 320$ не обойтись: при последней цифре $0$ у первой цифры 9 вариантов, а не 8.

Ответ: 328 чисел.

{"questions":[{"content":"Решавр считал двузначные числа с разными цифрами, составленные из цифр $0, 1, 2, 3, 4, 5$, и написал: $6 \\cdot 5 = 30$. В чем ошибка?[[choice-1]]","widgets":{"choice-1":{"type":"choice","options":["Ошибки нет: чисел 30","Ветвь «$0$» на первом месте надо вычеркнуть: первая цифра — 5 способов, всего $5 \\cdot 5 = 25$","Ноль нельзя ставить никуда: надо $5 \\cdot 4 = 20$","Цифры могут повторяться: надо $6 \\cdot 6 = 36$"],"explanations":["Среди 30 записей есть $01$, $02$, …, $05$ — это не двузначные числа","","На втором месте ноль разрешен: $10$, $20$, $50$ — двузначные числа","В условии сказано, что цифры разные, повторы запрещены"],"answer":[1]}},"hints":["Посмотрите на первый ярус дерева: может ли число начинаться с $0$?","Первая цифра — 5 способов (без нуля), вторая — любая из 5 оставшихся, ноль теперь можно.","$5 \\cdot 5 = 25$."],"level":"повышенный","step":1},{"content":"Сколько существует двузначных нечетных чисел, у которых цифры разные? [[input-1]]","widgets":{"input-1":{"type":"input","answer":"40"}},"hints":["Начнем с самого строгого условия: последняя цифра нечетная — 5 способов ($1, 3, 5, 7, 9$).","Первая цифра: не $0$ и не равна последней — $10-2=8$ способов.","$5 \\cdot 8 = 40$."],"level":"повышенный","step":1},{"content":"Сколько трехзначных четных чисел с разными цифрами можно составить из цифр $0, 1, 2, 3$? [[input-2]]","widgets":{"input-2":{"type":"input","answer":"10"}},"hints":["Самый строгий шаг — последняя цифра: $0$ или $2$. Но от нее зависит, сколько вариантов у первой цифры, поэтому разберем два случая.","Последняя $0$: первая — из $1, 2, 3$ (3 способа), средняя — из двух оставшихся: $3 \\cdot 2 = 6$.","Последняя $2$: первая — $1$ или $3$ (2 способа), средняя — из двух оставшихся (ноль можно): $2 \\cdot 2 = 4$.","Случаи не пересекаются («или»), складываем: $6 + 4 = 10$."],"level":"повышенный","step":1}],"mix":1}

Коды и номера: когда дерево не нарисовать

Код замка — четыре цифры, каждая от $0$ до $9$. Ноль впереди здесь разрешен: код — не число, а последовательность цифр. Если цифры могут повторяться, на каждой позиции 10 вариантов. Если все цифры кода разные, на каждой следующей позиции вариантов на один меньше.

Код из 4 цифр: с повторами в каждой колонке 10 вариантов, 10⁴ = 10 000; без повторов числа убывают на 1, 5040 — С повторами — $10^4 = 10\,000$ кодов, без повторов — $10 \cdot 9 \cdot 8 \cdot 7 = 5040$: запрет на повторы убирает почти половину кодов

У дерева кода четыре яруса и $10\,000$ листьев — нарисовать его нельзя, а посчитать по правилу легко. Таблица «позиция — число вариантов» и есть свернутое дерево: в каждой колонке записано число ветвей одного яруса. Если повторы разрешены, колонки одинаковые и произведение равно степени $10^4$. Если запрещены, числа в колонках убывают на единицу.

Обратите внимание

Код может начинаться с нуля, а число — нет. Перед подсчетом решите, что вы считаете: код (последовательность цифр) или число. От этого зависит, 10 или 9 вариантов у первой цифры.

Пример 2

Задача. На номере автомобиля стоят буква, три цифры от $001$ до $999$ и еще две буквы; разрешены 12 букв. Сколько номеров можно выдать с одним кодом региона?

Решение. Разобьем номер на четыре места: буква, группа цифр, буква, буква. Буквы могут повторяться — номер А 123 АА возможен, — поэтому на каждом буквенном месте 12 вариантов. Группа цифр — одно место с 999 вариантами: от $001$ до $999$, комбинацию $000$ не выдают. По правилу умножения:

$$12 \cdot 999 \cdot 12 \cdot 12 = 1728 \cdot 999 = 1\,726\,272$$

Это немного: в крупных регионах машин больше, поэтому им выдают несколько кодов региона.

Ответ: 1 726 272 номера.

Номер автомобиля как 4 места выбора: 12 · 999 · 12 · 12 = 1 726 272 номеров на один код региона — Четыре места номера: $12 \cdot 999 \cdot 12 \cdot 12 = 1\,726\,272$ номера на один код региона

{"questions":[{"content":"На кодовом замке 6 кнопок с цифрами от $1$ до $6$. Код — три разные кнопки, нажатые в определенном порядке. Какое выражение дает число таких кодов?[[choice-1]]","widgets":{"choice-1":{"type":"choice","options":["$6 \\cdot 6 \\cdot 6$","$6 + 5 + 4$","$3 \\cdot 2 \\cdot 1$","$6 \\cdot 5 \\cdot 4$"],"explanations":["Так считают, если кнопку можно нажать повторно, а здесь кнопки разные","Сложение считает варианты отдельных нажатий, а код — это три нажатия подряд","Так считают только порядок трех уже выбранных кнопок, а сами кнопки еще нужно выбрать из 6",""],"answer":[3]}},"hints":["Первая кнопка — любая из 6, вторая — любая из оставшихся 5, третья — из оставшихся 4.","Шаги идут подряд, числа перемножают: $6 \\cdot 5 \\cdot 4 = 120$."],"step":1},{"content":"Соотнесите задачу и выражение. Одно выражение лишнее.[[matcher-1]]","widgets":{"matcher-1":{"type":"matcher","labels":["Код из 3 цифр, цифры могут повторяться","Код из 3 разных цифр","Трехзначное число","Трехзначное число с разными цифрами"],"items":["$10 \\cdot 10 \\cdot 10$","$10 \\cdot 9 \\cdot 8$","$9 \\cdot 10 \\cdot 10$","$9 \\cdot 9 \\cdot 8$","$10 + 9 + 8$"]}},"instruction":"Соотнесите задачу и выражение","hints":["Код может начинаться с нуля, число — нет: у трехзначного числа на первом месте 9 вариантов.","Если цифры не повторяются, на каждом следующем месте вариантов на один меньше.","Ответ: код с повторами — $10 \\cdot 10 \\cdot 10$; код с разными цифрами — $10 \\cdot 9 \\cdot 8$; трехзначное число — $9 \\cdot 10 \\cdot 10$; трехзначное число с разными цифрами — $9 \\cdot 9 \\cdot 8$; лишнее — $10 + 9 + 8$."],"step":1}],"mix":1}

Число исходов для вероятности — без перечисления

В уроке «Монета и кубик» у двух бросков игральной кости была таблица из 36 исходов. Теперь видно, откуда 36: первый бросок — 6 строк, второй — 6 столбцов, $6 \cdot 6 = 36$. Таблица — то же дерево с двумя ярусами: строка — ветвь первого яруса, клетка строки — лист.

Таблица 36 исходов двух бросков как дерево из двух ярусов по 6 ветвей: ветвь — строка, лист — клетка, 6 · 6 = 36 — Таблица 36 исходов — это дерево из двух ярусов по 6 ветвей: $6 \cdot 6 = 36$

Для вероятности $P(A)=\dfrac{m}{n}$ из урока «Вероятность случайного события» нужно число всех исходов $n$. Правило умножения находит его без перечисления: у трех бросков монеты $2 \cdot 2 \cdot 2 = 8$ исходов, у десяти бросков — $2^{10} = 1024$, и такое дерево уже не нарисовать. Если монета симметрична, а кость правильная, все листья дерева — равновозможные исходы.

Пример 3

Задача. Игральную кость бросают три раза. Найдите вероятность того, что все три раза выпадет одно и то же число очков.

Решение. Каждый бросок — ярус из 6 ветвей. Всех исходов $n = 6 \cdot 6 \cdot 6 = 216$.

Благоприятные исходы тоже посчитаем по правилу: первый бросок — любой, 6 способов; второй должен совпасть с первым — 1 способ; третий — 1 способ. $m = 6 \cdot 1 \cdot 1 = 6$: это $(1;1;1)$, $(2;2;2)$, …, $(6;6;6)$.

$$P=\frac{6}{216}=\frac{1}{36}$$

Если сложить исходы бросков, $6 + 6 + 6 = 18$, получится $\frac{6}{18}=\frac{1}{3}$ — в 12 раз больше верного ответа.

Ответ: $\frac{1}{36}$.

{"questions":[{"content":"Монету бросают 4 раза. Найдите вероятность того, что все 4 раза выпадет орел. [[input-1]]","widgets":{"input-1":{"type":"input","answer":["0,0625","0.0625","1/16"]}},"hints":["Каждый бросок — ярус с двумя ветвями: всего исходов $n = 2 \\cdot 2 \\cdot 2 \\cdot 2 = 16$.","Благоприятный исход один: ОООО, $m = 1$.","$P = \\dfrac{1}{16} = 0{,}0625$."],"step":1},{"content":"Монету бросают 3 раза. Найдите вероятность того, что первый и последний броски дадут одинаковый результат. [[input-2]]","widgets":{"input-2":{"type":"input","answer":["0,5","0.5","1/2"]}},"hints":["Всех исходов $n = 2 \\cdot 2 \\cdot 2 = 8$.","Благоприятные исходы тоже по правилу: первый бросок — любой (2 способа), средний — любой (2), последний совпадает с первым (1): $m = 2 \\cdot 2 \\cdot 1 = 4$.","$P = \\dfrac{4}{8} = \\dfrac12 = 0{,}5$."],"level":"повышенный","step":1}],"mix":1}

Вывод

Правило умножения позволяет считать варианты, которые невозможно перебрать: коды, пароли, номера, исходы многих бросков. Именно так находят $n$ в формуле вероятности. Чтобы вспомнить главное, представьте дерево выборов: ярус — шаг, путь — способ, число способов — число листьев.

В следующем уроке «Перестановки, факториал, сочетания» ветвей на ярусах будет становиться все меньше, вплоть до одной, — так появятся факториал и перестановки.

Часто задаваемые вопросы

Как понять, складывать числа вариантов или умножать?

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

Обязательно ли рисовать дерево?

Нет. Дерево нужно, чтобы понять устройство выбора: какие шаги, есть ли запреты, одинаково ли число ветвей. Для подсчета хватит свернутого дерева — колонок «позиция — число вариантов».

Почему у кода первая цифра выбирается из 10 цифр, а у числа — из 9?

Код — это последовательность цифр, и $0123$ — обычный код. А число не записывают с нуля впереди: $0123$ — это $123$, трехзначное число. Поэтому у числа на первом месте нет ветви «0».

Что делать, если число вариантов на шаге зависит от предыдущего выбора?

Сначала попробуйте поменять порядок шагов и начать с самого строгого. Если и так число вариантов меняется, разбейте задачу на случаи, как в примере с четными числами: в каждом случае перемножьте, а результаты сложите.

Где пригодится правило умножения дальше?

В подсчете вероятностей: число всех исходов $n$ почти всегда находят этим правилом. На нем же строятся перестановки и сочетания — следующие темы модуля.

Награды за урок

Проверим знания по теме?

Комбинаторное правило умножения

Пройти тест