Элементы комбинаторики
Комбинаторикой называется область математики, в которой изучаются вопросы о том, сколько различных комбинаций (выборок), подчиненных тем или иным условиям, можно составить из элементов, принадлежащих заданному конечному множеству. Иногда комбинаторику рассматривают как введение в теорию вероятностей, так как методы комбинаторики помогают осуществить подсчет числа возможных исходов и числа благоприятных исходов в разных конкретных случаях в теории вероятностей.
Рассматрим следующие виды выборок – перестановки, размещения, сочетания.
Определение. Размещениями из n различных элементов по m элементов называются такие выборки, которые, имея по m элементов, выбранных из числа данных n элементов, отличаются одна от другой либо составом элементов, либо порядком их следования.
Обозначение. 
– число размещений из n элементов по m элементов. 
Без доказательства примем формулу:
.
Определение 2. Перестановками из n различных элементов называются размещения из n элементов по n элементов.
Обозначение. 
– число перестановок из n элементов.
, где 
.
Например, 
.
Запомните: 
.
Определение 3. Сочетаниями из n различных элементов по m элементов называются такие выборки, которые, имея по m элементов, выбранных из числа данных n элементов, отличаются одна от другой хотя бы одним элементом.
Обозначение. 
– число сочетаний из n элементов по m элементов.
.
Замечание. При решении комбинаторных задач необходимо обращать внимание на несколько моментов, которые не всегда явно оговариваются в условии:
|
|
|
1) при составлении выборок – упорядочиваем ли мы обьекты или нет, т. е. различаем ли мы места, на которые ставим обьекты;
2) при распределении объектов по выборкам – считаем ли мы эти выборки одинаковыми (равноценными) или нет.
Задача 1. В расписании занятий некоторого класса содержится 12 учебных предметов и требуется включить 5 разных предметов в расписание одного учебного дня. Сколькими способами может быть составлено расписание занятий на один учебный день?
Решение. Расписание на каждый день может отличаться либо предметами, либо порядком следования этих предметов, поэтому выборки, составленные из 12 элементов по 5 элементов – размещения.
Расписание может быть составлено 95040 способами.
Задача 2. Сколько различных пятизначных чисел можно составить из цифр 1,2,3,4,5 так, чтобы ни одна цифра не повторялась дважды в одном числе?
Решение. Требуется подсчитать число выборок, состоящих из всех предложенных пяти цифр, отличаются выборки только порядком следования элементов (речь идет о перестановках из 5 элементов).
Р5= 5!=120.
120 различных пятизначных чисел можно составить из предложенных цифр.
|
|
|
Задача 3. В группе 20 студентов. Сколькими способами можно выбрать из них трех человек для совместной подготовки реферата?
Решение. Необходимо выбрать 3 из 20, причем важен только состав выборки, порядок следования объектов в выборке роли не играет. Искомое число выборок (сочетаний) равно
Замечание. Все формулы, предложенные в §1 применимы в том случае, когда ведется подсчет выборок из множества, все элементы которого различны. Если некоторые элементы множества (выборки) повторяются, то извлекаемые выборки называются выборками с повторениями. Число выборок с повторениями находят по формулам:
– число размещений с повторениями (из n элементов по m элементов с повторениями, т.е. в одном размещении некоторый элемент может повториться сколько угодно раз).
– число перестановок из n элементов с повторениями, где первый элемент повторяется 
раз, второй элемент повторяется 
раз, …, k –ый элемент повторяется 
раз, причем 
.
– число сочетаний из n элементов по m с повторениями.
Основные понятия теории вероятностей
Дата добавления: 2015-12-20; просмотров: 19; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!