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

контрольная работа

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

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

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

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов 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 элементов, которые можно составить из данных трех различных элементов, причем указанные элементы в каждой группе могут повторяться, а сами группы отличаются друг от друга хотя бы одним элементом. Это задача на отыскание числа сочетаний с повторениями из трех элементов по девять. Следовательно,

Делись добром ;)