5. Понятие комбинаторики. Основные правила комбинаторики

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

Использование формул комбинаторики значительно облегчает проведение расчетов в теории вероятностей. 2. Основные правила комбинаторики Пусть А₁,А₂,…,А_k - это элементы заданного конечного множества. Правило суммы: Если элемент A₁ можно выбрать n₁ способами, A₂ можно выбрать n₂ способами, A_n можно выбрать n_k способами отличными от всех предыдущих, то выбор 1–го из элементов А1,А2,…,Аk может быть осуществлен n₁+n₂+…+n_k способами. Пример 1. В коробке 20 шаров, причем 5 из них красные, 6 синие, а остальные зеленые. Сколько существует способов извлечь из ящика 1 шар или красного или синего цвета. Решение: n₁+n₂=5+6=11. Правило произведения: Пусть элемент A₁ можно выбрать n₁ способами, после каждого такого выбора элемент A₂ можно выбрать n₂ способами, после (k-1) - го выбора элемент A_nможно выбрать n_k способами, тогда выбор всех элементов в указанном порядке может быть осуществлен n₁∙n₂∙…∙n_k способами. Пример 2. В конкурсе участвуют 10 человек. Для определения порядка выступления конкурсантов проводят жеребьевку. Сколькими способами можно выбрать трех человек для выступления под номерами 1,2,3. Решение: n₁∙n₂∙n₃ = 10∙9∙8=720

6. Основные комбинаторные соединения

Пусть дано множество из n элементов. Из этого множества могут быть составлены подмножества (комбинации) по m элементов трех основных видов: 1. перестановки; 2. размещения; 3. сочетания. Перестановки (m=n) О. 1. Перестановками без повторений называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их следования. Число всевозможных перестановок без повторений P_n=n! Пример 3. Сколько пятизначных чисел можно составить из цифр: числа 12345. Решение: О. 2. Перестановками с повторениями называются перестановки, в которых из общего числа n элементов имеется только k различных элементов, причем 1-й элемент повторяется n₁ раз, 2-й элемент повторяется n₂ раз, k-й элемент повторяется n_k раз ().

Число всевозможных перестановок с повторениями

Пример 4. Сколько пятизначных чисел можно составить из цифр числа 12213. Решение: . Размещения и сочетания О. 3. Размещениями без повторений называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо порядком следования. Число всевозможных размещений без повторений

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

О. 4. Размещениями с повторениями называются размещения, некоторые элементы (или все) которых могут оказаться одинаковыми. Число всевозможных размещений с повторениями

Пример 6. Десять студентов участвуют в конкурсе на назначение трех стипендий: президентской, губернаторской и потанинской. Причем, так как конкурс серьезный и победить в нем могут только настоящие вундеркинды, то для большего поощрения решено, что один человек может получить несколько стипендий одновременно. Сколько существует вариантов распределения стипендий. Решение: . O. 5. Сочетаниями без повторений называются комбинации, составленные из n различных элементов по m элементов, которые отличаются только составом. Число сочетаний без повторении

Пример 7. Десять студентов участвуют в конкурсе на назначение трех губернаторских стипендий. Причем один человек может получить только одну стипендию. Сколько существует вариантов распределения стипендий. Решение: . О. 6. Сочетаниями с повторениями называются сочетания некоторые элементы (или все) которых могут оказаться одинаковыми. Число всевозможных сочетаний с повторениями Пример 8. Десять студентов участвуют в конкурсе на назначение трех губернаторских стипендий. Причем, так как конкурс серьезный и победить в нем могут только настоящие вундеркинды, то для большего поощрения решено, что один человек может получить несколько стипендий одновременно. Сколько существует вариантов распределения стипендий. Решение: . Свойства сочетаний 1. ; 2. ; 3. ; 4. . Число размещений, перестановок и сочетаний связаны между собой равенством .