Введение в комбинаторику - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 1

Описание слайда:

Лекция 3 Введение в комбинаторику Цель лекции: принцип комбинаторики, число элементов суммы множеств, принцип математической индукции. Подмножества данного множества.

Слайд 2

Описание слайда:

Комбинаторика Расчет способов осуществления некоторых действий - является сущностью комбинаторных задач. Задача 1: Сколько вариантов попасть из А в С?

Слайд 3

Описание слайда:

Введение ЗАДАЧА 2: В соревновании участвуют 16 команд. Сколько способов распределения золотой, серебряной медали и бронзовой медали?

Слайд 4

Описание слайда:

Основное правило комбинаторики Правило умножения. Если необходимо выполнить по порядку k действий. Первое можно выполнить n1 способами, второе n2 – способами и т.д. То все k действий:

Слайд 5

Описание слайда:

Задача Задача 3. Сколько четырех значных чисел можно составить из цифр {1,2,3,4,5}, если А) ни одна цифр не повторяется более одного раза В) цифры могут повторятся С) числа должны быть нечетными

Слайд 6

Описание слайда:

Задача Задача 4. На гору ведет 7 дорог. Сколько вариантов подняться и спуститься с горы? А разными путями? Задача 5. Сколько трехзначных чисел можно составить из цифр 1,2,3,4,5, если каждую можно использовать не более одного раза

Слайд 7

Описание слайда:

Вычисление числа элементов суммы множеств Если задано множество А и множество В, то число элементов суммы (объединения) множеств равно:

Слайд 8

Описание слайда:

Задача 5 Задача 5. Каждый студент группы либо девушка, либо имеет светлые волосы, либо обожает дискретную математику (ДМ). В группе 20 девушек, из них 12 блондинок и одна блондинка обожает ДМ. Всего в группе 24 светловолосых студента, из них ДМ обожают 12, а всего 17 студенток и студентов обожают ДМ из них 6 студенток. Сколько студентов в группе?

Слайд 9

Описание слайда:

Решение задачи 5 Пусть А множество студенток – 20. В – множество светловолосых (М и Д) – 24. С – множество студентов обожающих ДМ – 17.

Слайд 10

Описание слайда:

Ответ задачи 5 Подставляем числа в формулу вычисления суммы числа трех множеств:

Слайд 11

Описание слайда:

Теорема о числе элементов объединения множеств Если А1,…,Аn – некоторые множества, то число элементов объединений этих множеств равно:

Слайд 12

Описание слайда:

Продолжение теоремы Правая часть этого равенства является суммой n слагаемых, где к - тое по порядку слагаемое имеет вид :

Слайд 13

Описание слайда:

Упорядоченное множество Определение: множество из которого задан порядок его элементов называется упорядоченным. Каждому элементу множества указан его порядок (место) в множестве. Если задано множество А={a1, a2, a3}, то A={a2, a1, a3} – упорядоченное множество.

Слайд 14

Описание слайда:

Число возможных слов длины k из алфавита мощностью n Пусть задано два множества А – алфавит, и D – упорядоченное множество натуральных чисел. Если задать отображение F на множестве D со значениями в А, то получим, что каждому натуральному числу будет соответствовать некоторая последовательность элементов из множества А – эта структура - слово. ТЕОРЕМА. Число возможных слов длины k из алфавита мощностью n равно:

Слайд 15

Описание слайда:

Принцип математической индукции Пусть имеется конечное упорядоченное множество n натуральных чисел А = {1,2,3,…,n}. Предположим, что для некоторых элементов этого множества выполняется некоторое утверждение, например:

Слайд 16

Описание слайда:

Принцип математической индукции 1) Если некоторое утверждение справедливо для k=1. 2) из справедливости утверждения для произвольного натурального k, следует его справедливость для k+1, то это утверждение справедливо для всякого натурального n.

Слайд 17

Описание слайда:

Пример доказательства При n = 1 неравенство выполняется. Предположим, что выполняется неравенство Докажем, что справедливо неравенство

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

Множество всех его подмножеств Если задано множество А, то можно рассматривать новое множество М(А) – множество всех подмножеств А, которые имеют k элементов.

Слайд 20

Описание слайда:

Пример множества всех подмножеств Пусть А={a,b,c}, тогда М(А)={{a},{b},{c},{a,b},{a,с},{b,с},{a,b,c}, } {{a,b},{a,с},{b,с}}

Слайд 21

Описание слайда:

Число сочетаний из n по k ТЕОРЕМА: Число всех k - элементарных подмножеств множества А из n элементов равно:

Слайд 22

Описание слайда:

Примеры задач Задача 6. Сколько способов выбора трех книг из пяти. Задача 7. В комиссию надо 3 человека. В группе 7 человек. Определите количество вариантов состава комиссии. Задача 8. В турнире участвовали 20 шахматистов. Каждые встретились один раз. Сколько сыграно партий?

Слайд 23

Описание слайда:

Пример графической задачи Задача 9. Задана прямоугольная сетка квадратов размерами m на n. Определите число различных вариантов путей из точки (0,0) в точку (m,n) по вертикальным и горизонтальным отрезкам.

Слайд 24

Описание слайда:

Теорема о сумме числа сочетаний Число сочетаний из n по k равно сумме числа сочетаний из (n-1) по k и числа сочетаний из (n-1) по (k-1).

Слайд 25

Описание слайда:

Теорема о сумме числа сочетаний ДОКАЗАТЕЛЬСТВО: Число кратчайших путей из точки (0,0) в точку А(k, n-k) равно:

Слайд 26

Описание слайда:

Задача Докажите тождество

Слайд 27

Описание слайда:

Количество подмножеств данного множества ВОПРОС. Сколько всего подмножеств имеет множество А, состоящее из n элементов, с учетом того, что пустое множество также включено в А. Число всех подмножеств из элементов n равно:

Слайд 28

Описание слайда:

Следствие теоремы Имеет место равенство:

Слайд 29

Описание слайда:

Упорядоченные множества. Перестановки и размещения Множество называется упорядоченным. Если каждому элементу множества противопоставлено некоторое число от 1 до n. Каждый элемент множества имеет свой номер. Упорядоченные множества, отличающиеся только номерами своих элементов, называются перестановками. ПРИМЕР. Составить все перестановки множества А={a,b,с}?

Слайд 30

Описание слайда:

Варианты перестановок множества Пусть задано множество А из n – элементов, а Pn – число перестановок. ТЕОРЕМА:

Слайд 31

Описание слайда:

Примеры Задача 11. Сколькими способами можно поставить 4 книги на полке. Задача 12. Сколькими способами можно упорядочить множество {1,2,3…2n} так, чтобы каждому четному элементу множества соответствовал четный номер.