Так, друзья, ну давайте разберем для начала какую-нибудь совсем простенькую задачу на правило сложения и правило умножения в комбинаторике. Вот у меня условие. Не помню цифр, сейчас мы его произведем. Можно из Москвы... давайте напишем: из Москвы можно разными способами долететь до Сиднея. Значит, вот Москва, вот, условно, Сидней. Я думаю, что если я вот так вот размахнусь, то мне все равно места хватит, потому что задача простенькая. Значит, из Москвы до Сиднея можно долететь, с точки зрения той задачи, которую мы сейчас будем решать, на самом деле двумя способами: можно лететь через Абу-Даби, [ПИШЕТ НА ДОСКЕ] то есть вот так, из Москвы сначала в Абу-Даби, а потом из Абу-Даби в Сидней, вот, а можно полететь в Куала-Лумпур и затем, сделав там пересадку, отправиться уже в Сидней. То есть, есть 2 маршрута, 2 способа самодоставки из Москвы в Сидней, при этом на каждом из вот этих вот отрезочков существует несколько рейсов. Значит, вот это я не могу запомнить. Давайте напишем: здесь у нас 5 рейсов из Москвы в Абу-Даби и 6 рейсов из Абу-Даби в Сидней. Соответственно, 4 рейса из Москвы в Куала-Лумпур и 3 рейса в Сидней. Нет, ну, товарищи, вы не думайте, конечно, что это какая-то реальность, то есть я во всяком случае не смотрел на расписание реальных самолетов, чтобы составить эту задачу, речь идет о какой-то модельной ситуации. Тем не менее, поскольку уж она записана с такими цифрами, то я вынужден пользоваться шпаргалкой. Ну вопрос, естественно, состоит в том, а сколько существует различных способов самодоставиться из Москвы в Сидней, пользуясь вот этими вот переходами: то ли из Москвы в Абу-Даби, а потом из Абу-Даби в Сидней, то ли из Москвы в Куала-Лумпур, а потом из Куала-Лумпура в Сидней? Вот такой вот простой вопрос в этой задаче. Ну и как ответить на этот вопрос? Ну давайте подумаем, где здесь правило сложения, где здесь правило умножения. Можно посмотреть, наверное, для начала вот на эту цепочку перемещений, то есть двигаться из Москвы в Сидней через Абу-Даби. Итак, у нас есть 5 вариантов того, как можно доставиться из Москвы в Абу-Даби, 5 вариантов рейсов, и вслед за ними, — вот, внимание, давайте я прямо сообразую это с теми словами, которые я произносил во время лекции, — вслед за ними, вслед за вот этими вот пятью вариантами есть 6 способов, 6 рейсов проследовать из Абу-Даби в Сидней. То есть для каждого способа перемещения из Москвы в Абу-Даби, для каждого из этих пяти способов, есть 6 вариантов того, как впоследствии продвинуться уже от Абу-Даби до Сиднея. Таким образом, здесь проглядывает, естественно, правило умножения: нам нужно 5 вариантов рейса здесь продолжить любым из 6-ти вариантов рейса тут, итого получится 5 х 6 вариантов. Но это только в случае, если мы будем двигаться из Москвы в Сидней через Абу-Даби. Но есть другой вариант, можно двигаться из Москвы в Сидней через Куала-Лумпур, и здесь вслед за четырьмя рейсами, которые идут из Москвы в Куала-Лумпур, есть 3 рейса, которые идут из Куала-Лумпура в Сидней. Соответственно, тут по такому же правилу умножения получается 4 х 3, то есть 12 вариантов перемещения. Ну, а поскольку дальше мы говорим, что либо мы двигаемся по вот этой цепочке, либо мы двигаемся по вот этой цепочке, именно либо — либо, то в этом месте уже возникает, естественно, правило сложения, и мы складываем вот эти 2 числа. Количество способов пройти по этой цепочке — 5 х 6 плюс количество способов пройти по этой цепочке, это 4 х 3. Ну и, вроде, очевидно, что больше никаких способов в рамках этой задачи доплыть, вернее, долететь, извините, из Москвы в Сидней не существует. Итого получаем 30 + 12, да? Ну это 42, если я нигде не обсчитался. Ну я надеюсь, вы понимаете, что число здесь не так важно, важно только осознать принцип, что в каком-то месте надо умножить, в каком-то месте надо сложить. Если вы его осознаете, то до числа уж какой-нибудь компьютер вам обязательно досчитает. Ну вот, в сущности, и вся недолга, вся задача.
