Элементы комбинаторики.

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

Опр. Функция , для которой при всех целых неотрицательных , называется - факториалом. (обозначается !)

Для любого натурального имеем:

(1)

По общей договоренности

Пример 1.

,

,

.

Пусть дано множество, состоящее из различных элементов.

Сочетанием из элементов по элементов () называется любое подмножество, которое содержит элементов данного множества.

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

Число сочетаний из элементов по элементов обозначается символом и вычисляется по формуле:

(5)

Имеют место формулы:

, (),

,

, ().

Пример 2.

Составить различные сочетания по 2 из элементов множества и подсчитать их число.

Решение

Из этих трех чисел можно составить следующие сочетания по два элемента: (1,2), (1,3), (2,3). Их число:

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

Размещение – это комбинации, состоящие из элементов, которые отличаются друг от друга либо составом элементов, либо порядком их расположения.

Число размещений из элементов по обозначается символом и может быть вычислено по формуле:

(2)

или

(3)

Пример 3

Составить различные размещения по 2 из элементов множества и подсчитать их число.

Решение.

Из трех элементов можно составить следующие размещения по 2 элемента: (1,2), (2,1), (1,3), (3,1), (2,3), (3,2). По формуле (3) их число:

Перестановкой из элементов называется размещение из элементов по элементов.

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

Число перестановок вычисляется по формуле:

(4)

Пример 4.

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

Решение.

Из элементов данного множества можно составить такие перестановки: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1). Их число по формуле (4):

Пример 5

Сколькими способами можно расставить на полке 4 вазочки различного цвета?

Решение.

Число способов равно числу перестановок из 4 элементов:

Дата добавления: 2015-07-14