Применение комбинаторики к подсчёту вероятностей

Размещено на http://www.allbest.ru/

[Введите текст]

Содержание

Введение

История возникновения

Формулы комбинаторики

Практика

Литература



Введение

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

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



История возникновения

Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты. Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н.э.). Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона. Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени n равна . Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло.

В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век). Ибн Эзра обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний. Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.

Джероламо Кардано написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В историю зарождавшейся теории вероятностей вошла переписка заядлого игрока шевалье де Мерэ с Пьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии - как для разработки шифров, так и для их взлома.

Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Наряду с Лейбницем, он считается основоположником современной комбинаторики. Сам термин «комбинаторика» придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.

В этот же период формируется терминология новой науки. Термин «сочетание» впервые встречается у Паскаля (1653). Термин «перестановка» употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «размещение».

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

- задача о ходе коня;

- задача о семи мостах, с которой началась теория графов;

- построение греко-латинских квадратов;

- обобщённые перестановки.

Кроме перестановок и сочетаний, Эйлер изучал разбиения, а также сочетания и размещения с условиями.

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

Сейчас это чрезвычайно содержательная и быстроразвивающаяся область математики.

Формулы комбинаторики

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

При решении задач комбинаторики используют следующие правила:

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

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

Размещения.

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

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

Поясним это на следующем примере. Пусть имеется три элемента: a, b и c. Тогда из этих трёх элементов можно составить шесть размещений по два элемента: ab, ac, ba, bc, ca, cb. Все приведённые размещения отличаются друг от друга хотя бы одним элементом или порядком их расположения.

Число размещений (читается: число размещений из n элементов по m элементов) можно найти из принципа умножения. Первый элемент размещения можно выбрать n способами. Как только такой выбор будет сделан, останется (n-1) возможностей, чтобы выбрать второй элемент; после этого останется (n-2) возможностей для выбора третьего элемента и т.д.; для выбора элемента m будет (n-m+1) возможностей. По принципу умножения находим

Легко понять, что .

Пример. Алфавит некоторого языка содержит 30 букв. Сколько существует шестибуквенных слов, составленных из букв этого алфавита, если буквы не могут повторяться?

Решение: Существует шесть мест, на которые нужно разместить 30 букв. Буквы не должны повторяться, значит воспользуемся формулой размещений без повторений:

=

Перестановки.

Рассмотрим частный случай, когда k = n. Соответствующее этому случаю размещение называется перестановкой.

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

Поясним это на следующем примере. Из этих трёх элементов: a, b и c. можно составить шесть перестановок: abc, acb, bac, bca, cab, cba. Все приведённые перестановки отличаются друг от друга только порядком их расположения.

Число перестановок n различных элементов обозначают символом Pn и равно

Пример. Сколькими способами могут восемь человек стать в очередь к театральной кассе?

Решение: Существует 8 мест, которые должны занять 8 человек.

I место - 8 способов.

II место - 7 способов и т.д.

По формуле перестановок без повторений получим: возможных способов.

Сочетания.

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

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

Поясним это на следующем примере. Пусть имеется три элемента: a, b и c. Из этих трёх элементов, в отличие от размещений, можно составить три сочетания по два элемента: ab, ac, bc. Все приведённые сочетания отличаются друг от друга хотя бы одним элементом.

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

Отсюда получаем, что число сочетаний будет равно

Заметим, что

.

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

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



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

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

Поясним это на следующем примере. Пусть имеется три элемента: a, b и c. Тогда из этих трёх элементов можно составить девять размещений с повторениями по два элемента: ab, ac, ba, bc, ca, cb, aa, bb, cc.

Таким образом, размещение с повторениями из n элементов по m элементов (при этом допускается, что m>n) может содержать любой элемент сколько угодно раз от 1 до m включительно или не содержать его совсем, т.е. каждое размещение с повторениями из n элементов по m элементов может состоять не только из различных элементов, но и m каких угодно и как угодно повторяющихся элементов. Число размещений с повторениями можно найти из принципа умножения. Первый элемент размещения можно выбрать n способами. Второй элемент также можно выбрать n способами (ведь элементы могут повторяться) и т.д. По принципу умножения находим

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



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

