Otvety_Zachet_Kombinatorika

Комбинаторный анализ							11
Пример:
Производящая функция для последовательности
( ) ∑	∑	∑( )	(∑ )	((	) )	(	)

Операции над производящими функциями

Для двух произвольных формальных рядов

						( )		∑		( )				∑
и произвольного действительного числа							определим
	1) Операцию умножения на число
										( )			∑
	2)	Операцию сложения
									( )	( )			∑(				)
	3)	Операцию произведения
									( ) ( )					∑
		где
																	∑
Если (		) и	( ) является аналитическими функциями в окрестности														, то их можно рассматривать как зна-
чения функций (			) и	( ) в точке		, а ряды понимать в обычном смысле. В этом случае операции 1)-3) так же
справедливы.
Пример:
(	) - производящая функция для последовательности
							( )		∑	(			)
(	) - производящая функция для последовательности
							( )		∑	(			)
Тогда:
	1) производящая функция для последовательности														:
								( )	(	)				∑				∑
	2) производящая функция для последовательности
					( )		( )	∑		∑				∑(			)
		(	)	( )	(	)	(		)											(	)
													(		)		(		)
	3) производящая функция для последовательности
			( )	( )	∑(					)				∑(							)
					( )	(	)	(	)	(			)		(		)

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

12

Производящие функции для НВ

Рассмотрим производящую функцию (

)

, описывающую количество НВ без возвращения из ГС объема

:

{

}

Каждый множитель (

) можно считать соответствием некоторому элементу

в ГС.

При перемножении

таких множителей в каждое слагаемое

из данного множителя можно войти либо

(элемент

входит в выборку 0 раз) либо

(элемент

входит в выборку 1 раз). Т.к. рассматриваем

выборку без возвращений, каждый элемент может входить в выборку не более одного раза.

Эту модель можно обобщить на случай, когда каждый элемент

может входить в выборку не более, чем

раз. В этом случае производящая функция будет иметь вид:

∑

(

)(

)

(

)

Пример:

Если некоторый элемент

может входить в выборку 1, 3 или 5 раз, то соответствующий множитель прини-

мает вид (

) .

В наиболее общем случае, если

элемент ГС может входить в выборку

раз, число НВ объема

будет описываться коэффициентами при

произведением:

∑

∏ (

)

Если на число вхождений всех элементов

не накладывается никаких ограничений (обычно НВсВ), то про-

изводящая функция принимает вид

∑

(

)

(

)

((

) )

(

)

Разложим функцию

( )

(

) в ряд Маклорена:

( )

( )(

)

( )( )

) )( )

∑

