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

Вспомните, что в математике любые совокупности называют множествами. Объекты, входящие в множества, называют его элементами. Множества обозначают большими латинскими буквами, а их элементы записывают в фигурных скобках. Считают, что все элементы множества различны.

Например,

Множества бывают конечными и бесконечными. Если множество не содержит ни одного элемента, его называют пустым и обозначают символом

Два множества называют равными, если они состоят из одних и тех же элементов.

Если — часть множества то его называют подмножеством множества и записывают Наглядно это изображают с помощью диаграммы Эйлера (рис. 135, а). В частности, для числовых множеств правильные такие соотношения:

Случается, что множества имеют общие элементы. Если множество содержит все общие элементы множеств и только их, то множество называют пересечением множеств Записывают это так: Диаграммой Эйлера пересечение изображают, как показано на рисунке 135, б. Множество, содержащее каждый элемент каждого из множеств и только эти

элементы, называется объединением множеств Если — объединение множеств то пишут (рис. 135, в).

Разницей множеств называют множество, состоящее из всех элементов множества не принадлежащих множеству Его обозначают Например, если

Говоря «множество», «подмножество», порядок их элементов не учитывают. Говорят, что они не упорядочены. Рассматривают и упорядоченные множества. Так называют множества с фиксированным порядком элементов. Их обозначают не фигурными, а круглыми скобками. Например, из элементов множества можно образовать 6 трёхэлементных упорядоченных множеств:

Как множества, все они равны, как упорядоченные множества — разные.

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

Комбинаторика — раздел математики, посвящённый решению задач выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами.

Рассмотрим два основных правила, с помощью которых решается много комбинаторных задач.

Пример №17

В городе есть два университета — политехнический и экономический. Абитуриенту нравятся три факультета в политехническом университете и два — в экономическом. Сколько возможностей имеет студент для поступления в университет?

Решение:

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

Описанную ситуацию можно обобщить в виде утверждения, которое называется правилом суммы.

Если элемент некоторого множества можно выбрать способами, а элемент множества способами, то элемент из множества или из множества можно выбрать способами.

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

Пример №18

Планируя летний отдых, семья определилась с местами его проведения: в Одессе — 1, в Евпатории — 3, в Ялте — 2, в Феодосии — 2. Сколько возможностей выбора летнего отдыха имеет семья?

Решение:

Поскольку все базы отдыха разные, то для решения задачи достаточно найти сумму элементов всех множеств, о которых говорится: Следовательно, семья может выбирать отдых из 8 возможных.

Пример №19

От пункта до пункта ведут три тропинки, а от — две. Сколько маршрутов можно проложить от пункта до пункта

Решение:

Чтобы пройти от пункта до пункта надо выбрать одну из трёх тропинок: 1, 2 или 3 (рис. 136). После этого следует выбрать одну из двух других троп: 4 или 5. Всего от пункта до пункта ведут 6 маршрутов, потому что Все эти маршруты можно обозначить с помощью пар:

Обобщим описанную ситуацию.

Если первый компонент пары можно выбрать способами, а. второй — способами, то такую пару можно выбрать способами.

Это — правило произведения, его часто называют основным правилом комбинаторики. Обратите внимание: речь идёт об упорядоченных парах, составленных из различных компонентов.

Правило произведения распространяется и на упорядоченные тройки, четвёрки и любые другие упорядоченные конечные множества. В частности, если первый компонент упорядоченной тройки можно выбрать способами, второй — способами, третий — способами, то такую упорядоченную тройку можно выбрать способами. Например, если столовая на обед приготовила 2 первых блюда — борщ (б) и суп (с), 3 вторых — котлеты (к), вареники (в), голубцы (г) и 2 десертных — пирожные (п) и мороженое (м), то всего из трёх блюд столовая может предложить 12 различных наборов, поскольку

Описанной ситуации соответствует диаграмма, изображённая на рисунке 137. Такие диаграммы называют деревьями.

Пример №20

Сколько разных поездов можно составить из 6 вагонов, если каждый из вагонов можно поставить на любом месте?

Решение:

Первым можно поставить любой из б вагонов. Имеем 6 выборов. Второй вагон можно выбрать из оставшихся 5 вагонов. Поэтому, согласно правилу умножения, два первых вагона можно выбрать способами. Третий вагон можно выбрать из 4 вагонов, которые остались. Поэтому три первых вагона можно выбрать способами. Продолжая подобные рассуждения, приходим к ответу: всего можно составить различных поездов.

Обратите внимание на решение последней задачи. Оно свелось к вычислению произведения всех натуральных чисел от 1 до 6. В комбинаторике подобные произведения вычисляют часто.

Произведение всех натуральных чисел от 1 до называют факториалом и обозначают

Например:

Условились считать, что

Языком теории множеств правила суммы и произведения можно сформулировать следующим образом.

Если пересечение множеств пустое, то количество элементов в их объединении равно сумме количества элементов множеств

Если множества имеют общие элементы, то

Если множества конечны, то количество возможных пар равно произведению количества элементов множеств

Пример №21

В розыгрыше на первенство города по баскетболу принимают участие команды из 12 школ. Сколькими способами могут быть распределены первое и второе места?

Решение:

Первое место может получить одна из 12 команд. После того, как определён обладатель первого места, второе место может получить одна из 11 команд. Следовательно, общее количество способов, которыми можно распределить первое и второе места, равно

Ответ. 132.

Пример №22

Сколько четырёхзначных чисел можно составить из цифр 0,1, 2, 3, 4, 5, если ни одна цифра не повторяется?

Решение:

Первой цифрой числа может быть одна из 5 цифр 1, 2, 3, 4, 5. Если первая цифра выбрана, то вторая может быть выбрана 5-ю способами, третья — 4-мя, четвёртая — 3-мя. Согласно правилу умножения общее число способов равно:

Ответ. 300.

Пример №23

Упростите выражение

Решение:

Размещения и перестановки

Задача:

Сколькими способами собрание из 20 человек может избрать председателя и секретаря?

Решение:

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

Обобщим задачу. Сколько упорядоченных - элементных подмножеств можно составить из различных элементов? На первое место можно поставить любой из данных элементов. На второе место — любой из остальных элементов и т. д. На последнее место можно поставить любой из остальных элементов. Из правила произведения следует, что из данных элементов можно получить -элементных упорядоченных подмножеств.

Например, из 4 элементов упорядоченных двухэлементных подмножеств можно образовать всего

Упорядоченое -элементное подмножество элементного множества называют размещением из элементов Их число обозначают

Из предыдущих рассуждений следует, что и что для любых натуральных

В правой части этого равенства множителей. Поэтому результат можно сформулировать в виде такого утверждения.

Число размещений из элементов по равно произведению последовательных натуральных чисел, наибольшее из которых

Примеры:

Пример №24

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

Решение:

Речь идёт об упорядоченных 5-элементных подмножествах некоторого множества, состоящего из 10 элементов.

Это размещения.

Ответ. 30 240 способами.

Число размещений из элементов по можно вычислять и по другой формуле: (проверьте самостоятельно).

Размещение элементов по называют перестановками из элементов. Их число обозначают

Например, из трёх элементов можно образовать 6 различных перестановок: Следовательно,

Подставив в формулу числа размещений получим, что

Число перестановок из элементов равно !

Примеры:

Пример №25

Сколькими способами можно составить список из 10 фамилий?

Решение:

Ответ. 3 628 800 способами.

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

Пример №26

Решите уравнение

Решение:

Пользуясь формулой размещений, данное уравнение можно заменить таким:

По условию задачи — натуральное число, поэтому — посторонний корень. Следовательно,

Пример №27

Решите уравнение

Решение:

Запишем выражения через произведения.

Имеем:

Поскольку по смыслу задачи Поэтому последнее уравнение можно сократить на произведение Тогда Но уравнение удовлетворяет только одно значение:

Пример №28

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

Решение:

Речь идёт об упорядоченных 3-элементных подмножествах множества, состоящего из 30 элементов. Это — размещения.

Пример №29

Сколькими способами можно разместить на полке 5 дисков?

