Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Правило суммы и правило произведения в комбинаторике

На главную Математический раздел Криптография и т.д. Новости

Правило суммы заключается в следующем. Если объект A можно выбрать m способами, а другой объект B можно выбрать n способами, тогда выбор "Объект А или объект В" можно выполнить m+n способами. Аналогично в теории множеств количество элементов объединения непересекающихся множеств равно сумме количеств элементов в каждом из множеств. Правило суммы очевидным способом обобщается на несколько типов объектов.

Пример. Мы можем добраться до центра города одной из 5 маршруток, одним из 3 автобусов, или одним троллейбусом. Сколько есть способов добраться? Ответ: 5 + 3 + 1 = 9.

Замечание. Требуется следить за тем, чтобы выбор A и выбор B был взаимоисключающим. Допустим, пусть в студенческой группе 5 человек шарят в английском, 4 в немецком, шарящих в других иностранных языках нет. Сколько человек в группе шарят в английском или немецком? Ответ: не более 9: некоторые могут шарить в обоих языках. Здесь нельзя применить правило суммы.

Правило произведения: если объект A можно выбрать способами, а другой объект B можно выбрать n способами, тогда пару (объект А, объект В) можно выбрать mn способами. Аналог в теории множеств: количество элементов декартова произведения множеств равно произведению количеств элементов "умножаемых" множеств. Правило легко обобщается на несколько типов объектов.

Пример. Секретный код имеет следующий вид: сначала любая строчная буква английского алфавита, далее две цифры. Сколько существует кодовых комбинаций? Ответ: 26 * 10 * 10 = 2600.

Комбинирование правила суммы и произведения. Очень часто в практических задачах удается вычислить количество вариантов некоторого выбора за счет умелого комбинирования двух правил.

Пример 1. Сколько существует трехзначных чисел, у которых есть хотя бы один нуль? I. Определим, сколько всего есть трехзначных чисел. Первая цифра может быть от 1 до 9, остальные - от 0 до 9, то есть всего 9 * 10 * 10 = 900 трехзначных чисел по правилу произведения. II. По правилу произведения всего 9 * 9 * 9 = 729 трехзначных чисел без нуля вообще (по 9 вариантов каждой цифры). III. По правилу суммы количество трехзначных чисел равно сумме количества трехзначных чисел без нулей и сумме количества трехзначных чисел с одним и более нулем. Следовательно, ответ: 900 - 729 = 171.

Пример 2. Сколько есть возможных позиций на шахматной доске, когда обе стороны сделали первый ход? Каждая стороны может сделать ход либо пешкой, либо конем. Каждой пешкой можно сделать первый ход 2 способами, всего 8 пешек. По правилу произведения у одной стороны есть 2 * 8 = 16 способов хода пешкой. Каждым конем можно сделать ход 2 способами, всего 2 коня. По правилу произведения у одной стороный есть 2 * 2 = 4 способа хода конем. По правилу суммы получаем, что у каждой стороны есть 16 + 4 = 20 способов хода. Заметим, что первый ход белых не исключает никакого хода черных: никакое поле, куда могут пойти черные, не будет занято. Следовательно, по правилу произведения есть 20 * 20 = 400 возможных позиций. Это можно было определить и перебором, но что быстрее?

copyright © Исканцев Н.В., 2014

К математическому разделу
На главную
X