Otvety_Zachet_Kombinatorika
.pdf
Лекции по курсу «Комбинаторный анализ»
семестр 3 Лектор: доцент кафедры ВМиК Орехов Эмиль Юрьевич
Материал собрал и склеил Ф.Тимур специально для МО-202, ноябрь, 2013
Рекомендуемая литература .......................................................................................................................................... |
3 |
Основы комбинаторики................................................................................................................................................ |
3 |
Основные правила комбинаторики ......................................................................................................................... |
3 |
Теорема 1. Основная теорема комбинаторики (правило произведения) ............................................................. |
3 |
Теорема 2. Правило суммы ...................................................................................................................................... |
4 |
Выбор ............................................................................................................................................................................. |
4 |
Упорядоченная выборка с возвращением (УВсВ) ................................................................................................. |
4 |
Упорядоченная выборка без возвращения (УВбВ)................................................................................................ |
4 |
Неупорядоченная выборка без возвращения (НВбВ)............................................................................................ |
5 |
Неупорядоченная выборка с возвращением (НВсВ) ............................................................................................. |
5 |
Схема выборочного контроля .................................................................................................................................. |
5 |
Бином Ньютона ......................................................................................................................................................... |
6 |
Полиномиальная теорема ......................................................................................................................................... |
6 |
Принцип включения и исключения............................................................................................................................. |
8 |
Теорема «Принцип включения и исключения» ..................................................................................................... |
8 |
Производящие функции ............................................................................................................................................. |
10 |
Основные понятия................................................................................................................................................... |
10 |
Операции над производящими функциями.......................................................................................................... |
11 |
Производящие функции для НВ............................................................................................................................ |
12 |
Производящие функции для УВ ............................................................................................................................ |
13 |
Решение рекуррентных соотношений................................................................................................................... |
14 |
Разложения правильно рациональной дроби на элементарные дроби. ................................................................. |
16 |
Разбиение чисел .......................................................................................................................................................... |
16 |
Теорема 1 ................................................................................................................................................................. |
16 |
Теорема 2 ................................................................................................................................................................. |
17 |
Числа Каталана............................................................................................................................................................ |
17 |
Циклы перестановок ................................................................................................................................................... |
19 |
Числа Стирлинга I рода .......................................................................................................................................... |
19 |
Разбиение множеств ................................................................................................................................................... |
21 |
Числа Стирлинга II рода......................................................................................................................................... |
21 |
Разложение объектов по ячейкам .............................................................................................................................. |
23 |
1 Размещение различных объектов в различные ячейки .................................................................................... |
23 |
2 Размещение не различных объектов в различные ячейки................................................................................ |
24 |
3 Размещение различных объектов в не различные ячейки................................................................................ |
24 |
4 Размещение не различных объектов в не различные ячейки........................................................................... |
25 |
Метод траекторий ....................................................................................................................................................... |
25 |
Комбинаторный анализ |
3 |
|
|
Рекомендуемая литература
Яблонский С.В. «Введение в дискретную математику» Липский В. «Комбинаторика для программистов» Холл М. «Комбинаторика» Риордан Дж. «Введение в комбинаторный анализ»
Ежов И. И. «Элементы комбинаторики» Рыбников К.А. «Введение в комбинаторный анализ»
Рыбников К.А «Комбинаторный анализ. Задачи и упражнения» Семенов А.С. «Четыре лекции по комбинаторике: методические указания» Ландо С.К. «Лекции о производящих функциях» Кофман А. «Введение в прикладную комбинаторику»
Комбинаторика – раздел математики, изучающий конечное или счетное дискретные объекты (множества последовательностей)
Основы комбинаторики Основные правила комбинаторики
Теорема 1. Основная теорема комбинаторики (правило произведения)
Пусть даны конечные множества: |
|
{ |
} |
{ |
} |
{ |
} |
Взяв по одному элементу из каждого множества, образуем упорядоченный набор |
( |
). Всего |
|||||||||||
существует |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∏ |
|
|
|
|
|
|
|
|
число таких наборов. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Доказательство приводится индукцией по количеству |
рассматриваемых множеств |
|
. |
||||||||||
. Набор |
состоит из единственного элемента ( |
) и таких наборов будет столько, сколько имеется |
|||||||||||
элементов в множестве |
, т.е. | |
| |
. |
|
|
|
|
|
|
|
|
|
|
. Набор |
( |
). Элемент |
образует пары: ( |
), ( |
) |
( |
), |
т.е. всего |
пар. Ана- |
||||
логично каждый из |
элементов множества |
образует |
различных пар с элементами множества |
. Следова- |
|||||||||
тельно, всего таких пар будет |
|
|
|
. |
|
|
|
|
|
|
|
||
Предположим, |
что теорема верна для всех |
, т.е. |
различных наборов вида ( |
|
) будет |
||||||||
. |
|
|
|
|
|
|
|
|
|
|
|
|
|
Рассмотрим теперь случай, когда |
. Заметим, что любой набор вида ( |
|
) можно рассматри- |
||||||||||
вать как пару (( |
|
) |
), |
где первый элемент состоит из |
|
элементов. Следовательно, анало- |
|||||||
гично случаю |
получим, что пар указанного вида будет ( |
|
) |
. Т.е. наборов исходного вида |
|||||||||
будет |
штук. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
■ |
Комбинаторный анализ |
4 |
Теорема 2. Правило суммы
Пусть даны конечные непересекающиеся множества:
{}
{}
{}
Выбрать элемент |
из множества |
или элемент |
из |
… или |
из , т.е. ровно один элемент из од- |
ного множества можно |
|
способами. |
|
|
|
Доказательство:
Очевидно, что выбор одного элемента из одного множества эквивалентен выбору одного элемента из объ-
единения этих множеств |
. Такое объединение содержит | |
| | | | | |
| | |
элементов. Следовательно, выбор одного элемента можно произвести |
|
способами. |
|
|
■
Выбор
Пусть имеется множество, содержащее элементов, из которого предполагается выбрать отдельные элементы. Это множество называется генеральной совокупностью (далее ГС) объёма .
Проведем последовательный выбор элементов из ГС. Полученная последовательность элементов называ-
ется выборкой объема .
Выбор элемента из ГС можно осуществить двумя способами
1)После извлечения выборный элемент не возвращается в ГС. Полученная последовательность эле-
ментов называется выборкой без возвращения.
2)После извлечения выборный элемент возвращается в ГС и может быть выбран повторно. Полученная последовательность элементов называется выборкой с возвращением.
Упорядоченная выборка с возвращением (УВсВ)
Формироваться упорядоченная выборка с возвращением объема из ГС объема будет из этапов:
1) Выбрать |
первый элемент выборки из ГС множества мощности . |
2) Выбрать |
второй элемент выборки из ГС множества мощности . |
) Выбрать |
элемент выборки из ГС множества мощности . |
В соответствии c основной теоремой комбинаторики формирование выборки можно осуществить т.е. способами.
Пример: сколько различных слов длиной из 5 букв можно составить, используя 10 букв алфавита.
,, .
Упорядоченная выборка без возвращения (УВбВ)
Формироваться упорядоченная выборка без возвращения объема из ГС объема будет из этапов:
1) Выбрать |
первый элемент выборки из ГС множества мощности . |
|
2) Выбрать |
второй элемент выборки из ГС множества мощности |
. |
) Выбрать |
элемент выборки из ГС множества мощности |
. |
В |
соответствии c основной |
теоремой комбинаторики формирование выборки можно осуществить |
||||||
( |
) |
( |
) т.е. |
|
способами. |
|
|
|
( ) |
|
|
||||||
|
|
|
|
|
|
|
|
|
УВбВ объема |
из ГС объема |
называется размещением из по |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( |
) |
|
|
Пример: сколькими способами можно сформировать команду из 3х спортсменов, каждый из которых будет участвовать в 3 видах соревнования, из 10 имеющихся спортсменов.
, , .
Комбинаторный анализ |
5 |
Неупорядоченная выборка без возвращения (НВбВ)
|
НВбВ объема из ГС объема представляет собой некоторое подмножество |
, | |
| |
|||
|
|
|
можно рассмотреть как ГС объема из которой можно образовать Перестановок. Т.о., каждая НВбВ |
|||
объема |
из ГС объема соответствует множеству из Упорядоченных выборок без возвращения объема из |
|||||
той же ГС. |
|
|
||||
|
Поскольку всего имеются УВбВ объема из ГС объема , то всего НВбВ объема |
из ГС объема равно |
||||
|
|
|
|
, обозначается как |
|
|
( |
) |
|
|
|||
Пример: сколькими способами можно выбрать в команду 3х бегунов на дистанцию 100м из 10 имеющихся спортсменов.
,,
Неупорядоченная выборка с возвращением (НВсВ)
Рассмотрим ГС |
{ |
}. Каждая НВсВ объёма |
из ГС объема однозначно определяется количе- |
|
ством входящих элементов |
|
|
|
|
Обозначим { |
} следующим образом |
|
|
|
|
|
|
|
|
Полученный таким образом код представляет собой определенные последовательности из , а нулей
Для решения исходной задачи достаточно подсчитать число различных последовательностей такого вида,
т.е. количество расстановок штук «1» и |
штук «0» на |
позицию. Заметим, что для формирования |
|||
последовательности достаточно разместить |
штук «1». |
|
|
|
|
Получаем НВсВ позиций из |
позиций. Количество таких выборок |
( |
) |
|
|
|
|
|
|||
( |
) |
|
|||
|
|
|
|
||
НВсВ объёма из ГС объема называют так же сочетаниями с повторениями из по .
Пример: На почте имеются три вида марок. Сколько существует различных способов наклеить 5 марок на коверт.
,,
Схема выборочного контроля
Задача:
Имеется партия, состоящая из |
изделий, среди которых |
дефектов. Для проверки предполагается отобрать |
|||||
изделий. Сколько имеется контрольных выборок объёма |
таких, что каждая содержит ровно дефектов изде- |
||||||
лия. |
|
|
|
|
|
|
|
Решение: сформулируем контрольную выборку в два этапа: |
|
|
|||||
Сформируем первую часть выборки, выбрав |
дефектных изделий из |
дефектных. Получаем НВбВ объе- |
|||||
ма из ГС объема |
. Всего |
выборок. |
|
|
|
|
|
Формируем вторую часть выборки, выбрав |
не дефектных изделий из |
не дефектных. Получаем |
|||||
НВбВ объема |
из ГС объема |
. Всего |
выборок. |
|
|
||
В соответствии с основной теоремой комбинаторики всего имеется |
|
выборок. |
|||||
Пример:
Из 10 лотерейных билетов два являются выигрышными. Предполагается купить 5 билетов. Определить количество исходов при которых купивший получит:
1)1 выигрышный билет
2)оба выигрышных билета
3)хотя бы один выигрышный билет
Решение: Считаем лотерейные билеты «изделием», выигрышные билеты – «дефектными изделиями», а покупаемые билеты – «контрольной выборкой». Получаем схему выборочного контроля.
,,
1) |
: |
|
|
|
|
|
( |
) |
|
|
|
|
|
|
|
|
|||
( |
) |
( |
) ( |
) |
|||||
|
|
||||||||
2) |
: |
|
|
|
|
|
( |
) |
|
|
|
|
|
|
|
|
|||
( |
) |
( |
) ( |
) |
|||||
|
|
||||||||
3) |
или |
: |
|
|
|
|
|
|
|
Комбинаторный анализ |
6 |
Бином Ньютона
Пусть и |
– произвольные действительные числа, |
– натуральное число. |
|
|
||||||||||
( |
) – бином, |
|
степень этого бинома можно представить в виде: |
|
|
|
||||||||
|
|
|
|
|
|
( |
) |
∑ |
|
|
|
|
|
|
где |
– некоторые коэффициенты. |
|
|
|
|
|
|
|
|
|
||||
Так как |
( |
) |
( |
)( |
) ( |
) |
|
|
|
|
получим в тех случаях, когда при |
|||
|
|
|
|
|
, то произведение вида |
|||||||||
перемножении |
биномов |
войдет |
раз из каких-то |
биномов, а |
войдет |
раз из оставшихся |
бино- |
|||||||
мов. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Таким образом |
|
будет столько, сколько существует способов расставить на |
позициях |
букв и |
||||||||||
|
букв . Для формирования расстановки достаточно поместить |
|
букв |
в каких-то |
позиций. Имеем НВбВ |
|||||||||
позиций из |
. Таких выборок . Таким образом |
|
|
|
|
|
|
|
||||||
( |
) |
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
( |
) |
∑ |
|
|
|
|
|
|
Формула Ньютона для степени бинома Коэффициенты в формуле бинома Ньютона называются биноминальными коэффициентами. С помощью
элементарных преобразований легко доказать соответствие между коэффициентами. |
|
|||||
– доказывается по формуле. |
|
|
|
|
|
|
, с учетом, что |
|
|
|
|
|
|
Можно вычислять биноминальные коэффициенты, используя операции сложения. |
|
|||||
Схема Паскаля: |
|
|
|
|
|
|
|
|
|
1 |
|
|
|
|
|
1 |
1 |
|
|
|
|
|
1 |
2 |
1 |
|
|
|
1 |
3 |
3 |
1 |
|
|
|
1 |
4 |
6 |
4 |
1 |
|
1 |
5 |
10 |
10 |
5 |
1 |
|
1 |
6 |
15 |
20 |
15 |
6 |
1 |
Если в формуле бинома Ньютона положить, что |
, получается тождество: |
|
||||
|
|
∑ |
|
|
|
|
Полиномиальная теорема
Дана генеральная совокупность |
{ |
}. |
Рассмотрим упорядоченную выборку объема такую, что |
||
элемент ГС входит в выборку ровно |
раз ( |
). Такая выборка называется переста- |
|||
новкой с повторениями. |
|
|
|
|
|
Сначала предположим, что в выборке все |
элементов различны. Тогда количество выборок состоящих из |
||||
данных элементов ровно . Заменим некоторые |
элементов этой выборки одинаковыми элементами. Количе- |
||||
ство «новых» выборок будет в |
раз меньше. |
|
|
||
Возьмем другие |
элементов полученной выборки и так же заменим их одинаковыми. Количество выборок |
||||
изменится еще в |
раз. |
|
|
|
|
Продолжая этот процесс, получим, что количество выборок с повторениями
Пример: Сколько различных слов можно получить, переставляя буквы слова «математика» Решение:
Имеем перестановку с повторениями объема ГС = { }
Количество различных перестановок с повторениями равно:
Комбинаторный анализ |
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
Полиномиальная теорема |
|
|
|
|
|
|
|
|
|
Для произвольных чисел |
( |
) и произвольного натурального |
справедливо равенство: |
|
|||||
( |
|
) |
∑ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Доказательство: |
|
|
|
|
|
|
|
|
|
Перемножим последовательно |
раз выражение ( |
). Получим сумму из |
слагаемых вида |
||||||
, где множитель |
берется из скобки и равен либо |
, …, либо . |
|
|
|||||
Обозначим через ( |
|
) количество таких слагаемых, в которых |
встречается |
раз, |
, …, |
||||
раз. Причем |
|
. |
|
|
|
|
|
|
|
Последовательность множителей в каждом таком слагаемом является перестановкой с повторениями, поэто-
му |
|
|
|
|
|
|
( |
) |
|
|
|
|
|
|
|
||
Бином Ньютона является частным случаем полиномиальной теоремы при |
, а биноминальные коэффи- |
||||
циенты |
для неотрицательных целых чисел и |
частным случаем полиномиальных коэффициентов. |
|||
Если в соотношение полиномиальной теоремы положить |
, получим |
||||
∑
Рассмотрим теперь задачу об упорядоченном разбиении множества на подмножестве заданной мощности,
раскрывающую еще один комбинаторный смысл полиномиальной теоремы. |
|
|
||||||
Пусть имеется множество |
мощности | | |
. Сформируем последовательность из |
непересекающихся |
|||||
непустых подмножеств |
|
множества |
таких, что |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Такой набор подмножеств называется разбиением множества . |
|
|
|
|||||
Подсчитаем количество разбиений множества |
таких, что | |
| |
|
|
||||
Решение: |
|
|
|
|
|
|
|
|
Образуем множество |
: Рассматриваем его как неупорядоченную выборку без возвращения |
элементов из |
||||||
объема : |
. |
|
|
|
|
|
|
|
Образуем множество |
: Рассматриваем его как неупорядоченную выборку без возвращения |
элементов из |
||||||
объема |
: |
. |
|
|
|
|
|
|
… |
|
|
|
|
|
|
|
|
Образуем множество |
: Рассматриваем его как неупорядоченную выборку без возвращения |
элементов |
||||||
из ( |
) объема |
( |
) |
: |
. |
|
|
|
Всего, согласно основной теоремы комбинаторики, имеется |
|
|
|
|||||
искомых разбиений. Пример:
Сколькими способами можно распределить 20 наименований товаров по 3м магазинам если в первый нужно
8 наименований, во второй – 7, в третий – 5. |
|
|
|
|
Решение: |
|
|
|
|
Множество , имеет мощность |
. |
, |
, |
. Количество способов равно: |
Комбинаторный анализ |
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
||||
Принцип включения и исключения |
|
|
|
|
|
||||
Пусть имеются два произвольных множества |
и , причем известны мощности этих множеств, а так же |
||||||||
мощности их пересечения. |
|
|
|
|
|
|
|
|
|
Найдем мощность объединения этих множеств. |
|
|
|
|
|||||
|
| |
| |
| | |
| |
| | |
|
| |
|
|
Решим аналогичную задачу для трех множеств |
, , |
: |
|
|
|||||
| |
| | | | | |
| | |
| |
| |
| |
| |
| |
| | |
| |
Пример. Каждый студент в группе – либо девушка, либо блондин, либо говорит по-английски. В группе 16 девушек, из них 6 блондинок, и 4 блондинки знают англий-
ский язык. Всего в группе 11 блондинов, по-английски из них говорят 8. Всего студентов, которые могут общаться на английском языке 20, из них 12 девушек. Сколько студентов в данной группе ?
Решение. Пусть − множество девушек, − множество блондинов, |
− множество студентов, которые зна- |
||
ют английский язык. Тогда | |
| – искомое число студентов в группе; |
− множество блондинок; |
|
− множество девушек, которые говорят по-английски; |
− множество всех блондинов (юношей и девушек), |
||
которые знают английский язык; |
− множество блондинок, которые говорят по-английски. Из данных |
||
задачи следует, что |
|
|
|
|
|
|
|
|
|
|
| | |
, | | |
, | | |
, | |
| |
, | |
| |
, | |
| |
, | |
| |
|
|
|
| |
| |
|
|
( |
|
) |
|
Таким образом, в группе 25 студентов. |
|
|
|
|
|
|
||||
Теорема «Принцип включения и исключения»
Если |
( ̅̅̅̅̅ ) конечные множества, то |
|
|
|
|
|
|
||||
|
| |
| |
| |
| |
| | |
(| |
| | |
| |
| |
|) |
|
|
(| |
| | |
|
|
| |
| |
|
|) |
( ) |
| |
| |
|
| | ∑| | |
∑ | |
| |
∑ | |
| |
( ) | |
| |
||||
Доказательство приводится методом индукцией по количеству объединяемых множеств |
|
||||||||||
Пусть |
. | | | |
|, для случаев |
и |
|
убедились в предыдущих примерах. |
|
|||||
Предположим, что теорема справедлива для произвольных |
множеств: |
|
|
||||||||
| | ∑| | |
∑ | |
| |
∑ | |
| |
( ) | |
| |
|||||
Докажем, что теорема верна и для |
множеств: |
|
|
|
|
|
|
||||
| | | |
| | | | | | |
| | | | | | ( |
)| |
||||||||
|
∑| | |
|
∑ | |
| |
( ) | |
|
| | | ∑| |
| |
|||
|
|
∑ |
| |
|
| |
( |
) | |
|
| |
|
|
|
∑| | |
∑ | |
| |
|
∑ | |
| |
( ) | |
| |
|||
■
Комбинаторный анализ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9 |
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пример |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Сколько чисел из первой тысячи натуральных чисел { |
|
|
|
|
|
|
|
} не делится ни на одно из чисел 2,3,5,7? |
|
||||||||||||||||||||||||||||||||||||||||||||
Решение |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пусть |
{ |
|
|
|
|
}, |
|
|
, |
|
|
, |
, |
|
|
– подмножества |
|
|
, элементы которых делятся соответственно на |
||||||||||||||||||||||||||||||||||
2,3,5,7. |
Тогда |
|
искомое |
|
количество |
чисел |
|
|
|
| |
| |
| |
|
|
|
|
|
|
|
|
|
|
| |
= |
| | |
| |
|
| | |
| |
|
| |
|
| | |
| |
|||||||||||||||||||
| |
| | |
|
|
| | |
|
| |
| |
|
|
|
|
| |
|
|
| |
|
|
|
| |
|
| |
|
|
|
| |
|
|
| |
|
|
|
|
|
| |
| |
|
|
|
|
| |
|
|
|
||||||||||
| |
| |
|
|
| |
|
|
|
| |
| |
|
|
|
|
|
|
|
|
|
|
| = |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
[ |
|
|
] |
|
[ |
|
|
] |
[ |
|
|
|
] |
|
[ |
|
|
|
] |
[ |
|
|
|
] |
[ |
|
|
|
] |
|
[ |
|
|
] |
[ |
|
|
] |
[ |
|
|
] |
[ |
|
|
] |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
[ |
|
|
|
] |
[ |
|
|
|
|
] |
|
[ |
|
|
|
|
] |
[ |
|
|
|
|
] |
[ |
|
|
|
|
|
] |
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
+… = 228 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Пример: Дана ГС |
|
{ |
|
|
|
|
|
}. Найти количество НВсВ объема |
|
|
|
|
|
таких, |
что в |
элемент |
входит |
||||||||||||||||||||||||||||||||||||
не более чем |
|
|
раз; элемент |
|
|
не более чем |
|
|
|
раза; элемент |
|
не более чем |
|
|
|
раз; |
|
|
|
|
|
||||||||||||||||||||||||||||||||
Решение |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Пусть – множество всех НВсВ объема |
|
|
|
|
из ГС . |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||
|
– множество НВсВ, которое сдержит более чем |
|
|
|
|
|
раз вхождений элемента . |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||
|
– множество НВсВ, которое сдержит более чем |
|
|
|
|
|
раз вхождений элемента . |
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||
|
– множество выборок, которое сдержит более чем |
|
|
|
|
|
раз вхождений элемента . |
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||||
| | |
|
|
|
|
|
|
- количество НВсВ. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
5 элементов |
гарантировано входят в выборку, |
остается выбрать |
|
|
|
|
|
|
элементов их трех, получаем |
||||||||||||||||||||||||||||||||||||||||||||
НВсВ: | |
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Аналогично рассуждая, получаем: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
| |
| |
|
|
|
| |
|
| |
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
| |
|
|
|
|
|
|
| |
|
|
| |
| |
| |
| |
|
| |
| |
|
|
| |
|
| |
|
|
| |
|
|
|
| |
| |
|
|
| |
|
| |
|
|
|
|
|
| |
|
|
||||||||||
Функцией из |
на |
называется отображение |
|
|
|
|
|
такое, что |
( |
) |
|
|
|
(любой элемент множества |
мо- |
||||||||||||||||||||||||||||||||||||||
жет преобразоваться из элемента множества |
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
Теорема: Даны множества |
и |
. | |
| |
|
|
, | |
| |
|
|
|
. Доказать, что число всех функций из |
на |
равно |
|
|||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
∑ ( |
) |
( |
|
|
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
Пусть – множество всех функций: |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
– множество функций из |
в |
таких, что |
|
|
|
( ). Тогда |
( ) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||||||
Найдем число всех функций из |
на |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
| | | | | | ∑| | |
|
|
|
∑ | |
|
|
|
| |
|
|
∑ | |
|
|
|
|
|
|
| |
|
|
|
( ) | |
|
|
|
|
|
| |
||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
| |
|
|
|
|
|
( |
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
| |
|
( |
|
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
| |
|
|
( |
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |
|
|
|
|
|
| ( |
|
|
|
|
|
) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
( |
) |
( |
|
) |
|
|
|
( |
|
|
|
) |
|
|
|
|
( ) |
|
|
|
|
|
|
|
( |
|
( |
)) |
|
∑ ( ) |
( |
|
) |
|||||||||||||||||||
Комбинаторный анализ |
10 |
Производящие функции Основные понятия
В комбинаторных задачах при подсчете числа объектов определенного вида решением часто является после-
довательность |
|
, где – число объектов размера . |
|
|
|
|
|
|||||
Например, если нужно найти число разных НВсВ объема |
из |
данной ГС объема |
, то |
|||||||||
Последовательность |
|
удобно записывать в виде формального ряда |
|
|||||||||
|
|
|
|
( ) |
∑ |
|
|
|
|
|
||
который называется производящей функцией для данной последовательности. |
|
|||||||||||
Такой рад используется только как краткая запись последовательности |
. Нет необходимости вы- |
|||||||||||
числять значение этого ряда для конкретных значений переменной |
|
. Необходимо лишь выполнить над рядом |
||||||||||
некоторые операции и вычислить коэффициенты при определенных степенях . |
|
|||||||||||
Если |
для |
, то |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
( ) |
∑ |
|
|
|
|
|
||
т.е. ряд является многочленом. |
|
|
|
|
|
|
|
|
|
|||
Если ряд |
( ) сходится в некоторой окрестности , то |
( |
) |
является аналитической функцией в этой |
||||||||
|
|
( )( |
) |
|
|
|
|
|
|
|
||
окрестности и коэффициенты |
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|||
Аналитическая функция – функция, которая совпадает со своим рядом Тейлора. В этом случае ряд |
||||||||||||
|
|
|
|
( ) ∑ |
∑ |
|
( )( |
|
) |
|
||
|
|
|
|
|
|
|
|
|
|
|||
называется рядом Маклорена функции |
( ). |
|
|
|
|
|
|
|
||||
Это позволяет отождествлять ряд и определенную через него аналитическую функцию в случае, если ряд сходится в окрестности , несмотря на то, что ряды трактуются только как формальные последовательности.
Пример:
Производящая функция для последовательности
|
( ) |
|
∑ |
|
|
( |
) |
|
||||
|
|
|
( |
)( ) |
( |
) |
|
|
|
|||
( |
)( |
|
|
|
|
|
|
|
|
|
|
|
|
) |
|
( |
|
)( |
) |
( |
) |
||||
( |
)( |
) |
|
( |
|
)( |
) |
( |
) |
|||
Пример:
Производящая функция для последовательности
( ) |
∑ |
|
|
|
|
|
|
|
|
|
|||
Пример: |
|
|
|
|
|
|
Из формулы Бинома Ньютона следует, что |
|
|
|
|
|
|
∑ |
∑ |
( |
) |
|
||
Т.о., для заданного производящей функцией последовательности |
является ( |
) . |
||||
Пример: |
|
|
|
|
|
|
Производящая функция для последовательности |
|
|
|
|||
( ) ∑ |
∑( ) |
( |
) |
|
||