Решение:

Речь идёт об упорядоченных 5-элементных множествах. Искомое количество способов равно

Ответ. 120 способами.

Пример №30

Изображённое на рисунке 140 кольцо раскрашено в 7 цветов. Сколько существует таких колец, раскрашенных теми же цветами только в других последовательностях?

Решение:

Зафиксируем одну какую-нибудь часть кольца, окрашенную одним цветом, б других частей можно раскрасить способами.

Ответ. 720 колец.

Пример №31

Сколько можно составить различных неправильных дробей, числителями и знаменателями которых есть числа 3,5, 7,9,11,13?

Решение:

Способ 1. Дробей, у которых числитель не равен знаменателю, можно составить то есть Из этих дробей только половина — неправильных, то есть — 15.

Неправильными являются также дроби, у которых числитель равен знаменателю. Таких дробей в нашем случае 6. Итак, всего можно составить (дробь).

Способ 2. Если знаменатель неправильной дроби 3, то его числителями могут быть все 6 данных чисел. Если знаменатель 5, то числителями неправильной дроби могут быть 5 чисел (5, 7, 9, 11, 13) и т.д. Наконец, если знаменатель — число 13, то существует только 1 неправильная дробь, со знаменателем 13. Всего таких неправильных дробей существует

Ответ. 21 дробь.

Комбинации и бином ньютона

Пусть дано множество из трёх элементов: Его двухэлементных подмножеств (не упорядоченных) существует всего три: Говорят, что существует 3 комбинации из трёх элементов по два. Пишут:

Комбинацией из элементов по называют любое элементное подмножество элементного множества.

Число комбинаций из элементов по обозначают В отличие от размещений, комбинации — подмножества неупорядоченные.

Сравните: При тех же значениях значение меньше Можно также указать, во сколько раз меньше. Каждую элементную комбинацию можно упорядочить способами. В результате из одной комбинации получают размещений (упорядоченных подмножеств) из тех же элементов. Итак,

число элементных комбинаций в раз меньше числа размещений из тех же элементов.

То есть, отсюда

Пример №32

Вычислите:

Решение:

Обратите внимание! Полагают также, что для любого

Пример №33

Сколькими способами из 25 учеников можно выбрать на конференцию двух делегатов?

Решение:

Здесь порядок учеников не имеет значения.

Ответ. 300-ми способами.

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

Доказательство. Пусть дано различных элементов: Всего из них можно образовать различных элементных комбинаций. Это количество комбинаций вычислим другим способом. Из данных элементов, кроме последнего можно образовать комбинаций. Остальные элементные комбинации из всех данных элементов можно образовать, если к каждой комбинации из первых элементов по дописать элемент Таких комбинаций

Следовательно, А это и требовалось доказать.

Такое комбинаторное тождество можно доказать также, воспользовавшись формулой числа комбинаций.

С комбинациями тесно связана формула бинома Ньютона. Вспомните формулу квадрата двучлена:

Умножив получим формулы:

Эти три формулы можно записать и так:

Оказывается, для каждого натурального значения правильна и общая формула:

Это тождество называют формулой бинома Ньютона. а её правую часть разложением бинома Ньютона. Бином — латинское название двучлена. Пользуясь этой формулой, возведём, например, двучлен в пятую степень. Поскольку

Доказать формулу бинома Ньютона можно методом математической индукции.

Доказательство. Предположим, что формула верна для некоторого натурального показателя степени Покажем, что тогда она верна и для следующего за ним значения

Выражения в скобках преобразованы согласно формулы

Следовательно, если формула бинома Ньютона верна для то она правильна и для Для она правильна, так как Поэтому на основе аксиомы математической индукции можно утверждать, что формула верна для любого натурального показателя

Вычислять коэффициенты разложения бинома Ньютона можно не по формуле числа комбинаций, а пользуясь числовым треугольником Паскаля — своеобразным способом вычисления коэффициентов разложения бинома Ньютона

Треугольник Паскаля можно продолжать как угодно далеко. Это следует из тождества Его крайние числа — единицы, а каждое другое равно сумме двух ближайших к нему чисел сверху.

Например, прибавляя числа шестой строки (для получим числа следующей строки (для Следовательно, Общий член разложения бинома можно определить по формуле

Например:

• первый член —
• второй член —
• третий член —

Пример №34

В турнире по шашкам приняли участие 5 девушек и 7 юношей. Каждый участник сыграл один раз с каждым другим. Сколько партий было: а) между девушками; б) между юношами; в) между юношами и девушками?

Решение:

а) Речь идёт о 2-элементных подмножествах (неупорядоченных) множества, состоящего из 5 элементов. Это — комбинации.

б) Аналогично

в) Воспользуемся правилом умножения. Поскольку каждой из 5 девушек предстоит сыграть с каждым из 7 юношей, возможных случаев

Пример №35

Для дежурства в столовой приглашают 3-х учеников из 7 класса и 2-х учеников из 10 класса. Сколькими способами это можно сделать, если в 7 классе учится 24 ученика, а в 10 классе — 18.

Решение:

Речь идёт о неупорядоченных подмножествах двух разных множеств. Это — комбинации.

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

Пример №36

Сколько разных делителей имеет число 1001?

Решение:

Разложим заданное число на простые множители: Если число — делитель числа 1001, то оно должно быть одним из чисел 7, 11,13 (три случая) или любым их произведением. Различных произведений может быть Делителем данного числа есть ещё единица. Следовательно, число 1001 имеет делителей.

Пример №37

Докажите, что выпуклый угольник имеет диагоналей.

Решение:

Отрезков, концами которых являются вершин данного -угольника, существует Среди них есть и сторон данного -угольника. Поэтому диагоналей он имеет

Пример №38

Докажите тождество

Сделайте обобщение.

Решение:

Все члены разложения бинома Ньютона такие же, как и члены разложения бинома только их члены с чётными номерами отрицательные.

Пример №39

Найдите номер члена разложения который не содержит

Решение:

Воспользуемся формулой общего члена разложения бинома. Имеем:

По условию задачи то есть Отсюда Следовательно, не содержит шестой член разложения бинома.

Элементы комбинаторики

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

Определение: Перестановки - это комбинации из одних и тех же элементов, отличающиеся только порядком элементов.

Пример:

Даны три числа 1, 2, 3. Определить количество комбинаций из этих элементов, отличающиеся только порядком элементов.

Решение:

Комбинации из данных элементов, отличающиеся только порядком элементов: 123; 132; 213; 231; 321; 312. Всего таких комбинаций Если дано n элементов, то число перестановок O2. Размещения - это комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их расположением.

Пример:

Даны три числа 1, 2, 3. Определить количество размещений из этих элементов по два, отличающиеся составом или порядком элементов.

Решение:

Комбинации из данных элементов по два, отличающиеся составом или порядком элементов: 12; 21; 23; 32; 13; 31. Всего таких комбинаций 6. Если дано n элементов, то число размещений по m элементов, которые отличаются либо составом элементов, либо их расположением:

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

Пример:

Даны три числа 1, 2, 3. Определить количество размещений из этих элементов по два, отличающиеся хотя бы одним элементом.

Решение:

Комбинации из данных элементов по два, отличающиеся хотя бы одним элементом: 12; 23; 13. Всего таких комбинаций 3. Если дано n элементов, то число сочетаний по m элементов, которые отличаются хотя бы одним элементом:

Пример:

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

Решение:

Число способов равно числу различных комбинаций из п элементов, отличающихся только порядком элементов, т.е. числу перестановок:

Пример:

Из колоды, содержащей 36 карт, наугад вынимают 3 карты. Найти вероятность того, что среди выбранных карт окажется один туз.

Решение:

Событие А состоит в том, что среди выбранных карт окажется один туз. Это сложное событие состоит из двух событий: выбирается один туз из четырех, а две другие карты выбираются из оставшихся 32 карт. Следовательно, число случаев, благоприятствующих появлению события A, равно Всего возможных равновероятных исходов, образующих полную группу определяется числом сочетаний из 36 карт по 3 карты, т.е. Таким образом, вероятность события А равна