Решение простейших комбинаторных задач.
учитель математики
МОУ «СОШ №5»
Мутигулина Г.Р.
В повседневной жизни нередко перед нами возникают проблемы, которые имеют не одно, а несколько различных вариантов решения. Чтобы сделать правильный выбор, очень важно не уступить ни одной из них. Для этого нужно осуществлять перебор всех возможных вариантов или хотя бы подсчитать их число.
Задачи, в которых идет речь о тех или иных комбинациях объектов, называются комбинаторными. Область математики, в которой изучаются комбинаторные задачи, называется комбинаторикой.
За последние годы комбинаторика переживает период бурного развития, связанного с общим повышением интереса к проблемам дискретной математики. Комбинаторные методы используются для решения транспортных задач, в частности задач по составлению расписаний; для составления планов производства и реализации продукции. Установлены связи между комбинаторикой и задачами линейного программирования.
В математике и ее приложениях часто приходится иметь дело с различного рода множествами и подмножествами: устанавливать их связь между элементами каждого, определять число множеств или их подмножеств, обладающих заданным свойством. Такие задачи приходится рассматривать при определении наиболее выгодных коммуникаций внутри города, при организации автоматической телефонной связи, работы морских портов, при выявлении связей внутри сложных молекул, генетического кода, а также в лингвистике, в автоматической системе управления, значит, и в теории вероятностей, и в математической статистике со всеми их многочисленными приложениями.
Один из разделов теории вероятностей – комбинаторика.
Комбинаторика – ветвь математики, изучающая комбинации и перестановки предметов. Еще комбинаторику можно понимать как перебор возможных вариантов. Комбинаторика возникла в XII веке. Долгое время она лежала вне основного русла развития математики.
Задачи, в которых идет речь о тех или иных комбинациях объектов, называются комбинаторными. Область математики, в которой изучаются комбинаторные задачи, называется комбинаторикой .
Раздел комбинаторики, в котором рассматривается лишь вопрос о подсчете числа решений комбинаторной задачи, называется теорией перечислений. Он тесно связан с теорией вероятностей. Во многих случаях при вычислении вероятности данного события надо найти число возможных вариантов и число благоприятных вариантов. Число вариантов отыскивается комбинаторными методами .
С задачами, в которых приходилось выбирать те или иные предметы, располагать их в определенном порядке и отыскивать среди разных расположений наилучшие, люди столкнулись еще в доисторическую эпоху, выбирая наилучшее положение охотников во время охоты, воинов – во время битвы, инструментов – во время работы.
Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда наряду с состязаниями в беге, метании диска, прыжках появились игры, требовавшие, в первую очередь, умения рассчитывать, составлять планы и опровергать планы противника.
Со временем появились различные игры (нарды, карты, шашки, шахматы и т.д.). В каждой из этих игр приходилось рассматривать различные сочетания фигур, и выигрывал тот, кто их лучше изучил, знал выигрышные комбинации и умел избегать проигрышных. Не только азартные игры давали пищу для комбинаторных размышлений математиков. Еще с давних пор дипломаты, стремясь к тайне переписки, изобретали сложные шифры, а секретные службы других государств пытались эти шифры разгадать. Стали применять шифры, основанные на комбинаторных принципах, например, на различных перестановках букв, заменах букв с использованием ключевых слов и т.д.
Комбинаторика как наука стала развиваться в XIII веке параллельно с возникновением теории вероятностей, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов. Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардано, Н.Тарталье (1499-1557), Г.Галилею (1564-1642) и французским ученым Б.Паскалю (1623-1662) и П.Ферма.
Комбинаторику как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666 году. Он также впервые ввел термин «комбинаторика». Значительный вклад в развитие комбинаторики внес Л.Эйлер. В современном обществе с развитием вычислительной техники комбинаторика «добилась» новых успехов. В настоящее время в образовательный стандарт по математике включены основы комбинаторики, решение комбинаторных задач методом перебора, составлением дерева вариантов (еще его называют «дерево возможностей») с применением правила умножения.
Возрастает роль комбинаторных задач уже в начальном обучении математике, так как в них заложены большие возможности не только для развития мышления учащихся, но и для подготовки учащихся к решению проблем, возникающих в повседневной жизни .
Рассмотрим исходные понятия, лежащие в основе решения комбинаторных задач и решения простейших комбинаторных задач.
Комбинаторика – раздел математики, в котором исследуются и решаются задачи выбора элементов из исходного множества и расположений их в некоторой комбинации, составляемых по некоторым законам.
Если из множества n элементов, каким либо способом выбрано k элементов, k ≤ n, то говорят, из множества произведена выборка объема k.
Например. а,b,с –элементы.
Выборка: по2: ав,ас, ва,вс, са,св.
по3: авс,асв, вас,вса, сав,сва.
Размещениями из m элементов по n называют такие выборки, из которых каждая содержит n элементов, взятых из данных m, и которые отличаются друг от друга либо составом, либо порядком.
Когда важен и состав и порядок – это размещение.
Задача. В классе 10 разных предметов и 5 уроков в день. Сколькими способами можно составить расписание на один день?
Ответ: 30240 способами.
Задача. Сколькими способами можно распределить два билета на разные кинофильмы между семью друзьями?
Ответ: 42 способами.
Размещения из n элементов по n элементам – перестановки из n элементов.
Отличаются только составом.
Например.
Дано: a,b,c,d – элементы.
abcd cabd abdc
acbd cbad adbc
adcb cdab acbd
acdb cdba badc
bacd dabc bcda
bcad dbac cadb
bdac dcab cbda
bdca dcba dacb
Задача. Сколькими способами можно рассадить 12 человек за столом, на котором 12 приборов.
Ответ: 479001600 способами.
Задача. Сколькими способами один почтальон может разнести 10 писем по десяти адресам.
Ответ: 3628800 способами.
Сочетанием из m элементов по n элементам называют такие выборки, каждая из которых содержит n элементов, взятых из m, которые отличаются друг от друга только составом.
Для сочетания важен состав, порядок не важен.
Задача. Из десяти кандидатов на одну и ту же должность должно быть выбрано трое. Сколькими способами можно сделать?
Ответ: 120 способами.
Задача. Десять видов открыток. Сколькими способами из них можно купить 8 открыток?
Ответ: 45 способами.
Задача. Сколькими способами можно выбрать трех дежурных из группы в 20 человек?
Ответ: 60 способами.
|
