Комбинаторика и вероятность

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

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

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

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

Поэтому я считаю, что комбинаторика и вероятность заслуживают пристального внимания. Цель работы: Обоснование изучения курса комбинаторики в старшей школе как реальную необходимость при осуществлении принципа непрерывности образования «Школа - ВУЗ».

Задачи: 1. Расширить и углубить знания по математике, познакомившись с формулами комбинаторики и вероятности.

2. Исследовать различные способы решения комбинаторных задач.

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

4. Разработать программу элективного курса «Комбинаторика и вероятность».

Объект исследования: Область математики - комбинаторика и вероятность. Методы исследования:

Теоретические методы - изучение научной литературы.

Практические методы - опрос старшеклассников, опыт.

При написании работы я тесно сотрудничала с моим руководителем Волковой Людмилой

Павловной.

2. Комбинаторика и вероятность.

2. 1. Кое-что из прошлого теории вероятностей

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

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

Неосновательно было бы думать, что такие древние полководцы, как Александр Македонский или Дмитрий Донской, готовясь к сражению, уповали только на доблесть и искусство воинов.

Несомненно, они на основании наблюдений и опыта военного руководства умели как-то оценить вероятность своего возвращения со щитом или на щите, знали, когда принимать бой, когда уклониться от него. Они не были рабами случая, но вместе с тем они были ещё очень далеки от теории вероятностей.

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

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

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

Впервые основы теории вероятностей были изложены последовательно французским математиком П. Лапласом (1719- 1827) в книге «Аналитическая теория вероятностей».

Автор писал: «Замечательно, что наука, которая началась с рассмотрения азартных игр, обещает стать наиболее важным объектом человеческого знания. Ведь по большей части важнейшие жизненные вопросы являются на самом деле лишь задачами теории вероятностей» [6, стр. 9].

Новый, наиболее плодотворный период связан с именами П. Л. Чебышева и его учеников А. А. Маркова и А. М. Ляпунова.

Наследие русских математиков получило развитие в работах советских математиков Е. Е. Слуцкого, С. Н. Бернштейна и особенно академика А. Н. Колмогорова.

Созданная А. Н. Колмогоровым советская школа теории вероятностей завоевала всеобщее признание и сегодня занимает ведущие позиции в мировой науке.

2. 2. Правило умножения. Перестановки и факториалы

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

Обсудим способы решения следующей задачи: Сколько чётных двузначных чисел можно составить из цифр 0, 1, 2, 5, 8, 9?

Первый способ. Выпишем по порядку все числа от 10 до 99 и выберем те, которые нам нужны: 10, 12, 18, 20, 22, 28, 50, 52, 58, 80, 82, 88. 90, 92, 98. Всего 15 чисел.

Второй способ. Первой цифрой не может быть 0. Если первая цифра 1, то вторая (чётная) цифра - это 0, 2, 8. Всего три варианта. Если первая цифра 2, то вторая цифра - это 0, 2, 8. Также возможны три варианта. Если первая цифра 5, 8 или 9, то рассуждение повторяется. В каждом из этих случаев по три варианта. Всего получается 5 раз по 3, то есть 15 чисел.

Третий способ. Для выбора первой цифры есть пять вариантов: 1, 2, 5, 8. 9. Для второй цифры есть три варианта: 0, 2, 8. Значит, всего 5*3 = 15 вариантов составления чисел.

Обсуждая способы решения, отмечаем, что первый способ неплох, но здесь можно пропустить какое-либо число. Кроме того, этот способ неудачен в более сложных ситуациях. Второй способ в сложных ситуациях также вряд ли применим. Третий способ наиболее удачен. Непонятно только обоснование: «Почему 5 и 3 следует перемножить»? Ответ на этот вопрос можно сделать из второго способа решения, в котором говорится: 5 * 3 - это 5 раз по 3.

Сформулируем и докажем общее правило умножения, которое будем использовать в качестве обоснования подсчёта вариантов.

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

Доказательство: Исходом проведения двух испытаний - А и В - по определению, является пара (а; b), у которой на первом месте стоит один из исходов испытания А, а на втором месте - один из исходов испытания В.

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

Исход (а; bj) проведения двух испытаний А и В впишем в клетку, стоящую в i -й строке и j -м столбце. Независимость испытаний означает, что все клетки будут заняты. Поэтому клеток в таблице столько, сколько всевозможных исходов независимого проведения испытаний А и В. С другой стороны, число всех клеток равно произведению числа строк на число столбцов, то есть равно n * k. Правило умножения доказано.

-5- b1 b2 bj bk

Вот как это рассуждение будет выглядеть при решении предыдущей задачи:

1 10 12 18

2 20 22 28

5 50 52 58

8 80 82 88

9 90 92 98

Всего 5 *3 = 15 чисел.

Правило умножения для двух независимых испытаний удобно объяснять, используя прямоугольные таблицы. Но если проводятся три испытания, надо строить прямоугольный параллелепипед, разбитый на кубики. Здесь и рисунок, и объяснения выглядят сложнее, будут невидимые кубики. Ещё труднее дело обстоит с четырьмя испытаниями. Окружающее нас пространство всего лишь трёхмерно, и для рисунка в этом случае не хватит измерений.

Теорема. Правило умножения для конечного числа испытаний. Число всех возможных исходов независимого проведения n испытаний равно произведению количеств исходов этих испытаний.

Решим следующую задачу двумя способами:

Первый способ. В коридоре три лампочки. Сколько способов освещения коридора (включая случай, когда все лампочки не горят)?

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

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

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

У множества, состоящего из n элементов, имеется ровно 2n различных подмножеств.

Решение примера начинается с произвольной нумерации элементов конечного множества.

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

Произведение подряд идущих первых n натуральных чисел обозначают n! и называют «эн факториал»: n! = 1 * 2 * 3 *. * (n -1) * n.

Теорема, n различных элементов можно занумеровать числами от 1 до n ровно n! способами.

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

Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок Рn = n!, где n=1,2,3,. ,n .

Рассмотрим басню Ивана Крылова «Квартет»:

Проказница Мартышка,

Да косолапый Мишка

Затеяли сыграть Квартет.

Ударили в смычки, дерут, а толку нет.

«Стой, братцы, стой! – кричит Мартышка. -

Погодите!

Как музыке идти? Ведь вы не так сидите».

В содержании басни можно легко рассмотреть задачу комбинаторики: Сколькими различными способами могут сесть музыканты?»

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

Значит, если применить правило произведения, то получим, что число перестановок из четырёх элементов (четырёх зверей) равно

Р4 = 4! = 4 * 3 * 2 * 1 = 24 .

2. 3. Выбор нескольких элементов. Биноминальные коэффициенты

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

Теперь проведём исследование задач с выбором большего числа элементов данного множества. Рассмотрим задачу: В городских соревнованиях по волейболу участвовали пять школ города Барабинска: №1, №2, №3, № 92, №93. Каждая школа играла с каждой один раз. Сколько всего игр было?