Математика · Комбинаторика, вероятность и статистика · 7 класс

Комбинаторика: правила подсчёта

3 рубашки и 2 пары брюк — сколькими способами можно одеться? В каком порядке могут встать в ряд 6 человек?

Ситуация

Утром в шкафу 3 рубашки и 2 пары брюк — сколькими способами можно одеться? Если пароль на телефоне состоит из 4 цифр, сколько вариантов придётся перебрать? Сколькими способами можно выстроить в ряд 6 дежурных класса? Всё это — задачи на подсчёт. Вместо того чтобы выписывать варианты по одному, мы нарисуем дерево, составим таблицу и откроем два простых правила.

Тема

Комбинаторика: правила сложения и умножения, перестановки, способы выбора. Выбор одежды, пароль телефона и дежурные по классу: дерево вариантов, правило умножения, перестановки n!

Ключевые понятия

Дерево вариантов
Правило умножения
Перестановки

Формулы

N = n_{1} \cdot n_{2} \cdot \dots \cdot n_{k}

Правило умножения: если выбор состоит из $k$ последовательных этапов, связанных союзом и, то числа вариантов перемножаются.

N = n_{1} + n_{2}

Правило сложения: первый или второй путь — числа вариантов несовместных групп складываются.

P_{n} = n! = 1 \cdot 2 \cdot 3 \cdot \dots \cdot n

Число способов расставить $n$ различных предметов в ряд — перестановки; $n!$ — « $n$ факториал».

n^{k} и n \cdot (n - 1) \cdot \dots \cdot (n - k + 1)

Последовательности длины $k$ из $n$ знаков: с повторениями $n^{k}$ , без повторений — на каждое следующее место на один вариант меньше.

Теория

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

Если выбор делается по этапам, нарисуем его в виде дерева: от каждой рубашки отходит столько ветвей, сколько есть брюк. Число листьев — произведение чисел ветвей: 3 рубашки и 2 пары брюк — $3 \cdot 2 = 6$ нарядов. Добавим обувь — ещё один ярус ветвей: $3 \cdot 2 \cdot 2 = 12$ . Это правило умножения: если «первый выбор и второй выбор», числа вариантов перемножаются. На первом шаге вырастите дерево сами.

Правило сложения: «или»

Из Ташкента в Самарканд можно добраться на 3 поездах или на 2 автобусах — всего $3 + 2 = 5$ путей. Если группы несовместны (нельзя ехать одновременно и на поезде, и на автобусе), числа вариантов складываются. Если затем из Самарканда в Бухару ведут 2 пути, то маршрутов Ташкент → Бухара $(3 + 2) \cdot 2 = 10$ — сначала «или», затем «и». Второй способ — таблица: строки — первый выбор, столбцы — второй, число клеток — ответ.

Перестановки: n!

Ставим на полку 3 книги. На 1-е место — любая из 3 книг (3 варианта), на 2-е — одна из оставшихся двух (2 варианта), на последнее остаётся одна: $3 \cdot 2 \cdot 1 = 6$ . Вообще для $n$ предметов $n \cdot (n - 1) \cdot \dots \cdot 1 = n!$ (« $n$ факториал»). Например, $4! = 24$ , $5! = 120$ — факториал растёт очень быстро. На третьем шаге все расстановки сгруппированы по первой книге: в каждой группе по $(n - 1)!$ расстановок, а групп $n$ .

Способ перебора (упорядоченный список)

Небольшую задачу можно решить систематическим списком: двузначные числа из цифр 1, 2, 3 — сначала начинающиеся с 1 (11, 12, 13), затем с 2, затем с 3: $3 \cdot 3 = 9$ чисел. Если цифры не должны повторяться, 11, 22, 33 выпадают: $3 \cdot 2 = 6$ — на второе место остаётся на одну цифру меньше. Если список упорядочен, ничто не пропускается и не считается дважды — проверьте на четвёртом шаге.

Типы задач

В любой задаче на подсчёт задают два вопроса: важен ли порядок (12 и 21 — разные?) и можно ли повторять (берётся ли один предмет дважды?). Порядок важен, повторения можно — PIN-код: $10^{4}$ . Порядок важен, без повторений — места призёров: $8 \cdot 7 \cdot 6$ . Порядок не важен, без повторений — выбор двух представителей: $\frac{8 \cdot 7}{2} = 28$ (каждая пара посчитана дважды). Порядок не важен, повторения есть — шарики мороженого: считается списком. На пятом шаге определите тип задачи.

О модели

На чертежах используются небольшие числа: на дереве до 36 листьев, на полке до 5 книг (из 120 расстановок рисуется лишь часть), в списке до 64 чисел — а правило работает для любых чисел. Число сочетаний $C_{n}^{k}$ и бином Ньютона изучают в 11 классе; здесь задачи, где порядок не важен, решаются только списком и рассуждением «пара посчитана дважды».

Знаете ли вы?

Число способов перемешать колоду из 52 карт равно $52! \approx 8 \cdot 10^{67}$ — больше, чем звёзд во Вселенной; вероятно, при каждом перемешивании получается новый порядок.
Знак « $n!$ » ввёл в 1808 году французский математик Кристиан Крамп; до него факториал записывали в виде длинного произведения.

Что внутри эксперимента

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

Другие эксперименты раздела

Статистика: среднее, медиана, σ — 8 класс
Вероятность: монета, кубик, Венн — 9 класс