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





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

 

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

Примеры:

1. Сколькими способами можно расставить на полке 5 книг?

2. Сколькими способами можно выбрать 2-х дежурных из нашего класса в 29 человек.

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

4. Каких чисел больше среди первых 100, натуральных чисел: содержащих в своей записи цифру 7 или нет?

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

С аналогичными задачами, получившими название комбинаторных, люди столкнулись в глубокой древности. Уже несколько тысячелетий назад в Древнем Китае увлекались составлением магических квадратов, в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же. В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата, и т.д.

Комбинаторные задачи возникали и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т.д. Комбинаторика становится наукой лишь в XVII в. – в период, когда возникла теория вероятностей. Чтобы решать теоретико-вероятностные задачи, нужно было уметь подсчитывать число различных комбинаций, подчиненных тем или иным условиям. После первых работ, выполненных в XVI в. итальянскими учеными Дж. Кардано, Н. Тартальей и Г. Галилеем, такие задачи изучали французские математики Б. Паскаль и П. Ферма. Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц, опубликовавший в 1666 г. работу «Об искусстве комбинаторики», в которой впервые появляется сам термин «комбинаторный». Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру. Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей. Теперь комбинаторика находит приложения во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений и т.д.

Основными задачами комбинаторики являются: 1) определение вида соединения; 2) подсчет числа соединений.

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

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

1.Правило суммы: если объект А может быть выбран n способами, а объект В – m способами, то выбор «А или В» может быть осуществлен n+m способами.

Пример. Если на одной полке книжного шкафа стоит 30 различных книг, а на другой - 40 различных книг (и не таких, как на первой полке), то выбрать одну книгу из стоящих на этих полках можно 30+40=70 способами.

При использовании правила сложения нужно следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В, т. е. чтобы ни одна комбинация не попала сразу в два класса. Если такие совпадения имеются, правило сложения в ранее сформулированной форме утрачивает силу, и мы получаем m + n – k способов выбора, где k — число совпадений.

2. Общее правило суммы: Если объект А можно выбрать m способами, а объект В — n способами, причем при k способах одновременно выбираются и А и В, то выбор «А или В» можно осуществить m + n – k способами.

Пример. Сколько чисел в первой сотне, не делящихся ни на 2, ни на 3?

Решение: Легче вычислить сначала количество чисел первой сотни, делящихся на 2 или на 3. Каждое второе число в натуральном ряде делится на 2, каждое третье— на 3. Поэтому в первой сотне есть 50 чисел, делящихся на 2, и 33 числа (неполное частное от деления 100 на 3), делящихся на 3. Но среди первых и вторых имеются числа, делящиеся и на 2, и на 3, т. е. делящиеся на 6. На 6 делится каждое шестое число в натуральном ряде. Если 100 разделить на 6, то неполное частное будет равняться 16, т. е. 16 чисел в первой сотне делится на 6. Итак, количество чисел в первой сотне, делящихся на 2 или на 3, равно 50 + 33 – 16 = 67. Все остальные не делятся ни на 2, ни на 3. Этих чисел 100 – 67 = 33.

3.Правило произведения: если объект А может быть выбран n способами и после каждого из таких выборов объект В – m способами, то выбор «А и В» в указанном порядке может быть осуществлен n*m способами.

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

Решение: Первое блюдо можно выбрать одно из трех (борщ, солянку или грибной суп), второе блюдо тоже одно из трех (мясо с макаронами, рыбу с картошкой или курицу с рисом), на десерт только два варианта (чай или компот). Используя правило произведения, получаем: 3х3х2=18.

Пример. В классе 25 человек. Сколькими способами:

а) можно распределить между ними два различных учебника;

б) можно распределить между ними два различных учебника так, чтобы никто не получил оба учебника;

Решение: а) Первый учебник может получить любой из 25 учащихся.Кто бы ни получил первый учебник, второй может достаться снова любому из 25, ведь в условии не сказано, что каждый должен получить не более одного учебника. Всего имеем 25* 25 = 625 способов.

б) В отличие от предыдущего задания, никто не должен получить оба учебника. Поэтому для каждого из 25 вариантов выбора обладателя первого учебника есть 24 способа выбора обладателя второго учебника. Всего имеем 25*24 = 600 способов.

Рассмотрим примеры, использующие правила суммы и произведения.

Пример. Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу (т.е. чтобы какое-то число очков встретилось на обеих костях)?

Решение. Сначала выберем одну кость. Это можно сделать 28 способами. При этом в случаях выбранная кость окажется "дублем", т.е. костью вида 00, 11, 22, 33,44 , 55 ,66, а в 21 случае - костью с различными числами очков (например, 05, 13 и т.д.).В первом случае вторую кость можно выбрать 6 способами (например, если на первом шагу выбрана кость 11, то на втором шагу можно взять одну из костей 01, 12, 13, 14, 15, 16).Во втором же случае вторую кость можно выбирать 12 способами (для кости 35 подойдут кости 03, 13, 23, 33, 34, 36, 05, 15, 25, 45, 55, 56). По правилу произведения в первом случае получаем 7*6=42 выбора, а во втором 21*12=252 выбора. Значит по правилу суммы получаем 42+252=294 способов выбора пары.

Пример. Сколько существует четырехзначных чисел, у которых все цифры нечетные? Сколько существует четырехзначных чисел, в записи которых есть хотя бы одна четная цифра?

Решение. Всего нечетных цифр - пять, поэтому выбор k-й цифры числа может быть сделан nк=5 способами (к=1, 2, 3, 4), а количество четырехзначных чисел, у которых все цифры нечетные, равно 5*5*5*5=625. Чтобы ответить на второй вопрос, проще не определять последовательно, сколько существует чисел, в записи которых ровно одна четная цифра, две цифры, три цифры, четыре цифры, а воспользоваться полученным ответом на первый вопрос. Все четырехзначные числа, а их 9999-999=9000, делятся на две группы: те, в записи которых все цифры нечетные, и те, в записи которых есть хотя бы одна четная цифра. Следовательно, количество чисел второго типа равно 9000-625=8375.

Пример. Из города А в город В ведут пять дорог, а из города В в город С — три дороги. Пусть, кроме того, из города А в город D можно попасть двумя путями, из D в C — четырьмя (рис.1). Сколькими способами можно добраться из А в С?

 

Рис. 1. Варианты перемещения между городами

 

Решение: Возможны два случая: путь из А в С проходит через город В или через город D. В каждом из этих случаев число возможных маршрутов легко подсчитать, воспользовавшись правилом произведения. В первом случае имеется 5*3 = 15 маршрутов; во втором — 2*4 = 8. Складывая, получаем общее число маршрутов: 15 + 8 = 23.

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

 





Читайте также:
Образование Киргизкой (Казахской) АССР: Предметом изучения Современной истории Казахстана являются ...
ТЕМА: Оборудование профилактического кабинета: При создании кабинетов профилактики в организованных...
Назначение, устройство и принцип работы автосцепки СА-3 и поглощающего аппарата: Дальнейшее развитие автосцепки подвижного состава...
Русский классицизм в XIX веке: Художественная культура XIX в. развивалась под воздействием ...

Рекомендуемые страницы:



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

Поиск по сайту

©2015-2021 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-08-20 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту:

Мы поможем в написании ваших работ! Мы поможем в написании ваших работ! Мы поможем в написании ваших работ!
Обратная связь
0.013 с.