Содержание
- 2. Проблемы комбинаторного анализа Задачи на перечисления, в которых необходимо определить количество размещений элементов конечного множества, удовлетворяющих
- 3. Магический квадрат Разместить числа 1,2,3,4,5,6,7,8,9 в виде квадрата так, чтобы сумма чисел из каждого из столбцов,
- 4. Шахматные задачи Задача про ферзей: “Поставить на шахматную доску наибольшее число ферзей таким образом, чтобы ни
- 5. Основные определения Если М – конечное множество, которое содержит n элементов, то будем его называть n-множеством
- 6. Правило суммы
- 7. Правило суммы Если первая задача может быть сделана n1 способами, а вторая – n2 способами, и
- 8. Можно применять правило суммы более, чем для 2 множеств. Пусть задачи T1, T2, …,Tm могут быть
- 9. Правило суммы Пример В городе находятся 4 технических ВУЗа, 1 медицинский и 2 гуманитарных. Сколькими способами
- 10. Правило суммы Если множество М – это объединение множеств М1, М2, …, Мk, которые не пересекаются
- 11. Правило произведения
- 12. Правило произведения Пусть задача может быть разбита на 2 подзадачи. Если первая подзадача может быть сделана
- 13. Правило произведения Если М1, М2, …, Мk – конечные множества и М=М1×М2×…×Мk – их декартово произведение,
- 14. Правило произведения Пример Имеются 4 научные темы, 3 студента и 2 преподавателя. Исследовательскую группу, занимающуюся одной
- 15. Правило произведения Пример Сколько различных битовых строк длинной 7 можно составить? Каждый из 7 бит может
- 16. Принцип Дирихле
- 17. Принцип Дирихле Если k+1 или более объектов расположены в k коробках, тогда есть по крайней мере
- 18. Реализация принципа Дирихле Если n объектов расположены в k коробках, то как минимум одна коробка содержит
- 19. Принцип Дирихле Пример Сколько человек из 100 родились в одном месяце? Среди 100 человек есть по
- 20. Перестановки и размещения
- 21. Перестановки Пусть М={а1,а2,...,аn} – фиксированное множество. Упорядоченные k-подмножества (b1,b2,...,bk) множества M называются его k-перестановками. Иными словами,
- 22. Размещения Если в перестановке участвуют все элементы множества (n-перестановка), то используют термин перестановка и обозначается .
- 23. Факториал Компактное представление для умножения последовательности целых чисел. Применяем n! Для представления произведения n·(n-1)·(n-2)·...·(2)·(1) гле n
- 24. Размещения без повторений Обозначим через количество k–перестановок n-множества М и найдем это число. Пример М =
- 25. Размещения без повторений Пример Из группы в 25 человек требуется выбрать старосту, заместителя старосты и профорга.
- 26. Перестановки без повторений Если n=k, тогда - количество всех способов упорядочения этих элементов: Пример М={1,2,3} P3=
- 27. Перестановки без повторений Пример На кафедре защищаются дипломники А, В, С и D, причем А и
- 28. Круговые перестановки Сколькими способами можно рассадить 5 детей за круглым и за квадратным столом? Рассмотрим случай,
- 29. Круговые перестановки Рассмотрим случай, когда дети сидят за круглым столом : Для n элементов существует (n-1)!
- 30. Перестановки с повторениями k-перестановкой с повторениями n-множества А или k-перестановкой с повторениями из n элементов будем
- 31. Перестановки с повторениями Две k-перестановки считаются равными, если они совпадают как своими элементами, так и порядком
- 32. Размещения с неограниченными повторениями Пример Сколько строк длиной n может быть сформировано из букв английского алфавита?
- 33. n-перестановки из n-множества с заданной спецификацией Пример Сколько слов можно составить из букв слова “Миссисипи” (слова
- 34. Сочетания
- 35. Сочетания k-сочетаниями множества М (короче – сочетаниями) называются неупорядоченные k-подмножества {ai,аj,...,аs} множества M. Два k-сочетания различны
- 36. Сочетания Количество всех различных сочетаний из n элементов по k обозначают :
- 37. Сочетания Пример Пусть C = {a, b, c, d} Количество 2-сочетаний из C равно 6 подмножеств:
- 38. Сочетания Пример Комитет, который разрабатывает курс по дискретной математики, должен состоять из 3 преподавателя дискретной математики
- 39. Свойства сочетаний
- 40. Сочетания с повторениями
- 41. Сочетания с повторениями Сочетаниями с повторениями из n элементов по k называются неупорядоченные k-подмножества множества М=Ma∪Mb∪…∪Mt,
- 42. Сочетания с повторениями Пример А={a,b,с}, 6-сочетаниями с повторениями из трех элементов будут: {а,b,а,а,а,а}, {b,b,a,c,a,a}, {с,с,с,с,b,b} и
- 43. Сочетания с повторениями Имеются предметы п различных видов. Число элементов каждого вида неограниченно. Сколько существует расстановок
- 44. Сочетания с повторениями Пример У преподавателя есть карточки на четыре различных варианта. Сколькими способами можно выбрать
- 45. Свойства сочетаний с неограниченными повторениями
- 46. Сочетания и размещения «с» и «без» повторений
- 47. Бином Ньютона
- 48. Биномиальные коэффициенты Пусть n и r неотрицательные натуральные числа, причем r≤n. Тогда Эти числа обычно называют
- 49. Бином Ньютона (a+b)4=(a+b)(a+b)(a+b)(a+b) Каждое слагаемое в разложении является результатом выбора а или b в каждом сомножителе
- 50. Бином Ньютона Биномиальная теорема: Для произвольного положительного целого числа n справедливы равенства:
- 51. Бином Ньютона. Пример Получить разложение
- 52. Пример: Доказать тождество Решение: Воспользуемся формулой бинома Ньютона, в которой положим, а = 1 и b
- 53. Треугольник Паскаля Каждый из внутренних элементов треугольника равен сумме двух элементов расположенных над ними.
- 54. Треугольник Паскаля (n+1) ряд треугольника состоит из коэффициента разложения (a+b)n
- 55. Формула включений и исключений
- 56. Формула включений и исключений Пусть даны N объектов (предметов), каждый из которых может обладать или не
- 57. Формула включений и исключений Если все свойства ai попарно не совместимы (т.е. N(aiak)=0 при i ≠k),
- 58. Формула включений и исключений Тогда, очевидно, т.к. при вычитании N(а1) и N(a2) из общего числа предметов
- 59. Формула включений и исключений
- 60. Формула включений и исключений При произвольном n справедлива формула включений и исключений:
- 61. Формула включений и исключений Сколько положительных целых чисел, не превышающих 1000, делятся на 7 или на
- 62. Формула включений и исключений. Пример В общей сложности 1232 студента выбрали курс на испанском языке, 879
- 63. Рекуррентные соотношения
- 64. Рекуррентные соотношения При решении многих комбинаторных задач используется метод сведения данной задачи к аналогичной задаче, касающейся
- 65. Рекуррентные соотношения Пример рекурсивно заданной функции Непосредственное задание функции
- 66. Линейные рекуррентные соотношения Рекуррентное соотношение вида an=b1(n)an-1+b2(n)an-2+b3(n)an-3+…+bp(n)ap называется линейным рекуррентным соотношением порядка р , т.к. аn
- 67. Рекуррентные соотношения Примеры 1) 2) 3) an+2=an·an+1-3an+1+1 - нелинейное рекуррентное соотношение порядка 2, т.к. зависит от
- 68. Линейные рекуррентные соотношения Решением рекуррентного соотношения является последовательность, при подстановке которой соотношение тождественно выполняется. Решение рекуррентного
- 69. Линейные рекуррентные соотношения с постоянными коэффициентами Линейное рекуррентное соотношение вида an=b1an-1+b2an-2+b3an-3+…+bpaр, bp≠0 c постоянными коэффициентами ci
- 70. Числа Фибоначчи
- 71. Последовательность (числа) Фибоначчи Числовая последовательность, в которой каждое число равно сумме двух предыдущих, называется последовательностью Фибоначчи
- 72. Числа Фибоначчи. Пример Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца),
- 73. Числа Фибоначчи. Пример Fn – количество пар кроликов через n месяцев. Через n+1 месяцев будет Fn
- 74. Отношения вида an+2=b1an+1+b2an Решение данных отношений основано на следующих утверждениях: 1) a1(n) и a2(n) – решения
- 75. Решение отношений вида an+2=b1an+1+b2an 1) Составляем квадратное уравнение r2=b1r+b2, которое является характеристическим для данного отношения. 2)
- 77. Скачать презентацию