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

Обновлено: 05.07.2024

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Непосредственное применение комбинаторных правил произведения (умножения) и суммы.

Несовместность способов выбора означает, что ни один способ выбора объекта Х не совпадает ни с одним способом выбора объекта Y .

Пример 1. Сколькими разными способами можно заказать напиток в кафе, где есть 8 видов сока и 5 видов минеральной воды?

Решение. В этом примере правило суммы не работает , так как способы выбора объектов X и Y совместны: один из способов выбора объекта X совпадает с одним из способов выбора объекта Y (выбор червового туза – это и способ выбора объекта X , и способ выбора объекта Y ).

Задача решается перебором подходящих карт: червовых карт 9 и ещё 3 туза (один уже учтён). Значит, червовую карту или туз можно выбрать 9+3=12-ю способами.

Пример показывает, что при использовании правила суммы необходимо проверять несовместность выборов. В противном случае, можно получить неверный ответ.

Правило суммы может быть применено к любому конечному числу объектов.

Пример 3. На книжной полке стоит 3 учебника по математике, 4 детектива, 2 задачника по теории вероятностей, 3 любовных романа, 2 сборника стихов и справочник по математике. Сколькими разными способами можно выбрать почитать художественную книгу?

Пример. В гардеробе имеется 3 юбки (чёрная, коричневая, фиолетовая) и 4 блузки (белая, сиреневая, желтая и розовая). Сколько разных нарядов можно из них составить?

Решение. Эту задачу можно решать перед формулировкой правила произведения. При этом целесообразно использовать граф для перебора всех вариантов:

Комбинаторика – раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.

Правила сложения и умножения в комбинаторике

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

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k способами, то все k действий вместе могут быть выполнены:

Пример 2.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

Сочетания без повторений. Сочетания с повторениями

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.

Размещения без повторений. Размещения с повторениями

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

Перестановки без повторений. Перестановки с повторениями

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k

Пример 8.

Пусть множество A состоит из n элементов, а множество B состоит из m элементов. При этом множества не пересекаются, A ∩ B = ∅.
Тогда общий набор, множество A ∪ B состоит из n + m элементов.
Выбрать один элемент a ∈ A ИЛИ b ∈ B можно n + m способами.

Например:
На подносе лежит 5 слив и 4 абрикоса.
Сколькими способами можно выбрать фрукт с подноса?
Всего фруктов: 5 + 4 = 9. Значит – 9 способов.

п.2. Правило произведения

Пусть множество A состоит из n элементов, а множество B состоит из m элементов. При этом множества не пересекаются, A ∩ B = ∅.
Тогда множество всех возможных упорядоченных пар (a, b) = A · B состоит из n · m элементов.
Выбрать упорядоченную пару a ∈ A И b ∈ B можно n · m способами.

Например:
Сколько всего двузначных четных чисел?
В двузначном числе на первом месте могут быть цифры , n = 9
В двузначном четном числе на втором месте могут быть цифры , m = 5
Всего nm = 9 · 5 = 45 чисел.

При составлении пар порядок бывает неважен: (a, b) или (b, a), – главное, составить пару. В таком случае, например, пары (1; 2) и (2; 1) – одно и то же.
Поэтому правило произведения для неупорядоченных пар:

Пусть множество A состоит из n элементов, а множество B состоит из m элементов. При этом множества не пересекаются, A ∩ B = ∅.
Тогда множество всех возможных неупорядоченных пар (a, b) ≡ (b, a) состоит из \(\mathrm>\) элементов.
Выбрать неупорядоченную пару a ∈ A И b ∈ B можно (n · m)/2 способами.

Например:
В саду поспевает 7 видов фруктов. Было решено сварить компот из любых двух фруктов. Сколько всего различных компотов можно сварить?
Первый фрукт можно выбрать n = 7 способами.
Второй фрукт можно выбрать m = 6 способами.
В данном случае 2 фрукта образуют неупорядоченную пару – неважно, в каком порядке их бросать в кастрюлю. Поэтому \(\mathrm=21>\).
Ответ: 21 различных компотов.

п.4. Примеры

Пример 1. О 4-значном пин-коде карты известно, что первая и последняя цифры у него одинаковые, вторая и третья – разные, и не равны первой цифре.
Сколько всего вариантов такого пин-кода?

В начале и в конце одновременно используются цифры , n = 10
На второй позиции могут использоваться все цифры, кроме уже использованной на первом месте, m = 9
На третьей позиции могут использоваться все цифры, кроме уже использованных на первом и втором месте, k = 8
По правилу произведения общее количество наборов: N = nmk = 10·9·8 = 720.
Ответ: 720 вариантов.

Пример 2. Сколько всего 3-значных чисел, у которых ровно две цифры.
а) семёрки; б) нули?

а) Варианты расстановки семёрок:
77x, x ≠ 7 – таких чисел 9
7x7, x ≠ 7 – таких чисел также 9
x77, x ≠ 7 – таких чисел 8 (слева не может стоять 0)
По правилу суммы: 9 + 9 + 8 = 26

б) Вариант расстановки нулей только x00, x ≠ 0 – таких чисел 9
Других вариантов нет.
Ответ: а) 26 чисел; б) 9 чисел.

Пример 3. На экзамене будет 5 задач по 5 разным темам. Каждая задача берется из списка, в котором 8 задач по теме. Вася умеет решать по 3 задачи из каждой темы.
Сколько всего вариантов билетов может быть на экзамене?
Сколько существует вариантов билетов, за которые Вася получит 5 баллов?
Сколько существует вариантов билетов, в которых Вася не решит ни одной задачи?

В экзамене по каждой теме n = 8 вариантов выбора задачи. По правилу произведения всего возможно N = 8 5 = 32768 вариантов билетов.
Вася готов решать k = 3 задачи по каждой теме. По правилу произведения всего он сможет полностью решить K = 3 5 = 243 вариантов.
Вася не готов решать m = 8 – 3 = 5 задач по каждой теме. По правилу произведения всего он вообще не сможет решить M = 5 5 = 3125 вариантов.
Ответ: 32768; 243; 3125.

Пример 4. Каких пятизначных чисел больше: тех, что не делятся на 5, или таких, у которых ни первая, ни вторая слева цифры – не пятёрки?

Сколько всего пятизначных чисел? На первом месте – 9 вариантов цифр, на четырёх последующих – по 10 вариантов. Итого: N = 9 · 10 4 = 90000 чисел.
Признак делимости на 5: последняя цифра 5 или 0.
Количество чисел с последней цифрой 5: M₁ = 9 · 10 3 · 1 = 9000.
Аналогично, с последним 0: M₂ = 9 · 10 3 · 1 = 9000.
Итого, чисел, которые не делятся на 5:
M = N – (M₁ + M₂) = 90000 – 2 · 9000 = 72000.
Сколько всего пятизначных чисел, у которых ни первая, ни вторая слева цифры – не пятёрки? На первом месте – 8 вариантов цифр, на втором – 9 вариантов. На остальных – по 10 вариантов.
Итого: K = 8 · 9 · 10 3 = 72000 чисел.
Получаем: M = K – искомых чисел поровну.
Ответ: их поровну.

Пример 5*. На глобусе проведено 17 параллелей и 24 меридиана. На сколько частей разделена поверхность глобуса?

Возьмём неразмеченный глобус. Проведем экватор.
Поверхность глобуса разделилась на 2 части.
Добавим еще одну параллель. Поверхность разделилась на 3 части.
Мы видим, что n параллелей делит поверхность на N = n + 1 частей.
Соответственно, для 17 параллелей, N = 18 частей.

Комбинаторика 1. Правило суммы 2. Правило произведения 3. Комбинаторные соединения 4. Перестановки 5. Размещения 6. Сочетания

Комбинаторика - один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в информационных технологиях, кибернетике и многих других науках.

ПРАВИЛО СУММЫ Пример 1 На одной тарелке 3 груши, на другой – 2 яблока. Сколько есть способов выбрать один фрукт? Пример 2 На полке стоит 2 книги по алгебре, 3 по геометрии, 1 по комбинаторике и 4 по литературе. Сколько есть способов выбрать книгу по математике?

ПРАВИЛО ПРОИЗВЕДЕНИЯ Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А, В) в указанном порядке можно осуществить mn способами. При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.

Комбинаторные соединения — это комбинации из каких-либо элементов. Типы соединений: • Перестановки • Размещения • Сочетания Существуют две схемы выбора элементов: • Без повторений • С повторениями

Комбинаторные соединения В комбинаторных соединениях может играть существенную роль или порядок элементов или их состав, или и порядок и состав. В зависимости от этого комбинаторные соединения имеют определённое название.

Перестановки без повторений — комбинаторные соединения, которые могут отличаться друг от друга лишь порядком входящих в них элементов. Pn= n!

Факториал числа — это произведение всех натуральных чисел до этого числа включительно. Обозначается с восклицательным знаком в конце. n! = 1 · 2 · 3 · 4 · … · (n-2) · (n-1) · n Случай 0! определен и имеет значение 0!=1, соответствующее комбинаторной интерпретации комбинации нуля объектов, другими словами, есть единственная комбинация нуля элементов, а именно: пустое множество.

Факториал числа Свойство факториала: (n + 1)! = (n + 1) · n! Пример 6! = (5+1)!=(5+1)*5!=6*(1*2*3*4*5)=720

Перестановки с повторениями — комбинаторные соединения, в которых среди образующих элементов имеются одинаковые.

Размещения без повторений — комбинаторные соединения, составленные из n элементов по m. При этом два соединения считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

Размещения без повторений Пример 9. В правление Банка избрано 9 человек. Сколькими способами можно выбрать из них Председателя, Заместителя Председателя и Секретаря?

Размещения без повторений Пример 10. Сколько словарей нужно издать для непосредственного перевода с русского, английского, немецкого и французского языков на любой из этих языков?

Размещения с повторениями — комбинаторные соединения, составленные из n элементов по m. При этом каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать.

Размещения с повторениями Пример 11. Сколько трехпозиционных комбинаций можно образовать из двоичных цифр? Пример 12. Есть кодовый замок с четырьмя дисками, на каждом из которых цифры от 0 до 9. Сколько существует вариантов кода?

Сочетания без повторений — комбинаторные соединения из n элементов по m, составленные из этих элементов и отличающиеся друг от друга только составом.

Сочетания без повторений Пример 13. В магазине есть краски 5 различных цветов. Вы хотите для оформления комнаты использовать 3 цвета. Сколько есть способов это сделать?

Сочетания с повторениями — комбинаторные соединения из n элементов по m, составленные из этих элементов без учета порядка с возможностью многократного повторения элементов.

Сочетания с повторениями Пример 14. В киоске продается 3 вида открыток сколькими способами можно купить 5 открыток?

Комбинаторика представляет собой область математики, занимающейся подсчётом элементов конечных множеств. Общие задачи подсчета элементов некоторого множества связаны с выборкой некоторого числа элементов из заданного базисного множества. Такие задачи полезно делить на типы в зависимости от того, как выбираются элементы: с повторением или без повторений, с учетом порядка выбора или без оного. Мы выведем формулы для каждого из перечисленных типов задач

Начнем с формулировки ряда простых задач.

Задача 1. В небольшой кондитерской к концу рабочего дня осталось несколько пирожных: четыре ванильных, два шоколадных и три фруктовых. Один покупатель собирается купить пирожные перед закрытием кондитерской. Сколько вариантов выбора существует, если покупатель может купить 1, 2, 3 пирожных?

Первая задача решается простым подсчетом. Поскольку все пирожные различны, мы просто можем сложить их количества. Это дает 4 + 2 + 3 = 9 пирожных, из которых покупатель может сделать выбор. Во втором случае 9*8=72 варианта выбора пирожных, в третьем 9*8*7= 504, если не важно какие именно пирожные выбирать!

Эти задачи иллюстрируют два фундаментальных правила пересчета.

Правило произведения утверждает, что если дана последовательность к событий с n₁ возможными исходами первого, n₂ - второго, и т. д., вплоть до n_k возможных исходов последнего, то общее число исходов последовательности k событий равно произведению n₁ * n₂*…* n_k.

Задача 2. Сколько существует трехзначных чисел, начинающихся с 3 или 4? Трехзначные числа, о которых идет речь в задаче, разбиваются на два непересекающихся класса. К одному из них относятся числа, начинающиеся с 3, а ко второму - с 4. Для подсчета чисел в первом классе заметим, что существует один возможный исход для первой цифры (она должна быть равна 3), 10 исходов для второй и 10 исходов для последней цифры.

По правилу произведения получаем, что всего чисел в первом классе насчитывается ровно 1*10*10 = 100. Аналогично можно подсчитать количество чисел во втором классе. Оно тоже равно 100. Наконец, по правилу суммы получаем, что существует 100 + 100 = 200 трехзначных чисел, начинающихся с 3 или 4.

Задача 3. Государственный регистрационный знак легкового автомобиля состоит из трех цифр и трех букв русского алфавита (не считая кода города). Будем считать, что в номере можно задействовать любую последовательность букв и цифр. Сколько различных автомобильных номеров может выдать ГИБДД?

Решение. Каждую из трех букв номера можно выбрать из 33 букв алфавита. По правилу произведения число различных последовательностей из трех букв равно 33*33*33 = 35937. Аналогично, число последовательностей трех цифр равно 10*10*10 = 1000. Наконец, поскольку каждый из автомобильных номеров состоит из трех букв и трех цифр, правило произведения дает искомый ответ: 35937000 различных автомобильных номеров может выдать ГИБДД.

Таким образом, мы имеем четыре разных уточнения формулировки.

1. Повторения разрешены и порядок выбора существенен. В этом случае у нас есть 9 возможностей: АА, АВ, АС, АВ, ВВ, ВС, С А, С В и СС.

2. Запрещено брать конфеты одного наименования, но порядок существенен. В этой ситуации - 6 случаев: АВ, АС, В А, ВС, С А и СВ.

3. Повторения разрешены, но порядок выбора не имеет значения. Тогда ответ - тоже 6 возможностей: АА, АВ, АС, ВВ, ВС и СС.

4. И, наконец, если нельзя брать одинаковые конфеты, а порядок не имеет значения, то у ребенка есть только три варианта выбора: АВ, АС и ВС.

Чтобы различать на терминологическом уровне тип конкретной задачи, введем несколько определений.

Начнем со вспомогательных терминов. Предположим, что мы берем элементы x₁, x₁, . x_k из множества X мощности k ( число элементов в множестве равно k). Каждый такой набор принято называть выборкой объема k из n элементов или, иначе, (n, k)-выборкой. Выборка называется упорядоченной, если порядок следования элементов в ней задан. При этом две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются разными. Если же порядок следования элементов в выборке не имеет значения, то выборка называется неупорядоченной.

Теперь введем основные термины в соответствии с типом уточнений, приведенных выше.

• (n, k)-размещением с повторениями называется упорядоченная (n, k)-выборка, элементы в которой могут повторяться;

• (n, k)-размещением без повторений называется упорядоченная (n, k)-выборка, элементам в которой повторяться запрещено;

• неупорядоченная (n, k)-выборка с повторяющимися элементами называется (n, k)-сочетанием с повторениями

• неупорядоченная (n, k)-выборка без повторяющихся элементов называется (n, k)-сочетанием без повторений.

Подсчитаем количество всех различных (n, k)-размещений с повторениями. На первое место выборки мы можем поставить любой из n элементов множества. Поскольку повторения разрешены, то на второе место мы опять можем поставить любой элемент из этого же множества, и т. д. Поскольку у нас k мест в выборке, то опираясь на правило произведения, получаем, что число всех (n, k)-размещений с повторениями равно n k .

Задача 5. Целые числа в компьютере представляются строчкой из N двоичных знаков. Первый из них отведен на знак (+ или -), а остальные N - 1 отвечают за модуль целого числа. Сколько различных целых чисел может использовать компьютер?

Решение. Двоичная цифра это 0 или 1. Для записи числа используется N таких цифр. Заметим, что двоичные строки, представляющие числа, могут иметь повторяющиеся цифры, и порядок их следования, естественно, существенен для данной задачи. Поэтому мы имеем дело с (2, N)-размещениями с повторениями. По выведенной формуле получаем, что общее количество таких строк равно 2 N .

Практически всегда различные размещения изображают различные числа, за исключением двух строк: -000000…00 и + 000000…00, которые изображают 0. Значит, компьютер может оперировать (2 N - 1) целыми числами.

Для числа всех (n, k)-размещений без повторений зафиксировано специальное обозначение P(n, k).Подсчитаем это число. На первое место выборки мы можем поставить любой из n элементов. Поскольку здесь нам не разрешены повторения, то для второго места мы можем выбрать любой из (n- 1) оставшихся элементов. На третье - из (n- 2) и так далее, вплоть до k-го места, куда можно написать любой из (n-k +1) элементов. Теперь применим правило произведения. Имеем Р(n, k) = n(n-1)(n - 2) … (n-k +1).

Для сокращения записи напомним, что произведение всех натуральных чисел от 1 до n включительно называется n факториал и обозначается символом n!. Выразим Р(n, k)

число различных (n, k)- размещений без повторений.

Число всех (n, k)- сочетаний без повторений обозначается символом С(n, k). Оно связано с числом (n, k)- размещений без повторений Р(n, k) формулой

Задача 6. По меню в ресторане можно выбрать ровно три из семи главных блюд. Сколькими способами Вы можете сделать заказ?

Решение. Здесь мы имеем дело с (7, 3)-сочетаниями без повторений.

Итак, у Вас есть 35 возможностей для различных заказов.

Исследуем, это сочетания с повторениями. Напомним, что это выборки, в которых порядок не важен, а вот повторы элементов допускаются. Поскольку порядок в наших выборках значения не имеет, а повторы разрешены, мы можем сгруппировать вместе одинаковые элементы, разделив группы какими-нибудь метками.

Предположим, например, что мы сделали выборку, состоявшую из пяти букв, каждая из которых может быть одной из а, 6^ и е.

Возвращаясь к общему случаю (n, k)-сочетаний без повторений (k объектов из n данных), заметим, что нам потребуется n-1 метка и k объектов. Таким образом, у нас будет (n- 1) + k ячеек для заполнения. Значит, число (n, k)-сочетаний без повторений совпадает с количеством способов размещения (n- 1) метки в (n+k-1) ячейку. Итак, общее число (n, k)-сочетаний без повторений равно

В таблице запишем все формулы для подсчета количества выборок k элементов из n-элементного множества, которые мы вывели сегодня.

Лекция 3. КОМБИНАТОРИКА