История развития комбинаторики кратко

Обновлено: 07.07.2024

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

Исследования, посвященные различным вариантам выборки заданного числа элементов из некоторого конечного множества, занимали лучшие математические умы человечества достаточно давно. Отдельные комбинаторные задачи решали в древней Индии, Китае, античной Греции. Тем не менее, как самостоятельная научная дисциплина комбинаторика стала выделяться из математики только в XVII-ом столетии. В этот период формируется терминология новой научной области, появляется ряд значительных исследований, посвященных комбинаторным методам. Перечислим наиболее значительные труды:

Рождение комбинаторики как раздела математики связано с трудами Б. Паскаля и П. Ферма по теории азартных игр. Большой вклад в развитие комбинаторных методов внесли Г.В. Лейбниц, Я. Бернулли и Л. Эйлер.

Французский философ, писатель, математик и физик Блез Паскаль (1623–1662) рано проявил свои выдающиеся математические способности. Круг математических интересов Паскаля был весьма разнообразен. Паскаль доказал одну из основных теорем проективной геометрии (теорема Паскаля), сконструировал суммирующую машину (арифмометр Паскаля), дал способ вычисления биномиальных коэффициентов (треугольник Паскаля), впервые точно определил и применил для доказательства метод математической индукции, сделал существенный шаг в развитии анализа бесконечно малых, сыграл важную роль в зарождении теории вероятности. В гидростатике Паскаль установил ее основной закон (закон Паскаля). “Письма к провинциалу” Паскаля явились шедевром французской классической прозы.

Готфрид Вильгельм Лейбниц (1646–1716) — немецкий философ, математик, физик и изобретатель, юрист, историк, языковед. В математике наряду с И. Ньютоном разработал дифференциальное и интегральное исчисление. Важный вклад внес в комбинаторику. С его именем, в частности, связаны теоретико-числовые задачи.

Готфрид Вильгельм Лейбниц имел мало внушительную внешность и поэтому производил впечатление довольно невзрачного человека. Однажды в Париже он зашел в книжную лавку в надежде приобрести книгу своего знакомого философа. На вопрос посетителя об этой книге книготорговец, осмотрев его с головы до ног, насмешливо бросил: “Зачем она вам? Неужели вы способны читать такие книги?” Не успел ученый ответить, как в лавку вошел сам автор книги со словами: “Великому Лейбницу привет и уважение!” Продавец никак не мог взять втолк, что перед ним действительно знаменитый Лейбниц, книги которого пользовались большим спросом среди ученых.

Часто приходится иметь дело с задачами выбора элементов из некоторой совокупности и расположения этих элементов в определенном порядке. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют комбинаторными задачами. Роль таких задач важна не только в математике, но и физике, химии, биологии, технике и экономике. Комбинаторные задачи приходится рассматривать при определении наиболее выгодных коммуникаций внутри города, при организации автоматической телефонной связи, при выявлении связей внутри сложных молекул, генетического кода, математической статистики и т. д.

Вложение	Размер
kombinatorika.docx	38.96 КБ
kombinatorika.pptx	325.58 КБ

Предварительный просмотр:

Муниципальное автономное общеобразовательное учреждение

средняя общеобразовательная школа № 147

Выпoлнил: ученик 4 А клacca

Глава I. 1.1. Исторические сведения о комбинаторике ………………….

Глава II. Исследовательская часть ……………………………….

Список используемых источников и литературы ………………………..

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

Основной темой и предметом данного исследования является —

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

Объект исследования : область математики – комбинаторика.

Цель работы: знакомство с понятием комбинаторика. Расширить область математических знаний. Развивать логическое мышление.

Гипотеза : комбинаторика интересна и имеет широкий спектр практической направленности.

Собрать, изучить и систематизировать материал о комбинаторике;
Рассмотреть, как элементы комбинаторики используются при решении различных жизненных ситуаций;
Использование комбинаторики в различных сферах жизнедеятельности.

Термин "комбинаторика" был введён в математический обиход знаменитым Лейбницем. Готфрид Вильгельм Лейбниц (1.07.1646 — 14.11.1716) — всемирно известный немецкий учёный, занимался философией, математикой, физикой, организовал Берлинскую академию наук и стал её первым президентом.

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

В течение всей своей жизни Лейбниц многократно возвращался к идеям комбинаторного искусства. Комбинаторику он понимал весьма широко, именно, как составляющую любого исследования, любого творческого акта, предполагающего сначала анализ (расчленение целого на части), а затем синтез (соединение частей в целое).

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.