((

(

)(

)

(

) (

) (

)

(

)

(

)(

)

(

)( )

(

)

(

)

(

)

(

)

( )

(

)(

)

∑

∑

∑

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

свозвращениями.

Спомощью производящих функций для НВ можно доказывать тождества, связанные с биноминальными коэффициентами.

Пример:

Доказать тождество Коши

∑

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

∑	( ) ( ) ( ) ∑ ∑ ∑ ∑

отсюда следует доказуемое тождество.

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

13

Производящие функции для УВ

При построении производящей функции описывающих НВ, использовалось свойство коммутативности умножения.

При формировании произведения , соответственного выбора объема , учитывалось, какой элемент входит в выборку и сколько раз, но не учитывается порядок элементов.

Таким способом невозможно построить производящую функцию, описывающую УВ. Однако, заметим, что

	(	)	∑	∑
Т.е. в расположении число	(количество УВбВ) является коэффициентом при							. Это позволяет описывать

спомощью производящих функций УВ.

Вданном случае описана УВбВ из ГС объема . Т.е. каждый элемент может входить в выборку 0 или 1 раз.

Построим производящую функцию для описания УВсВ из ГС

{

}.

Пусть известно, что элемент входит в УВ ровно

раз. Объем выборки .

Количество таких УВcВ равно

Т.к. это число должно быть коэффициентом при

, то множитель, соответствующий элементу , должен

быть равен

.

Тогда вся производящая функция имеет вид

Рассуждая аналогично, получим, что

множитель будет равен

А вся производящая функция примет вид:

∑

(

)

(

)

В наиболее общем случае, если элемент

может входить в УВ

раз, число УВ объема будет опи-

сываться коэффициентом при

Производящей функцией

∑

∏ (

)

Производящие функции такого вида называются экспоненциальными

Пример:

∑

ГС:

{

}

Построить экспоненциальную производящую функцию для числа УВсВ при условии, что: элемент входит

в выборку не более 2 раз, элемент

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

входит в выборку 1 или 2 раза.

Решение:

∑

(

) (

) (

) (

) (

) (

)

Комбинаторный анализ			14
Пример:
ГС:	{	}

Построить экспоненциальную производящую функцию для количества УВсВ.

Решение:

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

вид:
(						)	( )	∑
Т.о. количество УВсВ элементов из			определяется функцией , что совпадает с ранее полученным результа-
том.

Решение рекуррентных соотношений

Пусть имеется последовательность , заданная рекуррентным соотношением

,,…,

( )

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

т.е. вида	( ).
Пример
Найти заключительную формулу для вычисления произвольного члена		последовательности чисел Фибо-
наччи	:

,

Решение:

Построим производящую функцию для последовательности Фибоначчи:

( )

∑

∑(

)

∑

∑

∑

∑

∑

∑

(∑

)

∑

( ( )

)

( )

( )

(

)

( )

(

)(

)

√

√

Воспользуемся методом неопределенных коэффициентов

(

)

(

)

(

)

(

)

(

)

(

)(

)

(

)(

)

Приравнивая коэффициенты при одинаковых степенях

в числителе первой и последней дроби, получим

систему уравнений:

{

{

( ) (

)

(

)

∑

∑

∑(

)

∑

((

√

)

(

√

)

)

√

Комбинаторный анализ	15
Таким образом, процедура нахождения заключительной формулы для	члена последовательности, за-
данной рекуррентным соотношением, состоит из следующих этапов:

1)Записать производящую функцию для заданной последовательности, используя рекуррентные соотношения:

( ) ∑

∑ (

)

2) Путем эквивалентных преобразований привести все суммы в правой части равенства к виду

∑

и заменить их на ( )

3)Решить полученное соотношение относительно ( ), получив выражение для производящей функции ( ) в виде аналитической.

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

последовательности.

Пример:

Задано рекуррентное соотношение

,

,

Найти выражение для

( ) в замкнутом виде.

Решение:

Записываем производящую функцию

( )

∑

∑(

)

∑

∑

∑

∑

∑

∑

∑

∑

∑

(∑

)

(∑

)

∑

( ( )

)

( ( )

)

( )

(

)

( )(

)

( )

(

) ∑(

)

(

)(

)

(

)

∑(

)

(

)(

)

∑(

)

(

)(

)

∑(

)

(

)(

)

∑( )

(

)(

)

∑( )

(

)

∑( )

(

)

(

)(

)

(

)

(

)

∑( )

∑( )

∑( )

∑

( )

((

)(

)

(

)

(

) )

∑

( )

(

)

∑

(

)

(

)(

)

В итоге получаем:

( )

( )(

)

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

16

Разложения правильно рациональной дроби на элементарные дроби.

{самостоятельное изучение (смотри 1 семестр, курс алгебры)}

Разбиение чисел

Рассмотрим все возможные разбиения числа			на целых положительных слагаемых
Набор слагаемых непорядочен, поэтому можно положить				. Обозначим через	( ) число
таких разбиений.
			m
Очевидно, что ( )	, ( )	, ( )	, ki k
			i 1
Уменьшив каждое из слагаемых в этом разбиении на единицу, получим разбиение числа					на не более,
чем слагаемых (если некоторое			)

∑( )

Число таких разбиений по правилу суммы

		∑	(	)
Т.к. каждому такому разбиению взаимно однозначно соответствует разбиение числа					на слагаемых, то
		∑ (	)	( )
Это рекуррентное соотношение позволяет последовательно получать значения (					) для произвольных зна-
чения	и .
Теорема 1
Количество разбиений числа		на не более чем	слагаемых равно количеству разбиений числа на слагае-
мые, не превосходящие .
Доказательство:
Разбиению числа на не более, чем слагаемых				можно поставить в соответствие матри-
цу	, содержащую ровно единиц в следующем виде:
		(		)
где количество единиц в		строке равно .

Если транспонировать матрицу относительно главной диагонали, то получим новую матрицу размерности

, которая взаимно однозначно соответствует исходной матрице и определяет разбиение числа				на слагае-
мые, не превосходящие .
Отсюда следует, утверждение теоремы.
Каждое разбиение числа на слагаемых можно представить в виде последовательности (				), где
– количество слагаемых равно .
С другой стороны, любая последовательность неотрицательных целых чисел(			), удовлетворяющая
m
условию i li k , однозначно определяет разбиение числа .
i 1
Пусть ( ) – это количество всевозможных разбиений числа на слагаемые.
( ) – количество всевозможных разбиение числа		на слагаемые, не превышающие
( )	(	)
Пример:
Берем число и разбиваем его на слагаемые всеми возможными способами
(	)
(	)
(	)
(	)
(	)

Комбинаторный анализ																																	17
	Найдем производящую функцию для последовательности																			(		)		(	)			(		)	, на слагаемые,		не пре-
восходящие .
	Произведение (								)(									)		(											) равно сумме слага-
емых вида							, где – номер слагаемого, выбранного из																					сомножителя.
	Коэффициенты при				равны количеству слагаемых такого вида, равных																							, которое, в свою очередь, раны
																		m
количеству последовательностей (												) таких, что i li								k .
																		i 1
	Следует, что при			(		), т.е. рассматриваемое произведение
		(							)(									)		(											)
								(	)			(			)			(				)			∏(					)
	Является производящей функцией для последовательности																			(		)		(	)			(		)
	Аналогично, можно показать, что производящая функция для (																					)		(	)			( )
		(							)(									)		(											)
						(			)			(			)			(		)				∏(				)
	Теорема 2
	Количество разбиений числа							на попарно различные слагаемые равно количеству разбиений числа																									на не-
четные слагаемые.
	Доказательство:
	Производящая функция для количества разбиений на попарно различные слагаемые
						(		)	(			)(			)(			)				(			)
	Производящая функция для количества разбиений на нечетные слагаемые
		( )	(						)(									)		(								(		)	)
								(	)			(			)			(						)
	Воспользуемся соотношением
	И преобразуем функцию
		(	)																												( )
	Числа Каталана
	Это числовая последовательность (																	),		которая встречается во многих комбинаторных
задачах.
	Одно из таких задач – нахождение количества неизоморфных бинарных деревьев с заданным числом вер-
шин.
	Определение:
	Бинарное дерево		с		вершинами – это
		Пустое дерево						, если
					, где		–вершина, называемая корнем дерева, (левое поддерево) – бинарное дерево с
		вершинами, (правое поддерево) – бинарное дерево с																						вершинами.
	В этом случае
	Деревья	и	называются изоморфными (												),			если либо										, либо					и
	при этом			,		.
	Обозначим через			количество неизоморфных бинарных деревьев с																					вершинами.

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

18

Пример

Найдем число

неизоморфных бинарных деревьев с

вершинами.

Пусть

бинарное дерево с

вершинами.

Если – это бинарное дерево с

вершинами, то

– бинарное дерево с

вершинами. Т.к. существу-

ет

неизоморфных деревьев

, то при заданном

существует

неизоморфных деревьев .

Число

может принимать любое значение от

до

, откуда следует,

∑

Рассмотрим производящую функцию (заметим,

что выражение для ( )

похоже на произведение

( )

(

), и приведем некоторые преобразования)

( ) ∑

∑ (∑

) ∑ (∑

)

∑ (∑

)

∑

∑

( )

( )

Отсюда

( )

( )

Решив квадратное уравнение относительно

(

), получим ( )

√

,

.

Разложим √

в ряд Маклорена

((

)

)

(

) (

)

(

) (

)

( )

( )

(

)(

)

Разложим в ряд

∑

(

)

∑

(

)

∑

(

)

√

(

)

)

(

∑

( )

Для получения производящей функции

с положительными коэффициентами

в выражении для

(

)

√

выбираем «–»:

( )

√

∑

∑

Отсюда

Числа

называются числами Каталана

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

19

Циклы перестановок

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

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

элементы множества , причем элемент (	) помещается под соответствующим элементом .
В дальнейшем без ограничений общности будем рассматривать перестановки элементов вида {						}.
Пример
Рассмотрим перестановку множества	{	} такую, что ( )	, ( )	, ( )	, ( )	.
Эта перестановка записывается в виде
	(	)

Если порядок элементов в верхней строке фиксирован, то перестановку однозначно определяет последовательность в нижней строке.

Каждую перестановку можно представить графически с помощью ориентированного графа с множеством

вершин	{	}, в котором присутствует дуга (	) тогда и только тогда, когда ( )	.
Т.к.	– взаимно однозначная функция, то из каждой вершины выходит одна дуга и в каждую вершину вхо-
дит одна дуга.
Если строить маршрут из произвольной вершины			последовательно через вершину	( ),	( ),
(	) и т.д., то через некоторое число шагов вернемся в вершину .

Отсюда следует, что граф, соответствующий перестановке состоит из некоторого числа контуров (ориентированных циклов) с непересекающимися множествами вершин, объединения которых дает множество .

Каждому такому контуру соответствует перестановка,
		(				)
называющаяся циклом.
Пример
Перестановка
		(				)
представима в виде ориентированного графа:
1
				7
							2

4

							5
	3			6
Граф состоит из трех контуров:
(						)
(						)
(				)
Которым соответствует перестановка
(				) (		) ( )
Числа Стирлинга I рода
Числом Стирлинга I рода (без знака) ( ) называется число перестановок									го порядка, содержащих

циклов.

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

1)( )

(единственная перестановка) имеет вид

				(	)
	2)	( )	(для	, т.к. каждая перестановка содержит хотя бы 1 цикл)
Положим так же:
(	)
(	)	(для	)

Комбинаторный анализ																													20
Теорема 1
Для чисел Стирлинга I рода (без знака)												(		)справедливо следующее рекуррентное соотношение:
							(		)	(				)	(					)	(			)
где		и			.
Доказательство:
При				соотношение, очевидно, верно, т.к.													(	)		(	)
Пусть перестановка (							)		порядка множества {														} содержит				циклов. Всего таких пере-
становок будет			(		).
Элемент			можно добавить в любую из этих перестановок после любого из (																								) имеющихся элементов,
соответствующих циклов.
Все полученные перестановки различны, содержат																	циклов, и всего их будет (										)	(	).
Пусть перестановка (							)		порядка множества {														} содержит					циклов. Всего таких
перестановок будет					(		).
Из каждой такой перестановки можно сформировать единственную перестановку																												порядка, содержа-
щую циклов, добавив цикл, состоящий из единственного элемента .
Значит, всего полученных перестановок будет															(					).
Просмотренные два случая, описывают все перестановки																					порядка, содержащие							циклов, что доказы-
вает утверждение теоремы.
																													■
Теорема 2
Числа Стирлинга I рода (без знака)										(		) описываются производящей функцией
							( )				∑	(		)			(			)	(			)
Доказательство:
Проведем индукцией по числу
(	)	, что соответствует равенствам
(	)		, (		)	, т.е. теорема верна при											.
Пусть		(	)	(		)	(				) и				.
Тогда считаем
				(	)	(	)			(				)				(			)			(			)
		(	(		)	(	))			(				(	)		(				))	(		(			)	(	))
					(		)
		( (		)	(	)	(		)						(		) )(				)	(		)		(		)(	)
Числами Стирлинга I рода (со знаком)												(			) называются коэффициенты многочлена
										(		)			(					)	∑	(		)
Из определения видно, что числа Стирлинга I рода имеют чередующийся знак.
числа Стирлинга I рода без знака являются их абсолютными значениями
										(		)		|	(		)|	(		)	(	)
											0			1			2			3	4			5
								0			1			0			0			0	0			0
								1			0			1			0			0	0			0
								2			0			-1			1			0	0			0
								3			0			-2			-3			1	0			0
								4			0			-6			11			-6	1			0
								5			0			24			-50			35	-10			1