🗊Презентация Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18)

Категория: Математика
Нажмите для полного просмотра!
Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №1Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №2Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №3Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №4Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №5Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №6Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №7Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №8Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №9Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №10Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №11Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №12Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №13Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №14Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №15Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №16Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №17Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №18Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №19Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №20Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №21Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №22Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №23Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №24Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №25Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №26Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №27Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №28Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №29Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №30Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №31Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №32Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №33Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №34Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №35Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №36Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №37Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №38Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №39Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №40Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №41Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №42Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №43Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №44Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №45Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №46Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №47Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №48Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №49Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №50Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №51Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №52Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №53Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №54Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №55Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №56Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №57Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №58Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №59Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №60Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №61Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №62Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №63Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №64Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №65Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №66Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №67Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №68Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №69Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №70Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №71Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №72Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №73Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №74Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №75Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18), слайд №76
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Основы комбинаторного анализа. Формулы простого перечисления. (Лекции 16-18). Доклад-сообщение содержит 76 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Комбинаторика
Описание слайда:
Комбинаторика

Слайд 2


Проблемы комбинаторного анализа Задачи на перечисления, в которых необходимо определить количество размещений элементов конечного множества, удовлетворяющих определенным условиям; Задачи о существовании и построении Задачи о выборе
Описание слайда:
Проблемы комбинаторного анализа Задачи на перечисления, в которых необходимо определить количество размещений элементов конечного множества, удовлетворяющих определенным условиям; Задачи о существовании и построении Задачи о выборе

Слайд 3


Магический квадрат Разместить числа 1,2,3,4,5,6,7,8,9 в виде квадрата так, чтобы сумма чисел из каждого из столбцов, строк и диагоналей была одинакова.
Описание слайда:
Магический квадрат Разместить числа 1,2,3,4,5,6,7,8,9 в виде квадрата так, чтобы сумма чисел из каждого из столбцов, строк и диагоналей была одинакова.

Слайд 4


Шахматные задачи Задача про ферзей: “Поставить на шахматную доску наибольшее число ферзей таким образом, чтобы ни один из них не мог взять другого”. Больше, чем 8 ферзей на доску поставить не удастся. Задачу можно решить прямим перебором вариантов, и окажется, что всего есть 92 варианта такого размещения. (a, 6), (b, 3), (c, 5), (d, 8), (e, 1), (f, 4), (g, 2), (h, 7). (a, 6), (b, 1), (c, 5), (d, 2), (e, 8), (f, 3), (g, 7), (h, 4).
Описание слайда:
Шахматные задачи Задача про ферзей: “Поставить на шахматную доску наибольшее число ферзей таким образом, чтобы ни один из них не мог взять другого”. Больше, чем 8 ферзей на доску поставить не удастся. Задачу можно решить прямим перебором вариантов, и окажется, что всего есть 92 варианта такого размещения. (a, 6), (b, 3), (c, 5), (d, 8), (e, 1), (f, 4), (g, 2), (h, 7). (a, 6), (b, 1), (c, 5), (d, 2), (e, 8), (f, 3), (g, 7), (h, 4).

Слайд 5


Основные определения Если М – конечное множество, которое содержит n элементов, то будем его называть n-множеством и писать |М|=n. Подмножество АМ, которое содержит k элементов, называется k-подмножествoм. n-множество X называется линейно- упорядоченным, если каждому его элементу x взаимно однозначно соответствует номер i{1,2,..,n}. Взаимно-однозначное отображение f n-множества М нa себя называется подстановкой (n-подстановкой).
Описание слайда:
Основные определения Если М – конечное множество, которое содержит n элементов, то будем его называть n-множеством и писать |М|=n. Подмножество АМ, которое содержит k элементов, называется k-подмножествoм. n-множество X называется линейно- упорядоченным, если каждому его элементу x взаимно однозначно соответствует номер i{1,2,..,n}. Взаимно-однозначное отображение f n-множества М нa себя называется подстановкой (n-подстановкой).

Слайд 6


Правило суммы
Описание слайда:
Правило суммы

Слайд 7


Правило суммы Если первая задача может быть сделана n1 способами, а вторая – n2 способами, и если эти задачи не могут быть сделаны одновременно, то существует n1 + n2 способов сделать любую задачу.
Описание слайда:
Правило суммы Если первая задача может быть сделана n1 способами, а вторая – n2 способами, и если эти задачи не могут быть сделаны одновременно, то существует n1 + n2 способов сделать любую задачу.

Слайд 8


Можно применять правило суммы более, чем для 2 множеств. Пусть задачи T1, T2, …,Tm могут быть сделаны n1, n2, …, nm способами соответственно, и никакие 2 из этих задач не могут выполняться одновременно. Тогда количество способов выполнить любую из задач определяется как n1+n2+…+nm
Описание слайда:
Можно применять правило суммы более, чем для 2 множеств. Пусть задачи T1, T2, …,Tm могут быть сделаны n1, n2, …, nm способами соответственно, и никакие 2 из этих задач не могут выполняться одновременно. Тогда количество способов выполнить любую из задач определяется как n1+n2+…+nm

