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

Упорядоченные наборы с повторением и без повторений.

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

Пример. Упорядоченные наборы 3-х элементов множества {1,2} — это упорядоченные множества

{111} {112} {121} {122} {211} {212} {221} {222}. Упорядоченные наборы называют также словами.

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

Доказательство. Пусть F есть искомое число упорядоченных набо­ров с повторениями элементов из n данных. Тогда разобьем все упорядоченные наборы на n групп, где в i-тую группу войдут те на­боры, которые начинаются на -ый элемент. В нашем примере, где n= 2, = 3 группы выглядят так:

1: 111, 112, 121, 122;

2: 211, 212, 221, 222.

Тогда число наборов в каждой группе равно числу

упорядоченных наборов -1 элементов из n данных, т. е. F , а число групп есть n. Поэтому

Пример 1. Дан алфавит из n букв . Найти число различных слов длины в этом алфавите.

Решение. Нетрудно видеть, что это число равно числу упорядоченных

наборов элементов из n данных, т. е .

Пример 2. Дано множество из n элементов . Найти число различных подмножеств этого множества.

Решение. Для каждого подмножества введем характери­стический вектор длины n, компонента i которого равна 1, если входит в рассматриваемое подмножество, и 0 в про­тивном случае. Тогда характеристический вектор (слово в {0,1} длины n) однозначно определяет подмножество множества . Поэтому число подмножеств равно .

Пример 3. Пусть дано V — множество и множество Р некоторых упорядоченных пар . Тогда (V,P) называют ориентированным графом, V — множество вершин, Р — ориентированные ребра. Ребро называют петлей. Полным ориентированным графом с петлями на множе­стве V называют граф со всеми ориентированными ребрами. Тогда число ребер в полном ориентированном графе равно .

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