TODO: Дать краткую базу по факториалам, 0! = 1, сокращение факториалов в дробях, свойства.
В группе А-05-18 n студентов, а в А-13-18 — m. Выбрать одного студента из А-05-18 можно n способами, аналогично из тринадцатой группы одного студента можно выбрать m способами. А выбрать одного студента из обеих групп можно m+n способами.
<aside> 💡 Если некоторый объект А можно выбрать m способами, а другой объект B можно выбрать n способами, то выбор «либо A, либо B» можно осуществить m+n способами.
</aside>
Правило суммы применяется, когда удается разбить все изучаемые комбинации на несколько классов, причем каждая комбинация входит в один и только один класс. Иными словами, необходимо убедиться, что ни один из способов выбора объекта А не совпадает с каким-либо способом выбора объекта B. На предыдущем примере представим, что один из студентов недавно перевелся из одной группы в другую. Из списка пятой группы его еще не удалили, а в список студентов тринадцатой уже добавили. У нас появилось совпадение способов выбора объекта (студента), из-за чего правило суммы утрачивает силу. Способов выбора становится m+n-k, где k — число совпадений.
Возьмем те же условия про две группы, но в этот раз нам нужно выбрать пару из двух студентов, причем такую, где в каждой паре есть по студенту от каждой группы. Здесь стоит представить ментальный процесс выбора такой пары. Выбираем студента из пятой группы, то есть из n, полдела сделано. Теперь необходимо подобрать ему пару из студентов тринадцатой группы. Влияет ли наш выбор первого члена пары на выбор второго? Совершенно не влияет. Таким образом, пару мы выбираем из m студентов. Таким образом, мы, составляя комбинацию из двух элементов (студентов) точно знаем, сколькими способами можно выбрать первый элемент и сколькими способами можно выбрать второй элемент, причем число способов выбора второго элемента не зависит от того, как именно выбран первый. В таком случае, выбрать пару студентов можно m*n способами.
<aside> 💡 Если объект A можно выбрать m способами и если после каждого такого выбора объект B можно выбрать n способами, то выбор пары (A; B) в указанном порядке можно осуществить m*n способами.
</aside>
Как и в прошлый раз, попробуем сломать правило произведения в нашей задаче. Предположим, что мы хотим не просто взять пару студентов из разных групп, но и сделать это таким образом, чтобы в паре один из студентов оказался студентом, а второй — студенткой. Снова представим, как мы будем выбирать такую пару. Выбрали элемент из пятой группы. Он оказался парнем. Сколько у нас способов подобрать ему пару из тринадцатой? Столько, сколько в 13 группе девушек. Однако если бы мы выбрали в качестве первого элемента девушку, то способов выбрать ей пару из 13 группы было бы столько, сколько в ней студентов мужского пола. Таким образом, правило произведения более не применяется. Эту измененную задачу можно очень легко решить, используя только комбинации правила суммы и правила произведения. Пока попробуем решить простейшую задачу на правило произведения:
Сколько пятизначных шестнадцатиричных идентификаторов можно составить таким образом, чтобы любые две стоящих рядом цифры (знака) были различны?
Задача тривиальная. Выбрать первую цифру мы можем 16 способами. Во втором разряде мы не можем, по условию задачи, повторять предыдущий выбор, так что для него перед нами стоит выбор из 15 цифр. На третьей позиции мы не можем повторять вторую, но уже можем повторить первую, то есть, способов выбрать снова 15. Аналогично выбираем до пятого знака. Таким образом, получаем ответ:
$$ 16\cdot15\cdot15\cdot15\cdot15=16\cdot15^4=810000 $$
Вернемся к нашим демографическим вопросам. Сформулируем задачу:
[Вторая пара] В группе А-05-18 14 человек, половина из которых девушки, а в А-16-18 студентов 10, из них 3 девушки. Необходимо выбрать пару, состоящую из разнополых студентов различных групп. Сколькими способами можно это сделать?
[Третья пара] В группах А-13-18 и А-14-18 по 12 человек, в первой из них 5 девушек, а во второй 7. Необходимо выбрать пару, состоящую из разнополых студентов различных групп. Сколькими способами можно это сделать?
[Подменить значения на третьей паре] Для решения этой задачи вновь представим последовательность действий при выборе такой пары. Выбирать будем из групп по порядку. Способов выбрать первого студента (студентку) у нас 14, причем на девушек и парней приходится равное количество случаев (7). Если первым элементом оказалась девушка, то выбирать ей пару придется из 7 парней, а если из пятой группы мы выбрали парня, то способов выбрать ему девушку из шестнадцатой будет 3. По правилу произведения в первом случае получаем 77, а во втором 73 способов собрать пару. Так как подсчитанные нами количества способов являются исчерпывающими и не имеют никаких пересечений, то мы можем применять правило суммы:
$$ 7\cdot7+7\cdot3=70 $$
Представим кодировку длиной в два байта. Отбросив очевидность ответа, зададим следующий вопрос: сколько символов может содержать такая кодировка?