Размещения и перестановки без повторений




ПРИЛОЖЕНИЕ

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

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

Чтобы проводить комбинаторные рассуждения необходимо знать основные правила, схемы и формулы комбинаторики.

Пусть X – конечное множество, а – количество элементов в нем. Будем в этом случае говорить, что объект x из X может быть выбран n способами.

«Правило суммы»

Пусть , , …, – попарно непересекающиеся множества, т.е. при . Тогда, очевидно, выполняется равенство

.

Этот факт в комбинаторике называется «правилом суммы».

«Правило произведения»

«Если объект x может быть выбран m способами и после каждого из таких выборов объект y в свою очередь может быть выбран n способами, то выбор упорядоченной пары может быть осуществлен mn способами».

Доказательство. Воспользуемся правилом суммы. Пусть – множество элементов, из которых выбирается объект x. Для каждого рассмотрим множества , в которых первая компонента совпадает с . Множества попарно не пересекаются и . Тогда множество всех пар есть и (по правилу суммы)

¢

Замечание. В общем случае правило произведения формулируется следующим образом: «Если объект может быть выбран способами, после чего объект может быть выбран способами и для любого i, где , после выбора объектов объект может быть выбран способами, то выбор упорядоченной последовательности может быть осуществлен способами».

Доказательство проводится методом математической индукции.

Размещения и сочетания

Определение 1. Набор элементов , ,…, из множества называется выборкой объема r из n элементов (или, иначе, - выборкой).

Выборка называется упорядоченной, если порядок следования элементов в ней задан.

Замечание. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными.

Если порядок следования элементов не является существенным, то выборка называется неупорядоченной.

В выборках могут допускаться или не допускаться повторения элементов.

Определение 2. Упорядоченная -выборка, в которой элементы могут повторяться, называется - размещением с повторениями.

Определение 3. Упорядоченная -выборка, элементы которой попарно различны, называется - размещением без повторений (или, иначе, - размещением).

Замечание. -размещения без повторений называются перестановками множества X.

Определение 4. Неупорядоченная -выборка, в которой элементы могут повторяться, называется - сочетанием с повторениями.

Определение 5. Неупорядоченная -выборка элементы, которой попарно различны, называется - сочетанием без повторений (или, иначе, - сочетанием).

Замечание. Любое -сочетание можно рассматривать, как r -элементное подмножество n -элементного множества.

Пример 1. Пусть , т.е. . Найти какое-либо -сочетание без повторений.

Ответ: например, .

Пример 2. Пусть . Найти все -размещения и -сочетания (с повторениями и без повторений).

Ответ:

а) – множество всех -размещений с повторениями (9 упорядоченных пар);

б) – множество всех -размещений без повторений (6 упорядоченных пар);

в) – множество всех -сочетаний с повторениями (6 неупорядоченных пар);

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

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

Теорема 1. .

Доказательство. Каждое -размещение с повторениями является упорядоченной последовательностью длины r, причем каждый элемент этой последовательности может быть выбран n способами. По правилу произведения получаем

¢

Теорема 2. .

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

¢

Следствие.

Теорема 3. .

Доказательство. Каждое -сочетание без повторений можно упорядочить r! способами. Объединение получаемых таким образом попарно непересекающихся множеств -размещений без повторений для всевозможных -сочетаний без повторений, даст все -размещения без повторений. Тогда (здесь суммирование производится по всевозможным -сочетаниям без повторений), т.е. . Отсюда

¢

Теорема 4. .

Доказательство. Каждому -сочетанию В с повторениями, составленного из элементов множества поставим в соответствие такой вектор длины (), состоящий из r единиц и ()нулей, что число единиц находящихся между -м и i -м нулями, где , будет равно числу элементов , входящих в сочетание В. Число единиц, стоящих перед первым нулем равно числу элементов , а число единиц, стоящих после -го нуля равно числу элементов , входящих в сочетание В.

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

Количество векторов равно числу r -элементных подмножеств (номеров единичных компонент в этих векторах) ()-элементного множества (всех номеров компонент в этих векторах), т.е. числу -сочетаний без повторений:

¢

Пример 3. Пусть , , , -сочетание с повторениями, тогда .

Пример 4. Пусть , , , , тогда .

 

Задачи

 

Правила комбинаторики

1. В меню столовой имеется 7 первых, 9 вторых и 4 третьих блюда. Сколькими способами можно выбрать обед из трех блюд (первое, второе и третье)?

Ответ: .

2. Допустим, что у вас есть 4 пары туфель, 3 брюк и 2 свитера. Каким числом способов вы можете одеться?

Ответ: .

3. На гору ведут 7 дорог. Сколькими способами турист может подняться на гору и спуститься с нее, если подъем и спуск должны осуществляться по разным дорогам?

Ответ: .

4. Сколькими способами можно поставить на шахматную доску 2 ладьи (белую и черную) так, чтобы они не били друг друга?

Ответ: .

Размещения и перестановки без повторений

1. Сколько слов длиной 4 можно составить, используя только 7 различных букв, если буквы в слове не повторяются?

Ответ: .

2. В чемпионате участвует 16 команд. Сколькими способами могут быть распределены на финише 10 первых мест?

Ответ: .

3. Сколькими способами 4 юношей могут пригласить на танец 4 из 6 девушек?

Ответ: .

4. В чемпионате участвует 16 команд. Сколькими способами могут они быть распределены на финише турнира?

Ответ: .

5. Сколькими способами на шахматной доске можно расставить 8 одинаковых ладей так, чтобы они не били друг друга?

Ответ: .

6. Сколько существует таких перестановок чисел 1, 2, …, n, в которых число 1 стоит перед числом 2, причем числа 1 и 2 не обязательно соседние?

Ответ: .



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-29 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: