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

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

Введение

История возникновения Формулы комбинаторики Практика Литература

Комбинаторика (комбинаторный анализ) — раздел математики, который исследует в основном различные способы выборки заданного числа 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 г.