Элементы комбинаторики. Изучение курса должно начинаться с изучения основ комбинаторики, причем параллельно должна изучаться теория вероятностей

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

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

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

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

Размещением из n элементов множества Х по k элементам назовем любой упорядоченный набор () элементов множества Х.

Если выбор элементов множества Y из Х происходит с возвращением, т.е. каждый элемент множества Х может быть выбран несколько раз, то число размещений из n по k находится по формуле (размещения с повторениями).

Если же выбор делается без возвращения, т.е. каждый элемент множества Х можно выбирать только один раз, то количество размещений из n по k обозначается и определяется равенством
(размещения без повторений).

Частный случай размещения при n=k называется перестановкой из n элементов. Число всех перестановок из n элементов равно

Пусть теперь из множества Х выбирается неупорядоченное подмножество Y (порядок элементов в подмножестве не имеет значения). Сочетаниями из n элементов по k называются подмножества из k элементов, отличающиеся друг от друга хотя бы одним элементом. Общее число всех сочетаний из n по k обозначается и равно

Справедливы равенства: , ,

При решении задач комбинаторики используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами.

Правило произведения. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана m*n способами.

Date: 2015-06-08; view: 728; Нарушение авторских прав