RUВход: одна задача, четыре разных ответа
Из цифр $1, 2, 3, 4, 5, 6$ составляют наборы длины четыре. Сколько существует наборов, если:
- цифры могут повторяться и порядок важен — то есть считаем четырёхзначные числа из этих цифр;
- цифры различны, порядок важен;
- цифры различны, порядок не важен — важно только, какие четыре цифры взяли;
- цифры могут повторяться, порядок не важен — важно только, сколько раз взяли каждую.
Четыре вопроса отличаются двумя словами, ответы отличаются в разы: $1296$, $360$, $15$, $126$. Первые три берутся из блока «Мост» без изменений: $6^4$, затем $6 \cdot 5 \cdot 4 \cdot 3$, затем $\binom{6}{4}$. Четвёртый из «Моста» не достаётся и устроен так же, как одна из финальных задач дня. Урок — про то, как за полминуты понять, в какой из четырёх клеток ты находишься и что делать, когда задача не помещается ни в одну. Приёмов пять, идут они в том же порядке, что задачи на странице.
Опора: правило умножения
Единственное, что сегодня формулируется с нуля, — не формула, а условие её применимости. Обе оговорки в правиле рабочие, поэтому произносить его надо целиком.
Правило умноженияЕсли исход однозначно задаётся последовательностью решений, на первом шаге вариантов $m$, а на втором — $n$ при каждом исходе первого шага, то всего исходов $m \cdot n$.
«Однозначно задаётся» — разные последовательности решений дают разные исходы, и любой исход получается хотя бы одной последовательностью; иначе произведение считает каждый исход с кратностью и придётся делить. «При каждом» — число вариантов на втором шаге не зависит от того, что выбрали на первом (меняться от шага к шагу оно может). Выбирая двух дежурных по порядку из десяти, имеем 10 вариантов, затем 9: девятка одна и та же при любом первом выборе. А в условии «второй дежурный не однокурсник первого» перемножать нельзя — число вариантов на втором шаге зависит от первого, и надо разбирать случаи по числу однокурсников.
Четыре стандартных счёта — это правило умножения в четырёх режимах. Три клетки таблицы лежат в «Мосте» готовыми, четвёртая разбирается в приёме 4; работа сегодня не в клетках, а в том, как задача к ним сводится.
| Что берём | Порядок важен | Порядок не важен |
|---|
| $k$ из $n$, повторы разрешены | $n^k$ | $\binom{n+k-1}{k}$ |
| $k$ из $n$, повторы запрещены | $n(n-1)\cdots(n-k+1)$ | $\binom{n}{k}$ |
| все $n$ объектов | $n!$ | 1 |
Проверка порядка за пять секундПридумай два конкретных исхода, отличающихся только порядком, и спроси: это один результат или два разных? «Петя — золото, Ваня — серебро» и «Ваня — золото, Петя — серебро» — два разных. «Комиссия из Пети и Вани» и «комиссия из Вани и Пети» — один и тот же.
Приём 1: разрезать выбор на блоки
Условие вида «ровно столько-то из такой-то группы» почти никогда не считается одним сочетанием.
Задача. В группе 12 студентов, из них 5 девушек. Сколько существует команд из 4 человек, в которых ровно 2 девушки?
Порядок внутри команды не важен, значит сочетания. Но $\binom{12}{4}$ взять нельзя: условие делит людей на две группы, из которых берётся разное количество, и выбор распадается на два шага со своим сочетанием на каждом.
$$\binom{5}{2}\binom{7}{2} = 10 \cdot 21 = 210$$Перемножаем, а не складываем, потому что команда состоит из девушек и юношей одновременно. Складывают взаимоисключающие случаи: «ровно 2 девушки или ровно 3 девушки» — вот там сумма. Разрезав задачу на блоки, сразу спроси, получается ли каждый исход ровно одним способом: если какому-то исходу отвечают две раскладки по блокам, ответ завышен, а выглядит верным.
Приём 2: закодировать расстановку строкой
Разрез на блоки работает, пока исход — это подмножество, «кого взяли». Но исход часто устроен иначе: маршрут, расписание, последовательность однотипных шагов. Тогда его сначала записывают строкой, и только после этого видно, что именно выбирается.
Задача. Из левого нижнего угла прямоугольника шириной 3 клетки и высотой 2 клетки идут по линиям сетки в правый верхний, за шаг сдвигаясь на клетку вправо или вверх. Сколько путей?
Любой такой путь состоит ровно из трёх шагов вправо и двух вверх: иначе в правый верхний угол не попасть. Запишем путь словом, где В — шаг вправо, П — шаг вверх. Слову ВВПВП отвечает ровно один путь, и любому пути — ровно одно слово: кодировка ничего не теряет и не склеивает, а это и есть условие, при котором вместо путей разрешено считать слова. Слово из пяти букв полностью задано тем, на каких местах стоят буквы П:
$$\binom{5}{2} = 10$$Кодирование строкойЕсли исход — последовательность шагов нескольких типов, запиши его строкой символов. Дальше вопрос всегда один: на каких местах стоят символы одного вида. Перед подстановкой формулы проверь обратимость: по строке восстанавливается исход, а по исходу — строка. Эта форма нужна и дальше: в приёме 3 в строке появятся символы трёх видов, в приёме 4 — шары и перегородки.
Приём 3: делить на кратность
Правило умножения требует, чтобы разные последовательности решений давали разные исходы. Третий приём — нарушить это требование сознательно: посчитать с повторами, а потом поделить.
Деление на кратностьЕсли каждый нужный объект посчитан ровно $r$ раз и $r$ одинаково для всех объектов — раздели на $r$. Если $r$ у разных объектов разное, делить нельзя: надо разбивать на случаи.
Одно применение уже лежит в «Мосте»: $\binom{n}{k}$ — упорядоченный выбор, делённый на $k!$, потому что каждый набор посчитан столько раз, сколькими способами его выстраивают в ряд.
Расстановка по кругу
Задача. Сколькими способами рассадить 5 человек за круглым столом, если рассадки, отличающиеся поворотом стола, считаются одинаковыми?
Занумеруем стулья и рассадим людей как в ряду: $5! = 120$ нумерованных рассадок. Поворот на один стул переводит рассадку в другую нумерованную, но условие их не различает; поворотов 5, считая нулевой, и все дают разные рассадки — при нетривиальном повороте никто не остаётся на своём стуле. Значит кратность равна 5 и одинакова для всех:
$$\frac{5!}{5} = 4! = 24$$Круговые перестановки$n$ объектов по кругу, когда повороты не различаются, — это $(n-1)!$, а не $n!$. Практический ход короче деления: посади одного на фиксированное место и считай остальных как обычный ряд — тогда повороты не возникают вовсе.
Строка с повторяющимися символами
Задача. Сколько различных слов получается перестановкой букв слова КОЛОКОЛ?
Букв семь, но не все различны: К — две, О — три, Л — две. Будь все семь различны, слов было бы $7! = 5040$, и каждое реальное слово посчитано там несколько раз: две К переставляются между собой $2!$ способами, три О — $3!$, две Л — $2!$, причём независимо. Кратность равна $2! \cdot 3! \cdot 2! = 24$ и одна и та же для всех слов — зависит от состава, не от порядка:
$$\frac{7!}{2!\,3!\,2!} = \frac{5040}{24} = 210$$Тот же счёт отвечает на другой с виду вопрос: сколькими способами раздать 7 различных предметов трём людям порциями 2, 3 и 2? Слово из К, О и Л — это указание, кому достался каждый предмет.
Мультиномиальный коэффициент$$\frac{n!}{n_1!\,n_2!\cdots n_k!}, \qquad n_1 + n_2 + \cdots + n_k = n$$Число отвечает на три вопроса сразу: перестановки строки с повторами; раскладка $n$ различных объектов по $k$ пронумерованным ящикам заданных размеров; выбор составов групп по очереди $\binom{n}{n_1}\binom{n-n_1}{n_2}\cdots$ А если группы равного размера неразличимы («разбить на пары»), ответ делят ещё на число их перестановок: слово «пронумерованные» в условии читай первым.
Приём 4: считать количества вместо порядка
Вернёмся к четвёртому вопросу входной задачи: цифры из $\{1, \ldots, 6\}$, длина четыре, повторы разрешены, порядок не важен — это та клетка таблицы, которой в «Мосте» нет. Первое: «порядок не важен» здесь равносильно «запишем цифры по возрастанию» — у каждого набора с повторами ровно одна неубывающая запись, и наоборот. Второе: набор полностью описывается тем, сколько раз взята каждая из шести цифр, то есть нужно число решений уравнения
$$x_1 + x_2 + \cdots + x_6 = 4$$в целых неотрицательных числах, где $x_i$ — сколько раз взята цифра $i$. Третье — снова кодирование строкой, только символы другие. Выложим четыре одинаковых шара в ряд и вставим пять перегородок, делящих ряд на шесть участков: сколько шаров в $i$-м участке, столько раз взята $i$-я цифра. Перегородки можно ставить рядом и по краям — это и есть цифра, не взятая ни разу. Всего в ряду $4 + 5 = 9$ позиций, и строка задана тем, где стоят пять перегородок:
$$\binom{9}{5} = \binom{9}{4} = 126$$Выбор с повторениямиВзять $k$ объектов из $n$ типов, повторы разрешены, порядок не важен: $\binom{n + k - 1}{k}$. Запоминать надо не формулу, а картинку: $k$ шаров и $n - 1$ перегородка в одном ряду. Путаешься, $n + k - 1$ или $n + k$, — проверь на $n = 2$, $k = 2$: пар 11, 12, 22 ровно три.
Приём 5: считать запрещённое
Задача. Сколько слов длины 5 из букв $\{a, b, c, d\}$ содержат хотя бы одну букву $a$?
В лоб — пять слагаемых: ровно одна $a$, ровно две, и так до пяти, и в каждом слагаемом ещё сочетание на выбор позиций. В обход — слов без единой $a$ ровно $3^5$, и это одна строчка:
$$4^5 - 3^5 = 1024 - 243 = 781$$РефлексСлова «хотя бы один», «не менее одного», «существует», «ни одного», «не делится ни на» означают одно и то же: считай запрещённое и вычитай из всего. Прямой счёт в таких задачах почти всегда длиннее и почти всегда даёт арифметическую ошибку.
Приём ломается ровно в одном месте: когда запрещённых условий несколько и они пересекаются, простое вычитание убирает пересечения дважды. Для двух множеств поправка есть в «Мосте»: $|A \cup B| = |A| + |B| - |A \cap B|$. Для трёх картина продолжается со знакочередованием — одиночные складываем, пары вычитаем, тройку возвращаем:
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$Проверяется это подсчётом вкладов, а не доказательством. Элемент ровно из одного множества учтён один раз; элемент ровно из двух — дважды в первой сумме и один раз в сумме пар, итого $2 - 1 = 1$; элемент из всех трёх — $3 - 3 + 1 = 1$. Каждый учтён ровно один раз, что и нужно.
Осталась логическая деталь, на которой задачу теряют чаще, чем на арифметике. Если требуется, чтобы выполнялись два условия сразу, запрет — отрицание их обоих вместе, а отрицание «и» — это «или»: требование «есть и единица, и двойка» нарушено, когда нет единицы или нет двойки. Значит запрет — объединение и считается включениями-исключениями; написать вместо этого «нет ни единицы, ни двойки» значит взять кусок запрета. На этом шаге построена эталонная задача ниже.
Как это выглядит на экзамене«Не делится ни на 2, ни на 3, ни на 5» — это $1000 - |A_2 \cup A_3 \cup A_5|$, где $A_d$ — кратные $d$, а пересечения берутся через НОК: и на 2, и на 3 — значит на 6. Одна из трёх финальных задач дня устроена ровно так.
Пять проверок, которые ловят ошибку до отправки ответа
Обоснования никто не читает, второй попытки нет: каждая проверка ниже — часть решения, а не педантизм, и занимает меньше минуты.
- Каждый исход ровно один раз. Возьми конкретный исход и посчитай, сколькими путями твоя схема его выдаёт. Больше одного — ответ завышен ровно в кратность раз.
- Сложил или умножил. Умножают последовательные шаги («и»), складывают взаимоисключающие случаи («или»). Проверяется вставкой этого союза в русскую фразу.
- Крайний случай. Подставь $k = 0$ или $k = n$ — формула обязана дать 1. Подставь маленькие числа, при которых ответ пересчитывается руками.
- Порядок величины. Ответ лежит между нулём и числом исходов без ограничений; где есть доли — прикинь их произведением, как в проверке к задаче
y0101. - Целость. В задаче на счёт ответ — целое число. Дробь на выходе означает, что где-то поделили не на ту кратность.
ENOpening: one problem, four different answers
Form length-four sets from the digits $1, 2, 3, 4, 5, 6$. How many sets are there if:
- digits may repeat and order matters—in other words, we are counting four-digit numbers made from these digits;
- digits must be distinct and order matters;
- digits must be distinct and order does not matter—only which four digits were chosen matters;
- digits may repeat and order does not matter—only how many times each digit was chosen matters.
The four questions differ by two words, but their answers differ dramatically: $1296$, $360$, $15$, and $126$. The first three come directly from the Bridge: $6^4$, then $6 \cdot 5 \cdot 4 \cdot 3$, then $\binom{6}{4}$. The fourth is not in the Bridge and is built like one of today’s final problems. The lesson is about recognizing, within half a minute, which of the four cells you are in—and what to do when a problem fits none of them. There are five techniques, presented in the same order as the problems on the page.
Foundation: the multiplication rule
The only thing introduced from scratch today is not a formula but the condition under which it applies. Both qualifications in the rule matter, so state the whole rule.
Multiplication ruleIf an outcome is uniquely determined by a sequence of decisions, with $m$ choices at the first step and $n$ choices at the second for every outcome of the first step, then there are $m \cdot n$ outcomes in total.
“Uniquely determined” means that different decision sequences produce different outcomes and every outcome is produced by at least one sequence; otherwise the product counts each outcome with a multiplicity and you must divide. “For every” means that the number of choices at the second step does not depend on the first choice (it may still change from one step to another). Choosing two class monitors in order from ten people gives 10 choices and then 9: the 9 is the same for every first choice. But if the second monitor must not be a classmate of the first, multiplication cannot be applied directly—the number of second choices depends on the first, so split into cases according to the number of classmates.
The four standard counts are the multiplication rule in four different modes. Three cells of the table are supplied in the Bridge; the fourth is developed in Technique 4. The point today is not memorizing cells, but learning how to reduce a problem to one of them.
| What is selected | Order matters | Order does not matter |
|---|
| $k$ from $n$, repetitions allowed | $n^k$ | $\binom{n+k-1}{k}$ |
| $k$ from $n$, repetitions forbidden | $n(n-1)\cdots(n-k+1)$ | $\binom{n}{k}$ |
| all $n$ objects | $n!$ | 1 |
Check whether order matters in five secondsInvent two concrete outcomes that differ only in order and ask: are they one result or two? “Petya wins gold and Vanya silver” versus “Vanya wins gold and Petya silver” are two different results. “A committee consisting of Petya and Vanya” versus “a committee consisting of Vanya and Petya” is the same committee.
Technique 1: split a choice into groups
A condition of the form “exactly this many from that group” is almost never counted with one combination.
Problem. A class has 12 students, 5 of them girls. How many four-person teams contain exactly two girls?
Order inside a team does not matter, so we use combinations. But $\binom{12}{4}$ is not valid: the condition divides the people into two groups, from which different numbers must be chosen, so the selection has two steps, each with its own combination.
$$\binom{5}{2}\binom{7}{2} = 10 \cdot 21 = 210$$We multiply rather than add because the team contains girls and boys at the same time. We add mutually exclusive cases such as “exactly 2 girls or exactly 3 girls.” After splitting a problem into groups, immediately ask whether every outcome has exactly one such decomposition. If some outcome has two decompositions, the answer is overcounted even though it may look reasonable.
Technique 2: encode an arrangement as a string
Splitting into groups works while the outcome is a subset—“which objects were chosen.” But an outcome is often a route, a schedule, or a sequence of similar steps. Write it as a string first; only then does it become clear what is being selected.
Problem. From the lower-left corner of a rectangle 3 cells wide and 2 cells high, move along the grid lines to the upper-right corner, shifting one cell right or up at each step. How many paths are there?
Every such path has exactly three right moves and two up moves; otherwise it cannot reach the upper-right corner. Write a path as a word, where R means “move right” and U means “move up.” The word RRURU represents exactly one path, and every path corresponds to exactly one word: the encoding loses nothing and merges nothing, which is precisely the condition that lets us count words instead of paths. A five-letter word is fully determined by the positions occupied by U:
$$\binom{5}{2} = 10$$Encoding as a stringIf an outcome is a sequence of steps of several types, write it as a string of symbols. The question then always becomes: which positions contain symbols of one kind? Before substituting a formula, check reversibility: the outcome can be reconstructed from the string, and the string from the outcome. This form will return later: Technique 3 uses three kinds of symbols, and Technique 4 uses balls and dividers.
Technique 3: divide by overcounting
The multiplication rule requires different decision sequences to produce different outcomes. The third technique deliberately breaks that requirement: count with repetitions, then divide.
Division by overcountingIf every desired object is counted exactly $r$ times, with the same $r$ for all objects, divide by $r$. If different objects have different values of $r$, division is invalid: split into cases instead.
One example is already in the Bridge: $\binom{n}{k}$ is an ordered selection divided by $k!$, because every set is counted as many times as it can be arranged in a row.
Seating around a circle
Problem. In how many ways can 5 people sit around a circular table if seatings that differ only by rotating the table are considered identical?
Number the chairs and seat the people as in a row: $5! = 120$ numbered seatings. Rotating by one chair maps a seating to another numbered seating, but the condition does not distinguish them. There are 5 rotations, including the zero rotation, and they all give different numbered seatings: under any nontrivial rotation, nobody remains in the same chair. Thus the multiplicity is 5 for every seating:
$$\frac{5!}{5} = 4! = 24$$Circular permutationsArranging $n$ objects around a circle when rotations are indistinguishable gives $(n-1)!$, not $n!$. A shorter practical method is to place one person in a fixed seat and arrange the rest in a row; then rotations never arise.
A string with repeated symbols
Problem. How many distinct words can be formed by rearranging the letters of K-O-L-O-K-O-L?
There are seven letters, but they are not all distinct: K occurs twice, O three times, and L twice. If all seven were distinct, there would be $7! = 5040$ words. Each actual word is counted several times there: the two Ks can be swapped in $2!$ ways, the three Os in $3!$ ways, and the two Ls in $2!$ ways, independently. The multiplicity is $2! \cdot 3! \cdot 2! = 24$, the same for every word because it depends on the composition, not the order:
$$\frac{7!}{2!\,3!\,2!} = \frac{5040}{24} = 210$$The same count answers a different-looking question: in how many ways can 7 distinct objects be dealt to three people in batches of sizes 2, 3, and 2? A word of K, O, and L is a record of who received each object.
Multinomial coefficient$$\frac{n!}{n_1!\,n_2!\cdots n_k!}, \qquad n_1 + n_2 + \cdots + n_k = n$$This number answers three questions at once: permutations of a string with repeats; distributing $n$ distinct objects among $k$ numbered boxes of specified sizes; and choosing group memberships sequentially, $\binom{n}{n_1}\binom{n-n_1}{n_2}\cdots$. If equal-sized groups are not distinguishable (“partition into pairs”), divide once more by the number of ways to permute those groups. In a condition, read the word “numbered” first.
Technique 4: count quantities rather than order
Return to the fourth question in the opening example: choose a length-four multiset from $\{1, \ldots, 6\}$, with repetition allowed and order irrelevant. This is the table cell missing from the Bridge.
First, “order does not matter” is equivalent to “write the digits in nondecreasing order”: every multiset with repetitions has exactly one nondecreasing representation, and vice versa. Second, the set is completely described by how many times each of the six digits is chosen, so we need the number of nonnegative integer solutions to
$$x_1 + x_2 + \cdots + x_6 = 4$$where $x_i$ is the number of times digit $i$ is selected. Third, this is again string encoding, with different symbols. Place four identical balls in a row and insert five dividers, splitting the row into six sections. The number of balls in section $i$ is the number of times digit $i$ was selected. Dividers may be adjacent or at the ends; that represents a digit selected zero times. The row has $4 + 5 = 9$ positions, and the string is determined by the positions of the five dividers:
$$\binom{9}{5} = \binom{9}{4} = 126$$Sampling with replacementChoosing $k$ objects from $n$ types, with repetition allowed and order irrelevant, gives $\binom{n + k - 1}{k}$. Remember the picture rather than the formula: $k$ balls and $n-1$ dividers in one row. If you confuse $n+k-1$ with $n+k$, test $n=2$, $k=2$: the pairs 11, 12, and 22 give exactly three.
Technique 5: count the forbidden cases
Problem. How many length-5 words over $\{a,b,c,d\}$ contain at least one $a$?
Direct counting gives five terms: exactly one $a$, exactly two, and so on through five, with a further choice of positions in every term. The indirect route is one line: words with no $a$ at all number $3^5$.
$$4^5 - 3^5 = 1024 - 243 = 781$$The reflexThe phrases “at least one,” “one or more,” “there exists,” “none,” and “divisible by neither” all point to the same move: count the forbidden cases and subtract from the total. Direct counting in these problems is almost always longer and almost always invites an arithmetic error.
The technique fails in exactly one situation: when several forbidden conditions overlap. Simple subtraction then removes the overlaps twice. For two sets, the correction is in the Bridge: $|A \cup B| = |A| + |B| - |A \cap B|$. For three sets, the signs alternate: add singles, subtract pairs, add the triple intersection:
$$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$$You can verify this by counting contributions rather than proving a formula. An element in exactly one set is counted once; an element in exactly two is counted twice in the first sum and once in the pair sum, for $2-1=1$; an element in all three contributes $3-3+1=1$. Every element is counted exactly once.
One logical detail causes more lost points than the arithmetic. If two conditions must hold simultaneously, the forbidden event is the negation of both together, and the negation of “and” is “or”: “there is both a 1 and a 2” fails when there is no 1 or no 2. Thus the forbidden set is a union and must be counted by inclusion–exclusion. Writing “there is neither a 1 nor a 2” takes only part of the forbidden set. The model problem below is built around this step.
What it looks like on the exam“Divisible by neither 2, 3, nor 5” means $1000 - |A_2 \cup A_3 \cup A_5|$, where $A_d$ is the set of multiples of $d$ and intersections use the LCM: divisible by both 2 and 3 means divisible by 6. One of today’s three final problems has exactly this structure.
Five checks that catch an error before submission
No one reads the justification, and there is no second attempt. Each check below is part of the solution, not pedantry, and takes less than a minute.
- Every outcome exactly once. Take a concrete outcome and count how many paths through your scheme produce it. More than one means the answer is overcounted by that multiplicity.
- Add or multiply? Multiply sequential steps (“and”); add mutually exclusive cases (“or”). Test it by inserting the conjunction into the sentence describing the problem.
- Boundary case. Substitute $k=0$ or $k=n$; the formula must give 1. Also test small numbers whose answers you can calculate by hand.
- Order of magnitude. The answer lies between zero and the unrestricted number of outcomes. For fractions, estimate the probability by multiplying rough proportions, as in the check for
y0101. - Integer check. A counting answer is an integer. A fraction at the end means that the wrong multiplicity was divided out somewhere.