Otvety_Zachet_Kombinatorika

Комбинаторный анализ

21

Разбиением

элементного множества

на

блоков называется произвольное множество

{

}

непустых подмножеств множества

такое, что

1.

2.

,

Подмножества

называются блоками разбиения .

Множество всех разбиений множества

на

блоков обозначается

( ). А множество всех разбиений мно-

жества обозначается

(

).

Очевидно, что

(

)

(

)

(

)

Более того, {

( )

(

)} является разбиением множества (

). В дальнейшем без ограничений общно-

сти будем рассматривать разбиение множеств вида {

}.

Заметим,

что каждое разбиение множества {

} однозначно определяет разбиение

множества

{

}.

Обратно, если дано разбиение

{

} множества {

}, то построить из него разбиение

множества {

} можно (

) способами, т.е.

{

{ }

}

{

{ }

}

Если имеется множества всех разбиений

({

}), то, заменяя каждое разбиение последователь-

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

({

})

Пример

({

})

{1}

({

})

{1, 2}

{1}, {2}

({

})

{1, 2, 3}

{1, 2}, {3}

{1}, {2, 3}

{1}, {2}, {3}

{1, 3}, {2}

Числа Стирлинга II рода

Числом Стирлинга II рода (

) называется число разбиений

элементного множества на

блоков.

(

) |

( )|

|

|

Пример

(

)

Замечание: Число Стирлинга II рода не следует путать с полиномиальным коэффициентом

, который

выражает количество разбиений

элементного множества на упорядоченный набор из подмножеств фикси-

рованного размера

.

Прием

(

)

, т.к. пустое множество блоков является в соответствии с определением разбиения пустого

множества.

Очевидно, что

(

)

, где

(

)

, для

(

)

, для произвольного

Теорема 1

Для чисел Стирлинга II рода справедливо следующее рекуррентное соотношение (при

)

( )

(

)

(

)

Доказательство:

Рассмотрим множество всех разбиений множества {

} на

блоков. Это множество можно разбить на

два класса:

1) разбиение, которое содержит одноэлементный блок {

}

2)

разбиение, в которых

является элементом большего блока {

}

Мощность первого класса равна

(

) (число разбиений множества {

} на

блок)

Мощность второго класса составляет

(

), т.к. каждому разбиению множества {

} на

блоков соответствует в этом классе ровно

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

поочередно к

каждому блоку.

■

Комбинаторный анализ

22

Теорема 2

Для чисел Стирлинга II рода (

) справедливо следующее рекуррентное соотношение

(

)

∑

(

)

Доказательство:

Рассмотрим множество всех разбиений

( ) множества

{

}.

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

, кото-

рые являются блоками, созданными элементом .

Отметим, что для каждого

элементного блока

,

созданного элементом , существует

ровно

(

) разбиений множества

на

блоков, содержащих

в качестве блока, т.к. каждое такое разбиение

однозначно соответствует разбиению множества

на

блок,

элементный блок

, содержащий эле-

мент , можно выбрать

способами, при этом само число

можно изменять от 1 до

.

Таким образом,

( ) ∑

(

) ∑

(

) ∑

(

)

■

Числом Белла называется число всех разбиений

элементного множества.

|

(

)|, |

|

. Из определения следует, что

∑ (

)

Причем,

(

)

Теорема 3

Для чисел Белла

справедливо следующее рекуррентное соотношение

∑

Доказательство:

Аналогично доказательству теоремы 2

Множество всех разбиений

(

) множества

{

} можно разбить на различные классы в зави-

симости от блока , содержащего элемент

или, что то же самое, в зависимости от множества

.

Для каждого множества

мощности

существует ровно

разбиений множества

, содержащих

в

качестве блока.

Множество

можно выбрать

способами, при этом число

может изменяться от

до .

Отсюда следует утверждение теоремы

0

1

2

3

4

5

0

1

0

0

0

0

0

1

1

0

1

0

0

0

0

1

2

0

1

1

0

0

0

2

3

0

1

3

1

0

0

5

4

0

1

7

6

1

0

15

5

0

1

15

25

10

1

52

Существует зависимость между числами

(

) и числом всех функций из

элементного множества на

элементное множество, т.е.

такие, что

( )

, |

|

, |

|

.

Каждой функции

можно поставить в соответствие разбиение множеств

на

блоков

( )

{

(

)

} – ядро функции .

Условие

( )

гарантирует, что подмножества

( )

не пустые.

Обратно, каждому разбиение

( ) соответствует ровно

функций из на

таких, что (

)

.

Каждая из этих функций устанавливает взаимно однозначное соответствие между блоками разбиений

и

элементами множества .

Дает одну из

перестановок.

Так как число функций из

на

Комбинаторный анализ

23

Теорема 4

∑ (

)

Доказательство:

Подсчитаем двумя способами число всех функций

, где |

|

, | |

.

С одной стороны оно равно , с другой стороны, множество таких функций

можно классифицировать в