В 1713 году было опубликовано сочинение Я. Бернулли "Искусство предположений", в котором были изложены известные к тому времени комбинаторные факты и содержались формулы:

для числа перестановок из n элементов
для числа сочетаний без повторений и с повторениями,
для числа размещений с повторениями и без повторений.

Комбинаторика, пройдя многовековой путь развития, обретя собственные методы исследования, с одной стороны, широко используется при решении задач алгебры, геометрии, анализа, с другой стороны, сама использует геометрические, аналитические и алгебраические методы исследования.

В XX веке комбинаторика подверглась мощному процессу алгебраизации благодаря работам Дж.-К. Рота (1964), а затем Р. Стенли. Изучение ими частично упорядоченных множеств, свойств функции Мёбиуса, абстрактных свойств линейной зависимости, выявление их роли при решении комбинаторных задач способствовали обогащению комбинаторных методов исследования и дальнейшей интеграции комбинаторики в современную математику.

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

Меня комбинаторика привлекла интересными задачами, неожиданными решениями и результатами, новым взглядом на повседневные события. Для меня стало открытием, что многие казавшиеся непредсказуемыми процессы (даже протекающие в нашем классе!) подчиняются строгим математическим законам. Жаль, что комбинаторике уделяется так мало внимания в курсе начальной школы.

2.1. Исследовательская часть

Исследовать задачи, изучаемые комбинаторикой, я предлагаю на примере нашего класса. У нас в классе 22 ученика; 10 мальчиков, 12 девочек. Нашу учительницу зовут Наталья Матвеевна.

Видно, что от каждого кружочка-ученика отходят стрелочки к 21 другому кружочку и приходит тоже 21 стрелочка.

Похоже, этот праздник придумали продавцы открыток!

22 ученика поздравили друг друга по телефону с Новым годом. Сколько всего было сделано звонков?

Видно, что стрелок здесь в 2 раза меньше, стрелочки двойные так как одним разговором поздравляют друг друга сразу 2 человека.

231 звонок, тоже немало!

У Марка есть карточки с цифрами 3, 5, 6; у Саши 0, 1,2; а у Ильи 6, 8, 8. Ребята поспорили, кто из них составит больше чисел из своих цифр?

Решим задачу перебором:

0 первым в числе быть не может

У Марка 6 чисел, у Саши 4 числа, у Ильи 3 числа.

А если числа могут повторяться, методом перебора получится:

У Марка 27 чисел, у Саши 18 чисел, у Ильи 8 чисел.

Сколькими способами Наталья Матвеевна может рассадить 22 ученика за 11 парт?

Перебором эту задачу решать сложно, воспользуемся формулой о числе возможных перестановок

Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок

где n! = 1 * 2 * 3 . n.

22!=22*21*…2*1=1124000000000000000000 (считала программа Excel)

18 нулей! Даже если мы будем пересаживаться каждый урок все 4 года без выходных и каникул (365*4*4=35040) все равно перебрать все варианты не успеем!

Сколькими способами Наталья Матвеевна может из 22 учеников выбрать 3 дежурных?

Воспользуемся формулой о числе возможных сочетаний:

Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетаний

С m n = n! / (m! (n - m)!).

22!/(3!*(22-3)!)=1540 сам считал!

В предыдущей задаче мы подсчитали что из 22 учеников по 3 можно сделать 1540 выборок,

1540*6=9240 способов распределить рефераты ребятам.

Ну все таки меньше чем способов рассадить за парты!

Задача 7 (принцип Дирихле)

В нашем классе 22 ученика, Докажите, что хотя бы у двоих день рождения в одном месяце.

В году 12 месяцев, если в каждом месяце день рождения 1 ученика

22-12=10 ребят останутся без дня рождения, значит у нескольких дни рождения должны быть в один месяц.

Задача 8 (принцип Дирихле)

В коробке 10 красных, 10 синих, 5 зеленых и 5 желтых карандашей. Девочки достают карандаши из коробки, не глядя, какое минимальное число карандашей надо достать чтобы:

У Оли было не менее 2 карандашей одного цвета?

В худшем случае Оля сначала вытащит 1 красный, 1 синий, 1 зеленый и 1 желтый, любой следующий карандаш совпадет по цвету с каким-то предыдущим.

Оле надо взять не менее 5 карандашей.

У Алены было не менее 5 красных?

