Комбинато́рика Комбинато́рика (Комбинаторный анализ) раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и. - презентация

1 Комбинато́рика Комбинато́рика (Комбинаторный анализ) раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения, например в информатике и статистической физике.

2 Термин «комбинаторика» был введён Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Дата рождения: 1 июля 1646 Место рождения: Лейпциг, Саксония, Германия, Дата смерти: 14 ноября 1716 (70 лет) Священная Римская империя Научная сфера: философия, логика, математика, механика, физика, история, лингвистика Альма-матер: Лейпцигский университет, Йенский университет имени Фридриха Шиллера, Альтдорфский университет

3 Классические задачи комбинаторики При решении практических задач часто приходится выбирать из некоторого конечного множества объектов подмножество элементов, обладающих теми или иными свойствами, размещать элементы множеств в определенном порядке и т. д. Эти задачи принято называть комбинаторными задачами

4 Правила сложения и произведения Правило сложения. Если удается разбить множество объектов на классы и каждый объект входит в один и только один класс, то общее число объектов равно сумме числа объектов во всех классах. Правило умножения. Даны два произвольных конечных множества объектов А и В. Количество объектов в А равно N, в В М. Составляются упорядоченные пары аb, где а принадлежит и А b принадлежит B. Количество таких пар (объектов) равно N*M. Правило обобщается и на большее количество множеств объектов.

5 Перестановки Классической задачей комбинаторики является задача о числе перестановок: Сколькими способами можно переставить N различных предметов, расположенных на N различных местах.

6 Сколькими способами можно переставить три монеты 1,2,5 рублей, расположенных соответственно на трех местах с номерами 1, 2, 3?

7 Ответ: 6.

8 Сколькими способами можно пересадить четырех гостей А, Б, В, Г, сидящих соответственно на четырех местах 1, 2, 3, 4?

9 Ответ: 24.

10 N различных предметов, расположенных на N различных местах, можно переставить N! (эн-факториал) = 1*2*3*...* N способами. P n =N!

11 Сколькими способами можно переставить буквы в слове эскиз!

12 Ответ: 120.

13 Сколькими способами можно расположить на шахматной доске 8 ладей так, чтобы они не могли бить друг друга?

14 Ответ:

15 Размещения Задача формулируется следующим образом: Cколькими способами можно выбрать и разместить по М различным местам М из N различных предметов?

16 Сколькими способами можно выбрать и разместить на двух местах 1, 2 две из трех монет 1, 2, 5 рублей?

17 Ответ: 6.

18 Сколькими способами можно выбрать и разместить на двух местах 1, 2 двух из четырех гостей А, Б, В, Г?

19 Ответ: 12

20 Число размещений вычисляется по формуле

21 Сколько трехбуквенных словосочетаний можно составить из букв слова эскиз?

22 Ответ: 60

23 В чемпионате по футболу принимают участие 17 команд и разыгрываются золотые, серебряные и бронзовые медали. Сколькими способами они могут быть распределены?

24 Ответ: 4080

25 Партия состоит из 25 человек. Требуется выбрать председателя партии, его заместителя, секретаря и казначея. Сколькими способами можно это сделать, если каждый член партии может занимать лишь один пост.

26 Ответ:

27 Сочетания (выборки) Другой классической задачей комбинаторики является задача о числе выборок: сколькими способами можно выбрать М из N различных предметов?

28 Сколькими способами можно выбрать две из трех монет 1,2, 5 рублей? 3 Сколькими способами можно выбрать двух из четырех гостей А, Б, В, Г? 6 Сколькими способами можно выбрать три из пяти букв слова эскиз? 10 В чемпионате по футболу России принимают участие 17 команд и разыгрываются золотые, серебряные и бронзовые медали. Нас не интересует порядок, в котором располагаются команды-победительницы, ибо все они выходят на Европейские турниры. Сколько различных способов представления нашего государства на Европейских турнирах? 680

29 Партия состоит из 25 человек. Требуется выбрать председателя партии и его заместителя, ибо они представляют партию в президиуме межпартийных форумов. Сколькими способами можно это сделать, если каждый член партии может занимать лишь один пост? Сколькими способами можно поставить на шахматной доске 8 ладей (условие о том, что ладьи не могут бить друг друга, снимается)?

30 Сколько различных прямоугольников можно вырезать из клеток доски размером N*M (стороны прямоугольников проходят по границам клеток)?

31 Число сочетаний вычисляется по формуле

32 Правила сложения и произведения Правило сложения. Если удается разбить множество объектов на классы и каждый объект входит в один и только один класс, то общее число объектов равно сумме числа объектов во всех классах. Правило умножения. Даны два произвольных конечных множества объектов А и В. Количество объектов в А равно N, в В М. Составляются упорядоченные пары аb, где а принадлежит и А b принадлежит B. Количество таких пар (объектов) равно N*M. Правило обобщается и на большее количество множеств объектов.

33 Размещения с повторениями Даны предметы, относящиеся к N различным типам. Из них составляются всевозможные расстановки длины k. При этом в расстановки могут входить и предметы одного типа. Две расстановки считаются различными, если они отличаются или типом входящих в них предметов или порядком этих предметов.

34 Имеются предметы k различных типов. Сколько перестановок можно сделать из N 1 предметов первого типа, N 2 второго,..., N k k-го типа, N 1 +N 2 +…+N K =N. Общая формула для подсчета числа перестановок с повторениями: P(N 1,N 2,…,N K) =N!/(N 1 !*N 2 !*…*N K !) Перестановки с повторениями

35 Сочетания с повторениями Имеются предметы N различных типов Сколько существует расстановок длины k, если не различать порядок предметов в расстановке (различные расстановки должны отличаться хотя бы одним предметом)?

36 Сколько различных буквосочетаний можно получить из букв слова папа? Сколько различных буквосочетаний можно получить из букв слова капкан? Сколькими способами можно расположить в ряд 2 одинаковых яблока и 3 одинаковые груши? Сколько различных сообщений можно закодировать, меняя порядок 6 флажков: 2 красных, 3 синих и 1 зеленый?

37 Ответ: 6 (папа, папа, папа, пап, пап, папа).

38 Ответ: 180.

39 Ответ: 10.

40 Ответ: 60.