Элементы комбинаторики. Алгоритм решения задач

Алгоритм решения задач

1) Определить общее число всех равновозможных несовместных элементарных исходов .

2) Определить число исходов , благоприятных появлению события А.

3) Вычислить вероятность события А.

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

Определение 1. Пусть задана совокупность из элементов. Из этой совокупности определённым образом выбрали элементов. В этом случае говорят, что задана выборка длиной в элементов из элементов.

Выборки могут формироваться по-разному. Различия обусловлены следующими причинами:

1) допускается ли в выборках повторение элементов;

2) учитывается ли в выборке порядок следования элементов.

Определение 2. Перестановками без повторений называются выборки из элементов длиной в элементов () без повторений с учётом порядка.

Формула для подсчета: .

Определение 3. Размещениями без повторений называются выборки из элементов длиной в элементов () без повторений с учётом порядка.

Формула для подсчета: .

Определение 4. Сочетаниями без повторений называются выборки из элементов длиной в элементов () без повторений и без учёта порядка.

Формула для подсчета: .

Определение 5. Пусть имеется элементов, из которых элементов принадлежит первому типу, – второму, и т. д., – -му типу, при этом , а элементы одного типа неразличимы между собой. Выборки из этих элементов длиной в элементов с повторениями и с учётом порядка называются перестановками с повторениями .

Формула для подсчета: .

Определение 6. Выборки из элементов длиной в элементов с повторениями и с учётом порядка называются размещениями с повторениями . Здесь возможно, что .

Формула для подсчета: .

Определение 7. Выборки из элементов длиной в элементов с повторениями и без учёта порядка называются сочетаниями с повторениями . Здесь возможно, что .

Формула для подсчета: .

Важную роль в комбинаторике играют правила сложения и умножения.

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

Правило сложения. Пусть необходимо выполнить действий, причем никакие два из которых не могут производиться одновременно (действия попарно несовместны). Если первое действие можно выполнить способами, второе действие можно выполнить способами и т. д., -е действие можно выполнить способами, то хотя бы одно действие можно выполнить способами.

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

Дата добавления: 2014-01-14