Без повторения ( )

Упорядоченные наборы элементов из n-данных

Пример. , = 2. Тогда упорядоченные наборы без повторения:

.

Теорема. Число упорядоченных наборов элементов из n данных есть

где есть произведение. . Обозначают это число .

Доказательство. Пусть есть искомое число упорядоченных наборов элементов из n данных без повторения. Тогда разобьем все эти наборы на n групп, в i-тую группу войдут наборы, начинающиеся на . Тогда число элементов в i- ой группе равно числу упорядоченных наборов - ого элемента из ( — 1)-ого данного, так как элементы в наборе не повторяются, т.е. числу . Поэтому

т.к.

В нашем примере группы выглядят так:

Упорядоченный набор n элементов из n данных без повторения называют перестановкой: 1,2,3. Перестановки

{123} {132} {213} {231} {312} {321}.

Число перестановок из n- элементов есть (0! считаем равным 1).

Пример 1. Пусть (V, Р) — ориентированный граф. Полным

ориентированным графом называют граф, в котором присутствуют все

ориентиро­ванные ребра, кроме петель.

Тогда ориентированные ребра такого графа есть упорядоченные

пары из множества без повторений, и их число по доказанной теореме есть

Пример 2. Имеется n мест и человек. Скольким числом способов можно рассадить этих человек на местах.

Решение. 1. . Занумеруем места числами 1,2,..., . Тогда каждому упорядоченному набору элементов из соответствует способ посадки. Поэтому искомое число есть

.

2. Занумеруем людей 1,2,..,. . Тогда каждому упорядо­ченному выбору элементов из данных соответствует способ посадки и наоборот. Поэтому искомое число есть

Дата добавления: 2017-01-13