Слайд 9


Правило суммы Пример В городе находятся 4 технических ВУЗа, 1 медицинский и 2 гуманитарных. Сколькими способами можно получить высшее образование по государственному набору в данном городе? Решение: Поскольку государственный набор предполагает бесплатное обучение только в одном ВУЗе, применимо правило суммы, по которому число способов N выбора ВУЗа определяется как: N = 4+1+2 = 7.
Описание слайда:
Правило суммы Пример В городе находятся 4 технических ВУЗа, 1 медицинский и 2 гуманитарных. Сколькими способами можно получить высшее образование по государственному набору в данном городе? Решение: Поскольку государственный набор предполагает бесплатное обучение только в одном ВУЗе, применимо правило суммы, по которому число способов N выбора ВУЗа определяется как: N = 4+1+2 = 7.

Слайд 10


Правило суммы Если множество М – это объединение множеств М1, М2, …, Мk, которые не пересекаются попарно (MiMj=), тогда количество элементов множеств связаны соотношением | M | = | М1 | +…+ | Мk | Пусть объект a1 может быть выбран m1 способами, объект а2 - m2 способами и т. д., объект ak - mk способами. Тогда выбор объекта a1 или а2 и т.д., или ak может быть сделан m1 +m2+...+mk способами. Пример Раньше из Харькова в Москву в течение суток отправлялось 10 поездов, 3 автобуса и 2 самолета. Всего способов выехать из Харькова в Москву:
Описание слайда:
Правило суммы Если множество М – это объединение множеств М1, М2, …, Мk, которые не пересекаются попарно (MiMj=), тогда количество элементов множеств связаны соотношением | M | = | М1 | +…+ | Мk | Пусть объект a1 может быть выбран m1 способами, объект а2 - m2 способами и т. д., объект ak - mk способами. Тогда выбор объекта a1 или а2 и т.д., или ak может быть сделан m1 +m2+...+mk способами. Пример Раньше из Харькова в Москву в течение суток отправлялось 10 поездов, 3 автобуса и 2 самолета. Всего способов выехать из Харькова в Москву:

Слайд 11


Правило произведения
Описание слайда:
Правило произведения

Слайд 12


Правило произведения Пусть задача может быть разбита на 2 подзадачи. Если первая подзадача может быть сделана n1 способами, а вторая – n2 способами, то существует n1 ∙ n2 способов сделать эту задачу.
Описание слайда:
Правило произведения Пусть задача может быть разбита на 2 подзадачи. Если первая подзадача может быть сделана n1 способами, а вторая – n2 способами, то существует n1 ∙ n2 способов сделать эту задачу.

Слайд 13


Правило произведения Если М1, М2, …, Мk – конечные множества и М=М1М2…Мk – их декартово произведение, то | M | = | М1 |  …  | Мk | Пусть объект a1 выбирается m1 способами, а2 – m2 способами, и т.д., объект ak – mk способами, и пусть выбор объекта a1 не влияет на число способов выбора объектов a2,а3,...ak, выбор объекта а2 не влияет на число способов выбора объектов a3,а4 ...аk, т.д. Тогда выбор упорядоченного множества объектов (a1,a2,...,ak) в указанном порядке можно осуществить m1 · m2 · m3 ·... · mk способами. Пример Имеется 17 юношей и 21 девушка. Они могут составить
Описание слайда:
Правило произведения Если М1, М2, …, Мk – конечные множества и М=М1М2…Мk – их декартово произведение, то | M | = | М1 |  …  | Мk | Пусть объект a1 выбирается m1 способами, а2 – m2 способами, и т.д., объект ak – mk способами, и пусть выбор объекта a1 не влияет на число способов выбора объектов a2,а3,...ak, выбор объекта а2 не влияет на число способов выбора объектов a3,а4 ...аk, т.д. Тогда выбор упорядоченного множества объектов (a1,a2,...,ak) в указанном порядке можно осуществить m1 · m2 · m3 ·... · mk способами. Пример Имеется 17 юношей и 21 девушка. Они могут составить

Слайд 14


Правило произведения Пример Имеются 4 научные темы, 3 студента и 2 преподавателя. Исследовательскую группу, занимающуюся одной темой, составляет один студент и один преподаватель. Сколько существует комбинаций выбора различных тем и различных исследовательских групп? Решение: Так как одна исследовательская группа может вести только одну тему, применимо правило произведения, по которому число комбинаций равно 4·3·2=24.
Описание слайда:
Правило произведения Пример Имеются 4 научные темы, 3 студента и 2 преподавателя. Исследовательскую группу, занимающуюся одной темой, составляет один студент и один преподаватель. Сколько существует комбинаций выбора различных тем и различных исследовательских групп? Решение: Так как одна исследовательская группа может вести только одну тему, применимо правило произведения, по которому число комбинаций равно 4·3·2=24.

