XII Международный конкурс научно-исследовательских и творческих работ учащихся
Старт в науке
ОСНОВНЫЕ ФОРМУЛЫ КОМБИНАТОРИКИ.
Автор работы награжден дипломом победителя III степени
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Введение
"Число, положение и комбинация -
три взаимно пересекающиеся, но
различные сферы мысли, к которым
можно отнести все математические
идеи".
Дж. Сильвестр (1844 г.)
Представителям самых различных специальностей приходится решать задачи, в которых рассматриваются те или иные комбинации, составленные из букв, цифр и иных объектов. Начальнику цеха надо распределить несколько видов работ между имеющимися станками, агроному – разместить посевы сельскохозяйственных культур га нескольких полях, заведующему учебной частью школы – составить расписание уроков и т. д. Область математики, в которой изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов, называется комбинаторикой.
Комбинаторика возникла в XVI веке. В жизни привилегированных слоев тогдашнего общества большое место занимали азартные игры. Широко были распространены всевозможные лотереи. Понятно, что первоначально комбинаторные задачи касались в основном азартных игр – сколькими способами можно выбросить данное число очков, бросая две или три кости, или сколькими способами можно получить двух королей в данной карточной игре. Эти и другие проблемы азартных игр явились движущей силой в развитии комбинаторики и развивавшейся одновременно с ней теории вероятностей.
Одним из первых занялся подсчетом числа различных комбинаций при игре в кости итальянский математик Тарталья. Он составил таблицу, показывавшую, сколькими способами могут выпасть r костей. Однако при этом не учитывалось, что одна и та же сумма очков может быть получена разными способами (например, 1+3+4=4+2+2)
За последние годы комбинаторика переживает период бурного развития, связанного с общим повышением интереса к проблемам дискретной математики. Комбинаторные методы используются для решения транспортных задач, в частности задач по составлению расписаний; для составления планов производства и реализации продукции. Установлены связи между комбинаторикой и задачами линейного программирования, статистики и т. д.
Очевидно, комбинаторика – обширная, масштабная, увлекательная тема, занимающая немалую роль, как и в дискретной математике, так и в повседневной жизни. И в данном проекте, мы коснёмся основных понятий и формулировок комбинаторики, а также рассмотрим несколько задач. Более того, постараемся прийти к одному умозаключению.
Основные формулы комбинаторики
На самом начальном этапе нужно изучить основные формулы комбинаторики: сочетания, размещения, перестановки и научиться их применять для решения задач.
Комбинаторика перестановки
«Сколькими способами можно переставить n объектов?»
Пусть имеется n различных объектов.
Будем переставлять их всеми возможными способами (число объектов остается неизменными, меняется только их порядок). Получившиеся комбинации называются перестановками, а их число равно
Pn=n!=1⋅2⋅3⋅...⋅(n−1)⋅n
Символ n! называется факториалом и обозначает произведение всех целых чисел от 1 до n
Пример всех перестановок из n=3 объектов (различных фигур) - на картинке справа. Согласно формуле, их должно быть ровно P3=3!=1⋅2⋅3=6так и получается.
С ростом числа объектов количество перестановок очень быстро растет и изображать их наглядно становится затруднительно.
Комбинаторика размещения
Пусть имеется n различных объектов.
Будем выбирать из них m объектов и переставлять всеми возможными способами между собой (то есть меняется и состав выбранных объектов, и их порядок). Получившиеся комбинации называются размещениями из n объектов по m, а их число равно
=n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)
Пример всех размещений из n=3 объектов (различных фигур) по m=2m=2 - на картинке справа. Согласно формуле, их должно быть ровно A23=3⋅(3−2+1)=3⋅2=6A32=3⋅(3−2+1)=3⋅2=6.
Комбинаторика сочетания
Пусть имеется n различных объектов.
Будем выбирать из них m объектов все возможными способами (то есть меняется состав выбранных объектов, но порядок не важен). Получившиеся комбинации называются сочетаниями из n объектов по m, а их число равно
=n!(n−m)!⋅m!
Пример всех сочетаний из n=3 объектов (различных фигур) по m=2 - на картинке справа. Согласно формуле, их должно быть ровно =3!(3−2)!⋅2!=3. Ясно, что сочетаний всегда меньше чем размещений (так как при размещениях порядок важен, а для сочетаний - нет), причем именно в m! раз, то есть верна формула связи:
=⋅Pm
Основные комбинаторные объекты и методы
На практике часто приходится выделять из некоторого множества объектов подмножества элементов, обладающих теми или иными свойствами, располагать элементы одного или нескольких множеств в определенном порядке т.д. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют комбинаторными задачами. Область математики, в которой изучают комбинаторные задачи, называют комбинаторикой. Комбинаторику можно рассматривать как часть теории множеств любую комбинаторную задачу можно свести к задаче конечных множествах и их отображениях.
Есть несколько основных типов комбинаторных задач:
- существование объекта с заданными свойствами;
- подсчет или оценка количества искомых комбинаций или их описание;
- поиск оптимальной комбинации по какому-то параметру.
Простейшие способы комбинаторных подсчетов. Правило суммы.
Комбинаторика тесно связана теорией конечных множеств: понятия подмножество, объединение множеств, пересечение множеств оказываются полезными при решении комбинаторных задач, т. к. количество комбинаций — это число элементов соответствующего множества.
Задачи по комбинаторике
Морской семафор
На флоте иногда применяют семафор флажками. Каждой букве при этом соответствует определенное положение флажков. Как правило, флажки находятся по разные стороны от тела сигнальчика. Однако при передаче некоторых букв (б, д, к, х, ю, я) оба флажка расположены по одну и ту же сторону. Почему пришлось сделать такое исключение? Ответ на этот вопрос дает та же формула размещений с повторениями. Дело в том, что различных положений каждого флажка пять- вниз отвесно, вниз наклонно, горизонтально, вверх наклонно и вверх отвесно. Так как у нас два флажка, то общее число комбинаций основных положений равно А — 5^2— 25. При этом еще надо отбросить положение, когда оба флажка направлены вниз — оно служит для разделения слов. Всего получаем 24 комбинации, а этого недостаточно для передачи всех букв русского алфавита. Поэтому для некоторых букв и пришлось направить оба флажка в одну сторону.
Генетический код
Замечательным открытием биологии XX века была разгадка генетического кода. Удалось выяснить, каким образом наследственная информация передается потомству. Оказалось, что эта информация записана в гигантских молекулах дезоксирибонуклеиновой кислоты (ДНК). Различные молекулы ДНК отличаются друг от друга тем, в каком порядке идут них 4 азотистых основания: аденин, тиамин, гуанин и цитозин. Эти основания определяют порядок построения белков организма из двух десятков аминокислот, причем каждая аминокислота зашифрована кодом из трех азотистых оснований. Легко понять, откуда взялось число 3. Ведь с помощью комбинаций двух оснований можно зашифровать лишь 4^2=16 аминокислот, а этого недостаточно. Если же брать по 3 основания, то получим 4^3=64 комбинации. А этого с избытком хватит, чтобы зашифровать два десятка. Было бы весьма интересно узнать, как используется в природе избыточность информации-ведь число комбинаций равно 64, а число аминокислот втрое меньше. В одной хромосоме содержится несколько десятков миллионов азотистых оснований. Число различных комбинаций, в которых они могут идти друг за другом, невообразимо велико). Ничтожной доли этих комбинаций достаточно было, чтобы обеспечить все разнообразие живой природы за время существования жизни на Земле. Разумеется, надо иметь в виду, что лишь ничтожная доля теоретически возможных комбинаций приводит к жизнеспособным организмам.
Заключение
Можно сделать выводы и сказать, что: человеку часто приходится иметь дело с задачами, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов или число всех возможных способов осуществления некоторого действия. И целый раздел математики, называемый комбинаторикой, может дать ответы на вопросы: сколько всего есть комбинаций в том или другом случае. Комбинаторика имеет огромное значение в различных областях науки и сферы. Усиление интереса к комбинаторике в последнее время обуславливается бурным развитием кибернетики.
Рассмотрев использование комбинаторики в различных сферах жизнедеятельности, как элементы комбинаторики, в частности сочетания, используются при решении различных жизненных ситуаций; мы показали практическую значимость комбинаторики как области математики. Таким образом, мы пришли к умозаключению: комбинаторика – это раздел математики, находящийся на магистральном пути развития науки и имеющий широкий спектр практической направленности.
Литература
Н.Я. Виленкин “Комбинаторика”, 1969
М. А. Иванов, Ю. В. Якубович “Введение в комбинаторику. Теория и задачи”. 2018