Difference between revisions of "BSc: IntroductionToCombinatoricsAndDiscreteMathematics"

From IU
Jump to navigation Jump to search
(Created page with "= <span style="color:red;">Название дисциплины</span> = : '''Квалификация выпускника''': <span style="color:red;">бакалавр/ма...")
 
 
(9 intermediate revisions by the same user not shown)
Line 1: Line 1:
  +
= Введение в комбинаторику и дискретную математику=
= <span style="color:red;">Название дисциплины</span> =
 
: '''Квалификация выпускника''': <span style="color:red;">бакалавр/магистр</span>
+
: '''Квалификация выпускника''': бакалавр
: '''Направление подготовки''': __________________
+
: '''Направление подготовки''': 09.03.01 - “Информатика и вычислительная техника”
: '''Направленность (профиль) образовательной программы''': <span style="color:red;">(Указывается направленность (профиль) образовательной программы</span>
+
: '''Направленность (профиль) образовательной программы''': Математические основы ИИ
: '''Программу разработал(а)''': __________________
+
: '''Программу разработал(а)''':
   
 
== 1. Краткая характеристика дисциплины ==
 
== 1. Краткая характеристика дисциплины ==
  +
Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области <span style="color:red;">(указывается область изучаемой дисциплины. Например: программного обеспечения и его разработки; робототехники и т.д.)</span>, их применение для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают <span style="color:red;">(краткое описание содержания дисциплины)</span>.
 
  +
Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области комбинаторики и дискретной математики, их применение для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают основные правила комбинаторики (сложение, умножение, принцип Дирихле, формула включений и исключений), концепции (числа сочетаний и размещений, рекуррентные соотношения, разбиения, формальные степенные ряды и производящие функции).
   
 
== 2. Перечень планируемых результатов обучения ==
 
== 2. Перечень планируемых результатов обучения ==
: '''Целью освоения дисциплины''' ...
+
: '''Целью освоения дисциплины'''
  +
  +
: '''Задачами дисциплины''' являются изучение основных правил и концепций комбинаторики для различных прикладных задач.
   
: '''Задачами дисциплины''' вляются ... <span style="color:red;">(перечислить задачи дисциплины, например: изучение принципов организации подсистем обработки естественного языка для различных прикладных задач и тенденций развития лингвистических ресурсов в сфере интеллектуальных информационных технологий и т.д.).</span>
 
   
 
=== Общая характеристика результата обучения по дисциплине ===
 
=== Общая характеристика результата обучения по дисциплине ===
: '''Знания:''' сформированы систематические знания ...
+
: '''Знания:''' сформированы систематические знания по комбинаторике и дискретной математики.
<span style="color:red;">(информация, которой обладает обучающийся в определенных областях, полученная в процессе обучения, то есть это информация для осуществления какой-либо деятельности (действия))</span>
 
   
: '''Умения:''' сформированы умения ...
+
: '''Умения:'''
<span style="color:red;">(предполагает целенаправленное выполнение действий, по изученной информации)</span>
 
   
: '''Навыки (владения):''' сформировано владение навыками ...
+
: '''Навыки (владения):'''
<span style="color:red;">(автоматизированные устойчивые умения выполнять определенную работу, то есть действие выполняется без контроля сознания, автоматически)</span>
 
   
 
== 3. Структура и содержание дисциплины ==
 
== 3. Структура и содержание дисциплины ==
  +
<span style="color:red;">(Указываются: 1) порядковый номер раздела (количество разделов зависит от содержания Вашей дисциплины); 2) наименования разделов дисциплины; 3) темы указанных разделов (количество тем в каждом разделе зависит от содержания Вашей дисциплины)</span>
 
 
{| class="wikitable" style="width:70%;"
 
{| class="wikitable" style="width:70%;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
Line 30: Line 29:
 
| style="width:30%" | Наименование раздела <br> дисциплины
 
| style="width:30%" | Наименование раздела <br> дисциплины
 
| style="width:60%" | Содержание дисциплины по темам
 
| style="width:60%" | Содержание дисциплины по темам
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 1. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
  +
| style="text-align:center;" | 1. || Основные правила комбинаторики || - правило сложения
|- style="background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 2. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
  +
- правило умножения
|- style="background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 3. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
  +
- правило дополнения
|- style="background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 4. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
  +
- принцип Дирихле
|- style="background-color:#F8F9FA; color:#202122;"
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
| style="text-align:center;" | 5. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 2. || Основные комбинаторные величины || - размещения с повторениями / без повторений
| style="text-align:center;" | ... || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
  +
  +
- сочетания с повторениями/ без повторений
  +
  +
- перестановки
  +
  +
- треугольник Паскаля
  +
  +
- линейный город
  +
  +
- биномиальный и полиномиальный коэффициент
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 3. || Тождества с биномиальными коэффициентами || - симметричность
  +
  +
- унимодальность
  +
  +
- рекуррентное соотношение
  +
  +
- Бином Ньютона
  +
  +
- сумма биномиальных коэффициентов (в том числе альтернированная)
  +
  +
- сумма квадратов биномиальных коэффициентов
  +
  +
- сумма степеней натуральных чисел
  +
  +
- формула включений и исключений
  +
  +
- число беспорядков
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 4. || Рекуррентные соотношения || - линейные однородные рекуррентные соотношения
  +
  +
- л.о.р.с. для степени 2 с разными корнями
  +
  +
- л.о.р.с. для степени 2 с кратным корнем
  +
  +
- формулировка теоремы в общем случае
  +
  +
- числа Фибоначчи
  +
  +
- формулировка теоремы для неоднородного случая
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 5. || Разбиения || - упорядоченные и неупорядоченные разбиения
  +
  +
- диаграммы Юнга
  +
  +
- теоремы Эйлера о равенстве неупорядоченных разбиений
  +
  +
- асимптотика неупорядоченных разбиений
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 6 || Формальные степенные ряды и производящие функции || - формальные степенные ряды
  +
  +
- обратимость ряда, пример деления в столбик
  +
  +
- доказательство комб. тождеств при помощи формального степенного ряда
  +
  +
- производящие функции для рекуррентных соотношений
  +
  +
- возведение ряда в степень
  +
  +
- числа Каталана
  +
 
|}
 
|}
   
Line 50: Line 114:
 
| style="width:10%" | №<br>п/п
 
| style="width:10%" | №<br>п/п
 
| style="width:30%" | Наименование раздела<br>дисциплины (модуля)
 
| style="width:30%" | Наименование раздела<br>дисциплины (модуля)
| style="width:60%" | Перечень рассматриваемых тем (вопросов)<br><span style="color:red;">(Указываются ВСЕ задания для практических занятий по разделам дисциплины подробно в соответствии с темами)</span>
+
| style="width:60%" | Перечень рассматриваемых тем (вопросов)<br>
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 1. || ||
 
  +
| style="text-align:center;" |1 || Основные правила комбинаторики || ''Принцип Дирихле.'' Пусть есть <math>n</math> ящиков и <math>n+1</math> кроликов. Если расселить кроликов по ящикам, то найдется хотя бы один ящик, в котором окажутся не менее <math>2</math> кроликов.
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 2. || ||
 
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 3. || ||
 
  +
В мешке имеется <math>32</math> красных шара, <math>29</math> зеленых шаров, <math>45</math> синих, <math>17</math> желтых и по <math>30</math> белых, черных и серых (всего <math>213</math> шаров). Сколько шаров необходимо вынуть из мешка, чтобы среди них гарантированно нашлось <math>9</math> шаров одного цвета?
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 4. || ||
 
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 5. || ||
 
  +
Комиссия из <math>60</math> человек провела <math>40</math> заседаний, причем на каждом заседании присутствовали ровно <math>10</math> членов комиссии. Докажите, что найдутся два члена комиссии, по крайней мере дважды встречавшиеся на заседаниях.
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | ... || ||
 
  +
  +
  +
В таблице <math>10 \times 10</math> расставлены целые числа, причем любые два числа в соседних клетках отличаются не более, чем на <math>5</math>. Докажите, что среди этих чисел найдутся два равных.
  +
  +
  +
  +
Пусть имеется множество из <math>M</math> слов в алфавите из <math>k>1</math> символа. Докажите, что хотя бы одно из слов не короче <math>\log_k{M}</math>.
  +
  +
  +
  +
В правильном треугольнике со стороной <math>1</math> отмечено пять точек. Докажите, что найдется пара точек, удаленных друг от друга не более, чем на <math>1/2</math>.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" |2 || Основные комбинаторные величины || Пусть <math>A = \{a_1, \dots, a_n\}</math>. Извлекать элементы из <math>A</math> можно по порядку или <<пригорошнями>>. Первые называются ''размещениями'', вторые --- ''сочетаниями''. При этом каждое из них бывает как с повторениями символов, так и без.
  +
  +
* ''Размещением без повторений'' называется любой набор различных объектов <math>b_1,\dots,b_k \in A</math>, расположенных друг за другом в определенном порядке. Например, слова «лягушка» и «гуляшка» --- это два разных 7-размещения без повторений букв русского алфавита, хотя состоят они из одних и тех же букв.
  +
  +
''Размещение с повторениями'' --- это снова любой набор объектов <math>b_1,\dots,b_k \in A</math>, расположенных друг за другом в определенном порядке. Только теперь объекты в размещении могут совпадать. Например, «жаба» и «абаж» --- два разных 4-размещения с повторениями из букв русского алфавита.
  +
  +
''Сочетания без повторений'' отличаются от размещений без повторений тем, что в них порядок объектов значения не имеет. Так, «лягушка» и «гуляшка» представляют собой одно и то же 7-сочетание без повторений букв {л, я, г, у, ш, к, а } русского алфавита.
  +
  +
''Сочетания с повторениями'' аналогично, например { ж, а, б, а } = { а, б, а, ж }.
  +
  +
  +
  +
Сформулируйте на языке теории множеств что такое размещение с повторениями/ без повторений и сочетания с повторениями (не используя понятий набор и порядок, разрешается использовать все определения из первых двух листков, например: множество, элемент, подмножество, все виды отображений, декартово произведение).
  +
  +
Докажите формулу для числа размещений без повторений (если вы будете пользоваться правилом умножения, сформулируйте чётко, какие множества A и B вы используете).
  +
  +
  +
  +
(а) Сколько существует шестизначных чисел?
  +
  +
(б) Сколько существует шестизначных чисел, делящихся на 5?
  +
  +
(в) Сколько существует шестизначных чисел, в записи которых присутствует хотя бы одна чётная цифра?
  +
  +
  +
  +
На плоскости отмечено 10 точек так, что никакие три из них не лежат на одной прямой. Сколько существует треугольников с вершинами в этих точках?
  +
  +
  +
  +
<math>20</math> балбесов-первокурсников и семинарист пришли в кинотеатр и сели в одном ряду. Семинарист должен сидеть с краю, а Петю, Колю и Васю нельзя сажать втроем. Сколькими способами можно рассадить группу?
  +
  +
  +
  +
Из класса, в котором учатся <math>28</math> человек, назначаются на дежурство в столовую <math>4</math> человека.
  +
Сколькими способами это можно сделать?
  +
  +
Сколько существует способов набрать команду дежурных, в которую попадет ученик этого класса Коля Васин?
  +
  +
В группе учатся <math>20</math> студентов. Согласно новому указу Минздрава <math>75%</math> группы нужно вакцинировать.
  +
Сколькими способами это можно сделать?
  +
  +
Выяснилось, что один студент этой группы Коля Васин уже провакцинирован. Сколько теперь существует способов исполнить указ Минздрава?
  +
  +
  +
  +
У королевы есть <math>12</math> одинаковых зеркал. Сколькими способами их можно повесить в <math>8</math> разных залах замка так, чтобы в каждом зале было хотя бы одно зеркало?
  +
  +
  +
  +
В пекарне продавались <math>4</math> вида пирожков: элеши, эчпочмаки, перемячи и кыстыбыи. Сколькими способами можно купить <math>7</math> пирожков?
  +
  +
  +
  +
Есть <math>n</math> попарно различных чашек и <math>n</math> неразличимых стаканов. Также имеется <math>k</math> попарно различных ложек и <math>k</math> неразличимых кусков сахара. Сколькими способами можно разложить:
  +
  +
а) ложки по чашкам;
  +
  +
б) сахар по чашкам;
  +
  +
в) ложки по стаканам, если <math>n = 4</math>?
  +
  +
  +
  +
На ютуб-канале есть плейлист из <math>30</math> лекций по ДМ. Сколькими способами их можно переставить так, чтобы
  +
  +
а) шесть лекций, прочитанных Даниилом Владимировичем, расположились в правильном порядке (но не обязательно подряд)?
  +
  +
б) те же лекции по-прежнему были в правильном порядке, но никакие
  +
  +
в) две из них не шли подряд?
  +
  +
  +
  +
Сколько имеется способов раздать <math>11</math> разных цветков, трём девушкам: какой-то --- <math>5</math>, а остальным~--- по <math>3</math> цветка?
  +
  +
  +
  +
Дано множество <math>A = \{1, \dots , n\}</math>. Даны числа <math>k</math>, <math>s</math>.
  +
  +
* Сколько можно составить совокупностей из <math>s</math> различных <math>k</math>-элементных подмножеств множества <math>A</math>?
  +
  +
* Сколько из этих совокупностей устроены так, что каждое множество в них имеет непустое пересечение с подмножеством <math>\{1, \dots, l\} \subset A</math>?
  +
  +
  +
  +
Сколькими способами можно выбрать из полной колоды, содержащей <math>52</math> карты, <math>6</math> карт так, чтобы среди них были все <math>4</math> масти?
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" |3 || Тождества с биномиальными коэффициентами ||Покажите, что число <math>k</math>-сочетаний без повторений из <math>n</math>-элементного множества равно
  +
  +
а) Количеству последовательностей из 0 и 1 длины <math>n</math> с ровно <math>k</math> единицами.
  +
  +
б) (Линейный город) Количеству маршрутов путей из <math>A</math> в <math>B</math>, если идти можно только вправо и вверх (стороны прямоугольника <math>k</math> и <math>n-k</math>)
  +
  +
в) (Треугольник Паскаля) <math>k</math>-ому числу в <math>n</math>-ой строке треугольника Паскаля (нумерация с <math>0</math>)
  +
  +
г) (Бином Ньютона) Коэффициенту при мономе <math>a^kb^{n-k}</math> в разложении <math>(a+b)^n</math>.
  +
  +
[[Image:pic1dm1.png]]
  +
  +
  +
Многие из следующих тождеств/сумм можно доказывать/находить несколькими способами:
  +
  +
- через непосредственное определение
  +
  +
- при помощи формулы
  +
  +
- используя интерпретации выше
  +
  +
Докажите следующие тождества при целых неотрицательных<math>n,k</math>:
  +
  +
а) <math>C_{n+1}^k = C_{n}^k+C_{n}^{k-1}</math>
  +
  +
б) <math>C_{n}^k = C_{n}^{n-k}</math>
  +
  +
в) <math>C_{2n}^n = (C_{n}^{0})^2+\ldots+(C_{n}^n)^{2}</math>
  +
  +
  +
  +
Найдите суммы при целых неотрицательных <math>n,k,m</math> :
  +
  +
а) <math>C_{n}^0+ \ldots + C_{n}^n;</math>
  +
  +
б) <math>C_{n}^0-C_n^1 + \ldots +(-1)^n C_{n}^n;</math>
  +
  +
в) <math>C_{n}^0+C_n^2 + C_n^4+\ldots</math>
  +
  +
г*) <math>C_{n}^0+C_n^3 + C_n^6+\ldots</math>
  +
  +
д) <math>C_n^1 + 2 C_n^2 + 3 C_n^3 +\ldots + n C_{n}^n;</math>
  +
  +
е) <math>C_{n}^0+\frac{1}{2} C_n^1 + \frac{1}{3} C_n^2 + \ldots + \frac{1}{n+1} C_{n}^n;</math>
  +
  +
ж) <math>C_{n}^n + C_{n+1}^{n} + \ldots + C_{n+m}^{n};</math>
  +
  +
з) <math>C_n^k+C_{n+1}^{k}+\ldots+C_{n+m}^{k};</math>
  +
  +
и) <math>C_n^k + C_{n+1}^{k+1} + \ldots + C_{n+m}^{k+m};</math>
  +
  +
к) <math>C_n^0C_m^k+ C_n^1C_m^{k-1}+\ldots+C_n^kC_m^0;</math>
  +
  +
л) <math>(C_n^1)^2 + 2(C_n^2)^2 + 3(C_n^3)^2 + \ldots + n(C_n^n)^2;</math>
  +
  +
м*) <math>C_{2n}^{n} + 2C_{2n-1}^{n} + 4C_{2n-2}^{n}+ \ldots + 2^nC_n^{n};</math>
  +
  +
н*) <math>C_{2n}^{0} - C_{2n-1}^{1} + C_{2n-2}^{2}+ \ldots + (-1)^nC_n^{n}.</math>
  +
  +
  +
  +
Найдите <math>\sum_{(n_1,n_2,n_3), n_1+n_2+n_3=5, n_i \in \N } P(n_1,n_2,n_3) (-1)^{n_1+n_2}</math>.
  +
  +
Посчитайте коэффициенты при <math>x^{57}</math> и <math>x^{57}</math> в разложении <math> (x^2 + x^7 + x^9)^{20}</math>.
  +
  +
  +
На оси абсцисс разместим (произвольным образом) 2n точек, разобьем множество этих точек на пары (опять-таки, произвольно) и элементы каждой пары соединим дугой, так, как это показано на рисунке. Получившийся объект назовем хордовой диаграммой. Сколько существует различных хордовых диаграмм на 2n точках?
  +
  +
[[Image:pic2dm1.png]]
  +
  +
  +
Найдите количество чисел, не превосходящих <math>1001</math> и не делящихся ни на одно из чисел <math>7</math>, <math>11</math>, <math>13</math>.
  +
  +
  +
Пусть <math>\varphi(n)</math> --- ''функция Эйлера'', то есть количество натуральных чисел от <math>1</math> до <math>n</math>, взаимно простых c <math>n</math>.
  +
  +
  +
Найдите <math>\varphi(1)</math>; <math>\varphi(p)</math>; <math>\varphi(p^2)</math>; <math>\varphi(p^{\alpha})</math>, где <math>p</math> --- простое число, <math>\alpha > 2</math>.
  +
  +
  +
<math>\varphi(n) = n (1 - \frac{1}{p_1}) \ldots (1-\frac{1}{p_s})</math>, где <math>n=p_1^{\alpha_1}\cdot \ldots \cdot p_s^{\alpha_s}</math> --- каноническое разложение числа <math>n</math>.
  +
  +
  +
  +
В комнате площади <math>6</math> уложены три ковра площади <math>3</math> каждый (форма комнаты и ковров произвольная). Докажите, что какие-то два из этих трёх ковров перекрываются по площади, не меньшей~<math>1</math>.
  +
  +
  +
На кафтане расположено пять заплат произвольной формы. Площадь каждой из них больше половины площади кафтана. Тогда площадь общей части некоторых двух заплат большей одной пятой площади кафтана.
  +
  +
  +
(Число беспорядков) На полке стоят 10 книг. Сколькими способами их можно переставить так, чтобы (а) ни одна книга не осталась на своем месте? (б) на месте осталось ровно 4 книги?
  +
  +
  +
Сколькими способами можно расселить 20 туристов по 5 домикам, чтобы ни один домик не оказался пустым?
  +
  +
  +
Сколько существует различных сюръекций из множества X = {1, . . . , k} во множество Y = {1, . . . , n}?
  +
  +
  +
Сколько существует неупорядоченных разбиений k-элементного множества на n подмножеств?
  +
  +
  +
В ряд записали 105 единиц, поставив перед каждой знак «+» . Сначала изменили знак на противоположный перед каждой третьей единицей, затем — перед каждой пятой, а затем — перед каждой седьмой. Найдите значение полученного выражения. 7 ◦ . Сколько существует перестановок чисел от 1 до 7, при которых никакие два рядом расположенных числа не отличаются на 1?
  +
  +
  +
[Задача о мажордомах] К обеду за круглым столом приглашены n пар враждующих рыцарей. Требуется рассадить их так, чтобы никакие два врага не сидели рядом. Сколько существует таких рассадок?
  +
  +
  +
[Задача о паросочетаниях] За круглым столом нужно рассадить n супружеских пар. Сколькими способами это можно сделать, если требуется, чтобы мужчины и женщины чередовались и чтобы ни один муж не сидел рядом со своей женой?
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" |4 || Рекуррентные соотношения || Для каждого из следующих линейных рекуррентных соотношений найдите общее решение:
  +
  +
а) <math>a_{n+2}- 7a_{n+1}+ 12a_n = 0;</math>
  +
  +
б) <math>a_{n+3} - 2a_{n+2} - 4a_{n+1} + 8a_n = 0</math>;
  +
  +
в) <math>a_{n+2}+a_{n+1}+a_n=0;</math>
  +
  +
г) <math>a_{n+2}- 9a_n = 0;</math>
  +
  +
д) <math>a_{n+3}+ 3a_{n+2}+ 3a_{n+1} + a_n= 0;</math>
  +
  +
е) <math>a_{n+3}+5a_{n+2}+12a_{n+1}+8a_n=0</math>.
  +
  +
  +
  +
Найдите решение неоднородного линейного рекуррентного соотношения
  +
  +
а) <math>a_{n+2} = a_{n+1} + a_n + 1</math>;
  +
  +
б) <math>a_{n+2} = 2a_{n+1} - a_n + n + 1</math>;
  +
  +
в) <math>a_{n+2} = a_{n+1} + 6a_n + 3^n</math>?
  +
  +
  +
  +
''Числами Фибоначчи'' называется последовательность <math>F_n,n\geqslant 0</math>, удовлетворяющая соотношениям <math>F_0=0</math>, <math>F_1=1</math>, <math>F_n=F_{n-1}+F_{n-2}</math> для всех натуральных <math>n>1</math>.
  +
  +
  +
  +
Найдите формулу для нахождения <math>n</math>-ого члена последовательности <math>F_n</math>.
  +
  +
  +
  +
Найдите
  +
  +
* <math>F_0+F_1+\ldots+F_n</math>;
  +
  +
* <math>F_0^2+F_1^2+\ldots+F_n^2</math>;
  +
  +
* <math>F_0^3+F_1^3+\ldots + F_n^3</math>.
  +
  +
  +
  +
Сколькими способами можно разменять купюру в <math>100</math> рублей на монеты достоинством <math>1</math>, <math>2</math> и <math>5</math> рублей? %364
  +
  +
  +
  +
Найдите рекуррентное соотношение для последовательности <math>A_n</math>, где <math>A_n</math> -- число способов выложить прямоугольник размера
  +
  +
*<math>n \times 3</math>;
  +
  +
*<math>n \times 4</math> доминошками размера <math>1 \times 2</math>;
  +
  +
*число способов выложить колонну <math>2 \times 2\times n</math> кирпичами размера <math>2 \times 1 \times 1</math>.
  +
  +
  +
  +
Сколько существует строк из <math>20</math> нулей и единиц, в каждой из которых никакие два нуля не стоят рядом?
  +
  +
  +
  +
Докажите, что последовательность с общим членом <math>a_n=n^{k-1}</math> удовлетворяет соотношению <math>a_{n+k} - C_{k}^1 a_{n+k-1} + C_k^2 a_{n+k-2} - \ldots + (-1)^k C_k^ka_n=0</math>.
  +
  +
  +
В вершине B шестиугольника ABCDEF сидит лягушка. Каждую секунду лягушка может перепрыгнуть в одну из соседних вершин. Сколькими способами она может допрыгнуть до вершины A за n прыжков?
  +
  +
  +
  +
В центральной клетке левого столбца доски 1000 × 3 стоит шахматный король. Сколькими спо[1]собами он может добраться до правого столбца доски за 999 ходов?
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" |5 || Разбиения || а) Найдите количество упорядоченных разбиений числа <math>n</math> на <math>k</math> слагаемых.
  +
  +
б) Найдите общее количество упорядоченных разбиений числа <math>n</math> на слагаемые.
  +
  +
в) Какой ответ будет в предыдущих пунктах, если мы разрешим слагаемым принимать значение <math>0</math>?
  +
  +
  +
  +
Обозначим через <math>f(n;n_1,\ldots,n_k)</math> (<math>F (n;n_1,\ldots,n_k)</math>) количество упорядоченных (соотв. неупорядоченных) разбиений <math>n</math> на слагаемые <math>n_1,\ldots,n_k</math>.
  +
  +
  +
  +
Справедливы следующие рекуррентные формулы
  +
  +
а) <math>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)</math>;
  +
  +
б) <math>F(n;n_1,\ldots,n_k) = F(n-n_1;n_1,\ldots,n_k) + F(n;n_2,\ldots,n_k)</math>.
  +
  +
в) Каковы начальные условия в этих формулах?
  +
  +
  +
  +
а) Что больше: <math>f(20;1,4,6,9)</math> или <math>F(20;1,4,6,9)</math>? б) Найдите оба числа, используя рекуррентные формулы.
  +
  +
  +
  +
Диаграмма Юнга -- это конечный набор клеток, выровненных по левой границе, в котором длины строк образуют невозрастающую последовательность (каждая строка такой же длины как предыдущая, или короче). Весом диаграммы Юнга называется общее количество клеток диаграммы. Набор чисел, состоящий из длин строк, задаёт разбиение веса диаграммы в сумму слагаемых. Таким образом, есть соответствие между всеми неупорядоченными разбиениями натурального числа <math>n</math> и всеми диаграммами Юнга веса <math>n</math>.
  +
  +
  +
  +
Сколько существует диаграмм Юнга произвольного веса, но имеющих не более <math>p</math> строк и не более <math>q</math> столбцов?
  +
  +
  +
  +
На доске написано несколько целых положительных чисел: <math>a_0</math>, <math>a_1</math>, <math>a_2</math>, <math>\ldots</math>, <math>a_n</math>. Пишем на другой доске следующие числа: <math>b_0</math> --- сколько всего чисел на первой доске, <math>b_1</math> --- сколько там чисел, больших единицы, <math>b_2</math> --- сколько там чисел, больших двойки, и т.~д., пока получаются положительные числа. На этом заканчиваем --- нули не пишем. На третьей доске пишем числа <math>c_0</math>, <math>c_1</math>, <math>c_2</math>, <math>\ldots</math>, построенные по числам второй доски аналогичным образом. Докажите, что наборы чисел на первой и третьей досках совпадают.
  +
  +
  +
Докажите, что число неупорядоченных разбиений <math>a-b</math> на <math>c-1</math> слагаемых, не превосходящих <math>b</math>, равно числу неупорядоченных разбиений <math>a-c</math> на <math>b-1</math> слагаемых, не превосходящих <math>c</math>.
  +
  +
  +
Верно ли, что число неупорядоченных разбиений числа <math>n</math> на <math>k</math> слагаемых равно числу неупорядоченных разбиений числа <math>n</math> на слагаемые, максимальное из которых равно <math>k</math>?
  +
  +
  +
Докажите, что количество неупорядоченных разбиений <math>n</math> на различные нечётные слагаемые равно количеству симметричных диаграмм Юнга веса <math>n</math>.
  +
  +
  +
Какие натуральные числа можно разбить в сумму нескольких (больше одного) подряд идущих натуральных чисел?
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
  +
| style="text-align:center;" | 6 || Формальные степенные ряды и производящие функции || Рассмотрим множество последовательностей <math>(a_0,a_1,\ldots,a_n,\ldots)</math> (здесь <math>a_i</math> берутся из множества чисел <math>\Q</math>, <math>\R</math> или <math>\C</math>) и введём на них операции сложения и умножения следующим образом:
  +
  +
  +
  +
<math>(a_0,a_1,\ldots) + (b_0,b_1,\ldots) = (a_0+b_0, a_1+b_1,\ldots);</math>
  +
  +
  +
  +
<math>(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};</math>
  +
  +
  +
  +
  +
  +
Пусть <math>1= (1,0,0,\ldots,0,\ldots)</math>, <math>t = (0,1,0,\ldots,0,\ldots)</math>.
  +
  +
1) Найдите <math>t^2, t^3, \ldots, t^n</math>.
  +
  +
2) Покажите, что любая последовательность <math>(a_0,a_1,\ldots,a_n,\ldots,)</math> единственным образом представляется в виде <math>a_0 \cdot 1 + a_1 \cdot t + a_2 \cdot t^2 + \ldots + a_n \cdot t^n + \ldots</math>.
  +
  +
  +
  +
Покажите, что все свойства многочленов (коммутативность по сложению/умножению, ассоциативность, дистрибутивность) переносятся на формальные степенные ряды.
  +
  +
  +
  +
Пусть дан ряд <math>f(t)</math>. Корректна ли операция подстановки вместо <math>t</math> ряда <math>g(t)</math>? Ряда <math>g(t)</math> без свободного члена?
  +
  +
  +
  +
Определим ''производную'' формального степенного ряда <math>A = a_0 \cdot 1 + a_1 \cdot t + \ldots + a_n \cdot t^n + \ldots</math> как ряд <math>A' = a_1 + 2a_2 t + \ldots + n a_n t^{n-1} + \ldots</math>. Производную можно брать несколько раз подряд, через <math>A^{(n)}</math> обозначается <math>n</math>-ая производная ряда <math>A</math>.
  +
  +
Производная линейна, то есть <math>(\alpha A + \beta B)' = \alpha A' + \beta B'</math> (здесь <math>\alpha,\beta \in \R</math>, <math>A,B</math> --- формальные степенные ряды).
  +
  +
Выполнено ''тождество Лейбница'', то есть <math>(AB)' = A'B + AB'</math>.
  +
  +
(''Ряд Тейлора в нуле''). Докажите, что <math>a_n</math> --- свободный член ряда <math>\frac{A^{(n)}}{n!}</math>.
  +
  +
Пусть <math>F=1+t+t^2+\dots</math>, <math>G=1-t+t^2-t^3+\dots</math>. Найдите <math>F+G</math>, <math>F\cdot G</math>.
  +
  +
Пусть <math>F = \sum_{k=0}^{\infty} \frac{1}{k!}t^k</math>, <math>G = \sum_{k=0}^{\infty} \frac{(-1)^k}{k!}t^k</math>. Найдите <math>F \cdot G</math> и <math>F^2</math>.
  +
  +
Существует ли два таких ненулевых степенных ряда <math>F,G</math>, что <math>F\cdot G = F+G</math>?
  +
  +
Ряд <math>G</math> называется ''обратимым'', если существует такой ряд <math>F</math>, что <math>F\cdot G=1</math>. <math>F</math> называется ''рядом, обратным к <math>G</math>'' и обозначается так: <math>F = G^{-1}</math>.
  +
  +
  +
  +
Докажите, что ряд <math>G = a_0+ a_1 t + a_2 t^2 + a_3 t^3+ \dots</math> обратим тогда и только тогда, когда <math>a_0 \neq 0</math>, причём обратный ряд <math>G^{-1}</math> единственен.
  +
  +
  +
  +
Найдите коэффициенты ряда <math>\frac{1}{1-t}</math>; <math>\frac1{2-t}</math>; <math>\frac1{3+4t}</math>; <math>\frac1{(1-t)^{2}}</math>; <math>\frac1{(1-t)^{m}}</math>.
  +
  +
  +
  +
Верно ли равенство <math>\left(\frac{1}{1-t}\right)^2 \cdot \left(\frac{1}{1+t}\right)^2 = \left(\frac{1}{1-t^2}\right)^2</math> для формальных степенных рядов?
  +
  +
  +
  +
Сформулируйте комбинаторное тождество, получаемое при приравнивании коэффициентов в этих рядах.
  +
  +
  +
  +
При каких условиях на степенной ряд <math>F</math> его можно разделить на степенной ряд <math>G</math> (то есть уравнение <math>G\cdot X=F</math> разрешимо относительно неизвестного степенного ряда <math>X</math>)?
  +
  +
  +
  +
При каких условиях на степенной ряд <math>F</math> разрешимо уравнение <math>X^2=F</math>?
  +
  +
  +
  +
Пусть <math>X = \sum_{k=0}^{\infty} \alpha_k t^k</math> ---- степенной ряд, задаваемый уравнением <math>X^2 = 1+t</math>. Найдите коэффициенты <math>\alpha_0,\alpha_1,\alpha_2,\alpha_3</math>.
  +
  +
  +
  +
Пусть <math>\alpha \in \R</math>. Положим <math>C_{\alpha}^n = \frac{\alpha \cdot (\alpha-1) \cdot \ldots \cdot (\alpha-n+1)}{n!}</math>.
  +
  +
  +
  +
Если <math>\alpha \in \N, \alpha \geq n</math>, то <math>C_{\alpha}^n</math> совпадает с биномиальным коэффициентом.
  +
  +
  +
  +
Определим ряд <math>(1+t)^\alpha = \sum_{n=0}^{\infty} C_{\alpha}^n t^n</math>. Покажите, что при <math>\alpha\in \N</math> определения согласованы.
  +
  +
  +
  +
Покажите, что <math>(1+t)^{\alpha} \cdot (1+t)^{\beta} = (1+t)^{\alpha+\beta}</math>.
  +
  +
  +
  +
Используя определение, найдите коэффициенты ряда <math>(1+t)^{\frac{1}{2}}</math>. Сравните ответ с ответом в задаче предыдущей задаче пункте в.
  +
  +
  +
  +
Вычислите <math>\sum_{k=0}^n k^2 C_n^k {(\frac{1}{17})}^k</math>.
  +
  +
  +
Вычислите <math>\sum_{k=0}^{\infty} \frac{F_n}{2^n}</math> (<math>F_n</math> --- числа Фибоначчи).
  +
  +
  +
  +
* Как выглядит производящая функция для числа способов набрать <math>n</math> рублей монетами достоинством <math>1</math>, <math>2</math> и <math>5</math> рублей?
  +
  +
* Тот же вопрос, при условии, что есть всего три 5-рублёвые монеты.
  +
  +
  +
  +
Найдите производящую функцию для числа
  +
  +
* упорядоченных разбиений числа <math>n</math>;
  +
  +
* неупорядоченных разбиений <math>n</math>;
  +
  +
* неупорядоченных разбиений <math>n</math> на нечётные слагаемые;
  +
  +
* неупорядоченных разбиений <math>n</math> на попарно различные слагаемые.
  +
  +
Докажите, что функции в последних двух пунктах совпадают.
  +
  +
  +
  +
* Докажите тождество <math>4^n = \sum\limits_{i=0}^n C_{2i}^{i} \cdot C_{2(n-i)}^{n-i}</math>.
  +
  +
  +
Найдите радиус сходимости ряда
  +
  +
<math>\sum_{n=0}^{\infty} t^n</math>,
  +
  +
<math>\sum_{n=0}^{\infty} (-1)^n \cdot t^n</math>,
  +
  +
<math>\sum_{n=0}^{\infty} \lambda^n t^n</math>,
  +
  +
<math>\frac{1}{1-t^2}</math>.
  +
  +
  +
  +
Приведите пример, когда на границе ряда (то есть при <math>|t|=R</math>) есть сходимость в обеих точках; <math>\sum_{n=0}^{\infty}</math> расходимость в обеих точках; <math>\sum_{n=0}^{\infty}</math> сходимость в одной точке и расходимость в другой точке.
  +
  +
  +
  +
Найдите производящую функцию для последовательности <math>a_n = C_1 \lambda_1^n + C_2 \lambda_2^n</math>. \pu Какой у неё радиус сходимости?
  +
  +
  +
  +
В каких точках действительной прямой сходится ряд <math>\sum\limits_{n=0}^{\infty}a_nt^n</math>, где <math>a_n</math> задано следующим образом?
  +
  +
<math>a_n=\begin{cases} 3 \cdot (-6)^n + 4\cdot 3^n, & n=3k, k \in \N; \\ 5 \cdot \left(-\frac{1}{4}\right)^n + 2 \cdot 2^n, & n=3k+1, k \in \N; \\ 6 \cdot (-3)^n, & n=3k+2, k \in \N. \end{cases}</math>
  +
  +
 
|}
 
|}
  +
 
'''Текущий контроль успеваемости обучающихся по дисциплине:'''
 
'''Текущий контроль успеваемости обучающихся по дисциплине:'''
   
<span style="color:red;">(К формам текущего контроля можно отнести собеседование, коллоквиум, тест, контрольную работу, лабораторную работу, эссе, реферат и иные творческие работы.)</span>
 
 
{| class="wikitable" style="width:70%;"
 
{| class="wikitable" style="width:70%;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
| style="width:5%" | №<br>п/п
 
| style="width:5%" | №<br>п/п
 
| style="width:20%" | Наименование раздела<br>дисциплины
 
| style="width:20%" | Наименование раздела<br>дисциплины
| style="width:25%" | Форма текущего контроля<br><br><span style="color:red;">(выберите соответствующие формы контроля)</span>
+
| style="width:25%" | Форма текущего контроля<br>
| style="width:50%" | Материалы текущего контроля<br><br><span style="color:red;">(Указываются ВСЕ ЗАДАНИЯ/ВОПРОСЫ текущего контроля успеваемости обучающихся по разделам дисциплины подробно в соответствии с требованиями)</span>
+
| style="width:50%" | Материалы текущего контроля<br>
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 1 || Основные правила комбинаторики || Письменная контрольная || На кафедре дискретной математики лежит стопка 63 непроверенных контрольных работ студентов из четырёх разных групп: 20 работ из 312, 15 работ из 323, 18 работ из 324 и 10 работ из 325. Семинарист хочет взять наугад несколько работ на проверку. Какое минимальное количество работ необходимо взять, чтобы среди них гарантированно нашлось
| style="text-align:center;" | 1.
 
|
 
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
 
| Например:
 
Устный / письменный опрос:<br>-<br>-<br>-<br>...<br>
 
Тематика групповых проектов:<br>-<br>-<br>-<br>...<br>
 
Темы докладов:<br>-<br>-<br>-<br>...<br>
 
Тематика эссе:<br>-<br>-<br>-<br>...<br>
 
Задания, в том числе, для групповых проектов:<br>-<br>-<br>-<br>...<br>
 
Тестирование (письменное или компьютерное):<br>-<br>-<br>-<br>...<br><br>
 
Проверка разработки отдельных частей кода программного продукта.
 
   
  +
а) 4 работы из одной группы;
Другие формы текущего контроля, используемые Вами на занятиях<br>-<br>-<br>-<br>...<br>
 
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
б) 4 работы из 323 группы;
| style="text-align:center;" | 2.
 
  +
|
 
  +
в) 2 работы из одной группы и 2 работы из другой группы;
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
 
  +
  +
г) по одной работе из каждой из четырёх групп?
  +
  +
'''В этой задаче каждый пункт оценивается в 1 балл.'''
  +
  +
  +
  +
27 точек образуют прямоугольник размер <math>3 \times 9</math>. Каждая точка покрашена в красный или синий цвет. Докажите, что существуют 4 точки одного цвета, образующие одноцветный прямоугольник (со сторонами, параллельными исходному прямоугольнику).
  +
  +
  +
При каком минимальном значении <math>m</math> для прямоугольника из <math>6 \times m</math> точек, покрашенных в пять цветов, гарантированно найдётся одноцветный прямоугольник?
  +
  +
[[Image:pic3dm1.png]]
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 2 || Основные комбинаторные величины || Письменная контрольная || Даны множества <math>A,B</math>, причём <math>|A|=4</math>, <math>|B|=7</math>. Найдите количество таких соответствий <math>f: A \to B</math>, что:
  +
а) <math>f^{-1}</math> --- сюръективное отображение;
  +
б) <math>f^{-1}</math> --- сюръективное соответствие;
  +
в) <math>f</math> --- инъективное соответствие;
  +
г) <math>f</math> --- инъективное отображение.
  +
'''В этой задаче каждый пункт оценивается в 2 балла. Ответ надо дать в виде суммы не более 10 слагаемых, без использования чисел сочетаний/размещений/полиномиальных коэффициентов'''
  +
  +
  +
  +
Имеется 4 коробки (красная, синяя, желтая, зеленая), и 9 шаров (3 красных, 2 синих, и по одному желтому, зеленому, фиолетовому и белому). Сколькими способами можно разложить шары по коробками, если нужно чтобы в каждой коробке что-то лежало?
  +
''Ответ дайте в виде суммы не более 10 слагаемых, '''без использования''' знаков вида <math>C_*^*</math>, <math>A_*^*</math>, <math>P(*,*,*)</math>''
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 3 || Тождества с биномиальными коэффициентами || Письменная контрольная || Напишите коэффициент у данного монома в данном разложении (Ответ надо дать в виде суммы не более 10 слагаемых, разрешается использовать символ <math>P(*,*,*)</math>):
  +
  +
а) <math>x^{25}</math> в <math>(x^2+x^4-x^7)^{10}</math>;
  +
  +
б) <math>x^{26}</math> в <math>(x^2+x^4-x^7)^{10}</math>;
  +
  +
в) <math>x^{27}</math> в <math>(x^2+x^4-x^7)^{10}</math>.
  +
  +
  +
  +
Докажите тождество:
  +
<math>\sum_{k=r}^n C_n^k \cdot C_k^r \cdot 3^k = C_n^r \cdot 3^r \cdot 4^{n-r}</math>
  +
  +
  +
20 студентов (студенты разные) сдают экзамен в три дня. Студент может прийти в один из дней, а может и не прийти вовсе (неявка). Сколько существует различных распределений студентов по дням, таких чтобы
  +
