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

Размещено на http://www.allbest.ru/

Реферат

На тему:

"История развития элементов комбинаторики"

Работу выполнила:

Балашова А.А.

Группа:1ПИ1

Преподаватель:

Конурова А.Н.

Содержание

Введение

1. Элементы комбинаторики и примеры решений

2. Древний период

3. Средневековье

4. Новое время

5. Современное развитие

6. История развития элементов комбинаторики

Список литературы

Введение

Комбинаторика занимается различного вида соединениями, которые можно образовывать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии ещё во 2 в. до н.э. Индийцы умели вычислять числа, которые сейчас называют "сочетания". В 17 веке Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские учёные изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчётом возможных сочетаний ударных(долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в 12 веке, в книге "Теория и практика арифметики". Книга была написана французским автором в 1656 году. Автор посвятил сочетаниям и перестановкам целую главу.

1. Элементы комбинаторики и примеры решений

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

Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.

Если из множества, содержащего m элементов, требуется выбрать какие-то k элементов, то возникает вопрос: сколькими способами это можно сделать и какие подмножества при этом получаются. Такие задачи называются комбинаторными, а соответствующий раздел математики - комбинаторикой.

Все формулы для подсчета числа решений в комбинаторных задачах опираются на правило произведения: если элемент X можно выбрать k способами, а элемент Y можно выбрать n способами, то пару XY можно составить kn способами.

Размещение с повторением. Из множества, содержащего m элементов, нужно выбрать k элементов, причем выбранный элемент, после того, как его взяли, вновь возвращается в исходное множество (то есть элементы в выбранном множестве могут повторяться). Пользуясь правилом произведения, получим, что каждый из k элементов может быть выбран m способами. Таким образом, общее число комбинаций равно .

Пример. Сколько различных четырехзначных чисел можно составить из цифр 2, 3, 5, 7.

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

Размещение без повторений. Из множества, содержащего mразличных элементов, надо выбрать упорядоченное подмножество изk элементов (k?m), то есть такое подмножество, в котором элементы располагаются в определенном порядке, и изменение порядка элементов изменяет подмножество. Кроме этого, элементы в выбранном подмножестве не повторяются. Требуется выяснить, сколько таких комбинаций существует. По правилу произведения получаем, что первый элемент можно выбрать m способами, второй элемент - (m-1) способом, и так далее, а элемент с номером k можно выбрать (m - k + 1) способами. Следовательно, число упорядоченных k-элементных подмножеств, взятых из множества, содержащего mэлементов равно m(m-1)(m-2)…(m-k+1). Такие подмножества называются размещениями из m элементов по k элементов, а их общее число можно выразить формулой

.

элемент комбинаторика пример развитие

Пример. Сколько различных четырехзначных чисел можно составить из цифр 1, 2, 3, 4, 5, 6, при условии. Что цифры в числе не повторяются?

Решение. Общее число комбинаций равно числу размещений из 6 элементов по 4:

Перестановки. Пусть множество содержит m различных элементов. Рассмотрим все возможные варианты перестановок элементов этого множества. Получаемые при этом упорядоченные множества отличаются друг от друга только порядком входящих в них элементов. Такие упорядоченные множества называются перестановками. Число перестановок из m элементов равно:

Пример. Сколько различных четырехзначных чисел можно составить из цифр 2, 3, 5. 7, если цифры в числе не повторяются?

Решение. Количество чисел равно числу перестановок из четырех элементов:

Сочетания. Пусть из множества, содержащего m различных элементов, требуется выбрать подмножество, содержащее kразличных элементов (k--Ј m). Получаемые при этом подмножества не упорядочены.

Такие неупорядоченные подмножества называются сочетаниями. Число сочетаний из m элементов по k элементов вычисляется по формуле:

Пример. В группе 10 студентов. Сколькими способами можно выбрать из этой группы троих студентов для участия в конференции?

Решение. Число способов равно числу сочетаний из 10 элементов по 3 элемента:

.

2. Древний период

Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо^[1]. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты.

Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.).^[2]. Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона^[2]. Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени n равна .

Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха -- более 100000^[3]. Аристотель при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов. Аристоксен рассмотрел различные чередования длинных и коротких слогов в стихотворных размерах.^[3] Какие-то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии (совершенные числа, фигурные числа, пифагоровы тройки и др.).

3. Средневековье

В XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями.

В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век) и Леви бен Гершом (он же Герсонид, XIV век). Ибн Эзра подсчитывал число размещений с перестановками в огласовках имени Бога^[4] и обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний.

Несколько комбинаторных задач содержит «Книга абака» (Фибоначчи, XIII век). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.

4. Новое время

Джероламо Кардано написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В историю зарождавшейся теории вероятностей вошла переписка заядлого игрока шевалье де Мерэ сПьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались (и продолжают использоваться) в криптографии -- как для разработки шифров, так и для их взлома.

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

5. Современное развитие

В начале XX века начала развиваться комбинаторная геометрия: были доказаны теоремы Минковского -- Радона, Радона, Хелли, Юнга, Бляшке, а также строго доказана изопериметрическая теорема. На стыке топологии, анализа и комбинаторики были доказаны теоремы Борсука -- Улама и Люстерника -- Шнирельмана. Во второй четверти XX века были поставлены проблема Борсука и проблема Нелсона -- Эрдёша -- Хадвигера. В1940-х годах оформилась теория Рамсея. Отцом современной комбинаторики считается Пал Эрдёш, который ввёл в комбинаторику вероятностный анализ. Внимание к конечной математике и, в частности, к комбинаторике значительно повысилось со второй половины XX века, когда появились компьютеры. Сейчас это чрезвычайно содержательная и быстроразвивающаяся область математики.

Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления: «треугольник Паскаля». Хотя этот способ был уже известен на Востоке (примерно с X века), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Наряду с Лейбницем, он считается основоположником современной комбинаторики. Сам термин «комбинаторика» придумал Лейбниц, который в 1666 году (ему было тогда 20 лет) опубликовал книгу «Рассуждения о комбинаторном искусстве». Правда, термин «комбинаторика» Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику^[5]. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.

В этот же период формируется терминология новой науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653, опубликован в 1665 году). Термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя эпизодически он встречался и раньше). Бернулли использовал и термин «размещение» (arrangement).

После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала.^[6]

Окончательно комбинаторика как самостоятельный раздел математики оформилась в трудах Эйлера. Он детально рассмотрел, например, следующие проблемы:

· задача о ходе коня;

· задача о семи мостах, с которой началась теория графов;

· построение греко-латинских квадратов;

· обобщённые перестановки.

6. История развития элементов комбинаторики

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

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

В 18 веке к решению комбинаторных задач обращались выдающиеся математики. Замечательные достижения в области комбинаторики принадлежат Леонарду Эйлеру. Он рассматривал задачи о разбиении чисел, о циклических расстановках, о построении магических и латинских квадратов. В 1713 году было опубликовано сочинение Бернулли в котором с достаточно полной силой были изложены известные к тому времени комбинаторные факты. Комбинаторными задачами интересовались математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей. Теперь комбинаторика находит применение во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений и т.д. Комбинаторные задачи в физике, химии, биологии и других наук, которые не поддавались ранее решению из-за трудоёмкости вычислений, стали успешно решаться.

Список литературы

1. Виленкин Н.Я. Популярная комбинаторика. -- М.: Наука, 1975. -- 208 с.

2. История математики. С древнейших времен до начала Нового времени // История математики / Под редакцией А.П. Юшкевича, в трёх томах. -- М.: Наука, 1970. -- Т. I.

3. Математика XVII столетия // История математики / Под редакцией А. П. Юшкевича, в трёх томах. -- М.: Наука, 1970. -- Т. II.

4. Математика XVIII столетия // История математики / Под редакцией А. П. Юшкевича, в трёх томах. -- М.: Наука, 1972. -- Т. III.

5. Рыбников К. А. Комбинаторный анализ. Очерки истории. -- М.: Изд. мехмата МГУ, 1996. -- 124 с.

6. Рыбников К. А. История математики в двух томах. -- М.: Издательство МГУ, 1960-1963.

Размещено на Allbest.ru