ПОДГОТОВИЛИ: БАЛИМЧУК ЛАДА КОЗЛОВА АННА 10 «В» Комбинаторика.

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

Древний период Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). Гексаграмма из «Книги Перемен» Так же большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты.

Средневековье В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век).

Новые времена. Первые теоретические построения комбинаторики начались в XVII в. и связаны с именами Блеза Паскаля («Трактат об арифметическом треугольнике», 1665 г.), Пьера Ферма, Кристиана Гюйгенса, Якоба Бернулли («Искусство предположений»)

Готфрид Вильгельм Лейбниц Термин "комбинаторика" был введён в математический обиход знаменитым Лейбницем. В 1666 году Лейбниц опубликовал "Рассуждения о комбинаторном искусстве". В своём сочинении Лейбниц, вводя специальные символы, термины для подмножеств и операций над ними находит все k -сочетания из n элементов выводит свойства сочетаний.

Современное развитие комбинаторики. В 1940-х годах оформилась теория Рамсея. Отцом современной комбинаторики считается Пал Эрдёш, который ввёл в комбинаторику вероятностный анализ.

Внимание к конечной математике и, в частности, к комбинаторике значительно повысилось со второй половины XX века, когда появились компьютеры. Сейчас это чрезвычайно содержательная и быстроразвивающаяся область математики.

Факториал. Факториал числа n (обозначается n!, произносится эн факториал) произведение всех натуральных чисел до n включительно: По определению полагают 0! = 1. Факториал определён только для целых неотрицательных чисел. Эта функция часто используется в комбинаторике, теории чисел и функциональном анализе. Иногда словом «факториал» неформально называют восклицательный знак.

Комбинаторные соединения Перестановки Перестановки без повторений Перестановки с повторениями Размещения Размещения без повторений Размещения с повторениями Сочетания Сочетания без повторений Сочетания с повторениями 1.)Комбинаторные соединения: 2.)Бином Ньютона

Перестановка Перестановки – соединения, которые можно составить из n элементов, меняя всеми возможными способами их порядок. Формула :

Задача 1. Найти число перестановок множества, состоящего из трех элементов: A, B, C.

Перестановки с повторениями. Теорема. Число различных перестановок с повторениями из элементов {a 1, …, an}, в которых элементы a 1, …, an повторяются соответственно k 1,..., kn раз, равно (k1+k2+…+kn)! m! k1! k2! … kn! k1! k2! … kn! P

Пример. У мамы два яблока, три груши и четыре апельсина. Каждый день в течение девяти дней подряд она дает сыну один из оставшихся фруктов. Сколькими способами это может быть сделано? Р 2,3,4 = 9!9!9!9! 2! 3! 4! = *6*7*8*92*2*3 = Решение: У мамы всего 9 фруктов: два яблока, три груши и четыре апельсина. (k 1, k 2, …, k n )

Размещение. Размещением из n элементов по k ( ) называется любое множество, состоящее из любых k элементов, взятых в определенном порядке из n элементов.

Задача 2. Найти число размещений множества, состоящего из четырех элементов: A, B, C, D по два, т.е. сколько различных размещений по два элемента можно составить из указанного множества.

Размещения с повторениями. Размещения с повторениями – соединения, содержащие n элементов, выбираемых из элементов m различных видов ( ) и отличающиеся одно от другого либо составом, либо порядком элементов. Их количество в предположении неограниченности количества элементов каждого вида равно

Сочетания. Сочетания – соединения, содержащие по m предметов из n, различающихся друг от друга по крайней мере одним предметом. Сочетания – конечные множества, в которых порядок не имеет значения. Формула нахождения количества сочетаний без повторений:

Задача 3 Найти число сочетаний множества, состоящего из четырех элементов: A, B, C, D по два.

Сочетания с повторениями Если из множества, содержащего n элементов, выбирается поочередно m элементов, причём выбранный элемент каждый раз возвращается обратно, то количество способов произвести неупорядоченную выборку – число сочетаний с повторениями – составляет

Пример. Сколько наборов из 7 пирожных можно составить, если в распоряжении имеются 4 сорта пирожных? Решение:

Бином Ньютона. Бином Ньютона – это формула разложения степени двучлена (бинома) в виде многочлена от a и b. Например разложения бинома Ньютона для нескольких первых значений n.: и т.д.

Биномиальная формула Ньютона. -Биномиальные коэффициенты Биномиальные коэффициенты для различных n удобно представлять в виде таблицы, которая называется арифметический треугольник Паскаля

Треугольник Паскаля

Пример 4. Напишите разложение выражения (a+b) 5 по формуле бинома Ньютона.

Конец.