Понятие комбинаторики. Основные правила комбинаторики
Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов заданного конечного множества.
Использование формул комбинаторики значительно облегчает проведение расчетов в теории вероятностей. 2. Основные правила комбинаторики Пусть А1,А2,…,Аk - это элементы заданного конечного множества. Правило суммы: Если элемент A1 можно выбрать n1 способами, A2 можно выбрать n2 способами, An можно выбрать nk способами отличными от всех предыдущих, то выбор 1-го из элементов А1,А2,…,Аk может быть осуществлен n1+n2+…+nk способами. Пример 1. В коробке 20 шаров, причем 5 из них красные, 6 синие, а остальные зеленые. Сколько существует способов извлечь из ящика 1 шар или красного или синего цвета. Решение: n1+n2=5+6=11. Правило произведения: Пусть элемент A1 можно выбрать n1 способами, после каждого такого выбора элемент A2 можно выбрать n2 способами, после (k-1) - го выбора элемент Anможно выбрать nk способами, тогда выбор всех элементов в указанном порядке может быть осуществлен n1•n2•…•nk способами. Пример 2. В конкурсе участвуют 10 человек. Для определения порядка выступления конкурсантов проводят жеребьевку. Сколькими способами можно выбрать трех человек для выступления под номерами 1,2,3. Решение: n1•n2•n3 = 10•9•8=720
Основные комбинаторные соединения
Пусть дано множество из n элементов. Из этого множества могут быть составлены подмножества (комбинации) по m элементов трех основных видов: 1. перестановки; 2. размещения; 3. сочетания. Перестановки (m=n) О. 1. Перестановками без повторений называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их следования. Число всевозможных перестановок без повторений Pn=n! Пример 3. Сколько пятизначных чисел можно составить из цифр: числа 12345. Решение: О. 2. Перестановками с повторениями называются перестановки, в которых из общего числа n элементов имеется только k различных элементов, причем 1-й элемент повторяется n1 раз, 2-й элемент повторяется n2 раз, k-й элемент повторяется nk раз ().
Число всевозможных перестановок с повторениями
Пример 4. Сколько пятизначных чисел можно составить из цифр числа 12213. Решение: . Размещения и сочетания О. 3. Размещениями без повторений называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо порядком следования. Число всевозможных размещений без повторений
Пример 5. Десять студентов участвуют в конкурсе на назначение трех стипендий: президентской, губернаторской и потанинской. Причем, один человек может получить только одну стипендию. Сколько существует вариантов распределения стипендий. Решение:
О. 4. Размещениями с повторениями называются размещения, некоторые элементы (или все) которых могут оказаться одинаковыми. Число всевозможных размещений с повторениями
Пример 6. Десять студентов участвуют в конкурсе на назначение трех стипендий: президентской, губернаторской и потанинской. Причем, так как конкурс серьезный и победить в нем могут только настоящие вундеркинды, то для большего поощрения решено, что один человек может получить несколько стипендий одновременно. Сколько существует вариантов распределения стипендий. Решение: . O. 5. Сочетаниями без повторений называются комбинации, составленные из n различных элементов по m элементов, которые отличаются только составом. Число сочетаний без повторении
Пример 7. Десять студентов участвуют в конкурсе на назначение трех губернаторских стипендий. Причем один человек может получить только одну стипендию. Сколько существует вариантов распределения стипендий. Решение: . О. 6. Сочетаниями с повторениями называются сочетания некоторые элементы (или все) которых могут оказаться одинаковыми. Число всевозможных сочетаний с повторениями Пример 8. Десять студентов участвуют в конкурсе на назначение трех губернаторских стипендий. Причем, так как конкурс серьезный и победить в нем могут только настоящие вундеркинды, то для большего поощрения решено, что один человек может получить несколько стипендий одновременно. Сколько существует вариантов распределения стипендий. Решение: . Свойства сочетаний 1. ; 2. ; 3. ; 4. . Число размещений, перестановок и сочетаний связаны между собой равенством .