а) все студенты пришли на экзамен;
  +
б) в первый день пришёл хотя бы один студент;
  +
в) в каждый из дней пришли ровно 5 студентов?
  +
Теперь предположим, что экзамен длится 7 дней, а каждый студент имеет несколько попыток. Сколько существует различных распределений студентов по дням, таких чтобы
  +
г) каждый студент пришёл на экзамен трижды, причём в разные дни;
  +
д) каждый студент пришёл на экзамен трижды, но теперь необязательно в разные дни?
  +
'''В ответах разрешается использовать только знаки арифметических действий, возведение в степень, а также факториалы, <math>C_{\ast}^{\ast}</math>, <math>A_{\ast}^{\ast}</math> и <math>P(\ast,\ldots,\ast)</math>.'''
  +
  +
  +
Хитрый пароль состоит из двух частей. Первая часть --- код из 4 цифр, в которых как минимум две чётные цифры. Вторая часть --- код из 7 различных цифр, из которых первые 4 идут по возрастанию, а оставшиеся 3 по убыванию. Сколько существует хитрых паролей?
  +
''Ответ разрешается оставить в виде суммы нескольких слагаемых (без троеточий) с использованием факториалов, <math>C_{\ast}^{\ast}</math>, <math>A_{\ast}^{\ast}</math> и <math>P(\ast,\ldots,\ast)</math>''
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 4 || Рекуррентные соотношения || Письменная контрольная || Имеется алфавит из 6-х символов <math>\{a,b,c,d,e,f\}</math>. Обозначим через <math>A_n</math> количество последовательностей длины <math>n</math>, которые содержат нечётное количество символов <math>a</math>. Найдите и решите рекуррентное соотношение для <math>A_n</math>.
  +
  +
  +
  +
В наличии имеются плитки размеров <math>1\times 1</math>, <math>1 \times 2</math> нескольких типов. Для каждого набора плиток
  +
найдите рекуррентное соотношение для <math>a_n</math>, количества способов выложить плитку размером <math>1\times n</math> и выпишите явную формулу для решения
  +
  +
Заполните таблицу.
  +
{| class="wikitable"
  +
|-
  +
! набор плиток
  +
! рекуррентное соотношение 2-го порядка
  +
! явная формула
  +
|-
  +
| 1 вид плитки размера <math>1\times 1;</math>
  +
| <math>a_{n+2} = a_{n+1} + a_n,\ a_1 = 1,\ a_2 = 2</math>
  +
| <math>\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</math>
  +
|-
  +
| 1 вид плитки размера <math>1\times 2</math>
 
|
 
|
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 3.
 
|
 
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
 
 
|
 
|
  +
|-
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| 2 вида плитки размера <math>1\times 1;</math>
| style="text-align:center;" | 4.
 
|
 
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
 
 
|
 
|
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 5.
 
|
 
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
 
 
|
 
|
  +
|-
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| 1 вид плитки размера 1 <math> \times 2</math>
| style="text-align:center;" | ... || || ||
 
  +
|
  +
|
  +
|-
  +
| 2 вида плитки размера <math>1\times 1;</math>
  +
|
  +
|
  +
|-
  +
| 3 вида плитки размера 1 <math>\times 2</math>
  +
|
  +
|
  +
|-
 
|}
 
|}
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 5 || Разбиения || Письменная контрольная || Обозначим через <math>f(n;n_1,\ldots,n_k)</math> количество упорядоченных разбиений <math>n</math> на слагаемые <math>n_1,\ldots,n_k</math>, а через <math>F (n;n_1,\ldots,n_k)</math> количество неупорядоченных разбиений <math>n</math> на слагаемые <math>n_1,\ldots,n_k</math>. Найдите
  +
  +
а) <math>f(9;1,2,3,4,5,6,7,8,9)</math>;
  +
  +
б) <math>f(11;1,3,5,7,9)</math>;
  +
  +
в) <math>F(10;1,3,5,7,9)</math>.
  +
  +
  +
  +
==== Задача (10) ====
  +
Пусть <math>B</math> есть число способов представить число <math>100</math> в виде суммы нескольких различных элементов множества <math>\{1, 2, 3,\ldots,100\}</math> и такого же числа различных элементов множества <math>\{0, 1, 2, \ldots,99\}</math>. [Например, есть представления <math>(1+2)+(0+97)</math>, <math>(1)+(99)</math>, <math>(1+2+3)+(2+4+88)</math>.] Сравните <math>B</math> и <math>p(100)</math>, последнее -- это количество неупорядоченных разбиений числа <math>100</math>.
  +
  +
  +
  +
Пусть <math>B</math> есть число способов представить число <math>100</math> в
  +
виде суммы нескольких различных элементов множества <math>\{1, 2, 3,\ldots,100\}</math>
  +
и такого же числа различных элементов множества <math>\{0, 1, 2, \ldots,99\}</math>. [Например,
  +
есть представления <math>(1+2)+(0+97)</math>, <math>(1)+(99)</math>, <math>(1+2+3)+(2+4+88)</math>.]
  +
Сравните <math>B</math> и <math>p(100)</math>, последнее --- это количество неупорядоченных разбиений числа <math>100</math>.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 6 || Формальные степенные ряды и производящие функции || Письменная контрольная || Вычислите производящую функцию для следующих последовательностей. Преобразуйте формальный степенной ряд к отношению многочленов.
  +
{| class="wikitable"
  +
|-
  +
! последовательность <math>a_n</math>
  +
! производящая функция
  +
|-
  +
| числа Фибоначчи <math>0,1,1,2,\ldots</math>
  +
| <math>\frac{t}{1-t-t^2}</math>
  +
|-
  +
| количество положительных целых
  +
решений <math>(a,b)</math> уравнения <math>a+b=n</math>
  +
|
  +
|-
  +
| количество неотрицательных целых
  +
решений <math>(a,b,c)</math> уравнения <math>a+b+c=n</math>
  +
|
  +
|-
  +
| количество целых решений <math>(a,b,c)</math>
  +
уравнения <math>a+b+c=n</math>, с условиями
  +
<math>0\leq a \leq 6</math>, <math>0 \leq b \leq 3</math>, <math>0 \leq c \leq 1</math>
  +
|
  +
|}
  +
  +
  +
  +
Найдите радиус сходимости у следующих формальных степенных рядов.
  +
  +
а) <math>\frac{1}{1+4t}</math>;
  +
  +
б) <math>\frac{4}{1+9t}</math>;
  +
  +
в) <math>\frac{2t^2}{(1+9t^2)^2}</math>;
  +
  +
г) <math>\frac{1}{(t-2023)^{2023}}</math>;
  +
  +
д) <math>\frac{1}{\sqrt{1-3t}}</math>.
  +
  +
  +
  +
Найдите коэффициент при <math>x^{2023}</math> у следующих формальных степенных рядов.
  +
  +
а) <math>\frac{1}{1+4t}</math>;
  +
  +
б) <math>\frac{4}{1+9t}</math>;
  +
  +
в) <math>\frac{2t^2}{(1+9t^2)^2}</math>;
  +
  +
г) <math>\frac{1}{(t-2023)^{2023}}</math>;
  +
  +
д) <math>\frac{1}{\sqrt{1-3t}}</math>.
  +
  +
  +
|}
  +
 
'''Контрольные вопросы для подготовки к промежуточной аттестации:'''
 
'''Контрольные вопросы для подготовки к промежуточной аттестации:'''
 
{| class="wikitable" style="width:70%;"
 
{| class="wikitable" style="width:70%;"
Line 116: Line 804:
 
| style="width:25%" | Наименование <br> раздела дисциплины
 
| style="width:25%" | Наименование <br> раздела дисциплины
 
| style="width:65%" | Вопросы
 
| style="width:65%" | Вопросы
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 1. || ||
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 2. || ||
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 3. || ||
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 4. || ||
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 5. || ||
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | ... || ||
 
 
|}
 
|}
 
'''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:'''
 
'''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:'''
   
<span style="color:red;">(Указываются ВСЕ ЗАДАНИЯ/ВОПРОСЫ для промежуточной аттестации.)</span>
 
   
  +
1. Правило сложения. Правило умножения. Примеры: автомобильные номера, количество шестизначных чисел с различными условиями на цифры (задача 7.3). Принцип Дирихле. Пример на принцип Дирихле с квадратом.
1.<br>2.<br>3.<br>...<br>48.<br>49.<br>50.<br>...
 
  +
  +
2. Размещения, перестановки и сочетания. Доказательство формул для чисел размещения и сочетания с повторениями и без повторений. Типовые задачи (аналогичные 7.5, 7.6, 7.7, 7.8).
  +
  +
3. Бином Ньютона. Полиномиальный коэффициент и полиномиальная формула. Типовые задачи (аналогичные задачам 7.10, 8.5).
  +
  +
4. Комбинаторные тождества (6 штук).
  +
  +
5. Формула включений и исключений (формулировка и док-во для <math>n=3</math>). Формула для количества беспорядков на <math>n</math> элементах (Задача 9.4 про перестановки книг).
  +
  +
6. Формула включений и исключений (формулировка и док-во для <math>n=3</math>). Формула для количества сюръекций из <math>k</math>-элементного множества в <math>m</math>-элементное (Задача 9.5 про домики).
  +
  +
7. Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Рекуррентные формулы. (Задача 12.2 а)б)).
  +
  +
8. Задачи о разбиениях чисел на слагаемые. Упорядоченные разбиения. Количество всех упорядоченных разбиений на произвольные слагаемые. (Задача 12.1 а)б)).
  +
  +
9. Диаграммы Юнга. Теоремы Эйлера о равенстве количеств неупорядоченных разбиений числа <math>n</math> на <math>k</math> или не более, чем <math>k</math> слагаемых (3 штуки).
  +
  +
10. Линейные рекуррентные соотношения с постоянными коэффициентами. Характеристическое уравнение. Общая формула для соотношения <math>n</math>-го порядка (формулировка, частный случай <math>n=2</math> --- б/д). Формула для чисел Фибоначчи.
  +
  +
11. Формальные степенные ряды, операции над ними. Пример вычисления суммы и произведения (Задача 14.3).
  +
  +
12. Формальные степенные ряды. Определение обратного ряда. Пример деления в столбик. Примеры нахождения обратных рядов (задача 14.6).
  +
  +
13. Числа Фибоначчи и их производящая функция. Радиус сходимости, значение <math>\sum_{n=0}^{\infty} \frac{F_n}{2^n}</math>.
  +
  +
