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

 
 
 
 
 
 
 

Реферат на тему: 

«Правила  сложения и произведения в комбинаторике» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Выполнил:                                                                            Ученик 10 «А» класса

                                                                    МОУ «Борисоглебская гимназия  №1»

                                                                                                 Рыбаковский Андрей 

Руководитель:                                                                                   Солодкова Н.В 
 
 

Содержание:  

1. Что такое комбинаторика?.................................................................................3 

    1.1 Краткая историческая справка…...………………….................................3 

2. Правило суммы……….. ………...………………………................................4 

    2.1 Полная группа событий.……………….…..………..................................5 

    2.2 Примеры задач ………………………………………................................ 5 

3. Правило произведения ……………..……………………............................... 6

   

    2.2 Примеры задач ………………………………………................................ 6

   

    2.3 Пересекающиеся множества……………………………………………...7

 

    2.4 Примеры задач ………………………………………................................ 7 

Список  литературы …………………………………………...............................8 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Что такое комбинаторика? 

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

Термин  «комбинаторика» был введён в  математический обиход Лейбницем, который  в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». 

Иногда  под комбинаторикой понимают более  обширный раздел дискретной математики, включающий, в частности, теорию графов. 

Краткая историческая справка. 

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов  конечного множества. Некоторые  элементы комбинаторики были известны в Индии еще во II в. до н. э. В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали  соединения в связи с применением  их в поэтике, науке о структуре  стиха и поэтических произведениях. Например, в связи с подсчетом  возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы  из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.) французский автор А. Также  посвящает сочетаниям и перестановкам  целую главу.

Б. Паскаль  в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин "комбинаторика" стал употребляться  после опубликования Лейбницем  в 1665 г. работы "Рассуждение о комбинаторном  искусстве", в которой впервые  дано научное обоснование теории сочетаний и перестановок. Изучением  размещений впервые занимался Я. Бернулли во второй части своей книги "Искусство предугадывания" в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX веке.

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

3                                                 

Правило суммы. 

Если  некоторый объект А может быть выбран из совокупности объектов m

способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами. 

Суммой А + В двух событий А и В называют событие, состоящее в

появлении события А, или события В, или обоих этих событий. Например, если из орудия произведены два выстрела и А — попадание при первом выстреле, В — попадание при втором выстреле, то А + В — попадание при первом выстреле, или при втором, или в обоих выстрелах. В частности, если два события А и B — несовместные, то А + В — событие, состоящее в появлении одного из этих событий, безразлично какого. 

Суммой  нескольких событий называют событие, которое состоит в появлении хотя бы одного из этих событий. Например, событие А + В + С состоит в появлении одного из следующих событий: А, В, С, А и В, А и С, В и С, А и В и С. 

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

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

равна сумме вероятностей этих событий: Р (А + В) = Р (А) + Р (В). 

Доказательство:

Введем  обозначения: n — общее число возможных  элементарных исходов испытания; m₁ — число исходов, благоприятствующих событию A;

m₂— число исходов, благоприятствующих событию В. Число элементарных исходов, благоприятствующих наступлению либо события А, либо события В, равно m₁ + m₂. Следовательно, Р (A + В) = (m₁ + m₂) / n = m₁ / n + m₂ / n. Приняв во внимание, что m₁ / n = Р (А) и m₂ / n = Р (В), окончательно получим Р (А + В) = Р (А) + Р (В). 

Следствие:

Вероятность появления одного из нескольких попарно

несовместных  событий, безразлично какого, равна сумме вероятностей этих

событий: Р (A₁ + A₂ + ... + A_n) = Р (A₁) + Р (A₂) + ... + Р (A_n). 
 
 
 
 

4

Доказательство:

Рассмотрим  три события: А, В и С. Так как  рассматриваемые события попарно несовместны, то появление одного из трех событий, А, В и С, равносильно наступлению одного из двух событий, A + В и С, поэтому в силу указанной теоремы Р ( А + В + С) = Р [(А + В) + С] = Р (А + В) + Р (С) = Р (А) + Р (В) + Р (С). Для произвольного числа попарно несовместных событий доказательство проводится методом математической индукции.

    

Полная  группа событий.

    

Теорема Сумма вероятностей событий А₁ , А₂ ,..., А_n , образующих полную группу, равна единице: Р (A₁) + Р (А₂) + ... + Р (А_n) = 1. 

   

Доказательство:

Так как  появление одного из событий полной группы достоверно, а вероятность достоверного события равна единице, то Р(A₁ + A₂ + ... + A_n) = 1.   

Любые два события полной группы несовместны, поэтому можно применить теорему сложения: Р(А₁ + А₂ + ... + А_n) = Р(A₁) + Р(A₂) + ... + Р(А_n).     

Примеры задач. 

Задача  №1.

Ученик  должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может  выбрать одну тему для практической работы? 

Решение: X=17, Y=13

По правилу  суммы 17+13=30 тем. 

Задача  №2.

Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов  автомобильной лотереи. Сколькими способами можно выбрать один билет из спортлото или автомобильной лотереи? 

Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10=16 вариантов.

                              
 
 
 
 
 
 

5

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

Если  объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана m_n способами. 

Произведение  событий.  

Произведением двух событий А и В называют событие АВ, состоящее в совместном появлении (совмещении) этих событий.

Например, если А — деталь годная, В — деталь окрашенная, то АВ — деталь годна и окрашена.

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

Примеры задач. 

Задача  №1.

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

Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета. 

Задача  №2.

Сколько существует пятизначных чисел, которые  одинаково читаются слева направо  и справа налево? 

Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX, где Y и Z -любые цифры, а X - не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900 вариантов. 
 
 
 
 
 
 
 
 

6

Пересекающиеся  множества. 

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

Примеры задач. 

Задача  №1.

20 человек  знают английский и 10 - немецкий, из них 5 знают и английский, и немецкий. Сколько Человек всего? 

Ответ: 10+20-5=25 человек. 

Также часто для наглядного решения  задачи применяются круги Эйлера. Например:

Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским - 42. Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком?  

Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.  

Всеми тремя языками владеют три  туриста, значит, в общей части  кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и  французским владеют 10-3=7 человек.