Слайд 15


Правило произведения Пример Сколько различных битовых строк длинной 7 можно составить? Каждый из 7 бит может быть выбран двумя способами (0 или 1). Получаем: 27=128 различных битовых строк длинной 7.
Описание слайда:
Правило произведения Пример Сколько различных битовых строк длинной 7 можно составить? Каждый из 7 бит может быть выбран двумя способами (0 или 1). Получаем: 27=128 различных битовых строк длинной 7.

Слайд 16


Принцип Дирихле
Описание слайда:
Принцип Дирихле

Слайд 17


Принцип Дирихле Если k+1 или более объектов расположены в k коробках, тогда есть по крайней мере одна коробка, содержащая два или более из объектов.
Описание слайда:
Принцип Дирихле Если k+1 или более объектов расположены в k коробках, тогда есть по крайней мере одна коробка, содержащая два или более из объектов.

Слайд 18


Реализация принципа Дирихле Если n объектов расположены в k коробках, то как минимум одна коробка содержит как минимум n/k объектов. Доказательство: Предположим, что ни одна коробка не содержит более чем [n/k]–1 объектов. Общее количество элементов в коробках k([n/k]-1)<k(((n/k)+1)-1)=n Причем, [n/k]<(n/k)+1.
Описание слайда:
Реализация принципа Дирихле Если n объектов расположены в k коробках, то как минимум одна коробка содержит как минимум n/k объектов. Доказательство: Предположим, что ни одна коробка не содержит более чем [n/k]–1 объектов. Общее количество элементов в коробках k([n/k]-1)<k(((n/k)+1)-1)=n Причем, [n/k]<(n/k)+1.

Слайд 19


Принцип Дирихле Пример Сколько человек из 100 родились в одном месяце? Среди 100 человек есть по крайней мере [100/12] =9, которые родились в одном и том же месяце
Описание слайда:
Принцип Дирихле Пример Сколько человек из 100 родились в одном месяце? Среди 100 человек есть по крайней мере [100/12] =9, которые родились в одном и том же месяце

Слайд 20


Перестановки и размещения
Описание слайда:
Перестановки и размещения

Слайд 21


Перестановки Пусть М={а1,а2,...,аn} – фиксированное множество. Упорядоченные k-подмножества (b1,b2,...,bk) множества M называются его k-перестановками. Иными словами, k-перестановка – это размещение в определенном порядке k элементов из множества М.
Описание слайда:
Перестановки Пусть М={а1,а2,...,аn} – фиксированное множество. Упорядоченные k-подмножества (b1,b2,...,bk) множества M называются его k-перестановками. Иными словами, k-перестановка – это размещение в определенном порядке k элементов из множества М.

Слайд 22


Размещения Если в перестановке участвуют все элементы множества (n-перестановка), то используют термин перестановка и обозначается . Два размещения из n по k различны, если они состоят из различных элементов или из одинаковых, но расположенных в разном порядке. k-перестановки множества из n элементов называются размещениями из n по k элементов и обозначается .
Описание слайда:
Размещения Если в перестановке участвуют все элементы множества (n-перестановка), то используют термин перестановка и обозначается . Два размещения из n по k различны, если они состоят из различных элементов или из одинаковых, но расположенных в разном порядке. k-перестановки множества из n элементов называются размещениями из n по k элементов и обозначается .

Слайд 23


Факториал Компактное представление для умножения последовательности целых чисел. Применяем n! Для представления произведения n·(n-1)·(n-2)·...·(2)·(1) гле n – некоторое целое число. 0!=1
Описание слайда:
Факториал Компактное представление для умножения последовательности целых чисел. Применяем n! Для представления произведения n·(n-1)·(n-2)·...·(2)·(1) гле n – некоторое целое число. 0!=1

Слайд 24


Размещения без повторений Обозначим через количество k–перестановок n-множества М и найдем это число. Пример М = {1,2,3}. 2-перестановки (1,2);(2,1);(1,3);(3,1);(2,3); (3,2); 3-перестановки (1,2,3);(1,3,2);(2,1,3); (2,3,l); (3,1,2);(3,2,1).
Описание слайда:
Размещения без повторений Обозначим через количество k–перестановок n-множества М и найдем это число. Пример М = {1,2,3}. 2-перестановки (1,2);(2,1);(1,3);(3,1);(2,3); (3,2); 3-перестановки (1,2,3);(1,3,2);(2,1,3); (2,3,l); (3,1,2);(3,2,1).

Слайд 25


Размещения без повторений Пример Из группы в 25 человек требуется выбрать старосту, заместителя старосты и профорга. Сколько вариантов выбора руководящего состава группы?      Решение: Старосту можно выбрать одним из 25 способов. Поскольку выбранный староста не может быть своим заместителем, то для выбора заместителя старосты остается 24 варианта. Профорга выбирают одним из 23 способов. Всего вариантов:
Описание слайда:
Размещения без повторений Пример Из группы в 25 человек требуется выбрать старосту, заместителя старосты и профорга. Сколько вариантов выбора руководящего состава группы?      Решение: Старосту можно выбрать одним из 25 способов. Поскольку выбранный староста не может быть своим заместителем, то для выбора заместителя старосты остается 24 варианта. Профорга выбирают одним из 23 способов. Всего вариантов:

Слайд 26


Перестановки без повторений Если n=k, тогда - количество всех способов упорядочения этих элементов: Пример М={1,2,3} P3=
Описание слайда:
Перестановки без повторений Если n=k, тогда - количество всех способов упорядочения этих элементов: Пример М={1,2,3} P3=

Слайд 27


Перестановки без повторений Пример На кафедре защищаются дипломники А, В, С и D, причем А и В имеют комплексную тему и В не может защитить диплом после А. Сколькими способами можно определить очередность защит? Решение: Так как В и А защищают одну тему, необходимо рассматривать перестановки из трех элементов      Р3=3!=1∙2∙3=6
Описание слайда:
Перестановки без повторений Пример На кафедре защищаются дипломники А, В, С и D, причем А и В имеют комплексную тему и В не может защитить диплом после А. Сколькими способами можно определить очередность защит? Решение: Так как В и А защищают одну тему, необходимо рассматривать перестановки из трех элементов      Р3=3!=1∙2∙3=6

Слайд 28


Круговые перестановки Сколькими способами можно рассадить 5 детей за круглым и за квадратным столом? Рассмотрим случай, когда дети сидят за квадратным столом: После применения формулы для нахождения количества перестановок получаем: P(5,5) = 5!
Описание слайда:
Круговые перестановки Сколькими способами можно рассадить 5 детей за круглым и за квадратным столом? Рассмотрим случай, когда дети сидят за квадратным столом: После применения формулы для нахождения количества перестановок получаем: P(5,5) = 5!

Слайд 29


Круговые перестановки Рассмотрим случай, когда дети сидят за круглым столом : Для n элементов существует (n-1)! круговых перестановок.
Описание слайда:
Круговые перестановки Рассмотрим случай, когда дети сидят за круглым столом : Для n элементов существует (n-1)! круговых перестановок.

Слайд 30


Перестановки с повторениями k-перестановкой с повторениями n-множества А или k-перестановкой с повторениями из n элементов будем называть упорядоченный набор k элементов (bl,...bk) из множества М. Пример A={а,b,с}, |A|=3, Ma={a,a,...}, Mb={b,b,..}, Mc ={с,с,...}. 6-перестановками с повторениями из трех элементов будут: (а,b,с,a,a,a), (b,b,c,c,a,b), (c,b,b,c,a,a) и т.д.
Описание слайда:
Перестановки с повторениями k-перестановкой с повторениями n-множества А или k-перестановкой с повторениями из n элементов будем называть упорядоченный набор k элементов (bl,...bk) из множества М. Пример A={а,b,с}, |A|=3, Ma={a,a,...}, Mb={b,b,..}, Mc ={с,с,...}. 6-перестановками с повторениями из трех элементов будут: (а,b,с,a,a,a), (b,b,c,c,a,b), (c,b,b,c,a,a) и т.д.

Слайд 31


Перестановки с повторениями Две k-перестановки считаются равными, если они совпадают как своими элементами, так и порядком их расположения; и различными, если они отличаются либо элементами, либо порядком их расположения. Пример М – множество букв разрезной азбуки (все буквы в азбуке строчные). Различными 4-перестановками будут: (м,а,м,а),(р,а,м,а), (н,а,а,а), (а,н,а,а), (а,а,а,н) и т. д.
Описание слайда:
Перестановки с повторениями Две k-перестановки считаются равными, если они совпадают как своими элементами, так и порядком их расположения; и различными, если они отличаются либо элементами, либо порядком их расположения. Пример М – множество букв разрезной азбуки (все буквы в азбуке строчные). Различными 4-перестановками будут: (м,а,м,а),(р,а,м,а), (н,а,а,а), (а,н,а,а), (а,а,а,н) и т. д.

Слайд 32


Размещения с неограниченными повторениями Пример Сколько строк длиной n может быть сформировано из букв английского алфавита? По правилу произведения: 26n строк длинной n.
Описание слайда:
Размещения с неограниченными повторениями Пример Сколько строк длиной n может быть сформировано из букв английского алфавита? По правилу произведения: 26n строк длинной n.

