( + +...+ )n = å P( , ,..., )*,
(a + b)n = ∑k=0:n Cn,kakbn−k
p(n) = p(n-1) + p(n-2)- p(n-5)-p(n-7)+...+  *p(n-3* - ) + p(n-3* +)+...,
fn+m = fn-1·fm + fn·fm+1
5). Сколько различных трехзначных чисел можно составить, используя цифры 1, 2, 3, 4, 5, если каждую цифру можно использовать только один раз?
24 12
30 10
6). Сколько трехзначных чисел, делящихся на три, можно составить из всех нечетных цифр, если каждую из них использовать не более одного раза?
24
60
4
10
7). У одного человека имеется 8 книг, а у другого - 10. Сколькими способами они могут обменять друг у друга три книги на три книги?
1056
6720
176
241920
8). Сколько различных трехзначных чисел можно записать с помощью начетных цифр?
60
35
10
125
9). Решите рекуррентное соотношение fn+2 =-4 fn-1 - 4fn
, соответствующие начальным членам рекуррентной последовательности: a0 = 0, a1 = 6.
(C1+C2n)(-2)n-1.
C1(-2)n.+C2n(-2)n.
(6+6*2) (-2)n
18(-2)n-1
10). Группа школьников, в составе 25 человек, отправилась в лес. Известно, что 5 человек взяли с собой бутерброды с колбасой, 5 человек – бутерброды с ветчиной, 6 человек – бутерброды с сыром, 4 человека взяли бутерброды с ветчиной и сыром, 3 – с ветчиной и колбасой и 2 – с сыром. Некоторые взяли бутерброды трех сортов. Сколько человек взяли бутерброды трех сортов?
5
2
6
3
Вариант №2.
1). Всякое подмножество М, состоящее из k элементов, называется
Размещением
Сочетанием
Размещением с повторением
Перестановкой
2). Всякое упорядоченное конечное множество или всякая конечная последовательность длины n, все элементы которой различны называется
Размещением
Сочетанием
Размещением с повторением
Перестановкой
3). Каждый член этой последовательности, начиная с третьего, равен сумме двух предыдущих.
Рекуррентное соотношение
Числа Фибоначчи
Линейное рекуррентное соотношение с постоянными коэффициентами
Решение задачи о шляпах
4). Полиномиальная формула имеет вид
(+ +...+)n = å P(,,...,)*,
(a + b)n = ∑k=0:n Cn,kakbn−k
p(n) = p(n-1) + p(n-2)- p(n-5)-p(n-7)+...+ *p(n-3* -) + p(n-3* +)+...,
fn+m = fn-1·fm + fn·fm+1
5). Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов и одна из полос должна быть красной, (красный входит в состав данных пяти цветов)?
36
7
72
21
6). Из группы, состоящей из пяти мальчиков и восьми девочек, надо отобрать группу из четырех человек, так, чтобы в ней оказалось не менее трех девочек. Сколькими способами это можно сделать?
131
280
350
1960
7). Сколькими способами можно расставить 3 белых и 3 черных шашки на восьми полях первой горизонтали шахматной доски?
560
28
3136
66
8). Сколько различных «слов» можно составить из слова «Математика» за счет перестановки составляющих его букв?
3628800
24
151200
907200
9). ). Решите рекуррентное соотношение fn+2 =6 fn-1 - 9fn
, соответствующие начальным членам рекуррентной последовательности: a0 = 0, a1 = 6.
(C1+C2n)3n-1.
C13n.+C2n3n.
(6+6*2) 3n
18*3n-1
10). Группа школьников, в составе 25 человек, отправилась в лес. Известно, что 5 человек взяли с собой варежки, 5 человек –теплые носки, 6 человек –теплый свитер, 4 человека взяли теплые носки и варежки , 3 – варежки и теплый свитер и 2 – теплый свитер и теплые носки. Некоторые взяли все три вещи. Сколько человек взяли и варежки, и теплые носки, и теплый свитер?
5 2
6 3
5.ПРИМЕРНАЯ ТЕМАТИКА РЕФЕРАТОВ
Комбинаторные суммы и их вычисление.
Метод производящих функций в решении рекуррентных соотношений.
Перманенты и их свойства.
Числа Рамсея.
Методы линейной алгебры в теории графов.
Вероятностные методы в комбинаторике.
Восстановление графов.
Раскраска карт.
Покрытия и упаковки в теории графов.
Применение теории графов в программировании
6.ВОПРОСЫ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ ПО ДИСЦИПЛИНЕ «ДИСКРЕТНАЯ МАТЕМАТИКА»
Линейные рекуррентные соотношения с постоянными коэффициентами. Возвратные последовательности.
Вычисление сумм вида  , s = 1, 2, 3, ... .
Целочисленные функции x , x , mod.
Формула суммирования Эйлера.
Основные свойства треугольника Паскаля.
Использование многочленов для доказательства комбинаторных тождеств.
Вычисление комбинаторных чисел на ЭВМ.
Верхние и нижние оценки для чисел N (p, q, 2). Теорема Эрдеша.
Некоторые применения теоремы Рамсея.
Графы с цветными ребрами.
Число различных графов с p вершинами.
Число различных деревьев с р вершинами. Теорема Кэли. Соответствие Прюфера.
Формула Эйлера для плоских графов и ее следствия.
Раскрашиваемость вершин планарного графа шестью красками.
7. ВОПРОСЫ К ЭКЗАМЕНУ ПО ДИСЦИПЛИНЕ «ДИСКРЕТНАЯ МАТЕМАТИКА»
Понятие множества. Примеры множеств. Способы задания множеств.
Пустое множество. Равные множества. Подмножества. Примеры.
Универсальное множество. Дополнение подмножества до универсального множества.
Объединение, пересечение и вычитание множеств.
Теоретико-множественные тождества и их применение.
Кортеж. Декартово умножение множеств.
Бинарные отношения между элементами множеств. Граф и график отношения. Способы задания отношений.
Отношения, обратное и противоположное к данному отношению.
Основные свойства отношений на множестве.
Отношения эквивалентности и порядка.
Отображения. Функции. Равномощные множества. Композиция отображений.
Мощность множества. Счетные множества. Мощность континуума.
Комбинаторные правила суммы, произведения, включений и исключений.
Понятие перестановки. Число перестановок n-элементного множества.
Понятие сочетания. Числа всех сочетаний из n элементов по k элементов. Основные свойства сочетаний.
Понятие размещения. Число всех размещений из n элементов по k элементов.
Треугольник Паскаля и его свойства. Бином Ньютона, его свойства и некоторые приложения.
Метод рекуррентных соотношений (Определение и примеры).
Метод последовательного вычисления элементов решения рекуррентного соотношения.
Решение рекуррентных соотношений. Примеры.
Линейные рекуррентные соотношения с постоянными коэффициентами.
Числа Фибоначчи, их свойства и приложения.
Числа Каталана. Числа Стирлинга (1-го и 2-го рода), гармонические числа.
Суммы и рекуррентные соотношения. Преобразования сумм.
Производящие функции.
Целочисленные функции округления.
Иерархия. Асимптотическая аппроксимация.
Формула суммирования Эйлера-Маклорена.
Графы, ориентированные графы, псевдографы, мультиграфы.
Изоморфизм и гомеоморфизм графов, двудольные графы.
Маршруты, пути.
Матричное задание графов.
Операции над графами, подграфы.
Связность, компоненты связности, матрица связности, выделение компонент связности.
Поиск маршрутов в графах.
Деревья, свойства деревьев. Лес.
Остовное дерево, минимальное остовное дерево.
Эйлеровы графы и циклы.
Гамильтоновы графы и циклы.
Планарные графы.
Правильная раскраска вершин графов.
Раскраска планарных графов.
Принцип Дирихле.
Сущность теории Рамсея. Теорема Рамсея. Числа Рамсея.
Приложения теоремы Рамсея. Теорема Ван дер Вардена.
Биномиальные коэффициенты, их комбинаторный смысл.
Полиномиальные коэффициенты, их комбинаторный смысл.
Понятие выборки. Число k-выборок из n-множества.
Понятие размещения. Число k-размещений из n-множества.
Понятие перестановки. Число перестановок n-множества.
Понятие сочетания. Число сочетаний из n по k.
Комбинаторный смысл чисел Стирлинга первого рода.
Комбинаторный смысл чисел Стирлинга второго рода.
Метод включения-исключения.
Формулы обращения
Степень вершины графа. Теорема о сумме степеней вершин графа и ее следствие.
Связные графы. Компоненты связности графа.
Эйлеровы графы. Критерий эйлеровости.
Планарные графы.
Двудольные графы. Теорема Кенига.
|
