BSc: IntroductionToCombinatoricsAndDiscreteMathematics

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

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

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

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

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

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

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

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

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

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

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

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

Умения:

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

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

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

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

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

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
	Основные правила комбинаторики	Принцип Дирихле.' Пусть есть $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$.
	Основные комбинаторные величины	Пусть $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$ масти?
	Тождества с биномиальными коэффициентами	\i Покажите, что число $k$-сочетаний без повторений из $n$-элементного множества равно а) Количеству последовательностей из 0 и 1 длины $n$ с ровно $k$ единицами. б) (Линейный город) Количеству маршрутов путей из $A$ в $B$, если идти можно только вправо и вверх (стороны прямоугольника $k$ и $n-k$) в) (Треугольник Паскаля) $k$-ому числу в $n$-ой строке треугольника Паскаля (нумерация с $0$) г) (Бином Ньютона) Коэффициенту при мономе $a^{k}b^{n-k}$ в разложении $(a+b)^{n}$. Многие из следующих тождеств/сумм можно доказывать/находить несколькими способами: - через непосредственное определение - при помощи формулы - используя интерпретации выше \i Докажите следующие тождества при целых неотрицательных$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}$ \i Найдите суммы при целых неотрицательных $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 супружеских пар. Сколькими способами это можно сделать, если требуется, чтобы мужчины и женщины чередовались и чтобы ни один муж не сидел рядом со своей женой?
	Рекуррентные соотношения	Для каждого из следующих линейных рекуррентных соотношений найдите общее решение: а) $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 ходов?
	Разбиения	\i а) Найдите количество упорядоченных разбиений числа $n$ на $k$ слагаемых. б) Найдите общее количество упорядоченных разбиений числа $n$ на слагаемые. в) Какой ответ будет в предыдущих пунктах, если мы разрешим слагаемым принимать значение $0$? Обозначим через $f(n;n_{1},\ldots ,n_{k})$ ($F(n;n_{1},\ldots ,n_{k})$) количество упорядоченных (соотв. неупорядоченных) разбиений $n$ на слагаемые $n_{1},\ldots ,n_{k}$. \ii Справедливы следующие рекуррентные формулы а) $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})$. в) Каковы начальные условия в этих формулах? \i а) Что больше: $f(20;1,4,6,9)$ или $F(20;1,4,6,9)$? б) Найдите оба числа, используя рекуррентные формулы. Диаграмма Юнга --- это конечный набор клеток, выровненных по левой границе, в котором длины строк образуют невозрастающую последовательность (каждая строка такой же длины как предыдущая, или короче). Весом диаграммы Юнга называется общее количество клеток диаграммы. Набор чисел, состоящий из длин строк, задаёт разбиение веса диаграммы в сумму слагаемых. Таким образом, есть соответствие между всеми неупорядоченными разбиениями натурального числа $n$ и всеми диаграммами Юнга веса $n$. \i Сколько существует диаграмм Юнга произвольного веса, но имеющих не более $p$ строк и не более $q$ столбцов? \ii На доске написано несколько целых положительных чисел: $a_{0}$, $a_{1}$, $a_{2}$, $\ldots$, $a_{n}$. Пишем на другой доске следующие числа: $b_{0}$ --- сколько всего чисел на первой доске, $b_{1}$ --- сколько там чисел, больших единицы, $b_{2}$ --- сколько там чисел, больших двойки, и т.~д., пока получаются положительные числа. На этом заканчиваем --- нули не пишем. На третьей доске пишем числа $c_{0}$, $c_{1}$, $c_{2}$, $\ldots$, построенные по числам второй доски аналогичным образом. Докажите, что наборы чисел на первой и третьей досках совпадают. \ii Докажите, что число неупорядоченных разбиений $a-b$ на $c-1$ слагаемых, не превосходящих $b$, равно числу неупорядоченных разбиений $a-c$ на $b-1$ слагаемых, не превосходящих $c$. \ii Верно ли, что число неупорядоченных разбиений числа $n$ на $k$ слагаемых равно числу неупорядоченных разбиений числа $n$ на слагаемые, максимальное из которых равно $k$? \ii Докажите, что количество неупорядоченных разбиений $n$ на различные нечётные слагаемые равно количеству симметричных диаграмм Юнга веса $n$. \istar Какие натуральные числа можно разбить в сумму нескольких (больше одного) подряд идущих натуральных чисел?
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};$ \vspace*{-3mm} \begin{itemize} \item а) Пусть $1=(1,0,0,\ldots ,0,\ldots )$, $t=(0,1,0,\ldots ,0,\ldots )$. \begin{itemize} \item 1) Найдите $t^{2},t^{3},\ldots ,t^{n}$. \item 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$. \end{itemize} \item б) Выражения $a_{0}\cdot 1+a_{1}\cdot t+a_{2}\cdot t^{2}+\ldots +a_{n}\cdot t^{n}+\ldots$ ( с введёнными операциями сложения и умножения) называют формальными степенными рядами. $a_{0}$ называют свободным членом ряда. \begin{itemize} \item 1) Покажите, что все свойства многочленов (коммутативность по сложению/умножению, ассоциативность, дистрибутивность) переносятся на формальные степенные ряды. \item 2) Пусть дан ряд $f(t)$. Корректна ли операция подстановки вместо $t$ ряда $g(t)$? Ряда $g(t)$ без свободного члена? \end{itemize} \item в) Определим производную формального степенного ряда $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$. \begin{itemize} \item 1) Производная линейна, то есть $(\alpha A+\beta B)'=\alpha A'+\beta B'$ (здесь $\alpha ,\beta \in \mathbb {R}$, $A,B$ --- формальные степенные ряды). \item 2) Выполнено тождество Лейбница, то есть $(AB)'=A'B+AB'$. \item 3) (Ряд Тейлора в нуле). Докажите, что $a_{n}$ --- свободный член ряда ${\frac {A^{(n)}}{n!}}$. \end{itemize} \end{itemize} \begin{itemize} \item г) Пусть $F=1+t+t^{2}+\dots$, $G=1-t+t^{2}-t^{3}+\dots$. Найдите $F+G$, $F\cdot G$. \begin{itemize} \item 1) Пусть $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}$. \end{itemize} \item д) Существует ли два таких ненулевых степенных ряда $F,G$, что $F\cdot G=F+G$? \begin{itemize} \item Ряд $G$ называется обратимым, если существует такой ряд $F$, что $F\cdot G=1$. $F$ называется рядом, обратным к $G$ и обозначается так: $F=G^{-1}$. \end{itemize} \item е) Докажите, что ряд $G=a_{0}+a_{1}t+a_{2}t^{2}+a_{3}t^{3}+\dots$ обратим тогда и только тогда, когда $a_{0}\neq 0$, причём обратный ряд $G^{-1}$ единственен. \item ё) Найдите коэффициенты ряда $\frac{1}{1-t}$; $\frac1{2-t}$; $\frac1{3+4t}$; $\frac1{(1-t)^{2}}$; $\frac1{(1-t)^{m}}$. \item ж) Верно ли равенство $\left(\frac{1}{1-t}\right)^2 \cdot \left(\frac{1}{1+t}\right)^2 = \left(\frac{1}{1-t^2}\right)^2$ для формальных степенных рядов? \begin{itemize} \item Сформулируйте комбинаторное тождество, получаемое при приравнивании коэффициентов в этих рядах. \end{itemize} \item з) При каких условиях на степенной ряд $F$ его можно разделить на степенной ряд $G$ (то есть уравнение $G\cdot X=F$ разрешимо относительно неизвестного степенного ряда $X$)? \begin{itemize} \item 1) При каких условиях на степенной ряд $F$ разрешимо уравнение $X^{2}=F$? \item 2) Пусть $X=\sum _{k=0}^{\infty }\alpha _{k}t^{k}$ ---- степенной ряд, задаваемый уравнением $X^{2}=1+t$. Найдите коэффициенты $\alpha _{0},\alpha _{1},\alpha _{2},\alpha _{3}$. \end{itemize} \item и) Пусть $\alpha \in \mathbb {R}$. Положим $C_{\alpha }^{n}={\frac {\alpha \cdot (\alpha -1)\cdot \ldots \cdot (\alpha -n+1)}{n!}}$. \begin{itemize} \item 1) Если $\alpha \in \mathbb {N} ,\alpha \geq n$, то $C_{\alpha }^{n}$ совпадает с биномиальным коэффициентом. \item 2) $C_{\alpha +\beta }^{n}=\sum _{j=0}^{n}C_{\alpha }^{j}\cdot C_{\beta }^{n-j}$. \item 3) Определим ряд $(1+t)^{\alpha }=\sum _{n=0}^{\infty }C_{\alpha }^{n}t^{n}$. Покажите, что при $\alpha \in \mathbb {N}$ определения согласованы. \item 4) Покажите, что $(1+t)^{\alpha }\cdot (1+t)^{\beta }=(1+t)^{\alpha +\beta }$. \item 5) Используя определение, найдите коэффициенты ряда $(1+t)^{\frac {1}{2}}$. Сравните ответ с ответом в задаче предыдущей задаче пункте в. \end{itemize} \end{itemize} Вычислите $\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}$. Вычислите сумму $(C_{n}^{0})^{2}-(C_{n}^{1})^{2}+\ldots +(-1)^{n}(C_{n}^{n})^{2}$. Теорема Коши-Адамара. Пусть ${\frac {1}{R}}={{\overline {\lim \limits _{n\to \infty }}}{\sqrt[{n}]{|a_{n}|}}}$. Тогда ряд $\sum \limits _{n=0}^{\infty }a_{n}t^{n}$ сходится при $|t|<R$ и расходится при $|t|>R$, таким образом функция $f(t)=\sum \limits _{n=0}^{\infty }a_{n}t^{n}$ определена в каждой точке множества $\{t\mid |t|<R\}$. Число $R$ называется радиусом сходимости ряда. Найдите радиус сходимости ряда $\sum _{n=0}^{\infty }t^{n}$, \pu $\sum _{n=0}^{\infty }(-1)^{n}\cdot t^{n}$, \pu $\sum _{n=0}^{\infty }\lambda ^{n}t^{n}$, ${\frac {1}{1-t^{2}}}$. Приведите пример, когда на границе ряда (то есть при $|t|=R$) есть Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle сходимость в обеих точках; \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.
2.
3.
...
48.
49.
50.
...

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

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

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

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

Вид учебных занятий/деятельности

Деятельность обучающегося

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

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