Сделай Сам Свою Работу на 5

Комбинации с повторениями





ЛЕКЦИЯ 2

Размещения и перестановки. Сочетания. Комбинации с повторениями. Комбинаторный способ вычисления вероятностей по классической схеме. Геометрическое определение вероятности. Статистическое определение вероятности.

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

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

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

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

. (1.1)

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

Пример 1.7. В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить 4 фотографии. Сколькими способами это можно сделать, если ни одна страница газеты не должна содержать более одной фотографии?



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

.

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

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

Отметим, что перестановки состоят из одних и тех же элементов, но отличаются между собой порядком. Число перестановок n различных элементов обозначают символом Pn и равно

(1.2)

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



Решение. Будем считать выделенные книги за одну книгу. Тогда уже для шести книг существует P6=6!=720 перестановок. Однако четыре определенные книги можно переставить между собой P4=4!=24 способами. По принципу умножения имеем

P6P4 = 720×24 = 17280.

Сочетания

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

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

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

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



. (1.3)

Отсюда получаем

. (1.4)

Заметим, что Сn0=Cnn=1, Cn1=n.

Пример 1.9. Сколькими способами можно составить комиссию в составе из трех человек из имеющихся 9 человек, 4 женщин и 5 мужчин, если: а) не важен пол членов комиссии; б) комиссия должна состоять из двух женщин и одного мужчины.

Решение. а) Из смысла задачи следует, что порядок выбора членов комиссии не играет роли. Здесь важен только состав. Тогда выбрать комиссию из трех человек из 9 имеющихся можно

способами.

б) Двух женщин из 4 имеющихся можно выбрать С42 способами, а одного мужчину из 5 можно С51 способами. тогда общее количество способов выбора комиссии, в соответствии с принципом умножения, можно

способами.

Отметим, что при использовании сочетаний могут быть полезны следующие свойства:

10. (свойство симметрии),

20. ,

30. (свойство Паскаля).

 

Комбинации с повторениями

Пусть опыт состоит в выборе с возвращением k элементов из некоторого множества, состоящего из n элементов, но без последующего упорядочения. Различными исходами такого опыта будут все возможные наборы, отличающиеся только составом. При этом отдельные наборы могут содержать повторяющиеся элементы. Например, при k=4 наборы {1,1,2,1} и {2,1,1,1} неразличимы для данного эксперимента. Получающиеся в результате данного опыта комбинации называются сочетаниями с повторениями, а их общее число определяется формулой

(1.5)

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

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

Пусть выбор k элементов из некоторого множества, состоящего из n элементов, производится с возвращением и с упорядочением их в последовательную цепочку. Различными исходами такого выбора будут всевозможные наборы (вообще говоря, с повторениями) отличающиеся либо составом элементов, либо порядком их следования. Например, множества {1,1,2,1}, {2,1,1,1}, {1,1,3,1} являются различными комбинациями. Получаемые в результате комбинации называются размещениями с повторениями, а их общее число определяется формулой:

(1.6)

Данная формула легко получается из принципа умножения.

Пример 1.11. В лифт восьмиэтажного дома вошли 5 пассажиров. Сколькими способами могут выйти пассажиры на каждом этаже, начиная со второго?

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

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

Число перестановок из n различных элементов с повторениями, которые можно сделать из k1 элементов первого типа, k2 элементов второго типа, … , kn элементов n-го типа, находится по формуле

(1.7)

Пример 1.12. Сколькими способами можно нанизать на нить 4 зеленых, 5 синих и 6 красных бус?

Решение. Речь идет об отыскании числа перестановок с повторениями, которые можно сделать из k1=4 элементов первого типа (зеленых бус), k2=5 элементов второго типа (синих бус) и k3=6 элементов третьего типа (красных бус). По формуле (1.7) получаем

.

1.7. Комбинаторный способ вычисления
вероятностей по классической схеме

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

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

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

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

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

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

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

Таким образом, искомая вероятность равна

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.