BSc: IntroductionToCombinatoricsAndDiscreteMathematics

Введение в комбинаторику и дискретную математику

Квалификация выпускника: бакалавр

Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”

Направленность (профиль) образовательной программы: Математические основы ИИ

Программу разработал(а):

1. Краткая характеристика дисциплины

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

2. Перечень планируемых результатов обучения

Целью освоения дисциплины

Задачами дисциплины являются изучение основных правил и концепций комбинаторики для различных прикладных задач.

Общая характеристика результата обучения по дисциплине

Знания: сформированы систематические знания по комбинаторике и дискретной математики.

Умения:

Навыки (владения):

3. Структура и содержание дисциплины

№ п/п	Наименование раздела дисциплины	Содержание дисциплины по темам
1.	Основные правила комбинаторики	- правило сложения - правило умножения - правило дополнения - принцип Дирихле
2.	Основные комбинаторные величины	- размещения с повторениями / без повторений - сочетания с повторениями/ без повторений - перестановки - треугольник Паскаля - линейный город - биномиальный и полиномиальный коэффициент
3.	Тождества с биномиальными коэффициентами	- симметричность - унимодальность - рекуррентное соотношение - Бином Ньютона - сумма биномиальных коэффициентов (в том числе альтернированная) - сумма квадратов биномиальных коэффициентов - сумма степеней натуральных чисел - формула включений и исключений - число беспорядков
4.	Рекуррентные соотношения	- линейные однородные рекуррентные соотношения - л.о.р.с. для степени 2 с разными корнями - л.о.р.с. для степени 2 с кратным корнем - формулировка теоремы в общем случае - числа Фибоначчи - формулировка теоремы для неоднородного случая
5.	Разбиения	- упорядоченные и неупорядоченные разбиения - диаграммы Юнга - теоремы Эйлера о равенстве неупорядоченных разбиений - асимптотика неупорядоченных разбиений
6	Формальные степенные ряды и производящие функции	- формальные степенные ряды - обратимость ряда, пример деления в столбик - доказательство комб. тождеств при помощи формального степенного ряда - производящие функции для рекуррентных соотношений - возведение ряда в степень - числа Каталана

4. Методические и оценочные материалы

Задания для практических занятий:

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1	Основные правила комбинаторики	Принцип Дирихле. Пусть есть $n$ ящиков и $n+1$ кроликов. Если расселить кроликов по ящикам, то найдется хотя бы один ящик, в котором окажутся не менее $2$ кроликов. В мешке имеется $32$ красных шара, $29$ зеленых шаров, $45$ синих, $17$ желтых и по $30$ белых, черных и серых (всего $213$ шаров). Сколько шаров необходимо вынуть из мешка, чтобы среди них гарантированно нашлось $9$ шаров одного цвета? Комиссия из $60$ человек провела $40$ заседаний, причем на каждом заседании присутствовали ровно $10$ членов комиссии. Докажите, что найдутся два члена комиссии, по крайней мере дважды встречавшиеся на заседаниях. В таблице $10\times 10$ расставлены целые числа, причем любые два числа в соседних клетках отличаются не более, чем на $5$. Докажите, что среди этих чисел найдутся два равных. Пусть имеется множество из $M$ слов в алфавите из $k>1$ символа. Докажите, что хотя бы одно из слов не короче $\log _{k}{M}$. В правильном треугольнике со стороной $1$ отмечено пять точек. Докажите, что найдется пара точек, удаленных друг от друга не более, чем на $1/2$.
2	Основные комбинаторные величины	Пусть $A=\{a_{1},\dots ,a_{n}\}$. Извлекать элементы из $A$ можно по порядку или <<пригорошнями>>. Первые называются размещениями, вторые --- сочетаниями. При этом каждое из них бывает как с повторениями символов, так и без. Размещением без повторений называется любой набор различных объектов $b_{1},\dots ,b_{k}\in A$, расположенных друг за другом в определенном порядке. Например, слова «лягушка» и «гуляшка» --- это два разных 7-размещения без повторений букв русского алфавита, хотя состоят они из одних и тех же букв. Размещение с повторениями --- это снова любой набор объектов $b_{1},\dots ,b_{k}\in A$, расположенных друг за другом в определенном порядке. Только теперь объекты в размещении могут совпадать. Например, «жаба» и «абаж» --- два разных 4-размещения с повторениями из букв русского алфавита. Сочетания без повторений отличаются от размещений без повторений тем, что в них порядок объектов значения не имеет. Так, «лягушка» и «гуляшка» представляют собой одно и то же 7-сочетание без повторений букв {л, я, г, у, ш, к, а } русского алфавита. Сочетания с повторениями аналогично, например { ж, а, б, а } = { а, б, а, ж }. Сформулируйте на языке теории множеств что такое размещение с повторениями/ без повторений и сочетания с повторениями (не используя понятий набор и порядок, разрешается использовать все определения из первых двух листков, например: множество, элемент, подмножество, все виды отображений, декартово произведение). Докажите формулу для числа размещений без повторений (если вы будете пользоваться правилом умножения, сформулируйте чётко, какие множества A и B вы используете). (а) Сколько существует шестизначных чисел? (б) Сколько существует шестизначных чисел, делящихся на 5? (в) Сколько существует шестизначных чисел, в записи которых присутствует хотя бы одна чётная цифра? На плоскости отмечено 10 точек так, что никакие три из них не лежат на одной прямой. Сколько существует треугольников с вершинами в этих точках? $20$ балбесов-первокурсников и семинарист пришли в кинотеатр и сели в одном ряду. Семинарист должен сидеть с краю, а Петю, Колю и Васю нельзя сажать втроем. Сколькими способами можно рассадить группу? Из класса, в котором учатся $28$ человек, назначаются на дежурство в столовую $4$ человека. Сколькими способами это можно сделать? Сколько существует способов набрать команду дежурных, в которую попадет ученик этого класса Коля Васин? В группе учатся $20$ студентов. Согласно новому указу Минздрава $75\%$ группы нужно вакцинировать. Сколькими способами это можно сделать? Выяснилось, что один студент этой группы Коля Васин уже провакцинирован. Сколько теперь существует способов исполнить указ Минздрава? У королевы есть $12$ одинаковых зеркал. Сколькими способами их можно повесить в $8$ разных залах замка так, чтобы в каждом зале было хотя бы одно зеркало? В пекарне продавались $4$ вида пирожков: элеши, эчпочмаки, перемячи и кыстыбыи. Сколькими способами можно купить $7$ пирожков? Есть $n$ попарно различных чашек и $n$ неразличимых стаканов. Также имеется $k$ попарно различных ложек и $k$ неразличимых кусков сахара. Сколькими способами можно разложить: а) ложки по чашкам; б) сахар по чашкам; в) ложки по стаканам, если $n=4$? На ютуб-канале есть плейлист из $30$ лекций по ДМ. Сколькими способами их можно переставить так, чтобы а) шесть лекций, прочитанных Даниилом Владимировичем, расположились в правильном порядке (но не обязательно подряд)? б) те же лекции по-прежнему были в правильном порядке, но никакие в) две из них не шли подряд? Сколько имеется способов раздать $11$ разных цветков, трём девушкам: какой-то --- $5$, а остальным~--- по $3$ цветка? Дано множество $A=\{1,\dots ,n\}$. Даны числа $k$, $s$. Сколько можно составить совокупностей из $s$ различных $k$-элементных подмножеств множества $A$? Сколько из этих совокупностей устроены так, что каждое множество в них имеет непустое пересечение с подмножеством $\{1,\dots ,l\}\subset A$? Сколькими способами можно выбрать из полной колоды, содержащей $52$ карты, $6$ карт так, чтобы среди них были все $4$ масти?
3	Тождества с биномиальными коэффициентами	Покажите, что число $k$-сочетаний без повторений из $n$-элементного множества равно а) Количеству последовательностей из 0 и 1 длины $n$ с ровно $k$ единицами. б) (Линейный город) Количеству маршрутов путей из $A$ в $B$, если идти можно только вправо и вверх (стороны прямоугольника $k$ и $n-k$) в) (Треугольник Паскаля) $k$-ому числу в $n$-ой строке треугольника Паскаля (нумерация с $0$) г) (Бином Ньютона) Коэффициенту при мономе $a^{k}b^{n-k}$ в разложении $(a+b)^{n}$. Многие из следующих тождеств/сумм можно доказывать/находить несколькими способами: - через непосредственное определение - при помощи формулы - используя интерпретации выше Докажите следующие тождества при целых неотрицательных$n,k$: а) $C_{n+1}^{k}=C_{n}^{k}+C_{n}^{k-1}$ б) $C_{n}^{k}=C_{n}^{n-k}$ в) $C_{2n}^{n}=(C_{n}^{0})^{2}+\ldots +(C_{n}^{n})^{2}$ Найдите суммы при целых неотрицательных $n,k,m$ : а) $C_{n}^{0}+\ldots +C_{n}^{n};$ б) $C_{n}^{0}-C_{n}^{1}+\ldots +(-1)^{n}C_{n}^{n};$ в) $C_{n}^{0}+C_{n}^{2}+C_{n}^{4}+\ldots$ г*) $C_{n}^{0}+C_{n}^{3}+C_{n}^{6}+\ldots$ д) $C_{n}^{1}+2C_{n}^{2}+3C_{n}^{3}+\ldots +nC_{n}^{n};$ е) $C_{n}^{0}+{\frac {1}{2}}C_{n}^{1}+{\frac {1}{3}}C_{n}^{2}+\ldots +{\frac {1}{n+1}}C_{n}^{n};$ ж) $C_{n}^{n}+C_{n+1}^{n}+\ldots +C_{n+m}^{n};$ з) $C_{n}^{k}+C_{n+1}^{k}+\ldots +C_{n+m}^{k};$ и) $C_{n}^{k}+C_{n+1}^{k+1}+\ldots +C_{n+m}^{k+m};$ к) $C_{n}^{0}C_{m}^{k}+C_{n}^{1}C_{m}^{k-1}+\ldots +C_{n}^{k}C_{m}^{0};$ л) $(C_{n}^{1})^{2}+2(C_{n}^{2})^{2}+3(C_{n}^{3})^{2}+\ldots +n(C_{n}^{n})^{2};$ м*) $C_{2n}^{n}+2C_{2n-1}^{n}+4C_{2n-2}^{n}+\ldots +2^{n}C_{n}^{n};$ н*) $C_{2n}^{0}-C_{2n-1}^{1}+C_{2n-2}^{2}+\ldots +(-1)^{n}C_{n}^{n}.$ Найдите $\sum _{(n_{1},n_{2},n_{3}),n_{1}+n_{2}+n_{3}=5,n_{i}\in \mathbb {N} }P(n_{1},n_{2},n_{3})(-1)^{n_{1}+n_{2}}$. Посчитайте коэффициенты при $x^{57}$ и $x^{57}$ в разложении $(x^{2}+x^{7}+x^{9})^{20}$. На оси абсцисс разместим (произвольным образом) 2n точек, разобьем множество этих точек на пары (опять-таки, произвольно) и элементы каждой пары соединим дугой, так, как это показано на рисунке. Получившийся объект назовем хордовой диаграммой. Сколько существует различных хордовых диаграмм на 2n точках? Найдите количество чисел, не превосходящих $1001$ и не делящихся ни на одно из чисел $7$, $11$, $13$. Пусть $\varphi (n)$ --- функция Эйлера, то есть количество натуральных чисел от $1$ до $n$, взаимно простых c $n$. Найдите $\varphi (1)$; $\varphi (p)$; $\varphi (p^{2})$; $\varphi (p^{\alpha })$, где $p$ --- простое число, $\alpha >2$. $\varphi (n)=n(1-{\frac {1}{p_{1}}})\ldots (1-{\frac {1}{p_{s}}})$, где $n=p_{1}^{\alpha _{1}}\cdot \ldots \cdot p_{s}^{\alpha _{s}}$ --- каноническое разложение числа $n$. В комнате площади $6$ уложены три ковра площади $3$ каждый (форма комнаты и ковров произвольная). Докажите, что какие-то два из этих трёх ковров перекрываются по площади, не меньшей~$1$. На кафтане расположено пять заплат произвольной формы. Площадь каждой из них больше половины площади кафтана. Тогда площадь общей части некоторых двух заплат большей одной пятой площади кафтана. (Число беспорядков) На полке стоят 10 книг. Сколькими способами их можно переставить так, чтобы (а) ни одна книга не осталась на своем месте? (б) на месте осталось ровно 4 книги? Сколькими способами можно расселить 20 туристов по 5 домикам, чтобы ни один домик не оказался пустым? Сколько существует различных сюръекций из множества X = {1, . . . , k} во множество Y = {1, . . . , n}? Сколько существует неупорядоченных разбиений k-элементного множества на n подмножеств? В ряд записали 105 единиц, поставив перед каждой знак «+» . Сначала изменили знак на противоположный перед каждой третьей единицей, затем — перед каждой пятой, а затем — перед каждой седьмой. Найдите значение полученного выражения. 7 ◦ . Сколько существует перестановок чисел от 1 до 7, при которых никакие два рядом расположенных числа не отличаются на 1? [Задача о мажордомах] К обеду за круглым столом приглашены n пар враждующих рыцарей. Требуется рассадить их так, чтобы никакие два врага не сидели рядом. Сколько существует таких рассадок? [Задача о паросочетаниях] За круглым столом нужно рассадить n супружеских пар. Сколькими способами это можно сделать, если требуется, чтобы мужчины и женщины чередовались и чтобы ни один муж не сидел рядом со своей женой?
4	Рекуррентные соотношения	Для каждого из следующих линейных рекуррентных соотношений найдите общее решение: а) $a_{n+2}-7a_{n+1}+12a_{n}=0;$ б) $a_{n+3}-2a_{n+2}-4a_{n+1}+8a_{n}=0$; в) $a_{n+2}+a_{n+1}+a_{n}=0;$ г) $a_{n+2}-9a_{n}=0;$ д) $a_{n+3}+3a_{n+2}+3a_{n+1}+a_{n}=0;$ е) $a_{n+3}+5a_{n+2}+12a_{n+1}+8a_{n}=0$. Найдите решение неоднородного линейного рекуррентного соотношения а) $a_{n+2}=a_{n+1}+a_{n}+1$; б) $a_{n+2}=2a_{n+1}-a_{n}+n+1$; в) $a_{n+2}=a_{n+1}+6a_{n}+3^{n}$? Числами Фибоначчи называется последовательность $F_{n},n\geqslant 0$, удовлетворяющая соотношениям $F_{0}=0$, $F_{1}=1$, $F_{n}=F_{n-1}+F_{n-2}$ для всех натуральных $n>1$. Найдите формулу для нахождения $n$-ого члена последовательности $F_{n}$. Найдите $F_{0}+F_{1}+\ldots +F_{n}$; $F_{0}^{2}+F_{1}^{2}+\ldots +F_{n}^{2}$; $F_{0}^{3}+F_{1}^{3}+\ldots +F_{n}^{3}$. Сколькими способами можно разменять купюру в $100$ рублей на монеты достоинством $1$, $2$ и $5$ рублей? %364 Найдите рекуррентное соотношение для последовательности $A_{n}$, где $A_{n}$ -- число способов выложить прямоугольник размера $n\times 3$; $n\times 4$ доминошками размера $1\times 2$; число способов выложить колонну $2\times 2\times n$ кирпичами размера $2\times 1\times 1$. Сколько существует строк из $20$ нулей и единиц, в каждой из которых никакие два нуля не стоят рядом? Докажите, что последовательность с общим членом $a_{n}=n^{k-1}$ удовлетворяет соотношению $a_{n+k}-C_{k}^{1}a_{n+k-1}+C_{k}^{2}a_{n+k-2}-\ldots +(-1)^{k}C_{k}^{k}a_{n}=0$. В вершине B шестиугольника ABCDEF сидит лягушка. Каждую секунду лягушка может перепрыгнуть в одну из соседних вершин. Сколькими способами она может допрыгнуть до вершины A за n прыжков? В центральной клетке левого столбца доски 1000 × 3 стоит шахматный король. Сколькими спо[1]собами он может добраться до правого столбца доски за 999 ходов?
5	Разбиения	а) Найдите количество упорядоченных разбиений числа $n$ на $k$ слагаемых. б) Найдите общее количество упорядоченных разбиений числа $n$ на слагаемые. в) Какой ответ будет в предыдущих пунктах, если мы разрешим слагаемым принимать значение $0$? Обозначим через $f(n;n_{1},\ldots ,n_{k})$ ($F(n;n_{1},\ldots ,n_{k})$) количество упорядоченных (соотв. неупорядоченных) разбиений $n$ на слагаемые $n_{1},\ldots ,n_{k}$. Справедливы следующие рекуррентные формулы а) $f(n;n_{1},\ldots ,n_{k})=f(n-n_{1};n_{1},\ldots ,n_{k})+f(n-n_{2};n_{1},\ldots ,n_{k})+\ldots +f(n-n_{k};n_{1},\ldots ,n_{k})$; б) $F(n;n_{1},\ldots ,n_{k})=F(n-n_{1};n_{1},\ldots ,n_{k})+F(n;n_{2},\ldots ,n_{k})$. в) Каковы начальные условия в этих формулах? а) Что больше: $f(20;1,4,6,9)$ или $F(20;1,4,6,9)$? б) Найдите оба числа, используя рекуррентные формулы. Диаграмма Юнга -- это конечный набор клеток, выровненных по левой границе, в котором длины строк образуют невозрастающую последовательность (каждая строка такой же длины как предыдущая, или короче). Весом диаграммы Юнга называется общее количество клеток диаграммы. Набор чисел, состоящий из длин строк, задаёт разбиение веса диаграммы в сумму слагаемых. Таким образом, есть соответствие между всеми неупорядоченными разбиениями натурального числа $n$ и всеми диаграммами Юнга веса $n$. Сколько существует диаграмм Юнга произвольного веса, но имеющих не более $p$ строк и не более $q$ столбцов? На доске написано несколько целых положительных чисел: $a_{0}$, $a_{1}$, $a_{2}$, $\ldots$, $a_{n}$. Пишем на другой доске следующие числа: $b_{0}$ --- сколько всего чисел на первой доске, $b_{1}$ --- сколько там чисел, больших единицы, $b_{2}$ --- сколько там чисел, больших двойки, и т.~д., пока получаются положительные числа. На этом заканчиваем --- нули не пишем. На третьей доске пишем числа $c_{0}$, $c_{1}$, $c_{2}$, $\ldots$, построенные по числам второй доски аналогичным образом. Докажите, что наборы чисел на первой и третьей досках совпадают. Докажите, что число неупорядоченных разбиений $a-b$ на $c-1$ слагаемых, не превосходящих $b$, равно числу неупорядоченных разбиений $a-c$ на $b-1$ слагаемых, не превосходящих $c$. Верно ли, что число неупорядоченных разбиений числа $n$ на $k$ слагаемых равно числу неупорядоченных разбиений числа $n$ на слагаемые, максимальное из которых равно $k$? Докажите, что количество неупорядоченных разбиений $n$ на различные нечётные слагаемые равно количеству симметричных диаграмм Юнга веса $n$. Какие натуральные числа можно разбить в сумму нескольких (больше одного) подряд идущих натуральных чисел?
6	Формальные степенные ряды и производящие функции	Рассмотрим множество последовательностей $(a_{0},a_{1},\ldots ,a_{n},\ldots )$ (здесь $a_{i}$ берутся из множества чисел $\mathbb {Q}$, $\mathbb {R}$ или $\mathbb {C}$) и введём на них операции сложения и умножения следующим образом: $(a_{0},a_{1},\ldots )+(b_{0},b_{1},\ldots )=(a_{0}+b_{0},a_{1}+b_{1},\ldots );$ $(a_{0},a_{1},\ldots )\cdot (b_{0},b_{1},\ldots )=(c_{0},c_{1},\ldots ){\text{, где }}c_{n}=\sum _{j=0}^{n}a_{j}\cdot b_{n-j};$ Пусть $1=(1,0,0,\ldots ,0,\ldots )$, $t=(0,1,0,\ldots ,0,\ldots )$. 1) Найдите $t^{2},t^{3},\ldots ,t^{n}$. 2) Покажите, что любая последовательность $(a_{0},a_{1},\ldots ,a_{n},\ldots ,)$ единственным образом представляется в виде $a_{0}\cdot 1+a_{1}\cdot t+a_{2}\cdot t^{2}+\ldots +a_{n}\cdot t^{n}+\ldots$. Покажите, что все свойства многочленов (коммутативность по сложению/умножению, ассоциативность, дистрибутивность) переносятся на формальные степенные ряды. Пусть дан ряд $f(t)$. Корректна ли операция подстановки вместо $t$ ряда $g(t)$? Ряда $g(t)$ без свободного члена? Определим производную формального степенного ряда $A=a_{0}\cdot 1+a_{1}\cdot t+\ldots +a_{n}\cdot t^{n}+\ldots$ как ряд $A'=a_{1}+2a_{2}t+\ldots +na_{n}t^{n-1}+\ldots$. Производную можно брать несколько раз подряд, через $A^{(n)}$ обозначается $n$-ая производная ряда $A$. Производная линейна, то есть $(\alpha A+\beta B)'=\alpha A'+\beta B'$ (здесь $\alpha ,\beta \in \mathbb {R}$, $A,B$ --- формальные степенные ряды). Выполнено тождество Лейбница, то есть $(AB)'=A'B+AB'$. (Ряд Тейлора в нуле). Докажите, что $a_{n}$ --- свободный член ряда ${\frac {A^{(n)}}{n!}}$. Пусть $F=1+t+t^{2}+\dots$, $G=1-t+t^{2}-t^{3}+\dots$. Найдите $F+G$, $F\cdot G$. Пусть $F=\sum _{k=0}^{\infty }{\frac {1}{k!}}t^{k}$, $G=\sum _{k=0}^{\infty }{\frac {(-1)^{k}}{k!}}t^{k}$. Найдите $F\cdot G$ и $F^{2}$. Существует ли два таких ненулевых степенных ряда $F,G$, что $F\cdot G=F+G$? Ряд $G$ называется обратимым, если существует такой ряд $F$, что $F\cdot G=1$. $F$ называется рядом, обратным к $G$ и обозначается так: $F=G^{-1}$. Докажите, что ряд $G=a_{0}+a_{1}t+a_{2}t^{2}+a_{3}t^{3}+\dots$ обратим тогда и только тогда, когда $a_{0}\neq 0$, причём обратный ряд $G^{-1}$ единственен. Найдите коэффициенты ряда ${\frac {1}{1-t}}$; ${\frac {1}{2-t}}$; ${\frac {1}{3+4t}}$; ${\frac {1}{(1-t)^{2}}}$; ${\frac {1}{(1-t)^{m}}}$. Верно ли равенство $\left({\frac {1}{1-t}}\right)^{2}\cdot \left({\frac {1}{1+t}}\right)^{2}=\left({\frac {1}{1-t^{2}}}\right)^{2}$ для формальных степенных рядов? Сформулируйте комбинаторное тождество, получаемое при приравнивании коэффициентов в этих рядах. При каких условиях на степенной ряд $F$ его можно разделить на степенной ряд $G$ (то есть уравнение $G\cdot X=F$ разрешимо относительно неизвестного степенного ряда $X$)? При каких условиях на степенной ряд $F$ разрешимо уравнение $X^{2}=F$? Пусть $X=\sum _{k=0}^{\infty }\alpha _{k}t^{k}$ ---- степенной ряд, задаваемый уравнением $X^{2}=1+t$. Найдите коэффициенты $\alpha _{0},\alpha _{1},\alpha _{2},\alpha _{3}$. Пусть $\alpha \in \mathbb {R}$. Положим $C_{\alpha }^{n}={\frac {\alpha \cdot (\alpha -1)\cdot \ldots \cdot (\alpha -n+1)}{n!}}$. Если $\alpha \in \mathbb {N} ,\alpha \geq n$, то $C_{\alpha }^{n}$ совпадает с биномиальным коэффициентом. Определим ряд $(1+t)^{\alpha }=\sum _{n=0}^{\infty }C_{\alpha }^{n}t^{n}$. Покажите, что при $\alpha \in \mathbb {N}$ определения согласованы. Покажите, что $(1+t)^{\alpha }\cdot (1+t)^{\beta }=(1+t)^{\alpha +\beta }$. Используя определение, найдите коэффициенты ряда $(1+t)^{\frac {1}{2}}$. Сравните ответ с ответом в задаче предыдущей задаче пункте в. Вычислите $\sum _{k=0}^{n}k^{2}C_{n}^{k}{({\frac {1}{17}})}^{k}$. Вычислите $\sum _{k=0}^{\infty }{\frac {F_{n}}{2^{n}}}$ ($F_{n}$ --- числа Фибоначчи). Как выглядит производящая функция для числа способов набрать $n$ рублей монетами достоинством $1$, $2$ и $5$ рублей? Тот же вопрос, при условии, что есть всего три 5-рублёвые монеты. Найдите производящую функцию для числа упорядоченных разбиений числа $n$; неупорядоченных разбиений $n$; неупорядоченных разбиений $n$ на нечётные слагаемые; неупорядоченных разбиений $n$ на попарно различные слагаемые. Докажите, что функции в последних двух пунктах совпадают. Докажите тождество $4^{n}=\sum \limits _{i=0}^{n}C_{2i}^{i}\cdot C_{2(n-i)}^{n-i}$. Найдите радиус сходимости ряда $\sum _{n=0}^{\infty }t^{n}$, $\sum _{n=0}^{\infty }(-1)^{n}\cdot t^{n}$, $\sum _{n=0}^{\infty }\lambda ^{n}t^{n}$, ${\frac {1}{1-t^{2}}}$. Приведите пример, когда на границе ряда (то есть при $|t|=R$) есть сходимость в обеих точках; $\sum _{n=0}^{\infty }$ расходимость в обеих точках; $\sum _{n=0}^{\infty }$ сходимость в одной точке и расходимость в другой точке. Найдите производящую функцию для последовательности $a_{n}=C_{1}\lambda _{1}^{n}+C_{2}\lambda _{2}^{n}$. \pu Какой у неё радиус сходимости? В каких точках действительной прямой сходится ряд $\sum \limits _{n=0}^{\infty }a_{n}t^{n}$, где $a_{n}$ задано следующим образом? $a_{n}={\begin{cases}3\cdot (-6)^{n}+4\cdot 3^{n},&n=3k,k\in \mathbb {N} ;\\5\cdot \left(-{\frac {1}{4}}\right)^{n}+2\cdot 2^{n},&n=3k+1,k\in \mathbb {N} ;\\6\cdot (-3)^{n},&n=3k+2,k\in \mathbb {N} .\end{cases}}$

Текущий контроль успеваемости обучающихся по дисциплине:

№ п/п	Наименование раздела дисциплины	Форма текущего контроля	Материалы текущего контроля
1	Основные правила комбинаторики	Письменная контрольная	На кафедре дискретной математики лежит стопка 63 непроверенных контрольных работ студентов из четырёх разных групп: 20 работ из 312, 15 работ из 323, 18 работ из 324 и 10 работ из 325. Семинарист хочет взять наугад несколько работ на проверку. Какое минимальное количество работ необходимо взять, чтобы среди них гарантированно нашлось а) 4 работы из одной группы; б) 4 работы из 323 группы; в) 2 работы из одной группы и 2 работы из другой группы; г) по одной работе из каждой из четырёх групп? В этой задаче каждый пункт оценивается в 1 балл. 27 точек образуют прямоугольник размер $3\times 9$. Каждая точка покрашена в красный или синий цвет. Докажите, что существуют 4 точки одного цвета, образующие одноцветный прямоугольник (со сторонами, параллельными исходному прямоугольнику). При каком минимальном значении $m$ для прямоугольника из $6\times m$ точек, покрашенных в пять цветов, гарантированно найдётся одноцветный прямоугольник?
2	Основные комбинаторные величины	Письменная контрольная	Даны множества $A,B$, причём $|A|=4$, $|B|=7$. Найдите количество таких соответствий $f:A\to B$, что: а) $f^{-1}$ --- сюръективное отображение; б) $f^{-1}$ --- сюръективное соответствие; в) $f$ --- инъективное соответствие; г) $f$ --- инъективное отображение. В этой задаче каждый пункт оценивается в 2 балла. Ответ надо дать в виде суммы не более 10 слагаемых, без использования чисел сочетаний/размещений/полиномиальных коэффициентов Имеется 4 коробки (красная, синяя, желтая, зеленая), и 9 шаров (3 красных, 2 синих, и по одному желтому, зеленому, фиолетовому и белому). Сколькими способами можно разложить шары по коробками, если нужно чтобы в каждой коробке что-то лежало? Ответ дайте в виде суммы не более 10 слагаемых, без использования знаков вида $C_{*}^{*}$, $A_{*}^{*}$, $P(*,*,*)$
3	Тождества с биномиальными коэффициентами	Письменная контрольная	Напишите коэффициент у данного монома в данном разложении (Ответ надо дать в виде суммы не более 10 слагаемых, разрешается использовать символ $P(*,*,*)$): а) $x^{25}$ в $(x^{2}+x^{4}-x^{7})^{10}$; б) $x^{26}$ в $(x^{2}+x^{4}-x^{7})^{10}$; в) $x^{27}$ в $(x^{2}+x^{4}-x^{7})^{10}$. Докажите тождество: $\sum _{k=r}^{n}C_{n}^{k}\cdot C_{k}^{r}\cdot 3^{k}=C_{n}^{r}\cdot 3^{r}\cdot 4^{n-r}$ 20 студентов (студенты разные) сдают экзамен в три дня. Студент может прийти в один из дней, а может и не прийти вовсе (неявка). Сколько существует различных распределений студентов по дням, таких чтобы а) все студенты пришли на экзамен; б) в первый день пришёл хотя бы один студент; в) в каждый из дней пришли ровно 5 студентов? Теперь предположим, что экзамен длится 7 дней, а каждый студент имеет несколько попыток. Сколько существует различных распределений студентов по дням, таких чтобы г) каждый студент пришёл на экзамен трижды, причём в разные дни; д) каждый студент пришёл на экзамен трижды, но теперь необязательно в разные дни? В ответах разрешается использовать только знаки арифметических действий, возведение в степень, а также факториалы, $C_{\ast }^{\ast }$, $A_{\ast }^{\ast }$ и $P(\ast ,\ldots ,\ast )$. Хитрый пароль состоит из двух частей. Первая часть --- код из 4 цифр, в которых как минимум две чётные цифры. Вторая часть --- код из 7 различных цифр, из которых первые 4 идут по возрастанию, а оставшиеся 3 по убыванию. Сколько существует хитрых паролей? Ответ разрешается оставить в виде суммы нескольких слагаемых (без троеточий) с использованием факториалов, $C_{\ast }^{\ast }$, $A_{\ast }^{\ast }$ и $P(\ast ,\ldots ,\ast )$
4	Рекуррентные соотношения	Письменная контрольная	Имеется алфавит из 6-х символов $\{a,b,c,d,e,f\}$. Обозначим через $A_{n}$ количество последовательностей длины $n$, которые содержат нечётное количество символов $a$. Найдите и решите рекуррентное соотношение для $A_{n}$. В наличии имеются плитки размеров $1\times 1$, $1\times 2$ нескольких типов. Для каждого набора плиток найдите рекуррентное соотношение для $a_{n}$, количества способов выложить плитку размером $1\times n$ и выпишите явную формулу для решения Заполните таблицу. набор плиток рекуррентное соотношение 2-го порядка явная формула 1 вид плитки размера $1\times 1;$ $a_{n+2}=a_{n+1}+a_{n},\ a_{1}=1,\ a_{2}=2$ ${\frac {1+{\sqrt {5}}}{2{\sqrt {5}}}}\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-{\frac {1-{\sqrt {5}}}{2{\sqrt {5}}}}\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}$ 1 вид плитки размера $1\times 2$ 2 вида плитки размера $1\times 1;$ 1 вид плитки размера 1 $\times 2$ 2 вида плитки размера $1\times 1;$ 3 вида плитки размера 1 $\times 2$
5	Разбиения	Письменная контрольная	Обозначим через $f(n;n_{1},\ldots ,n_{k})$ количество упорядоченных разбиений $n$ на слагаемые $n_{1},\ldots ,n_{k}$, а через $F(n;n_{1},\ldots ,n_{k})$ количество неупорядоченных разбиений $n$ на слагаемые $n_{1},\ldots ,n_{k}$. Найдите а) $f(9;1,2,3,4,5,6,7,8,9)$; б) $f(11;1,3,5,7,9)$; в) $F(10;1,3,5,7,9)$. Задача (10) Пусть $B$ есть число способов представить число $100$ в виде суммы нескольких различных элементов множества $\{1,2,3,\ldots ,100\}$ и такого же числа различных элементов множества $\{0,1,2,\ldots ,99\}$. [Например, есть представления $(1+2)+(0+97)$, $(1)+(99)$, $(1+2+3)+(2+4+88)$.] Сравните $B$ и $p(100)$, последнее -- это количество неупорядоченных разбиений числа $100$. Пусть $B$ есть число способов представить число $100$ в виде суммы нескольких различных элементов множества $\{1,2,3,\ldots ,100\}$ и такого же числа различных элементов множества $\{0,1,2,\ldots ,99\}$. [Например, есть представления $(1+2)+(0+97)$, $(1)+(99)$, $(1+2+3)+(2+4+88)$.] Сравните $B$ и $p(100)$, последнее --- это количество неупорядоченных разбиений числа $100$.
6	Формальные степенные ряды и производящие функции	Письменная контрольная	Вычислите производящую функцию для следующих последовательностей. Преобразуйте формальный степенной ряд к отношению многочленов. последовательность $a_{n}$ производящая функция числа Фибоначчи $0,1,1,2,\ldots$ ${\frac {t}{1-t-t^{2}}}$ количество положительных целых решений $(a,b)$ уравнения $a+b=n$ количество неотрицательных целых решений $(a,b,c)$ уравнения $a+b+c=n$ количество целых решений $(a,b,c)$ уравнения $a+b+c=n$, с условиями $0\leq a\leq 6$, $0\leq b\leq 3$, $0\leq c\leq 1$ Найдите радиус сходимости у следующих формальных степенных рядов. а) ${\frac {1}{1+4t}}$; б) ${\frac {4}{1+9t}}$; в) ${\frac {2t^{2}}{(1+9t^{2})^{2}}}$; г) ${\frac {1}{(t-2023)^{2023}}}$; д) ${\frac {1}{\sqrt {1-3t}}}$. Найдите коэффициент при $x^{2023}$ у следующих формальных степенных рядов. а) ${\frac {1}{1+4t}}$; б) ${\frac {4}{1+9t}}$; в) ${\frac {2t^{2}}{(1+9t^{2})^{2}}}$; г) ${\frac {1}{(t-2023)^{2023}}}$; д) ${\frac {1}{\sqrt {1-3t}}}$.

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

№ п/п

Наименование раздела дисциплины

Вопросы

Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

1. Правило сложения. Правило умножения. Примеры: автомобильные номера, количество шестизначных чисел с различными условиями на цифры (задача 7.3). Принцип Дирихле. Пример на принцип Дирихле с квадратом.

2. Размещения, перестановки и сочетания. Доказательство формул для чисел размещения и сочетания с повторениями и без повторений. Типовые задачи (аналогичные 7.5, 7.6, 7.7, 7.8).

3. Бином Ньютона. Полиномиальный коэффициент и полиномиальная формула. Типовые задачи (аналогичные задачам 7.10, 8.5).

4. Комбинаторные тождества (6 штук).

5. Формула включений и исключений (формулировка и док-во для $n=3$). Формула для количества беспорядков на $n$ элементах (Задача 9.4 про перестановки книг).

6. Формула включений и исключений (формулировка и док-во для $n=3$). Формула для количества сюръекций из $k$-элементного множества в $m$-элементное (Задача 9.5 про домики).

7. Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Рекуррентные формулы. (Задача 12.2 а)б)).

8. Задачи о разбиениях чисел на слагаемые. Упорядоченные разбиения. Количество всех упорядоченных разбиений на произвольные слагаемые. (Задача 12.1 а)б)).

9. Диаграммы Юнга. Теоремы Эйлера о равенстве количеств неупорядоченных разбиений числа $n$ на $k$ или не более, чем $k$ слагаемых (3 штуки).

10. Линейные рекуррентные соотношения с постоянными коэффициентами. Характеристическое уравнение. Общая формула для соотношения $n$-го порядка (формулировка, частный случай $n=2$ --- б/д). Формула для чисел Фибоначчи.

11. Формальные степенные ряды, операции над ними. Пример вычисления суммы и произведения (Задача 14.3).

12. Формальные степенные ряды. Определение обратного ряда. Пример деления в столбик. Примеры нахождения обратных рядов (задача 14.6).

13. Числа Фибоначчи и их производящая функция. Радиус сходимости, значение $\sum _{n=0}^{\infty }{\frac {F_{n}}{2^{n}}}$.

14. Числа Каталана. Производящая функция для чисел Каталана.

15. Задача о раскраске множества в два цвета.

16. Сумма степеней натуральных чисел.

17. Знакопеременные тождества (2 штуки): сумма биномиальных коэффициентов и количество сюръекций.

18. Формула включений и исключений.

19. Формула включений и исключений (формулировка и док-во для $n=3$). Формула для функции Эйлера через произведение по простым сомножителям (док-во через формулу вкл-искл.) (Задача 9.1в.)

20. Формула обращения Мёбиуса.

21. Функция Эйлера. Формула с произведением по простым числам: доказательство при помощи формулы обращения Мёбиуса (Задача 10.6в).

22. Линейные рекуррентные соотношения с постоянными коэффициентами. Характеристическое уравнение. Общая формула для соотношения 2-го порядка с одинаковыми корнями характеристического уравнения.

23. Линейные рекуррентные соотношения с постоянными коэффициентами. Характеристическое уравнение. Общая формула для соотношения 2-го порядка с различными корнями характеристического уравнения.

24. Формальный степенной ряд $(1-x)(1-x^{2})(1-x^{3})\ldots$. Теорема Эйлера о коэффициентах этого ряда (формулировка). Проверка верности теоремы Эйлера для $k=1,2$. Теорема о количестве разбиений на чётное и нечётное количество различных слагаемых (формулировка).

25. Формальные степенные ряды. Строгое формальное определение через последовательности. Пример вычисления суммы и произведения рядов (Задача 14.3)

26. Формальные степенные ряды, операции над ними. Определение обратного ряда. Пример деления в столбик. Комбинаторное тождество, получаемое с использованием формального степенного ряда ${\frac {1}{(1-x^{2})^{2}}}$.

27. Формальные степенные ряды, операции над ними. Определение обратного ряда. Критерий обратимости ряда (задача 14.5).

28. Вычисление суммы $\sum _{k=0}^{n}k^{2}C_{n}^{k}\left({\frac {1}{17}}\right)^{k}$.

29. Определение радиуса сходимости формального степенного ряда. Теорема Коши-Адамара о сходимости степенных рядов (формулировка). Примеры, иллюстрирующие теорему (3 примера, показывающие, что на границе может быть сходимость/расходимость, задача 15.2).

30. Принцип Дирихле. Оценки мощности множества попарно неортогональных $(-1,0,1)$-векторов: верхняя оценка величиной 140 и нижняя оценка величиной 70.

31. Числа Каталана. Формула для коэффициентов ряда ${\sqrt {1+x}}$. (Задача 14.9)

32. Числа Каталана. Формула для коэффициентов ряда ${\sqrt {1+x}}$ (б/д). Вывод из неё формулы для чисел Каталана.

33. Производящая функция для количества неупорядоченных разбиений в общем виде и для разбиений специального вида (задача 15.10). Доказательство того, что количества разбиений на попарно различные слагаемые и на нечётные слагаемые совпадают.

Перечень учебно-методического обеспечения дисциплины

Список основной литературы:

Список дополнительной литературы:

Методические указания для обучающихся по освоению дисциплины

Вид учебных занятий/деятельности	Деятельность обучающегося
Лекция	Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практическое (семинарское) занятие	При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его. Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
Устный/письменный опрос	Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
Контрольная работа	При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.

Методы и технологии обучения, способствующие формированию компетенции

Методы и технологии обучения, способствующие формированию компетенции

Информационно – коммуникационная технология, Педагогика сотрудничества, Традиционные технологии, Модульная технология