[МУЗЫКА] В этом видео мы обсудим следующее правило подсчетов — правило произведения. Оно также довольно простое. Пусть у нас есть k объектов первого типа и n объектов второго типа. Тогда у нас есть k * n пар объектов, в которых первый объект первого типа, а второй объект второго типа. Давайте рассмотрим пример. Пусть у нас есть видео, четыре штуки. И пусть у нас есть пользователи, три штуки. И у нас есть следующие данные: каждый пользователь оценил каждое видео. Сколько всего будет оценок? Каждая оценка — это на самом деле пара, это пользователь оценил видео, это пара из пользователя и видео. Таким образом, у нас объектов первого типа три, это пользователи, объектов второго типа — их четыре, это видео. И нам нужно посчитать количество пар, в которых первый объект первого типа, а второй объект — второго типа. По правилу произведения 4 * 3 = 12 оценок видео. Можно посмотреть на это на картинке. Удобно изображать пары в виде таблицы. Здесь строки соответствуют пользователям, а столбцы соответствуют видео. И в каждой клеточке мы пишем оценку пользователя, которую пользователь дал этому видео. Хорошо, давайте сформулируем правило произведений на языке множеств. Если у нас есть два множества A и B и они конечные, тогда у нас есть размер A умножить на размер B пар объектов, в которых первый объект из первого множества, из множества A, и второй объект из второго множества, из множества B. Почему вообще правило произведения верно? Давайте снова вернемся к табличке. Пусть у нас множество A, оно конечно, и оно состоит из элементов a1, ..., ak, а B состоит из элементов b1, ..., bn. Просто обозначим так элементы. И давайте рассмотрим таблицу, в которой строки будут соответствовать элементам множества A. У нас будет k строк, соответствующих элементам a1, a2, ..., ak. А также у нас будет n столбцов, они будут соответствовать элементам множества B. Каждый столбец соответствует b1, b2, ..., bn. Хорошо, если мы рассмотрим пару, состоящую из элемента ai и элемента bj, то элементу ai соответствует своя строка, элементу bj соответствует свой столбец. И получается, что паре соответствует клеточка. В эту клеточку давайте и напишем соответствующую пару, ai bj. Таким образом, пар элементов из множества A и из множества B ровно столько же, сколько клеток в этой таблице. А количество клеток мы знаем, как посчитать: это количество горизонталей умножить на количество вертикалей. Итак, у нас есть правило произведения. Но не можем ли мы как-то представить его в виде картинки с вершинами и стрелками, не подпадает ли оно под конструкцию из прошлого видео? Оказывается, можем. Давайте для простоты и наглядности будем считать, что в множестве A у нас пять элементов, а в множестве B у нас три элемента. Тогда мы можем рассмотреть следующую картинку. В ней всего три вершины: вершина s, вершина t и одна вершина посередине. Из вершины s в среднюю вершину ведет пять ребер, по числу элементов в множестве A. И средней вершины в вершину t ведет три ребра, по числу элементов множества B. Тогда в вершину s мы можем попасть одним способом из вершины s. В среднюю вершину можем попасть пятью способами, есть пять типов путей: через верхнее ребро, через следующее, через третье и так далее. Суммарно пять путей. И заметим, что выбор пути сюда соответствует выбору элемента множества A, ребер столько же, сколько элементов множества A, каждое ребро соответствует своему элементу. А в вершину t мы уже можем попасть 15 способами, потому что у нас есть три типа путей, которые ведут в вершину t: через верхнее ребро, через среднее и через нижнее. Каждых путей каждого типа пять штук, получается, 5 + 5 + 5 — 15 путей. Заметим, что выбор второго ребра соответствует выбору элемента множества B, вторых ребер столько же, сколько элементов множества B, каждое из них соответствует какому-то своему элементу множества B. Таким образом, путей у нас получилось 15, и на самом деле выбор каждого пути — это сначала выбор элемента из множества A, а потом выбор элемента из множества B. На самом деле путь соответствует просто паре элементов, где первое из множества A, а второе — из множества B. Итак, в этом уроке мы начали обсуждать подсчеты. И подсчеты начинаются с очень простых наблюдений, таких как правило суммы. Но оказывается, что даже в них уже есть свои тонкости, и нужно о некоторых вещах помнить. Оказывается, что даже эти простые идеи могут уже быть полезны, с помощью них можно делать вполне нетривиальные вещи. Дальше мы увидим, как на основе этих простых базовых идей строятся более сложные конструкции в вопросах о подсчетах. И мы обсудим это в следующих уроках. [МУЗЫКА]
