Отговор_Зачет_Комбинаторика
Лекции по курса "Комбинаторен анализ"
Семестър 3 Лектор: Доцент от катедрата на ВМИК Орехов Емил Юриевич
Основни правила на комбинаториката.
Теорема 1. Основна теорема на комбинаториката (правило за произведение).
Теорема 2. Правило за суми.
Поръчано извличане (SAR) .
Поръчано вземане на проби без подмяна (UVBV).
Извънредно вземане на проби без подмяна (NVBF).
Неподредено вземане на проби с връщане (OIR) .
Схема на пробовземния контрол.
Принципът на включване и изключване.
Теорема "Принцип на включване и изключване".
Операции върху генериращи функции.
Генериращи функции за HB.
Генериращи функции за SW.
Решение на рекурентни отношения.
Разлагане на правилно рационална дроб на елементарни дроби. .
Числа на Стърлинг от първи вид.
Числа на Стърлинг от втори род.
Разлагане на обекти в клетки.
1 Поставяне на различни обекти в различни клетки .
2 Поставяне на неразлични обекти в различни клетки.
3 Поставяне на различни обекти в различни клетки.
4 Поставяне на неразлични обекти в неразлични клетки.
Яблонски С.В. „Въведение в дискретната математика“ Липски В. „Комбинаторика за програмисти“ Хол М. „Комбинаторика“ Риордан Дж. „Въведение в комбинаторния анализ“
Ezhov I.I. "Елементи на комбинаториката" Rybnikov K.A. "Въведение в комбинаторния анализ"
Рибников К. А. „Комбинаторен анализ. Задачи и упражнения „Семенов А.С. „Четири лекции по комбинаторика: насоки“ Lando S.K. "Лекции по генериращи функции" Кофман А. "Въведение в приложната комбинаторика"
Комбинаториката е дял от математиката, който изучава крайни или преброими дискретниобекти (набори от последователности)
Основи на комбинаториката. Основни правила на комбинаториката
Теорема 1. Основна теорема на комбинаториката (правило за произведение)
Нека са дадени крайни множества:
Вземайки по един елемент от всяко множество, образуваме подредено множество
броят на такива набори.
Доказателството е чрез индукция върху количеството
се състои от един елемент (
) и ще има толкова много такива набори, колкото са
елементи в комплекта
всеки е логичен
различни двойки с елементи от комплекта
Следователно ще има общо такива двойки
че теоремата е вярна за всички
различни набори от формата (
Помислете сега за случая, когато
. Имайте предвид, че всеки набор от формуляра (
където е първият елемент
елементи. Следователно, аналог
получаваме, че двойката от посочения тип ще бъде (
. Тези. набори изглед на източник
Теорема 2. Правило за суми
Нека са дадени крайни несвързани множества:
от , т.е. точно един елемент от един
много възможни
Очевидно изборът на един елемент от едно множество е еквивалентен на избора на един елемент от общото
единството на тези множества
. Тази асоциация съдържа
елементи. Следователно може да се направи избор на един елемент
Нека има набор, съдържащ елементи, от които се предполага, че се избират отделни елементи. Този набор се нарича генерална съвкупност (по-нататък GS) на обема.
Нека извършим последователен подбор на елементи от ХС. Получената последователност от елементи се нарича
е извадка от тома.
Изборът на елемент от ХС може да стане по два начина
1) След екстракцията избираемият елемент не се връща в ХС.Получената последователност от елементи
ченгета се нарича вземане на проби без връщане.
2) След извличане избраният елемент се връща в GS и може да бъде избран повторно. Получената последователност от елементи се нарича обратно извличане.
Поръчано извличане (SAR)
Ще се формира поръчана извадка, като връщането на обема от обема на GS ще бъде от етапите:
първият елемент на извадката от HS на набора от мощности.
вторият елемент на извадката от GS на силовия комплект .
примерен елемент от GS на силовия комплект .
В съответствие с основната теорема на комбинаториката, формирането на извадка може да се извърши, т.е. начини.
Пример: колко различни думи от 5 букви могат да бъдат направени с помощта на 10 букви от азбуката.
Поръчан избор без замяна (UVBV)
Поръчана проба без връщане на обема от обема GS ще бъде формирана от следните стъпки:
първият елемент на извадката от HS на набора от мощности.
вторият елемент на извадката от ХС на силовия комплект
примерен елемент от GS на силовия комплект
съответствие с основното
с помощта на комбинаторната теорема може да се направи вземане на проби