Теория вероятностей. 
Теория вероятностей и математическая статистика

КОМБИНАТОРИКА

В результате освоения материала данной главы студент должен: знать

• • основные правила комбинаторики;
• • основные понятия комбинаторики; уметь
• • классифицировать выбор элементов с повторениями и без повторений (размещения, сочетания, перестановки);
• • решать задачи, связанные с числом возможных расположений или с числом возможных актов совершения действий;

владеть

• • методами комбинаторного анализа;
• • навыками решения задач, связанных с выбором и расположением элементов.

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

Комбинаторика — один из разделов дискретной математики, используемый в теории вероятностей и математической статистике. Исследователю часто приходится иметь дело с задачами, в которых требуется подсчитать «число возможных расположений» элементов, «число возможных актов» совершения действий. В дальнейшем словосочетания, взятые в кавычки, будем заменять на более простое словосочетание «число способов». Например: сколькими способами можно расположить на полке пять книг? Или: 10 человек претендуют на занятие трех должностей в корпорации; сколькими способами сотрудники могут быть назначены на эти вакансии?

В основе решения комбинаторных задач лежат два правила.

Правило умножения. Пусть некоторый выбор А можно осуществить п способами, а затем другой выбор В можно совершить т способами, тогда выбор АВ в указанном порядке можно сделать п? т способами.

Пример 1.1. Замок открывается если введен пароль из трех различных цифр. Сколько таких паролей существует?

Решение. На первом месте может находиться любая из 10 цифр, на втором месте — любая из 9 цифр, на третьем месте — любая из 8 цифр. В соответствии с правилом умножения число паролей будет равно 10 • 9 • 8 = 720.

Сформулируем правило умножения в комбинаторике в общем виде. Пусть требуется выполнить последовательно к действий. Если первое действие можно выполнить п₁ способами, второе — п₂ способами и т. д., то все к действий вместе в указанном порядке будут выполнены п_г? п₂‘ … • п_к способами.

Пример 1.2. Даны цифры 0,1, 2, 3, 4. Из них составляются пятизначные нечетные числа. Сколько различных чисел можно составить?

Решение. Любая из цифр 1, 2, 3, 4 может стоять на первом месте. Любая из цифр нечетны 1,3 — на последнем в силу нечетности числа. Тогда общее количество чисел равно 4 • 5 • 5 • 5 • 2 = 1000.

Правило сложения. Пусть можно сделать выбор, А одного элемента из первой группы, содержащей п элементов, и выбор В одного элемента из второй группы с т элементами. Тогда выбор А + В одного элемента из первой или второй группы будет выполнен п + т способами.

Пример 1.3. В корзине 20 белых, 30 желтых и 10 красных роз. Сколько существует способов выбрать белую или красную розы?

Решение. Белая роза может быть извлечена п_х = 20 способами, красная — п₂ = = 10 способами. По правилу сложения одна из двух: белая или красная роза — будет извлечена Щ + п_г = 20 + 10 = 30 способами.

Теперь рассмотрим различные подходы к выбору элементов.