Элементы комбинаторики (220,00 руб.)

Стр.1

Стр.2

Стр.3

Стр.4

В.И. Седакова ЭЛЕМЕНТЫ КОМБИНАТОРИКИ УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ для студентов факультета математики и информатики, и начального образования СУРГУТ 2 0 0 9 1

Стр.1

УДК 511.178 (072) ББК 22.141я72 Э 456 Учебно-методическое пособие утверждено на заседании кафедры высшей математики и информатики «20» марта 2009 года, протокол № 7 Учебно-методическое пособие утверждено на заседании научно-методического совета факультета ДНИМО «26» марта 2009 года, протокол № 3 Рецензент: Толпекина Н.В., доцент СЕДАКОВА В.И. Э 456 Элементы комбинаторики. Учебно-методическое пособие для студентов факультета математики и информатики и начального образования. – Сургут: ООО «Четыре цвета», 2009. – 69 с. Комбинаторика является одним из разделов математики, играющих важную роль при решении некоторых современных проблем теории вероятностей, математической логики, теории чисел. В пособии изложены основные понятия и методы решения комбинаторных задач. Изложение материала построено на использовании теоретико-множественных понятий. Пособие рассчитано на студентов и преподавателей педагогических вузов, учащихся старших классов общеобразовательных учреждений. УДК 511.178 (072) ББК 22.141я72 © Седакова В.И., 2009 © ООО «Четыре Цвета», 2009 2

Стр.2

ПРЕДИСЛОВИЕ В последние годы в математические дисциплины включена новая содержательная линия (с условным названием «Анализ данных»), которая объединяет в себе разделы математики, изучающие случайные явления: теорию вероятности и математическую статистику, теорию игр, теорию случайных процессов и др. Эти разделы принято обозначать термином стохастика (от греч. stochastikos – умеющий угадывать, случайный). В основу новой содержательной линии включены вопросы описательной статистики (сбор, представление и элементарный анализ данных), комбинаторики (способы перебора и подсчета различных комбинаций из элементов выборки), теории вероятностей (статистическое и классическое определение вероятности, элементарные действия с событиями). Комбинаторика – один из разделов дискретной математики, который приобрел большое значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислительной технике, кибернетике. Элементы теории вероятностей, в частности, элементы комбинаторики на современном этапе являются составной частью всего курса математики, начиная с начальной школы. На современном этапе раздел комбинаторики включен в программу начальной школы, поэтому знание этого раздела математики необходимо студентам – будущим учителям учителей начальных классов, учителям математики и информатики. От увлеченности учителя элементами комбинаторики, от умения решать комбинаторные задачи зависит заинтересованность учеников этим материалом. Цель этого учебно-методического пособия – познакомить студентов, как будущих учителей с основными понятиями комбинаторики и методами решения комбинаторных задач. Изложение комбинаторики ведется на теоретико-множе-ственной основе, что отвечает современному подходу к этой области математики. Пособие предназначено учащимся средних общеобразовательных учреждений, студентам факультета математики и информатики, будущим учителям начальных классов, преподавателям вузов. Оно может быть полезно и лицам, занимающимся комбинаторными расчетами. 3

Стр.3

ВВЕДЕНИЕ На практике часто приходится выбирать из некоторого множества объектов подмножества элементов, обладающих теми или иными свойствами, располагать элементы одного или нескольких множеств в определенном порядке и т.д. Например, мастеру приходится распределять различные виды работ между рабочими, агроному – размещать сельскохозяйственные культуры на нескольких полях, офицеру – выбирать из солдат взвода наряд и т.д. Поскольку в таких задачах речь идет о тех или иных комбинациях объектов, их называют комбинаторными задачами. Область математики, в которой изучаются комбинаторные задачи, называют комбинаторикой. Комбинаторику можно рассматривать как часть теории множеств – любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях. Различают несколько уровней решения комбинаторных задач. Начальным уровнем является поиск хотя бы одного расположения объектов, обладающего заданными свойствами (например, отыскание такого расположения десяти точек на пяти отрезках, при котором на каждом отрезке лежит по четыре точки, или такого расположения восьми ферзей на шахматной доске, при котором они не бьют друг друга). Иногда удается доказать, что данная комбинаторная задача не имеет решения (например, нельзя расположить 10 шаров в 9 урнах так, чтобы в каждой урне было не более одного шара – хотя бы в одной из урн окажется не менее двух шаров). Если комбинаторная задача имеет несколько решений, то возникает вопрос о подсчете числа таких решений, об описании всех решений данной задачи. Наконец, часто бывает, что различные решения данной комбинаторной задачи отличаются друг от друга некоторыми параметрами. В этом случае возникает проблема поиска оптимального варианта решения такой задачи. В этом пособии мы рассмотрим лишь вопрос о подсчете числа решений комбинаторной задачи. Этот раздел комбинаторики, называемый теорией перечислений, тесно связан с теорией вероятностей. Во многих случаях при вычислении вероятности данного события надо найти общее число возможных вариантов и число благоприятных вариантов, а поиск числа вариантов делается на основе использования комбинаторных методов. 4

Стр.4