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

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

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

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

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

                                                         Гуcев Дмитрий

                                     Руководитель: Вырышевa

                                                                            Нaтaлья Мaтвеевнa

Содержание

Введение

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

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

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

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

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

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

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

Задачи исследования: 

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

Глава I.

1. Исторические сведения о комбинаторике.

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

Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается в древней Индии (начиная примерно с IV века до н. э.). Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, до нас не дошло.

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

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

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

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

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

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

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

2. Современные подходы к исследованию проблемы

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

3. Актуальность изучения комбинаторики 

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

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

Глава 2.

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

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

Задача 1

22 ученика подарили друг другу «валентинки». Сколько всего понадобилось «валентинок»?

Решать задачу будем графически, изобразим ребят кружочками, а а «валентинки» стрелочками

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

То есть каждый ученик дарит и получает 21 «валентинку». Учеников у нас 22, стрелочек-«валентинок»

22*21=462

Потребуется 462 «валентинки»!

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

Задача 2

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

Сделаем рисунок:

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

22*21:2=231

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

 Задача 3

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

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

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

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

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

Задача 4

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

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

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

Pn = n!,

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

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

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

Задача 5

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

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

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

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

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

Задача 6

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

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

а внутри каждой тройки сообщения можно распределить (число перестановок из 3 элементов)

3!=6 способами

значит:

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 школьных лет!

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

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

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

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

1. Виленкин, Н.Я. Комбинаторика / Н.Я. Виленкин. М.: Наука. Гл. ред. физ.-мат. лит., 1969.— 323 с.
2. Липский, В. Комбинаторика для программистов / В. Липский. – М.: мир, 1998. – 200 с.
3. Райгородский, А. М. Линейно-алгебраические и вероятностные методы в комбинаторике / А. М. Райгородский. — Летняя школа «Современная математика». — Дубна, 2006.
4. http://combinatorica.narod.ru/
5. http://www.smekalka.pp.ru/math_combination.html