Слайд 33


n-перестановки из n-множества с заданной спецификацией
Описание слайда:
n-перестановки из n-множества с заданной спецификацией

Слайд 34


Сочетания
Описание слайда:
Сочетания

Слайд 35


Сочетания k-сочетаниями множества М (короче – сочетаниями) называются неупорядоченные k-подмножества {ai,аj,...,аs} множества M.   Два k-сочетания различны тогда и только тогда, когда они отличаются хотя бы одним элементом. Пример Различными 2-сочетаниями множества М = {l,2,3 }: {1,2},{1,3},{2,3}.
Описание слайда:
Сочетания k-сочетаниями множества М (короче – сочетаниями) называются неупорядоченные k-подмножества {ai,аj,...,аs} множества M.   Два k-сочетания различны тогда и только тогда, когда они отличаются хотя бы одним элементом. Пример Различными 2-сочетаниями множества М = {l,2,3 }: {1,2},{1,3},{2,3}.

Слайд 36


Сочетания Количество всех различных сочетаний из n элементов по k обозначают :
Описание слайда:
Сочетания Количество всех различных сочетаний из n элементов по k обозначают :

Слайд 37


Сочетания Пример Пусть C = {a, b, c, d} Количество 2-сочетаний из C равно 6 подмножеств: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.
Описание слайда:
Сочетания Пример Пусть C = {a, b, c, d} Количество 2-сочетаний из C равно 6 подмножеств: {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}.

Слайд 38


Сочетания Пример Комитет, который разрабатывает курс по дискретной математики, должен состоять из 3 преподавателя дискретной математики математики и 4 программиста. Есть 9 преподавателей дискретной математики и 11 программистов. Сколько существует способов сделать это? После применения правила произведения получаем:
Описание слайда:
Сочетания Пример Комитет, который разрабатывает курс по дискретной математики, должен состоять из 3 преподавателя дискретной математики математики и 4 программиста. Есть 9 преподавателей дискретной математики и 11 программистов. Сколько существует способов сделать это? После применения правила произведения получаем:

Слайд 39


Свойства сочетаний
Описание слайда:
Свойства сочетаний

Слайд 40


Сочетания с повторениями
Описание слайда:
Сочетания с повторениями

Слайд 41


Сочетания с повторениями Сочетаниями с повторениями из n элементов по k называются неупорядоченные k-подмножества множества М=MaMb…Mt, где MiMj=, is, i,j{a,b,…,t}, Ma={a,a,...}, Mb={b,b,..},…,Mt={t,t,...} |{a,b,c,…,t}|=n.
Описание слайда:
Сочетания с повторениями Сочетаниями с повторениями из n элементов по k называются неупорядоченные k-подмножества множества М=MaMb…Mt, где MiMj=, is, i,j{a,b,…,t}, Ma={a,a,...}, Mb={b,b,..},…,Mt={t,t,...} |{a,b,c,…,t}|=n.

Слайд 42


Сочетания с повторениями Пример А={a,b,с}, 6-сочетаниями с повторениями из трех элементов будут: {а,b,а,а,а,а}, {b,b,a,c,a,a}, {с,с,с,с,b,b} и т.д.
Описание слайда:
Сочетания с повторениями Пример А={a,b,с}, 6-сочетаниями с повторениями из трех элементов будут: {а,b,а,а,а,а}, {b,b,a,c,a,a}, {с,с,с,с,b,b} и т.д.

Слайд 43


Сочетания с повторениями Имеются предметы п различных видов. Число элементов каждого вида неограниченно. Сколько существует расстановок длины k, если не принимать во внимание порядок элементов? Такие расстановки называют сочетаниями с повторениями, количество и обозначение которых следующее:
Описание слайда:
Сочетания с повторениями Имеются предметы п различных видов. Число элементов каждого вида неограниченно. Сколько существует расстановок длины k, если не принимать во внимание порядок элементов? Такие расстановки называют сочетаниями с повторениями, количество и обозначение которых следующее:

Слайд 44


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

Слайд 45


Свойства сочетаний с неограниченными повторениями
Описание слайда:
Свойства сочетаний с неограниченными повторениями

Слайд 46


Сочетания и размещения «с» и «без» повторений
Описание слайда:
Сочетания и размещения «с» и «без» повторений

Слайд 47


Бином Ньютона
Описание слайда:
Бином Ньютона

Слайд 48


Биномиальные коэффициенты Пусть n и r неотрицательные натуральные числа, причем rn. Тогда Эти числа обычно называют биномиальными коэффициентами.
Описание слайда:
Биномиальные коэффициенты Пусть n и r неотрицательные натуральные числа, причем rn. Тогда Эти числа обычно называют биномиальными коэффициентами.

Слайд 49


Бином Ньютона (a+b)4=(a+b)(a+b)(a+b)(a+b) Каждое слагаемое в разложении является результатом выбора а или b в каждом сомножителе (a+b) и последовательного их перемножения Пример Найти коэффициент при a3b
Описание слайда:
Бином Ньютона (a+b)4=(a+b)(a+b)(a+b)(a+b) Каждое слагаемое в разложении является результатом выбора а или b в каждом сомножителе (a+b) и последовательного их перемножения Пример Найти коэффициент при a3b

Слайд 50


Бином Ньютона Биномиальная теорема: Для произвольного положительного целого числа n справедливы равенства:
Описание слайда:
Бином Ньютона Биномиальная теорема: Для произвольного положительного целого числа n справедливы равенства:

Слайд 51


Бином Ньютона. Пример Получить разложение
Описание слайда:
Бином Ньютона. Пример Получить разложение

Слайд 52


Пример: Доказать тождество       Решение: Воспользуемся формулой бинома Ньютона, в которой положим, а = 1 и b = 1, тогда
Описание слайда:
Пример: Доказать тождество       Решение: Воспользуемся формулой бинома Ньютона, в которой положим, а = 1 и b = 1, тогда

Слайд 53


Треугольник Паскаля Каждый из внутренних элементов треугольника равен сумме двух элементов расположенных над ними.
Описание слайда:
Треугольник Паскаля Каждый из внутренних элементов треугольника равен сумме двух элементов расположенных над ними.

Слайд 54


Треугольник Паскаля (n+1) ряд треугольника состоит из коэффициента разложения (a+b)n
Описание слайда:
Треугольник Паскаля (n+1) ряд треугольника состоит из коэффициента разложения (a+b)n

Слайд 55


Формула включений и исключений
Описание слайда:
Формула включений и исключений

Слайд 56


Формула включений и исключений Пусть даны N объектов (предметов), каждый из которых может обладать или не обладать одним или несколькими из свойств a1,a2,...,an . Через обозначим отсутствие свойства ai; через N(a) – количество предметов, обладающих свойством а (а – любое из свойств аi или ); через N(a,b,c,…,k) – количество предметов, обладающих попарно различными свойствами а,b,c,..,,k
Описание слайда:
Формула включений и исключений Пусть даны N объектов (предметов), каждый из которых может обладать или не обладать одним или несколькими из свойств a1,a2,...,an . Через обозначим отсутствие свойства ai; через N(a) – количество предметов, обладающих свойством а (а – любое из свойств аi или ); через N(a,b,c,…,k) – количество предметов, обладающих попарно различными свойствами а,b,c,..,,k

Слайд 57


Формула включений и исключений Если все свойства ai попарно не совместимы (т.е. N(aiak)=0 при i k), то формула имеет вид:
Описание слайда:
Формула включений и исключений Если все свойства ai попарно не совместимы (т.е. N(aiak)=0 при i k), то формула имеет вид:

Слайд 58


Формула включений и исключений Тогда, очевидно, т.к. при вычитании N(а1) и N(a2) из общего числа предметов число N(ala2) вычитается дважды.
Описание слайда:
Формула включений и исключений Тогда, очевидно, т.к. при вычитании N(а1) и N(a2) из общего числа предметов число N(ala2) вычитается дважды.

Слайд 59


Формула включений и исключений
Описание слайда:
Формула включений и исключений

Слайд 60


Формула включений и исключений При произвольном n справедлива формула включений и исключений:
Описание слайда:
Формула включений и исключений При произвольном n справедлива формула включений и исключений:

Слайд 61


Формула включений и исключений Сколько положительных целых чисел, не превышающих 1000, делятся на 7 или на 11?
Описание слайда:
Формула включений и исключений Сколько положительных целых чисел, не превышающих 1000, делятся на 7 или на 11?

Слайд 62


Формула включений и исключений. Пример В общей сложности 1232 студента выбрали курс на испанском языке, 879 – на французском языке, и 114 – на русском языке. Далее, 103 выбрали курсы и на испанском и на французском языке, 23 –на испанском и русском языке и 14 – на французском и русском языке. Если 2092 студента выбрали по крайней мере один из испанского, французского и русского языков, то сколько студентов выбрали курс на всех трех языках? Решение 7 студентов выбрали курс на всех трех языках.
Описание слайда:
Формула включений и исключений. Пример В общей сложности 1232 студента выбрали курс на испанском языке, 879 – на французском языке, и 114 – на русском языке. Далее, 103 выбрали курсы и на испанском и на французском языке, 23 –на испанском и русском языке и 14 – на французском и русском языке. Если 2092 студента выбрали по крайней мере один из испанского, французского и русского языков, то сколько студентов выбрали курс на всех трех языках? Решение 7 студентов выбрали курс на всех трех языках.