При перестановке букв в слове «толпа» получается P5 = 5! = 120 «слов». Если же переставлять буквы в слове «топот», то получится меньше различных «слов», потому что ни перестановка двух букв «т», ни перестановка двух букв «о» не изменяют «слова». Мы имеем здесь дело с перестановками с повторениями.

Общую задачу сформулируем следующим образом.

Имеется n элементов m различных типов: n1 элементов первого типа, n2 элементов второго типа, …, nm элементов m-го типа, . Сколько можно составить различных перестановок из этих элементов?

Число перестановок c повторениями обозначают . Если бы все элементы были различны, то число перестановок равнялось бы n!. Но из-за того, что некоторые элементы совпадают, получится меньшее число перестановок. В первой группе элементы (первого типа) можно переставлять друг с другом n1! способами. Но так как все эти элементы одинаковы, то перестановки ничего не меняют. Точно также ничего не меняют n2! перестановок элементов во второй группе и т.д. Перестановки элементов в разных группах можно делать независимо друг от друга. Поэтому (из принципа умножения) элементы можно переставлять друг с другом способами так, что она остаётся неизменной.

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

где .



Пример. Сколько различных перестановок можно образовать изо всех букв слова «перестановка»?

Решение: В слове «перестановка»12 букв, из них повторяются 2 буквы «е» и две буквы «а». Число перестановок из 12 элементов вычисляется с помощью формулы P12 = 12!. Но среди этих перестановок будут повторяющиеся, в которых буквы «е» или «а» меняются местами. Чтобы не считать такие перестановки, используется формула для перестановок с повторениями:

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

Пусть имеются предметы n различных типов. Сколькими способами можно составить из них комбинацию из m элементов, если не принимать во внимание порядок элементов в комбинации, но при этом предметы одного и того же типа могут повторяться? Иными словами, различные комбинации должны отличаться количеством предметов хотя бы одного типа. Такие комбинации называются сочетаниями с повторениями, а их общее число будем обозначать . Поясним это на следующем примере. Пусть имеется три элемента: a, b и c. Тогда из этих трёх элементов можно составить шесть сочетаний с повторениями по два элемента: ab, ac, bc, aa, bb, cc. Таким образом, сочетание с повторениями из n элементов по m элементов (при этом допускается, что m>n) может содержать любой элемент сколько угодно раз от 1 до m включительно или не содержать его совсем, т.е. каждое сочетание с повторениями из n элементов по m элементов может состоять не только из m различных элементов, но и m каких угодно и как угодно повторяющихся элементов.

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

Существует специальная формула для вычисления числа сочетаний с повторениями:



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

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

Практика

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

Задача 1. В колоде 36 карт. Какова вероятность вынуть: а) туза; б) туза пик; в) тузы красного цвета; г) любую карту, кроме туза.

Решение: Найдем общее число возможных исходов. Поскольку вынимается только одна карта, то число всевозможных исходов будет n=36. Найдем число благоприятствующих исходов для каждого случая.

а) В колоде всего четыре туза, следовательно, m1=4. Тогда

б) Имеется всего один пиковый туз, т.е. m2=1 и



в) Тузов красного цвета в колоде два (черви и бубни), т.е. m3=2 и

г) Карт, отличающихся от туза, в колоде всего m4=32. Следовательно, искомая вероятность будет равна

Задача 2. В лотерее разыгрывается 100 билетов, из них 25 - выигрышных. Главный приз - 1, второстепенных призов - 5 и остальные призы поощрительные. Какова вероятность того, что владелец одного билета: а) выиграет главный приз; б) выиграет ценный приз; в) хоть что-нибудь выиграет; г) выбросит деньги на ветер?

Решение: Очевидно, что общее исходов n=100. Рассмотрим каждую из ситуаций отдельно.

а) Благоприятствующих исходов выиграть главный приз только один: m1=1. Поэтому вероятность выиграть компьютер будет

б) Для второго случая m2 = 1 + 5 = 6, т.е. вероятность выиграть ценный приз



в) Всего выигрышных билетов m3=25, следовательно, вероятность хоть что-нибудь выиграть равна

г) Поскольку проигрышных билетов m4=75, то вероятность выбросить деньги на ветер, т.е. ничего не выиграть, равна

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

Теперь найдем число благоприятствующих возможных исходов. Два белых шара можно вынуть способом, два разных цветных шара способами. Тогда общее число благоприятствующих исходов, в соответствии с принципом сложения, равно m = m1+m2 = 16. Таким образом,



Задача 4. Наудачу взятый телефонный номер состоит из 5 цифр. Какова вероятность, что в нем все цифры разные?

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

Номера, у которых все цифры разные, - это размещения без повторений

Таким образом, искомая вероятность (при сделанном предположении) будет равна

Задача 5. Зенитная батарея, состоящая из 3 орудий, производит залп по группе, состоящей из 4 самолётов. Каждое из орудий выбирает себе цель наудачу независимо от остальных. Найти вероятность того, что все орудия выстрелят по разным самолётам.

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

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

Задача 6. Зенитная батарея, состоящая из 3 орудий, производит залп по группе, состоящей из 4 самолётов. Каждое из орудий выбирает себе цель наудачу независимо от остальных. Найти вероятность того, что все орудия выстрелят по одному и тому же самолёту.

Решение: Если все орудия выстрелят по одному и тому же самолету, то число благоприятствующих исходов будет равно m=4. Таким образом,

Задача 7. Собрание, на котором присутствуют 20 человек, в том числе 8 женщин, выбирают делегацию из 5 человек. Найти вероятность того, что в делегацию войдут 3 женщины, считая, что каждый из присутствующих может быть избран с одинаковой вероятностью?

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

А число благоприятных исходов будет равно:



.

Таким образом,

Задача 8. Для уменьшения общего количества игр 10 команд случайным образом разбиты на две равные подгруппы. Определить вероятность того, что две наиболее сильные команды окажутся в одной подгруппе.

Решение: В данной задаче порядок неважен, т.е. не принимается во внимание порядок отбора команд в группу. Следовательно, в данной задаче мы имеем дело с сочетаниями. Для того чтобы разбить 10 на две равные подгруппы достаточно выбрать 5 команд, которые и образуют одну из подгрупп, тогда остальные образуют другую подгруппу. Таким образом, общее число разбиений команд на две равные подгруппы будет равно. Для того, чтобы разбить команды на две подгруппы с указанными условиями, можно поступить следующим образом. Либо выбрать две наиболее сильные команды (это можно сделать способами ), а затем добавить к ним 3 оставшиеся команды из оставшихся 8 не самых сильных команд (способов). Либо выбрать сразу 5 команд из 8 не самых сильных команд ( способов). Тогда число благоприятствующих исходов будет равно . Таким образом,

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

Решение: Книги, которые должны стоять рядом, считаем за одну книгу. Тогда нужно расставить 5 книг по шести местам. Применяя формулу перестановок, получаем: P5 = 5!. Мы учли перестановки шести книг, не учитывая порядок внутри тех книг, которые мы посчитали за одну. А так как две книги по двум местам можно разместить только двумя способами (P2), то получаем следующее произведение: m = P2 * P5 = 2 * 5!. Это количество благоприятных исходов. Общее число исходов будет равно P6 = 6!. Тогда

Задача 10. 10 вариантов контрольной работы распределены среди 6 студентов. Найти вероятность того, что варианты с номерами 1, 2 и 3 не будут использованы.

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

Задача 11. В первой урне находятся 5 белых и 3 черных шара, во второй - 4 белых и 6 черных шаров. Из каждой урны случайным образом вынули по одному шару. Найти вероятность того, что оба шара будут разного цвета.

Решение: Оба шара будут разного цвета, если: 1) мы одновременно вынем белый из первой урны (это можно сделать способами) и чёрный из второй ( способов); либо 2) вынем чёрный из первой ( способов) и белый из второй (). Таким образом . Общее число исходов будет равно: , т.е. мы вынем один шар из первой урны и один из второй. Тогда

Задача 12. В урне 4 белых и 5 чёрных шаров. Из урны взяли три шара. Какова вероятность того, что шары будут одного цвета?

Решение:

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

Решение: Представим себе, что на 9 одинаковых карточках написаны цифры 1, 2, 3, 4, 5, 6, 7, 8, 9 и эти карточки помещены в урну. Выбор наудачу трехзначного числа равносилен последовательному извлечению с возвращением из урны 3 карточек и записыванием цифр в порядке их появления. Следовательно, число всех элементарных исходов опыта равно (по формуле размещений с повторениями) . Количество благоприятных случаев для интересующего нас события подсчитываем так: две различные цифры х и у можно выбрать  способами; если х и у выбраны, то из них можно составить , т.е. 3 трехзначных числа, в которых х встречается два раза, а у - один раз; столько же будет чисел, в которых у встречается дважды, х - один раз. Таким образом, число благоприятных случаев равно . Искомая вероятность равна:

Задача 14. В партии из N деталей имеется n бракованных. Какова вероятность того, что среди наудачу отобранных k деталей окажется s бракованных?

Решение: Количество всех элементарных исходов равно . Для подсчета числа благоприятных случаев рассуждаем так: из n бракованных можно выбрать s деталей  способами, а из N - n небракованных можно выбрать k - s небракованных деталей  способами; по правилу произведения число благоприятных случаев равно . Искомая вероятность равна:

Задача 15. На 10 карточках написаны буквы: «а», «а», «а», «м», «м», «т», «т», «е», «и», «к». После тщательного перемешивания карточки раскладывают в ряд. Какова вероятность того, что получится слово «математика»?

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

Всего возможных исходов:

Всего благоприятных исходов:

 - слово "математика". Тогда искомая вероятность равна:

Задача 16. Какова вероятность того, что в компании из r человек хотя бы у двоих совпадут дни рождения? (Для простоты предполагается, что 29 февраля не является днём рождения)

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

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

Тогда вероятность того, что дни рожденья совпадут хотя бы у двух человек, равна:

Задача 17. В бригаде 4 женщины и 3 мужчин. Среди членов бригады разыгрываются 4 билета в театр. Какова вероятность того, что среди обладателей билетов окажется 2 женщины и 2 мужчин?

Решение: Из 7 членов бригады 4 человека можно выбрать способами, следовательно, число всех элементарных исходов испытания равно 35. Далее, из 4 женщин можно выбрать 2 женщин способами, а из 3 мужчин можно выбрать 2 мужчин способами. Тогда число благоприятных случаев будет равно 6*3=18. Таким образом,

Задача 18. Набирая номер телефона, абонент забыл одну цифру и набрал её наудачу. Найти вероятность того, что набрана нужная цифра.

Решение: Абонент мог набрать любую из 10 цифр, поэтому общее число возможных исходов равно 10. Благоприятствующим является лишь один исход, т.к. нужная цифра лишь одна. Тогда искомая вероятность равна:

Задача 19. Набирая номер телефона, абонент забыл две последние цифры, и помня лишь, что эти цифры различны, набрал их наудачу. Найти вероятность того, что набраны нужные цифры.

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



Литература

1. Гмурман Е.В. "Теория вероятностей и математическая статистика", Москва, "Высшая школа", 2003 г.

2. Гмурман Е.В. "Руководство к решению задач по теории вероятностей и математической статистике", Москва "Высшая школа", 2004 г.

3. Андрухаев Х.М. «Сборник задач по теории вероятностей», Москва, «Просвещение», 1985 г.

Размещено на Allbest.ru