В худшем случае Алена сначала вытащит 4 красных, 10 синих, 5 зеленых и 5 желтых, следующий карандаш точно будет пятым красным.

Алене надо взять не менее (5+10+5+5) =25 карандашей.

У Кати было по одному карандашу каждого цвета?

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

Кате надо взять не менее (10+10+5+1) =26 карандашей.

Используя методы комбинаторики, наши девочки даже с завязанными глазами возьмут наименьшее количество карандашей, чтобы получить требуемые цвета. В нашем классе очень умные, бойкие и красивые девочки!

Комбинаторика очень интересная наука, если применить ее к нашему классу получаются потрясающие результаты! Чтобы перепробовать все возможные пересадки за партами, варианты троек для дежурства и т.д. нам не хватит 11 школьных лет!

Мне решение задач на комбинаторику позволило по-новому взглянуть на изучаемые в школе разделы математики, надеюсь, это поможет в дальнейшем освоении формальной логики алгебры.

Предлагаю шире изучать комбинаторику в школе; например, во время занятий кружков и факультативов.

Дальнейшее изучение комбинаторики, логически предполагает рассмотрение применения простейших формул теории вероятности к жизни нашего класса.

Список используемых источников и литературы

Предварительный просмотр:

Подписи к слайдам:

История комбинаторики Выпoлнил : ученик 4 А класса Гуcев Дмитрий Руководитель: Вырышевa Нaтaлья Мaтвеевнa

Объект исследования : область математики – комбинаторика. Цель работы: знакомство с понятием комбинаторика. Расширить область математических знаний. Развивать логическое мышление. Гипотеза : комбинаторика интересна и имеет широкий спектр практической направленности.

Задачи исследования : Собрать, изучить и систематизировать материал о комбинаторике; 2. Рассмотреть, как элементы комбинаторики используются при решении различных жизненных ситуаций; 3. Использование комбинаторики в различных сферах жизнедеятельности.

Комбинато́рика — раздел математики , изучающий дискретные объекты, множества ( сочетания , перестановки , размещения и перечисления элементов). В разное время комбинаторикой занимались: Готфрид Лейбниц (1646-1716) Леонард Эйлер (1707-1783) Якоб Бернулли (1654-1705) Комбинаторика – древняя наука!

22 ученика поздравили друг друга по телефону с Новым годом. Сколько всего было сделано звонков? Сделаем рисунок: Видно, что стрелок здесь в 2 раза меньше, стрелочки двойные так как одним разговором поздравляют друг друга сразу 2 человека. 22*21:2=231 звонок 231 звонок, тоже немало! Задача № 2 22 1 2 3 4 21 …

У Марка есть карточки с цифрами 3, 5, 6; у Саши 0, 1, 2; а у Ильи 6, 8, 8. Ребята поспорили, кто из них составит больше чисел из своих цифр? Решим задачу перебором: У Марка 6 чисел, у Саши 4 числа, у Ильи 3 числа. А если числа могут повторяться, методом перебора получится: У Марка 27 чисел, у Саши 18 чисел, у Ильи 8 чисел. Марк Саша Илья 357 375 573 537 753 735 240 204 420 402 0 первым в числе быть не может 688 868 886 Задача № 3

Сколькими способами Наталья Матвеевна может рассадить 22 ученика за 11 парт? Перебором эту задачу решать сложно, воспользуемся формулой о числе возможных перестановок. Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок P n = n !, где n ! = 1 * 2 * 3 . n . 22!=22*21*…2*1=1124000000000000000000 ( считала программа Excel ) 18 нулей! Даже если мы будем пересаживаться каждый урок все 4 года без выходных и каникул (365*4*4=35040) все равно перебрать все варианты не успеем! Задача № 4

Сколькими способами Наталья Матвеевна может из 22 учеников выбрать 3 дежурных? Воспользуемся формулой о числе возможных сочетаний: Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетаний С m n = n ! / ( m ! ( n - m )!). 22!/(3!*(22-3)!)=1540 сам считал! Задача № 5

В коробке 10 красных, 10 синих, 5 зеленых и 5 желтых карандашей. Девочки достают карандаши из коробки, не глядя, какое минимальное число карандашей надо достать чтобы: 10 У Оли было не менее 2 карандашей одного цвета? В худшем случае Оля сначала вытащит 1 красный, 1 синий, 1 зеленый и 1 желтый, любой следующий карандаш совпадет по цвету с каким-то предыдущим. Оле надо взять не менее 5 карандашей. У Алены было не менее 5 красных? В худшем случае Алена сначала вытащит 4 красных, 10 синих, 5 зеленых и 5 желтых, следующий карандаш точно будет пятым красным. Алене надо взять не менее (5+10+5+5) =25 карандашей. Задача № 7 (принцип Дирихле) У Кати было по одному карандашу каждого цвета? В худшем случае Катя сначала вытащит 10 красных, 10 синих, 5 зеленых (или 5 желтых), следующий карандаш точно будет последним недостающим. Кате надо взять не менее (10+10+5+1) =26 карандашей.

Вывод Комбинаторика очень интересная наука, если применить ее к нашему классу получаются потрясающие результаты! Чтобы перепробовать все возможные пересадки за партами, варианты троек для дежурства и т.д. нам не хватит 11 школьных лет!

Математическое поле комбинаторика в той или иной степени изучался во многих древних обществах. Его изучение в Европе восходит к работе Леонардо Фибоначчи в 13 веке нашей эры, что принесло на континент арабские и индийские идеи. Его продолжают изучать и в современную эпоху.

Содержание

Самые ранние записи

В Греции, Плутарх написал это Ксенократ из Халкидона (396–314 г. до н.э.) обнаружил, что в греческом языке возможно множество различных слогов. Это была бы первая попытка решить сложную проблему в перестановки и комбинации. [2] Это утверждение, однако, неправдоподобно: это одно из немногих упоминаний комбинаторики в Греции, и найденное ими число 1,002 × 10. 12 , кажется слишком круглым, чтобы быть более чем предположением. [3] [4]

В Бхагавати Сутра первое упоминание о проблеме комбинаторики; Задача заключалась в следующем: сколько возможных комбинаций вкусов возможно при выборе вкусов по одному, по два, по три и т. д. из шести различных вкусов (сладкий, острый, терпкий, кислый, соленый и горький). Бхагавати также является первым текстом, в котором упоминается выбрать функцию. [5] Во втором веке до нашей эры Пингала включил проблему перечисления в Чанда Сутра (также Chandahsutra), который спрашивал, сколько способов можно составить шестисложный метр из коротких и длинных нот. [6] [7] Пингала нашла количество метров, в которых п < displaystyle n>длинные заметки и k < displaystyle k>короткие заметки; это эквивалентно нахождению биномиальные коэффициенты.

Идеи Бхагавати были обобщены индийским математиком. Махавира в 850 г. н.э., а работа Пингалы по просодия был расширен Бхаскара II [5] [8] и Хемачандра в 1100 году нашей эры. Бхаскара был первым известным человеком, который нашел функцию обобщенного выбора, хотя Брахмагупта возможно, знал раньше. [1] Хемачандра спросил, сколько метров существует определенной длины, если длинная нота считается вдвое длиннее короткой, что равносильно нахождению Числа Фибоначчи. [6]

Древняя китайская книга гаданий И Цзин описывает гексаграмму как перестановку с повторением шести линий, где каждая линия может быть в одном из двух состояний: сплошной или пунктирной. Описывая гексаграммы таким образом, они определяют, что существуют 2 6 = 64 < displaystyle 2 ^ = 64> возможные гексаграммы. Китайский монах также мог подсчитать количество конфигураций в игре, похожей на Идти около 700 г. н.э. [3] Хотя в Китае было относительно мало достижений в области перечислительной комбинаторики, около 100 г. н.э. они решили Площадь Ло Шу какой комбинаторный дизайн проблема нормального магический квадрат третьего порядка. [1] [9] Магические квадраты по-прежнему интересовали Китай, и они начали обобщать свои оригинальные 3 × 3 < displaystyle 3 times 3>площадь между 900 и 1300 годами нашей эры. Китай переписывался с Ближним Востоком по этой проблеме в 13 веке. [1] Ближний Восток также узнал о биномиальных коэффициентах из индийских работ и обнаружил связь с полиномиальным расширением. [10] Работа индусов повлияла на арабов, как видно из работы аль-Халил ибн Ахмад который рассмотрел возможные варианты расположения букв для образования слогов. Его расчеты показывают понимание перестановок и комбинаций. В отрывке из работы арабского математика Умара аль-Хайями, датируемом примерно 1100 годом, подтверждается, что индусы знали биномиальные коэффициенты, но также и то, что их методы достигли Ближнего Востока.

В Греции, Плутарх писал, что Ксенократ открыл количество различных слогов, возможных в греческом языке. Маловероятно, но это одно из немногих упоминаний комбинаторики в Греции. Число, которое они нашли, 1,002 × 10 12 , также кажется слишком круглым, чтобы быть более чем предположением. [3] [4]

Абу Бакр ибн Мухаммад ибн аль-Хусейн аль-Караджи (c.953-1029) писал о биномиальной теореме и треугольнике Паскаля. В уже утерянной работе, известной только из последующего цитирования аль-Самав'аль, Аль-Караджи ввел идею аргументации с помощью математической индукции.

В философ и астроном Раввин Авраам ибн Эзра (ок. 1140) подсчитал перестановки с повторениями в вокализации Божественного Имени. [11] Он также установил симметрию биномиальные коэффициенты, а замкнутая формула была получена позже талмудист и математик Леви бен Герсон (более известный как Герсонид), в 1321 г. [12] Арифметический треугольник - графическая диаграмма, показывающая отношения между биномиальные коэффициенты- был представлен математиками в трактатах, датируемых еще 10 веком, и в конечном итоге стал известен как Треугольник Паскаля. Позже Средневековая Англия, кампанология предоставил примеры того, что сейчас известно как Гамильтоновы циклы в определенных Графики Кэли по перестановкам. [13]

Комбинаторика на Западе

Комбинаторика пришла в Европу в 13 веке благодаря математикам. Леонардо Фибоначчи и Иорданус де Немор. Фибоначчи Liber Abaci познакомил Европу со многими арабскими и индийскими идеями, в том числе с числами Фибоначчи. [14] [15] Иордан был первым, кто расположил биномиальные коэффициенты в треугольнике, как он это сделал в предложении 70 из De Arithmetica. Это также было сделано на Ближнем Востоке в 1265 году и в Китае около 1300 года. [1] Сегодня этот треугольник известен как Треугольник Паскаля.

ПаскальВклад в треугольник, носящий его имя, основан на его работе над его формальными доказательствами и связями, которые он установил между треугольником Паскаля и вероятностью. [1] Из письма Лейбниц отправлен в Даниэль Бернулли мы узнаем, что Лейбниц формально изучал математическую теорию перегородки в 17 веке, хотя никаких официальных работ опубликовано не было. Вместе с Лейбницем Паскаль опубликовал De Arte Combinatoria в 1666 году, позже переизданный. [16] Паскаль и Лейбниц считаются основоположниками современной комбинаторики. [17]

И Паскаль, и Лейбниц понимали, что биномиальное разложение был эквивалентен функция выбора. Представление о соответствии алгебры и комбинаторики было расширено Де Муавром, который нашел расширение полинома. [18] Де Муавр также нашел формулу психических расстройств, используя принцип принцип включения-исключения, метод, отличный от Николауса Бернулли, который нашел его ранее. [1] Де Муавру также удалось приблизиться к биномиальные коэффициенты и факториал, и нашел замкнутую форму чисел Фибоначчи, изобретая производящие функции. [19] [20]

В 18 веке Эйлер работал над проблемами комбинаторики и несколькими проблемами вероятности, которые связаны с комбинаторикой. Проблемы, над которыми работал Эйлер, включают Рыцарский тур, Греко-латинский квадрат, Числа Эйлера, и другие. Чтобы решить Семь мостов Кенигсберга проблема, которую он изобрел теорию графов, которая также привела к формированию топология. Наконец, он начал с перегородки с использованием производящие функции. [21]

Современная комбинаторика

В 19 веке предметом частично упорядоченные наборы и теория решетки возникла в результате работы Дедекинд, Пирс, и Шредер. Однако это было Гаррет Биркоффплодотворная работа в его книге Теория решеток опубликовано в 1967 г., [22] и работа Джон фон Нейман это действительно установило предметы. [23] В 1930-е гг. зал (1936) и Вайснер (1935) независимо сформулировал общую формулу обращения Мёбиуса. [24] В 1964 г. Джан-Карло Рота Об основах комбинаторной теории I. Теория функций Мёбиуса. представил теорию посетов и решеток как теории комбинаторики. [23] Ричард П. Стэнли оказал большое влияние на современную комбинаторику благодаря своей работе в теория матроидов, [25] для введения полиномов Дзета, [26] для явного определения эйлеровых множеств, [27] развивая теорию биномиальных поз вместе с Ротой и Питером Дубиле, [28] и больше.

Читайте также: