Перестановки

Принцип сложения.

Если действие А можно осуществить n₁ способами, а действие В можно осуществить n₂ способами, то осуществить действия А или В можно n₁+n₂ способами.

По решению слову ИЛИ соответствует знак сложения.

Пример: В ящике 6 белых, 3 черных и 7 красных шаров. Сколькими способами можно вынуть один шар?

n=6+3+7=16 по принципу сложения комбинаторики.

Пусть дано множество, состоящее из n-элементов. Множества, состоящие из этих же элементов, но отличающиеся порядком вхождения этих элементов, называется перестановками данного множества.

Рассмотрим множество из трех элементов {1;2;3}. Составим все перестановки данного множества: {1;3;2}{2;1;3}{2;3;1}{3;1;2}{3;2;1}, само множество тоже является перестановкой.

В общем случае число перестановок множества, состоящего из n-элементов, обозначается символом P_n. Число перестановок не зависит от характера элементов, а зависит от их количества.

Составить перестановки множества означает, что нужно произвести действие, состоящее из n-этапов, то есть один за другим в некотором порядке выписать все n-элементы множества.

По принципу произведения комбинаторики:
P_n =n×(n-1) × (n-2)…×1=n! ÞP_n=n!

Пример: Сколькими способами можно расставить 6 книг на книжной полке?

Пример: Сколькими способами можно рассадить четырех гостей за круглым столом?

4. Размещения.

Пусть дано множество, состоящее из n -элементов. Выберем из него упорядоченные подмножества, состоящее из m элементов. Такие подмножества называются размещениями данного множества из n по m.

Пример: Возьмем множество, состоящее из 3^х элементов. Составим все размещения данного множества по два элемента в каждом.

{1,2,3}: {1;2}{1;3}{3;1}{2;3}{3;2}, получилось шесть размещений по два элемента в каждом.

Число размещений из n по m обозначается , где n – число элементов множества (объем совокупности), m - где n – число элементов подмножества (объем выборки).

Составить размещение из n -элементов по m, значит произвести действия, состоящие из m этапов.

=n(n-1)…(n–m+1)=

- число размещений из n по m.

Пример: Сколькими способами можно выбрать из 20 студентов 3^х дежурных так чтобы один из студентов был старшим?

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