Слайд 63


Рекуррентные соотношения
Описание слайда:
Рекуррентные соотношения

Слайд 64


Рекуррентные соотношения При решении многих комбинаторных задач используется метод сведения данной задачи к аналогичной задаче, касающейся меньшего числа предметов. Такой метод называется методом рекуррентных соотношений. Пользуясь рекуррентным соотношением можно свести задачу об n предметах к задаче об (n–1) предметах, потом об (n–2) предметах и т.д. Последовательно уменьшая число предметов, доходим до задачи, которую уже легко решить. Во многих случаях удается получить из рекуррентного отношения явную формулу для решения комбинаторной задачи.
Описание слайда:
Рекуррентные соотношения При решении многих комбинаторных задач используется метод сведения данной задачи к аналогичной задаче, касающейся меньшего числа предметов. Такой метод называется методом рекуррентных соотношений. Пользуясь рекуррентным соотношением можно свести задачу об n предметах к задаче об (n–1) предметах, потом об (n–2) предметах и т.д. Последовательно уменьшая число предметов, доходим до задачи, которую уже легко решить. Во многих случаях удается получить из рекуррентного отношения явную формулу для решения комбинаторной задачи.

Слайд 65


Рекуррентные соотношения Пример рекурсивно заданной функции Непосредственное задание функции
Описание слайда:
Рекуррентные соотношения Пример рекурсивно заданной функции Непосредственное задание функции

Слайд 66


Линейные рекуррентные соотношения Рекуррентное соотношение вида an=b1(n)an-1+b2(n)an-2+b3(n)an-3+…+bp(n)ap называется линейным рекуррентным соотношением порядка р , т.к. аn выражается через р элементов вида Соотношение линейно-рекуррентное, т.к. показатель каждой степени аі равен 1.
Описание слайда:
Линейные рекуррентные соотношения Рекуррентное соотношение вида an=b1(n)an-1+b2(n)an-2+b3(n)an-3+…+bp(n)ap называется линейным рекуррентным соотношением порядка р , т.к. аn выражается через р элементов вида Соотношение линейно-рекуррентное, т.к. показатель каждой степени аі равен 1.

Слайд 67


Рекуррентные соотношения Примеры 1) 2) 3) an+2=an·an+1-3an+1+1 - нелинейное рекуррентное соотношение порядка 2, т.к. зависит от an и an+1 4) an+3=6an·an+2+an+1 - нелинейное рекуррентное соотношение порядка 3, т.к. зависит от an, an+1 и an+2 5) an+2=3an+1-2an - линейное рекуррентное соотношение порядка 2, т.к. зависит от an и an+1
Описание слайда:
Рекуррентные соотношения Примеры 1) 2) 3) an+2=an·an+1-3an+1+1 - нелинейное рекуррентное соотношение порядка 2, т.к. зависит от an и an+1 4) an+3=6an·an+2+an+1 - нелинейное рекуррентное соотношение порядка 3, т.к. зависит от an, an+1 и an+2 5) an+2=3an+1-2an - линейное рекуррентное соотношение порядка 2, т.к. зависит от an и an+1

Слайд 68


Линейные рекуррентные соотношения Решением рекуррентного соотношения является последовательность, при подстановке которой соотношение тождественно выполняется. Решение рекуррентного соотношения р-го порядка называется общим, если оно зависит от р произвольных постоянных С1,С2,…,Ср и путем подбора этих постоянных можно получить любое решение данного соотношения. Пример an+2=3an+1-an an=2n; an+1=2n+1 ; an+2=2n+2 2n+2=3·2n+1-2·2n=3·2n·21-2·2n 2n- решение данного рекуррентного соотношения
Описание слайда:
Линейные рекуррентные соотношения Решением рекуррентного соотношения является последовательность, при подстановке которой соотношение тождественно выполняется. Решение рекуррентного соотношения р-го порядка называется общим, если оно зависит от р произвольных постоянных С1,С2,…,Ср и путем подбора этих постоянных можно получить любое решение данного соотношения. Пример an+2=3an+1-an an=2n; an+1=2n+1 ; an+2=2n+2 2n+2=3·2n+1-2·2n=3·2n·21-2·2n 2n- решение данного рекуррентного соотношения

Слайд 69


Линейные рекуррентные соотношения с постоянными коэффициентами Линейное рекуррентное соотношение вида an=b1an-1+b2an-2+b3an-3+…+bpaр, bp0 c постоянными коэффициентами ci при 1іp называется линейным однородным рекуррентным соотношением с постоянными коэффициентами р.
Описание слайда:
Линейные рекуррентные соотношения с постоянными коэффициентами Линейное рекуррентное соотношение вида an=b1an-1+b2an-2+b3an-3+…+bpaр, bp0 c постоянными коэффициентами ci при 1іp называется линейным однородным рекуррентным соотношением с постоянными коэффициентами р.

Слайд 70


Числа Фибоначчи
Описание слайда:
Числа Фибоначчи

Слайд 71


Последовательность (числа) Фибоначчи Числовая последовательность, в которой каждое число равно сумме двух предыдущих, называется последовательностью Фибоначчи (числами Фибоначчи). F(n+1) = F(n) + F(n–1). Выражение чисел Фибоначчи через имеет вид: F(n) = где , если n нечетно (р - целая часть числа ______) , если n четно
Описание слайда:
Последовательность (числа) Фибоначчи Числовая последовательность, в которой каждое число равно сумме двух предыдущих, называется последовательностью Фибоначчи (числами Фибоначчи). F(n+1) = F(n) + F(n–1). Выражение чисел Фибоначчи через имеет вид: F(n) = где , если n нечетно (р - целая часть числа ______) , если n четно

Слайд 72


Числа Фибоначчи. Пример Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через 2 месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов? Решение: Через месяц будет 2 пары кроликов. Через 2 месяца приплод даст только первая пара кроликов и получится 3 пары. Через 3 месяца приплод дадут и исходная пара, и пара, появившаяся 2 месяца тому назад. Всего будет 5 пар кроликов.
Описание слайда:
Числа Фибоначчи. Пример Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через 2 месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов? Решение: Через месяц будет 2 пары кроликов. Через 2 месяца приплод даст только первая пара кроликов и получится 3 пары. Через 3 месяца приплод дадут и исходная пара, и пара, появившаяся 2 месяца тому назад. Всего будет 5 пар кроликов.

Слайд 73


Числа Фибоначчи. Пример Fn – количество пар кроликов через n месяцев. Через n+1 месяцев будет Fn пар и еще столько новорожденных пар кроликов, сколько было в конце месяца n-1, т.е. Fn-1.  Fn+1= Fn +Fn-1 По условию: F0=1, F1=2  F2=1+2=3 F3=2+3=5 F4=3+5=8 и т.д. где Fn – числа Фибоначчи
Описание слайда:
Числа Фибоначчи. Пример Fn – количество пар кроликов через n месяцев. Через n+1 месяцев будет Fn пар и еще столько новорожденных пар кроликов, сколько было в конце месяца n-1, т.е. Fn-1.  Fn+1= Fn +Fn-1 По условию: F0=1, F1=2  F2=1+2=3 F3=2+3=5 F4=3+5=8 и т.д. где Fn – числа Фибоначчи

Слайд 74


Отношения вида an+2=b1an+1+b2an Решение данных отношений основано на следующих утверждениях: 1) a1(n) и a2(n) – решения данного рекуррентного отношения, тогда для любых чисел А и В последовательность an=А·a1(n)+В·a2(n) также решение этого отношения. 2) Если число r1 – корень квадратного уравнения r2=b1r+b2 , то последовательность 1, r, r2, ... , rn-1, ... есть решение рекуррентного отношения an+2=b1an+1+b2an
Описание слайда:
Отношения вида an+2=b1an+1+b2an Решение данных отношений основано на следующих утверждениях: 1) a1(n) и a2(n) – решения данного рекуррентного отношения, тогда для любых чисел А и В последовательность an=А·a1(n)+В·a2(n) также решение этого отношения. 2) Если число r1 – корень квадратного уравнения r2=b1r+b2 , то последовательность 1, r, r2, ... , rn-1, ... есть решение рекуррентного отношения an+2=b1an+1+b2an

Слайд 75


Решение отношений вида an+2=b1an+1+b2an 1) Составляем квадратное уравнение r2=b1r+b2, которое является характеристическим для данного отношения. 2) Если квадратное уравнение имеет 2 различных корня r1 и r2, то общее решение отношения an+2=b1an+1+b2an имеет вид:
Описание слайда:
Решение отношений вида an+2=b1an+1+b2an 1) Составляем квадратное уравнение r2=b1r+b2, которое является характеристическим для данного отношения. 2) Если квадратное уравнение имеет 2 различных корня r1 и r2, то общее решение отношения an+2=b1an+1+b2an имеет вид:

Слайд 76


Общее решение для рекуррентного отношения для чисел Фибоначчи Fn= Fn-1 +Fn-2 Характеристическое уравнение: r2=r+1 Корни уравнения: числа и Общее решение:
Описание слайда:
Общее решение для рекуррентного отношения для чисел Фибоначчи Fn= Fn-1 +Fn-2 Характеристическое уравнение: r2=r+1 Корни уравнения: числа и Общее решение:

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию