Презентация по математике Примеры комбинаторных конфигураций и задач

Иордан Ирина ИвановнаМБОУ СОШ №50Новосибирск-2015Примеры комбинаторных конфигураций и задач Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций Теория конфигураций Теория конфигураций является традиционным и наиболее разработанным разделом комбинаторики. Теория конфигураций рассматривает задачи выбора и расположения элементов некоторого, обычно конечного, множества, в соответствии с заданными правилами. Перечислительная комбинаторика основным методом исследования провозгласила метод производящих функций, используя который было доказано громадное число комбинаторных тождеств. Элементарными комбинаторными конфигурациями являются сочетания, размещения, перестановки. Для подсчёта числа этих конфигураций используются правила суммы и произведения. Примерами комбинаторных конфигураций являются: Размещение из n элементов по k – это упорядоченный набор из k различных элементов некоторого n-элементного множества.Сочетание из n по k - это набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.Например, <1,3,2,5> — это 4-элементное размещение 6-элементного множества {1,2,3,4,5,6}.В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы <2,1,3> и <3,2,1> являются различными, хотя состоят из одних и тех же элементов {1,2,3} (т.е. совпадают как сочетания).Перестановка из n элементов (обычно чисел 1,2,…,n) - это всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n.Например, три элемента a, b, c можно расставить по-разному: abc, acb, bac, bca, cab, cba. Каждое из этих расположений называют перестановкой из трех элементов. Примерами комбинаторных конфигураций являются: Композиция числа n - это всякое представление n в виде упорядоченной суммы целых положительных чисел. Например, существует 16 композиций числа 5: 5 = 5; 5 = 1 + 4; 5 = 4 + 1; 5 = 1 + 3 + 1; 5 = 3 + 2; 5 = 1 + 2 + 2; 5 = 3 + 1 + 1; 5 = 1 + 2 + 1 + 1; 5 = 2 + 3; 5 = 1 + 1 + 3; 5 = 2 + 2 + 1; 5 = 1 + 1 + 2 + 1; 5 = 2 + 1 + 2; 5 = 1 + 1 + 1 + 2; 5 = 2 + 1 + 1 + 1; 5 = 1 + 1 + 1 + 1 + 1. Разбиение числа n - это всякое представление n в виде неупорядоченной суммы целых положительных чисел.Например, (3,1,1) или (3,2) - разбиения числа 5, поскольку 5 = 3 + 1 + 1 = 3 + 2. Всего существует p(5)=7 разбиений числа 5: (1,1,1,1,1), (2,1,1,1), (2,2,1), (3,1,1), (3,2), (4,1), (5). Правило суммы. Правило произведения Если элемент A можно выбрать m способами, а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами. Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда упорядоченную пару элементов (A, B) можно выбрать m*k способами. Стадион имеет 4 входа: A, B, C и D. Укажите все возможные способы, какими посетитель может войти через один вход и выйти через другой. Сколько таких способов?Решение: Посетитель может войти через один из четырех входа, а выйти через один из трех оставшихся, т.е. имеется 4·3=12 способов.Ответ: 12 способов. Из села Дятлово в село Матвеевское ведут три дороги, а из села Матвеевское в село Першино – четыре дороги. Сколькими способами можно попасть из Дятлова в Першино через Матвеевское?Решение: В село Матвеевское из Дятлова можно попасть тремя способами. А из Матвеевского в Першино – 4 способами. Значит, 3·4=12 способов.Ответ: 12 способов. Петр решил пойти на новогодний карнавал в костюме мушкетера. В ателье проката ему предложили на выбор различные по фасону и цвету предметы: пять пар брюк, шесть камзолов, три шляпы, две пары сапог. Сколько различных карнавальных костюмов можно составить из этих предметов?Решение: Брюки можно выбрать пятью способами, камзолы – шестью, шляпы – тремя, сапоги – двумя. Значит, костюм можно составить 5·6·3·2=180 способами.Ответ: 180 способов. Выведем формулу для числа перестановок из n элементов.Пусть мы имеем n элементов. На первое место можно поставить любой из них. Для каждого выбора первого элемента на второе место можно поставить один из оставшихся n-1 элементов. Для каждого выбора первых двух элементов на третье место можно поставить один из оставшихся n-2 элементов и т.д. в результате получим, чтоPn = n(n-1)(n-2) ·…·3·2·1.Расположив множители в порядке возрастания, получимPn = 1·2·3·…·(n-2)(n-1)n.Для произведения первых n натуральных чисел используется специальное обозначение: n! (читается «n факториал»).Таким образом, число всевозможных перестановок из n элементов вычисляется по формуле Pn = n! Факториал Факториалом (от латинского factor - деятель, создатель, множитель) числа n называют произведение всех натуральных чисел от 1 до n включительно. Записывается так: n! По определению 0!=1, 1!=1. Факториалы отрицательных или действительных чисел не существуют. Факториалы чисел очень быстро растут в значениях при росте n, и даже при относительно небольших n будут иметь огромные числовые значения. Так 20!=2432902008176640000, а 100! будет состоять уже из 158 цифр. Сколькими способами могут быть расставлены 8 участниц финального забега на восьми беговых дорожках?Решение: Число способов равно числу перестановок из 8 элементов. Р8=1∙2∙3∙4∙5∙6∙7∙8=8!=40320. Значит, существует 40320 способов расстановки участниц забега на восьми беговых дорожках.Ответ: 40320 способов. Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0, 2, 4, 6?Решение: Из цифр 0, 2, 4, 6 можно получить Р4 перестановок. Из этого числа надо исключить те перестановки, которые начинаются с 0, т.к. натуральное число не может начинаться с цифры 0. Число таких перестановок равно Р3. Значит, искомое число четырехзначных чисел, которые можно составить из цифр 0, 2, 4, 6 равно Р4 – Р3= 4!–3!=1∙2∙3∙4 – 1∙2∙3= 24 – 6=18.Ответ: 18 чисел. Имеется девять различных книг, четыре из которых – учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом?Решение: Сначала будем рассматривать учебники как одну книгу. Тогда на полке надо расставить не 9, а 6 книг это можно сделать Р6 способами. В каждой из полученных комбинаций можно выполнить Р4 перестановок учебников. Значит, искомое число способов расположения книг на полке равно произведению Р6·Р4 = 6! ·4! = 720·24 = 17280.Ответ: 17280 способов. Сколькими способами 9 человек могут встать в очередь в театральную кассу?Решение: Число способов равно числу перестановок из 9 элементов.Р9=9!=1∙2∙3∙4∙5∙6∙7∙8∙9=362880.Ответ: 362880 способов. В расписании на понедельник шесть уроков: алгебра, геометрия, биология, история, физкультура, химия. Сколькими способами можно составить расписание на этот день так, чтобы два урока математики (алгебра и геометрия) стояли рядом?Решение: Рассмотрим алгебру и геометрию как один урок. Тогда расписание надо составить не из 6, а из 5 уроков – Р5 способов. В каждой из полученных комбинаций можно выполнить Р2 перестановки алгебры и геометрии. Значит, искомое число способов составления расписания: Р5∙Р2=1∙2∙3∙4∙5∙1∙2= 120∙2=240 Ответ: 240 способов.