14. Числа Каталана. Производящая функция для чисел Каталана.
  +
  +
15. Задача о раскраске множества в два цвета.
  +
  +
16. Сумма степеней натуральных чисел.
  +
  +
17. Знакопеременные тождества (2 штуки): сумма биномиальных коэффициентов и количество сюръекций.
  +
  +
18. Формула включений и исключений.
  +
  +
19. Формула включений и исключений (формулировка и док-во для <math>n=3</math>). Формула для функции Эйлера через произведение по простым сомножителям (док-во через формулу вкл-искл.) (Задача 9.1в.)
  +
  +
20. Формула обращения Мёбиуса.
  +
  +
21. Функция Эйлера. Формула с произведением по простым числам: доказательство при помощи формулы обращения Мёбиуса (Задача 10.6в).
  +
  +
22. Линейные рекуррентные соотношения с постоянными коэффициентами. Характеристическое уравнение. Общая формула для соотношения 2-го порядка с одинаковыми корнями характеристического уравнения.
  +
  +
23. Линейные рекуррентные соотношения с постоянными коэффициентами. Характеристическое уравнение. Общая формула для соотношения 2-го порядка с различными корнями характеристического уравнения.
  +
  +
24. Формальный степенной ряд <math>(1-x)(1-x^2)(1-x^3)\ldots</math>. Теорема Эйлера о коэффициентах этого ряда (формулировка). Проверка верности теоремы Эйлера для <math>k=1,2</math>. Теорема о количестве разбиений на чётное и нечётное количество различных слагаемых (формулировка).
  +
  +
25. Формальные степенные ряды. Строгое формальное определение через последовательности. Пример вычисления суммы и произведения рядов (Задача 14.3)
  +
  +
26. Формальные степенные ряды, операции над ними. Определение обратного ряда.
  +
Пример деления в столбик. Комбинаторное тождество, получаемое с использованием формального степенного ряда <math>\frac{1}{(1-x^2)^2}</math>.
  +
  +
27. Формальные степенные ряды, операции над ними. Определение обратного ряда. Критерий обратимости ряда (задача 14.5).
  +
  +
28. Вычисление суммы <math>\sum_{k=0}^n k^2 C_n^k \left(\frac{1}{17}\right)^k</math>.
  +
  +
29. Определение радиуса сходимости формального степенного ряда. Теорема Коши-Адамара о сходимости степенных рядов (формулировка). Примеры, иллюстрирующие теорему (3 примера, показывающие, что на границе может быть сходимость/расходимость, задача 15.2).
  +
  +
30. Принцип Дирихле. Оценки мощности множества попарно неортогональных <math>(-1,0,1)</math>-векторов: верхняя оценка величиной 140 и нижняя оценка величиной 70.
  +
  +
31. Числа Каталана. Формула для коэффициентов ряда <math>\sqrt{1+x}</math>. (Задача 14.9)
  +
  +
32. Числа Каталана. Формула для коэффициентов ряда <math>\sqrt{1+x}</math> (б/д). Вывод из неё формулы для чисел Каталана.
  +
  +
33. Производящая функция для количества неупорядоченных разбиений в общем виде и для разбиений специального вида (задача 15.10). Доказательство того, что количества разбиений на попарно различные слагаемые и на нечётные слагаемые совпадают.
  +
  +
  +
 
=== Перечень учебно-методического обеспечения дисциплины ===
 
=== Перечень учебно-методического обеспечения дисциплины ===
 
Список основной литературы:
 
Список основной литературы:
   
 
Список дополнительной литературы:
 
Список дополнительной литературы:
  +
 
=== Методические указания для обучающихся по освоению дисциплины ===
 
=== Методические указания для обучающихся по освоению дисциплины ===
<span style="color:red;">(Указываются рекомендации для обучающихся, которые раскрывают суть их работы при различных видах деятельности в рамках освоения дисциплины. Данные рекомендации должны охватывать работу с лекционным материалом, подготовку и работу во время проведения семинарских занятий, самостоятельную работу, подготовку к текущему контролю и промежуточной аттестации)</span>
 
   
  +
<span style="color:red;">(Выберите соответствующие виды учебных занятий, которые используются при изучении Вашей дисциплины)</span>
 
 
{| class="wikitable" style="width:80%;"
 
{| class="wikitable" style="width:80%;"
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#FF0000; font-weight:bold;"
+
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; font-weight:bold;"
 
| style="width:20%" | Вид учебных<br>занятий/деятельности
 
| style="width:20%" | Вид учебных<br>занятий/деятельности
 
| style="width:80%" | Деятельность обучающегося
 
| style="width:80%" | Деятельность обучающегося
  +
|- style="background-color:#F8F9FA; color:#202122;"
|-
 
  +
| style="text-align:center;" | Лекция || Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
| style="vertical-align:middle; text-align:center; color:red;" | Лекция
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
| style="vertical-align:middle; text-align:left; color:red;" | Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
 
  +
| style="text-align:center;" | Практическое (семинарское) занятие || При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.
|-
 
  +
Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
| style="vertical-align:middle; text-align:center; color:red;" | Практическое (семинарское) занятие
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.<br>Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
 
  +
| style="text-align:center;" | Устный/письменный опрос || Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
|-
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
| style="vertical-align:middle; text-align:center; color:red;" | Устный/письменный опрос
 
  +
| style="text-align:center;" | Контрольная работа || При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
| style="vertical-align:middle; text-align:left; color:red;" | Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
 
  +
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Реферат
 
| style="vertical-align:middle; text-align:left; color:red;" | Поиск источников и литературы, составление библиографии. При написании реферата рекомендуется использовать разнообразные источники, монографии и статьи из научных журналов, позволяющие глубже разобраться в различных точках зрения на заданную тему. Изучение литературы следует начинать с наиболее общих трудов, затем следует переходить к освоению специализированных исследований по выбранной теме. Могут быть использованы ресурсы сети «Интернет» с соответствующими ссылками на использованные сайты.<br>Если тема содержит проблемный вопрос, следует сформулировать разные точки зрения на него. Рекомендуется в выводах указать свое собственное аргументированное мнение по данной проблеме. Подготовить презентацию для защиты реферата.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Эссе
 
| style="vertical-align:middle; text-align:left; color:red;" | Написание прозаического сочинения небольшого объема и свободной композиции, выражающего индивидуальные впечатления и соображения по конкретному поводу или вопросу и заведомо не претендующего на определяющую или исчерпывающую трактовку предмета. При работе над эссе следует четко и грамотно формулировать мысли, структурировать информацию, использовать основные понятия, выделять причинно-следственные связи. Как правило эссе имеет следующую структуру: вступление, тезис и аргументация его, заключение. В качестве аргументов могут выступать исторические факты, явления общественной жизни, события, жизненные ситуации и жизненный опыт, научные доказательства, ссылки на мнение ученых и др.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Подготовка к промежуточной аттестации
 
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей.<br>Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Практические (лабораторные) занятия
 
| style="vertical-align:middle; text-align:left; color:red;" | Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Самостоятельная работа
 
| style="vertical-align:middle; text-align:left; color:red;" | Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Видеопрезентация
 
| style="vertical-align:middle; text-align:left; color:red;" | Подготовка видеопрезентаций по курсу. Видеопрезентации могут быть сделаны на любую тему, затронутую в ходе курса. Темы должны быть заранее согласованы с преподавателем. Видеопрезентации продолжительностью около 5 минут (300 секунд) должны быть подготовлены в группах, определяемых преподавателем. Несмотря на то, что это групповая работа, должен явно присутствовать вклад каждого члена группы.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Доклад
 
| style="vertical-align:middle; text-align:left; color:red;" | Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Дискуссия
 
| style="vertical-align:middle; text-align:left; color:red;" | Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Контрольная работа
 
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Тестирование (устное/письменное)
 
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Индивидуальная работа
 
| style="vertical-align:middle; text-align:left; color:red;" | При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Разработка отдельных частей кода
 
| style="vertical-align:middle; text-align:left; color:red;" | Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Выполнение домашних заданий и групповых проектов
 
| style="vertical-align:middle; text-align:left; color:red;" | Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.
 
 
|}
 
|}
 
=== Методы и технологии обучения, способствующие формированию компетенции ===
 
=== Методы и технологии обучения, способствующие формированию компетенции ===
<span style="color:red;">(Указываются все используемые преподавателем методы и технологии обучения)</span>
 
 
{| class="wikitable"
 
{| class="wikitable"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
| Методы и технологии обучения, способствующие формированию компетенции
 
| Методы и технологии обучения, способствующие формированию компетенции
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| Информационно – коммуникационная технология, Педагогика сотрудничества, Традиционные технологии, Модульная технология
| &nbsp;
 
|}
 
<span style="color:red;">Например:</span>
 
{| class="wikitable" style="width:80%;"
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center; width:5%;" | 1.
 
| style="width:20%;" | Информационно – коммуникационная технология
 
| style="width:75%;" | &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 2.
 
| Технология развития критического мышления
 
| Основные методические приемы развития критического мышления
 
# Прием «Кластер»
 
# Таблица
 
#Учебно-мозговой штурм
 
#Интеллектуальная разминка
 
#Зигзаг, зигзаг -2
 
#Прием «Инсерт»
 
#Эссе
 
#Приём «Корзина идей»
 
#Приём «Составление синквейнов»
 
#Метод контрольных вопросов
 
#Приём «Знаю../Хочу узнать…/Узнал…»
 
#Круги по воде
 
#Ролевой проект
 
#Да – нет
 
#Приём «Чтение с остановками»
 
#Приём «Взаимоопрос»
 
#Приём «Перепутанные логические цепочки»
 
#Приём «Перекрёстная дискуссия»
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 3.
 
| Проектная технология
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 4.
 
| Технология проблемного обучения
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 5.
 
| Кейс – технология
 
| К методам кейс-технологий, активизирующим учебный процесс, относятся:
 
*метод ситуационного анализа (Метод анализа конкретных ситуаций, ситуационные задачи и упражнения; кейс-стадии)
 
*метод инцидента;
 
*метод ситуационно-ролевых игр;
 
*метод разбора деловой корреспонденции;
 
*игровое проектирование;
 
*метод дискуссии.
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 6.
 
| Технология интегрированного обучения
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 7.
 
| Педагогика сотрудничества
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 8.
 
| Технологии уровневой дифференциации
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 9.
 
| Групповая технология
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 10.
 
| Традиционные технологии (классно-урочная система)
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 11.
 
| Здоровьесберегающие технологии
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 12.
 
| Игровая технология
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 13.
 
| Модульная технология
 
|
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 14.
 
| Технология мастерских
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| &nbsp;
 
| и др.
 
| &nbsp;
 
 
|}
 
|}

Latest revision as of 01:09, 4 April 2024

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

Квалификация выпускника: бакалавр
Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”
Направленность (профиль) образовательной программы: Математические основы ИИ
Программу разработал(а):

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

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

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

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


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

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

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


п/п
Наименование раздела
дисциплины
Содержание дисциплины по темам
1. Основные правила комбинаторики - правило сложения

- правило умножения

- правило дополнения

- принцип Дирихле

2. Основные комбинаторные величины - размещения с повторениями / без повторений

- сочетания с повторениями/ без повторений

- перестановки

- треугольник Паскаля

- линейный город

- биномиальный и полиномиальный коэффициент

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

- унимодальность

- рекуррентное соотношение

- Бином Ньютона

- сумма биномиальных коэффициентов (в том числе альтернированная)

- сумма квадратов биномиальных коэффициентов

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

- формула включений и исключений

- число беспорядков

4. Рекуррентные соотношения - линейные однородные рекуррентные соотношения

- л.о.р.с. для степени 2 с разными корнями

- л.о.р.с. для степени 2 с кратным корнем

- формулировка теоремы в общем случае

- числа Фибоначчи

- формулировка теоремы для неоднородного случая

5. Разбиения - упорядоченные и неупорядоченные разбиения

- диаграммы Юнга

- теоремы Эйлера о равенстве неупорядоченных разбиений

- асимптотика неупорядоченных разбиений

6 Формальные степенные ряды и производящие функции - формальные степенные ряды

- обратимость ряда, пример деления в столбик

- доказательство комб. тождеств при помощи формального степенного ряда

- производящие функции для рекуррентных соотношений

- возведение ряда в степень

- числа Каталана

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

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


п/п
Наименование раздела
дисциплины (модуля)
Перечень рассматриваемых тем (вопросов)
1 Основные правила комбинаторики Принцип Дирихле. Пусть есть ящиков и кроликов. Если расселить кроликов по ящикам, то найдется хотя бы один ящик, в котором окажутся не менее кроликов.


В мешке имеется красных шара, зеленых шаров, синих, желтых и по белых, черных и серых (всего шаров). Сколько шаров необходимо вынуть из мешка, чтобы среди них гарантированно нашлось шаров одного цвета?


Комиссия из человек провела заседаний, причем на каждом заседании присутствовали ровно членов комиссии. Докажите, что найдутся два члена комиссии, по крайней мере дважды встречавшиеся на заседаниях.


В таблице расставлены целые числа, причем любые два числа в соседних клетках отличаются не более, чем на . Докажите, что среди этих чисел найдутся два равных.


Пусть имеется множество из слов в алфавите из символа. Докажите, что хотя бы одно из слов не короче .


В правильном треугольнике со стороной отмечено пять точек. Докажите, что найдется пара точек, удаленных друг от друга не более, чем на .

2 Основные комбинаторные величины Пусть . Извлекать элементы из можно по порядку или <<пригорошнями>>. Первые называются размещениями, вторые --- сочетаниями. При этом каждое из них бывает как с повторениями символов, так и без.
  • Размещением без повторений называется любой набор различных объектов , расположенных друг за другом в определенном порядке. Например, слова «лягушка» и «гуляшка» --- это два разных 7-размещения без повторений букв русского алфавита, хотя состоят они из одних и тех же букв.

Размещение с повторениями --- это снова любой набор объектов , расположенных друг за другом в определенном порядке. Только теперь объекты в размещении могут совпадать. Например, «жаба» и «абаж» --- два разных 4-размещения с повторениями из букв русского алфавита.

Сочетания без повторений отличаются от размещений без повторений тем, что в них порядок объектов значения не имеет. Так, «лягушка» и «гуляшка» представляют собой одно и то же 7-сочетание без повторений букв {л, я, г, у, ш, к, а } русского алфавита.

Сочетания с повторениями аналогично, например { ж, а, б, а } = { а, б, а, ж }.


Сформулируйте на языке теории множеств что такое размещение с повторениями/ без повторений и сочетания с повторениями (не используя понятий набор и порядок, разрешается использовать все определения из первых двух листков, например: множество, элемент, подмножество, все виды отображений, декартово произведение).

Докажите формулу для числа размещений без повторений (если вы будете пользоваться правилом умножения, сформулируйте чётко, какие множества A и B вы используете).


(а) Сколько существует шестизначных чисел?

(б) Сколько существует шестизначных чисел, делящихся на 5?

(в) Сколько существует шестизначных чисел, в записи которых присутствует хотя бы одна чётная цифра?


На плоскости отмечено 10 точек так, что никакие три из них не лежат на одной прямой. Сколько существует треугольников с вершинами в этих точках?


балбесов-первокурсников и семинарист пришли в кинотеатр и сели в одном ряду. Семинарист должен сидеть с краю, а Петю, Колю и Васю нельзя сажать втроем. Сколькими способами можно рассадить группу?


Из класса, в котором учатся человек, назначаются на дежурство в столовую человека. Сколькими способами это можно сделать?

Сколько существует способов набрать команду дежурных, в которую попадет ученик этого класса Коля Васин?

В группе учатся студентов. Согласно новому указу Минздрава группы нужно вакцинировать. Сколькими способами это можно сделать?

Выяснилось, что один студент этой группы Коля Васин уже провакцинирован. Сколько теперь существует способов исполнить указ Минздрава?


У королевы есть одинаковых зеркал. Сколькими способами их можно повесить в разных залах замка так, чтобы в каждом зале было хотя бы одно зеркало?


В пекарне продавались вида пирожков: элеши, эчпочмаки, перемячи и кыстыбыи. Сколькими способами можно купить пирожков?


Есть попарно различных чашек и неразличимых стаканов. Также имеется попарно различных ложек и неразличимых кусков сахара. Сколькими способами можно разложить:

а) ложки по чашкам;

б) сахар по чашкам;

в) ложки по стаканам, если ?


На ютуб-канале есть плейлист из лекций по ДМ. Сколькими способами их можно переставить так, чтобы

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

б) те же лекции по-прежнему были в правильном порядке, но никакие

в) две из них не шли подряд?


Сколько имеется способов раздать разных цветков, трём девушкам: какой-то --- , а остальным~--- по цветка?


Дано множество . Даны числа , .

  • Сколько можно составить совокупностей из различных -элементных подмножеств множества ?
  • Сколько из этих совокупностей устроены так, что каждое множество в них имеет непустое пересечение с подмножеством ?


Сколькими способами можно выбрать из полной колоды, содержащей карты, карт так, чтобы среди них были все масти?

3 Тождества с биномиальными коэффициентами Покажите, что число -сочетаний без повторений из -элементного множества равно

а) Количеству последовательностей из 0 и 1 длины с ровно единицами.

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

в) (Треугольник Паскаля) -ому числу в -ой строке треугольника Паскаля (нумерация с )

г) (Бином Ньютона) Коэффициенту при мономе в разложении .

Pic1dm1.png


Многие из следующих тождеств/сумм можно доказывать/находить несколькими способами:

- через непосредственное определение

- при помощи формулы

- используя интерпретации выше

Докажите следующие тождества при целых неотрицательных:

а)

б)

в)


Найдите суммы при целых неотрицательных  :

а)

б)

в)

г*)

д)

е)

ж)

з)

и)

к)

л)

м*)

н*)


Найдите .

Посчитайте коэффициенты при и в разложении .


На оси абсцисс разместим (произвольным образом) 2n точек, разобьем множество этих точек на пары (опять-таки, произвольно) и элементы каждой пары соединим дугой, так, как это показано на рисунке. Получившийся объект назовем хордовой диаграммой. Сколько существует различных хордовых диаграмм на 2n точках?

Pic2dm1.png


Найдите количество чисел, не превосходящих и не делящихся ни на одно из чисел , , .


Пусть --- функция Эйлера, то есть количество натуральных чисел от до , взаимно простых c .


Найдите ; ; ; , где --- простое число, .


, где --- каноническое разложение числа .


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


На кафтане расположено пять заплат произвольной формы. Площадь каждой из них больше половины площади кафтана. Тогда площадь общей части некоторых двух заплат большей одной пятой площади кафтана.


(Число беспорядков) На полке стоят 10 книг. Сколькими способами их можно переставить так, чтобы (а) ни одна книга не осталась на своем месте? (б) на месте осталось ровно 4 книги?


Сколькими способами можно расселить 20 туристов по 5 домикам, чтобы ни один домик не оказался пустым?


Сколько существует различных сюръекций из множества X = {1, . . . , k} во множество Y = {1, . . . , n}?


Сколько существует неупорядоченных разбиений k-элементного множества на n подмножеств?


В ряд записали 105 единиц, поставив перед каждой знак «+» . Сначала изменили знак на противоположный перед каждой третьей единицей, затем — перед каждой пятой, а затем — перед каждой седьмой. Найдите значение полученного выражения. 7 ◦ . Сколько существует перестановок чисел от 1 до 7, при которых никакие два рядом расположенных числа не отличаются на 1?


[Задача о мажордомах] К обеду за круглым столом приглашены n пар враждующих рыцарей. Требуется рассадить их так, чтобы никакие два врага не сидели рядом. Сколько существует таких рассадок?


[Задача о паросочетаниях] За круглым столом нужно рассадить n супружеских пар. Сколькими способами это можно сделать, если требуется, чтобы мужчины и женщины чередовались и чтобы ни один муж не сидел рядом со своей женой?

4 Рекуррентные соотношения Для каждого из следующих линейных рекуррентных соотношений найдите общее решение:

а)

б) ;

в)

г)

д)

е) .


Найдите решение неоднородного линейного рекуррентного соотношения

а) ;

б) ;

в) ?


Числами Фибоначчи называется последовательность , удовлетворяющая соотношениям , , для всех натуральных .


Найдите формулу для нахождения -ого члена последовательности .


Найдите

  • ;
  • ;
  • .


Сколькими способами можно разменять купюру в рублей на монеты достоинством , и рублей? %364


Найдите рекуррентное соотношение для последовательности , где -- число способов выложить прямоугольник размера

  • ;
  • доминошками размера ;
  • число способов выложить колонну кирпичами размера .


Сколько существует строк из нулей и единиц, в каждой из которых никакие два нуля не стоят рядом?


Докажите, что последовательность с общим членом удовлетворяет соотношению .


В вершине B шестиугольника ABCDEF сидит лягушка. Каждую секунду лягушка может перепрыгнуть в одну из соседних вершин. Сколькими способами она может допрыгнуть до вершины A за n прыжков?


В центральной клетке левого столбца доски 1000 × 3 стоит шахматный король. Сколькими спо[1]собами он может добраться до правого столбца доски за 999 ходов?

5 Разбиения а) Найдите количество упорядоченных разбиений числа на слагаемых.

б) Найдите общее количество упорядоченных разбиений числа на слагаемые.

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


Обозначим через () количество упорядоченных (соотв. неупорядоченных) разбиений на слагаемые .


Справедливы следующие рекуррентные формулы

а) ;

б) .

в) Каковы начальные условия в этих формулах?


а) Что больше: или ? б) Найдите оба числа, используя рекуррентные формулы.


Диаграмма Юнга -- это конечный набор клеток, выровненных по левой границе, в котором длины строк образуют невозрастающую последовательность (каждая строка такой же длины как предыдущая, или короче). Весом диаграммы Юнга называется общее количество клеток диаграммы. Набор чисел, состоящий из длин строк, задаёт разбиение веса диаграммы в сумму слагаемых. Таким образом, есть соответствие между всеми неупорядоченными разбиениями натурального числа и всеми диаграммами Юнга веса .


Сколько существует диаграмм Юнга произвольного веса, но имеющих не более строк и не более столбцов?


На доске написано несколько целых положительных чисел: , , , , . Пишем на другой доске следующие числа: --- сколько всего чисел на первой доске, --- сколько там чисел, больших единицы, --- сколько там чисел, больших двойки, и т.~д., пока получаются положительные числа. На этом заканчиваем --- нули не пишем. На третьей доске пишем числа , , , , построенные по числам второй доски аналогичным образом. Докажите, что наборы чисел на первой и третьей досках совпадают.


Докажите, что число неупорядоченных разбиений на слагаемых, не превосходящих , равно числу неупорядоченных разбиений на слагаемых, не превосходящих .


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


Докажите, что количество неупорядоченных разбиений на различные нечётные слагаемые равно количеству симметричных диаграмм Юнга веса .


Какие натуральные числа можно разбить в сумму нескольких (больше одного) подряд идущих натуральных чисел?

6 Формальные степенные ряды и производящие функции Рассмотрим множество последовательностей (здесь берутся из множества чисел , или ) и введём на них операции сложения и умножения следующим образом:





Пусть , .

1) Найдите .

2) Покажите, что любая последовательность единственным образом представляется в виде .


Покажите, что все свойства многочленов (коммутативность по сложению/умножению, ассоциативность, дистрибутивность) переносятся на формальные степенные ряды.


Пусть дан ряд . Корректна ли операция подстановки вместо ряда ? Ряда без свободного члена?


Определим производную формального степенного ряда как ряд . Производную можно брать несколько раз подряд, через обозначается -ая производная ряда .

Производная линейна, то есть (здесь , --- формальные степенные ряды).

Выполнено тождество Лейбница, то есть .

(Ряд Тейлора в нуле). Докажите, что --- свободный член ряда .

Пусть , . Найдите , .

Пусть , . Найдите и .

Существует ли два таких ненулевых степенных ряда , что ?

Ряд называется обратимым, если существует такой ряд , что . называется рядом, обратным к и обозначается так: .


Докажите, что ряд обратим тогда и только тогда, когда , причём обратный ряд единственен.


Найдите коэффициенты ряда ; ; ; ; .


Верно ли равенство для формальных степенных рядов?


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


При каких условиях на степенной ряд его можно разделить на степенной ряд (то есть уравнение разрешимо относительно неизвестного степенного ряда )?


При каких условиях на степенной ряд разрешимо уравнение ?


Пусть ---- степенной ряд, задаваемый уравнением . Найдите коэффициенты .


Пусть . Положим .


Если , то совпадает с биномиальным коэффициентом.


Определим ряд . Покажите, что при определения согласованы.


Покажите, что .


Используя определение, найдите коэффициенты ряда . Сравните ответ с ответом в задаче предыдущей задаче пункте в.


Вычислите .


Вычислите ( --- числа Фибоначчи).


  • Как выглядит производящая функция для числа способов набрать рублей монетами достоинством , и рублей?
  • Тот же вопрос, при условии, что есть всего три 5-рублёвые монеты.


Найдите производящую функцию для числа

  • упорядоченных разбиений числа ;
  • неупорядоченных разбиений ;
  • неупорядоченных разбиений на нечётные слагаемые;
  • неупорядоченных разбиений на попарно различные слагаемые.

Докажите, что функции в последних двух пунктах совпадают.


  • Докажите тождество .


Найдите радиус сходимости ряда

,

,

,

.


Приведите пример, когда на границе ряда (то есть при ) есть сходимость в обеих точках; расходимость в обеих точках; сходимость в одной точке и расходимость в другой точке.


Найдите производящую функцию для последовательности . \pu Какой у неё радиус сходимости?


В каких точках действительной прямой сходится ряд , где задано следующим образом?


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


п/п
Наименование раздела
дисциплины
Форма текущего контроля
Материалы текущего контроля
1 Основные правила комбинаторики Письменная контрольная На кафедре дискретной математики лежит стопка 63 непроверенных контрольных работ студентов из четырёх разных групп: 20 работ из 312, 15 работ из 323, 18 работ из 324 и 10 работ из 325. Семинарист хочет взять наугад несколько работ на проверку. Какое минимальное количество работ необходимо взять, чтобы среди них гарантированно нашлось

а) 4 работы из одной группы;

б) 4 работы из 323 группы;

в) 2 работы из одной группы и 2 работы из другой группы;

г) по одной работе из каждой из четырёх групп?

В этой задаче каждый пункт оценивается в 1 балл.


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


При каком минимальном значении для прямоугольника из точек, покрашенных в пять цветов, гарантированно найдётся одноцветный прямоугольник?

Pic3dm1.png

2 Основные комбинаторные величины Письменная контрольная Даны множества , причём , . Найдите количество таких соответствий , что:

а) --- сюръективное отображение; б) --- сюръективное соответствие; в) --- инъективное соответствие; г) --- инъективное отображение. В этой задаче каждый пункт оценивается в 2 балла. Ответ надо дать в виде суммы не более 10 слагаемых, без использования чисел сочетаний/размещений/полиномиальных коэффициентов


Имеется 4 коробки (красная, синяя, желтая, зеленая), и 9 шаров (3 красных, 2 синих, и по одному желтому, зеленому, фиолетовому и белому). Сколькими способами можно разложить шары по коробками, если нужно чтобы в каждой коробке что-то лежало? Ответ дайте в виде суммы не более 10 слагаемых, без использования знаков вида , ,

3 Тождества с биномиальными коэффициентами Письменная контрольная Напишите коэффициент у данного монома в данном разложении (Ответ надо дать в виде суммы не более 10 слагаемых, разрешается использовать символ ):

а) в ;

б) в ;

в) в .


Докажите тождество:


20 студентов (студенты разные) сдают экзамен в три дня. Студент может прийти в один из дней, а может и не прийти вовсе (неявка). Сколько существует различных распределений студентов по дням, таких чтобы а) все студенты пришли на экзамен; б) в первый день пришёл хотя бы один студент; в) в каждый из дней пришли ровно 5 студентов? Теперь предположим, что экзамен длится 7 дней, а каждый студент имеет несколько попыток. Сколько существует различных распределений студентов по дням, таких чтобы г) каждый студент пришёл на экзамен трижды, причём в разные дни; д) каждый студент пришёл на экзамен трижды, но теперь необязательно в разные дни? В ответах разрешается использовать только знаки арифметических действий, возведение в степень, а также факториалы, , и .


Хитрый пароль состоит из двух частей. Первая часть --- код из 4 цифр, в которых как минимум две чётные цифры. Вторая часть --- код из 7 различных цифр, из которых первые 4 идут по возрастанию, а оставшиеся 3 по убыванию. Сколько существует хитрых паролей? Ответ разрешается оставить в виде суммы нескольких слагаемых (без троеточий) с использованием факториалов, , и

4 Рекуррентные соотношения Письменная контрольная Имеется алфавит из 6-х символов . Обозначим через количество последовательностей длины , которые содержат нечётное количество символов . Найдите и решите рекуррентное соотношение для .


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

Заполните таблицу.

набор плиток рекуррентное соотношение 2-го порядка явная формула
1 вид плитки размера
1 вид плитки размера
2 вида плитки размера
1 вид плитки размера 1
2 вида плитки размера
3 вида плитки размера 1
5 Разбиения Письменная контрольная Обозначим через количество упорядоченных разбиений на слагаемые , а через количество неупорядоченных разбиений на слагаемые . Найдите

а) ;

б) ;

в) .


Задача (10)

Пусть есть число способов представить число в виде суммы нескольких различных элементов множества и такого же числа различных элементов множества . [Например, есть представления , , .] Сравните и , последнее -- это количество неупорядоченных разбиений числа .


Пусть есть число способов представить число в виде суммы нескольких различных элементов множества и такого же числа различных элементов множества . [Например, есть представления , , .] Сравните и , последнее --- это количество неупорядоченных разбиений числа .

6 Формальные степенные ряды и производящие функции Письменная контрольная Вычислите производящую функцию для следующих последовательностей. Преобразуйте формальный степенной ряд к отношению многочленов.
последовательность производящая функция
числа Фибоначчи
количество положительных целых

решений уравнения

количество неотрицательных целых

решений уравнения

количество целых решений

уравнения , с условиями , ,


Найдите радиус сходимости у следующих формальных степенных рядов.

а) ;

б) ;

в) ;

г) ;

д) .


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

а) ;

б) ;

в) ;

г) ;

д) .


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


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

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


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

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

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

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

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

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

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

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

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

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

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

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

13. Числа Фибоначчи и их производящая функция. Радиус сходимости, значение .

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

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

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

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

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

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

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

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

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

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

24. Формальный степенной ряд . Теорема Эйлера о коэффициентах этого ряда (формулировка). Проверка верности теоремы Эйлера для . Теорема о количестве разбиений на чётное и нечётное количество различных слагаемых (формулировка).

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

26. Формальные степенные ряды, операции над ними. Определение обратного ряда. Пример деления в столбик. Комбинаторное тождество, получаемое с использованием формального степенного ряда .

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

28. Вычисление суммы .

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

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

31. Числа Каталана. Формула для коэффициентов ряда . (Задача 14.9)

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

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


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

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

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

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

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

Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.

Устный/письменный опрос Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
Контрольная работа При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.

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

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