зависимости от множества (

).

Очевидно, что каждая функция

является отображением множества

на множество ( ).

Таким образом, для произвольного подмножества

, где |

|

, число всех функций из

в

таких,

что ( )

, равно

(

).

Учитывая, что подмножество

мощности

можно выбрать

способами, получаем

∑

(

)

∑

(

)

Предел суммирования можно заменить, т.к.

( )

при

.

Поскольку равенство множеств выполняется для произведения целого неотрицательного числа

,

эти мно-

жества тождественно равны.

■

Из определения числа Стирлинга I рода и Теоремы 4 следует отношение между чисел Стирлинга I и II рода

∑ (

)

(

)

{

Суммирование производится по всем

, для которых

(

) или

(

) отличны от .

в различные ячейки эквивалентна задаче о подсчете числа всех функций из

элементного множества на

элементное множество .

Комбинаторный анализ

24

Количество таких функций:

∑(

)

(

)

(

)

Если задано условие, что ровно

ячеек должно остаться пустыми, то размещение объектов можно провести

в два этапа.

1)

Выбрать

способами пустые ячейки.

2)

Заполнить оставшиеся

ячеек

способами

(

) (

)

Всего, в соответствии с основной теоремой комбинаторики, получаем

(

)

(

)

Пусть известно, что в

ячейку необходимо поместить ровно

объектов

∑

любое количество объектов)

Выборка неупорядоченная (объекты не различимы) с возвращением.

Следует, что количество размещений неразличимых объектов в

различимые ячеек равно

.

Пусть задано исключение, что все ячейки должны быть заполнены.

Проведем размещение объектов в два этапа

1)

Поместить в каждую из

ячеек по одному объекту (единственным способом)

2)

Разместить оставшиеся

объектов в

ячеек

Т.е. все размещения можно провести

количеством способов.

Пусть задано условие, что ровно

ячеек должно оставаться пустыми.

Проведем размещение объектов в два этапа

1)

Выберем

способами пустые ячейки

2)

Заполним оставшиеся

ячейки объектами

способами

жества.

Если объектами занять ровно ячеек, получаем разбиение

элементного множества на подмножеств.

Количество таких разбиений равно числу Стирлинга II рода, т.е. (

).

В общем случае количество заполненных ячеек может принимать значение от до .

Тогда решением задачи будет число

∑ (

)

Комбинаторный анализ

26

Теорема 2

Пусть

(

),

(

) точки с целочисленными координатами, при этом

,

(

) – точка, симметричная точке относительно оси

Тогда число траекторий из

в

, имеющих с осью

общие точки, равно числу траекторий из

в .

Доказательство:

y

A

B

x

A’

Каждой траектории

из

в

, имеющей с

общую точку, поставим в соответствие траекторию

следу-

ющим образом:

Часть траекторий

до первой общей точки с

симметрично отображаем относительно .

Таким образом, каждой траектории

из

в

соответствует траектория

из

в .

Обратно каждой траектории из

в

соответствует траектория из

в .

Таким образом, между множеством траекторий из

в

, имеющих с

общую точку, и множеством траек-

торий из

в

установлено взаимно однозначное соответствие.

■

Теорема 3

Пусть

, тогда количество траекторий из точки

(

) в точку

(

), не имеющих вершин (кроме

точки ) на оси

, равно

.

Доказательство:

Все траектории из точки

в точку

не имеющих вершин на оси

, проходят через точку (

).

Общее число траекторий из

в

равно

(по теореме 1).

Число траекторий из

в

, пересекающих ось , по теореме 2 равно числу траекторий из точки (

) в

точку , т.е.

.

Следовательно, искомое число траекторий равно

(

)

(

)

.

(

) (

)

(

) (

)

(

) (

)

■

Пример:

К кассе подошли

человек.

из них имеют монеты достоинством 1 рубль, – достоинством по 50 ко-

пеек.

.

Билет стоит 50 копеек. Сначала в кассе денег нет.

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

покупателей в очереди так, чтобы ни один из покупателей не

ждал очереди.

Решение

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

Построим траекторию из точки

(

) в точку (

), соответствующую данного способу размеще-

ния покупателей, следующим образом:

{

Условию задачи удовлетворяют траектории, не пересекающие прямую

(не должны возникать ситуа-

ции, когда в кассе нет 50 копеек и пришел покупатель с 1 рублем).

Комбинаторный анализ

27

(

) в точку (

), т.е.

(сдвигаем систему координат на -1 по оси ординат, при-

меняем теорему 2, возвращаем систему координат на место).

Откуда следует число траекторий:

Вариант 2

Задача сводится к подсчету числа траекторий из точки ( ) в точку (

), не имеющих

вершин на оси

, кроме точки (

).

Согласно теореме 3, число таких траекторий равно

.

Пример:

Сколько существует правильных скобочных последовательностей, состоящих из

скобок ( открывающих

и

закрывающих)

Решение

Построим траекторию из точки

( ) в точку (