Пример 1. Тема 3.2. Разбиения. Включения и исключения

Разбиения

Тема 3.2. Разбиения. Включения и исключения

Резюме по теме

Вопросы для повторения

1.Чем занимается комбинаторика?

2.Кем впервые был введен термин комбинаторика?

3.В чем заключается смысл правила суммы и произведения?

4.Что представляет собой выборка?

5.Когда используются перестановки?

6.Назовите отличие размещения от перестановки?

7.В чем особенность размещений с повторениями?

8.Что такое сочетание?

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

Цель: ознакомиться с понятиями комбинаторики разбиения, включения и исключения.

Задачи:

1 Рассмотреть разбиения.

2 Рассмотреть полиномиальную формулу.

3 Рассмотреть формулы включения и исключения.

Подсчитаем число разбиений конечного множества Х, где , на k подмножеств Х ₁, Х ₂, …, Х_k таких, что каждое Х_i содержит n_i элементов, т.е.

, при , , i =1, 2,.., k. (1)

Очевидно, что при этом n ₁+ n ₂+…+ n_k = n. Отметим, что для некоторых номеров i возможно . Число указанных разбиений при фиксированных n_i обозначается .

Замечание. В данном случае набор подмножеств множества Х в разбиении является упорядоченным, т.е. Х ₁, Х ₂, …, Х_k – упорядоченная последовательность множеств.

Лемма. .

Доказательство: Множество Х ₁ может быть выбрано . После выбора Х ₁ множество Х ₂ можно выбрать способами (т.к. и ) и т.д. Тогда по правилу произведения выбор упорядоченной последовательности множеств Х ₁, Х ₂, …, Х_k можно произвести способами.

Теорема 1. .

Доказательство: [после сокращений]= , что и требовалось доказать.

Пример 2.

Требуется найти число размещений с повторениями из n элементов по k элементов, в которых первый элемент встречается ровно n ₁ раз, второй элемент встречается ровно n ₂ раз, …, k –ый элемент встречается ровно n_k раз (n ₁+ n ₂+…+ n_k = n).

Теорема 2. Число таких размещений равно .

Доказательство. Каждому размещению указанного типа поставим в соответствие разбиение множества номеров элементов в выборке на подмножества Х ₁, Х ₂, …, Х_k, где Х_i – множество номеров элементов i –го типа в выборке. Очевидно, что при этом выполняются условия (1). Указанное соответствие между размещениями данного типа и разбиениями, удовлетворяющими (1), является взаимно однозначным (биективным). Следовательно, в силу теоремы 1, теорема 2 верна.

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