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

решения комбинаторных задач используют различные модели комбинаторных конфигураций

Теория конфигураций рассматривает задачи выбора и расположения элементов некоторого, обычно конечного, множества, в соответствии с заданными правилами. Перечислительная комбинаторика основным методом исследования провозгласила метод производящих функций, используя который было доказано громадное число комбинаторных тождеств.
Элементарными комбинаторными конфигурациями являются сочетания, размещения, перестановки. Для подсчёта числа этих конфигураций используются правила суммы и произведения.

это упорядоченный набор из 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 в виде упорядоченной суммы целых положительных чисел.
Например, существует 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).

а элемент B можно выбрать k способами, то выбор элемента A или B можно осуществить m + k способами.
Если элемент A можно выбрать m способами, а после каждого выбора элемента A элемент B можно выбрать k способами, тогда упорядоченную пару элементов (A, B) можно выбрать m*k способами.

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

Из села Дятлово в село Матвеевское ведут три дороги, а из села Матвеевское в село Першино – четыре дороги. Сколькими способами можно попасть из Дятлова в Першино через Матвеевское?
Решение: В село Матвеевское из Дятлова можно попасть тремя способами. А из Матвеевского в Першино – 4 способами. Значит, 3·4=12 способов.
Ответ: 12 способов.

Петр решил пойти на новогодний карнавал в костюме мушкетера. В ателье проката ему предложили на выбор различные по фасону и цвету предметы: пять пар брюк, шесть камзолов, три шляпы, две пары сапог. Сколько различных карнавальных костюмов можно составить из этих предметов?
Решение: Брюки можно выбрать пятью способами, камзолы – шестью, шляпы – тремя, сапоги – двумя. Значит, костюм можно составить 5·6·3·2=180 способами.
Ответ: 180 способов.

элементов. На первое место можно поставить любой из них. Для каждого выбора первого элемента на второе место можно поставить один из оставшихся 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!

произведение всех натуральных чисел от 1 до n включительно. Записывается так: n!
По определению 0!=1, 1!=1. Факториалы отрицательных или действительных чисел не существуют. Факториалы чисел очень быстро растут в значениях при росте n, и даже при относительно небольших n будут иметь огромные числовые значения. Так 20!=2432902008176640000, а 100! будет состоять уже из 158 цифр.

беговых дорожках?
Решение: Число способов равно числу перестановок из 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!=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 способов.