Реферат на тему комбинаторика

Обновлено: 04.07.2024

Функция "чтения" служит для ознакомления с работой. Разметка, таблицы и картинки документа могут отображаться неверно или не в полном объёме!

Реферат на тему:

средней школы №53

Глухов Михаил Александрович

г. Набережные Челны

2002 г.Содержание

Размещенияи сочетаниябез повторений______________________________

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

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.) французский автор А. Также посвящает сочетаниям и перестановкам целую главу.Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин "комбинаторика" стал употребляться после опубликования Лейбницем в 1665 г. работы "Рассуждение о комбинаторном искусстве", в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.

Общие правила комбинаторики, определение понятий множества и факториала. Содержание разделов комбинаторики - перечислительного, экстремального и вероятностного. Понятие о размещении, перестановке и сочетании элементов. Решение комбинаторных задач.

Рубрика	Математика
Вид	реферат
Язык	русский
Дата добавления	21.12.2016
Размер файла	16,8 K

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Государственное автономное профессиональное образовательное учреждение

"Тобольский медицинский колледж имени Володи Солдатова"

ОСНОВЫ КОМБИНАТОРИКИ

Введение
1. Общие правила комбинаторики
2. Факториал числа
3. Перестановки
4. Размещения
5. Сочетания
6. Решение комбинаторных задач
Заключение
Список литературы

Введение

Число, место и комбинация - три взаимно перекрещивающиеся, но отличные сферы мышления, к которым можно отнести все математические идеи. (Дж. Сильвестр)

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

Комбинаторика занимается различного рода соединениями, которые можно образовать из элементов некоторого конечного множества. Термин "комбинаторика" происходит от латинского combina - сочетать, соединять.

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

На уроке математике мне встретились комбинаторные задачи, которые в последствие заинтересовали меня, и я поставила перед собой цель: рассмотреть шире тему комбинаторика. В дальнейшем поставленная цель позволила мне определить тему реферативной работы.

Для выполнения поставленной цели необходимо решить следующие задачи:

1. Подобрать и изучить литературу по теме реферата.

2. Узнать правила комбинаторики.

3. Узнать виды комбинаторных соединений.

4. Узнать роль факториала числа в комбинаторики.

5. Научиться решать комбинаторные задачи.

1. Общие правила комбинаторики

Комбинаторные задачи бывают самых разных видов. Однако большинство задач решается с помощью двух основных правил -- правила суммы и правила произведения.

Правило суммы

Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор "либо А, либо В" можно осуществить (m+n) способами.

При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В. Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k) способов выбора, где k--число совпадений.

Правило произведения

Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А, В) в указанном порядке можно осуществить mn способами.

При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.

Комбинаторные соединения

Комбинаторные соединения - это такие комбинации из каких-либо элементов.

Существуют две схемы выбора элементов:

2. Факториал числа

Факториал числа - это произведение всех натуральных чисел до этого числа включительно.

Обозначается с восклицательным знаком в конце.

n! = 1 · 2 · 3 · 4 · … · (n-2) · (n-1) · n

Случай 0! определен и имеет значение 0!=1, соответствующее комбинаторной интерпретации комбинации нуля объектов, другими словами, есть единственная комбинация нуля элементов, а именно: пустое множество.

Ниже приведены значения факториалов от 0 до 10.

4! = 1 · 2 · 3 · 4 = 24

5! = 1 · 2 · 3 · 4 · 5 = 120

6! = 1 · 2 · 3 · 4 · 5 · 6 = 720

7! = 1 · 2 · 3 · 4 · 5 · 6 · 7 = 5040

8! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 = 40320

9! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 = 362880

10! = 1 · 2 · 3 · 4 · 5 · 6 · 7 · 8 · 9 · 10 = 3628800

6! = (1 · 2 · 3 · 4 · 5) · 6 = 720

А значение (1 · 2 · 3 · 4 · 5) = 5! = 120

3. Перестановки

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

Формула:

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

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

Перестановки с повторениями -- комбинаторные соединения, в которых среди образующих элементов имеются одинаковые. В таких соединениях участвуют несколько типов объектов, причём имеется некоторое количество объектов каждого типа. Поэтому в выборках встречаются одинаковые.

Задача

Сколькими способами можно разместить на странице 5 различных заметок?

Решение: т.к. имеются 5 заметок, и все они участвуют в выборе, то это перестановки. Применим формулу перестановок: Pn=n!, получаем, P5= 5! = 120.

Ответ: Существуют 120 способов разместить имеющиеся заметки.

комбинаторика множество факториал вероятностный

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

Формула:

A = n (n - 1)(n - 2) . (n - m + 1).

Размещения без повторений - комбинаторные соединения, составленные из n элементов по m. При этом два соединения считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

Размещения с повторениями - комбинаторные соединения, составленные из n элементов по m. При этом каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать.

Задача

Сколько можно составить сигналов из 6 флажков различного цвета, взятых по 2?

Решение: Искомое число сигналов

Ответ: можно составить 30 сигналов.

5. Сочетания

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

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

Сочетания с повторениями - комбинаторные соединения из n элементов по m, составленные из этих элементов без учета порядка с возможностью многократного повторения предметов.

Задача

Сколькими способами можно выбрать две детали из ящика, содержащего 10 деталей?

Решение: Искомое число способов

Ответ: 45 способами.

6. Решение комбинаторных задач

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

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

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

Нужно чётко определить тип соединений в задаче, а для этого надо, составив несколько различных комбинаций, проверить повторяются ли элементы, меняется ли их состав, важен ли порядок элементов.

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

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

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

В ходе проделанной работы я:

1. Узнал основные правила комбинаторики.

2. Узнал виды комбинаторных соединений.

3. Узнал роль факториала числа в комбинаторики.

4. Научился решать комбинаторные задачи.

Таким образом, я выполнил поставленную цель.

1. А.С. Чесноков, В.И. Жохов, Н.Я. Виленкин, С.И. Шварцбурд Математика 6 класс.

2. Ю.М. Колягин,Ю.В. Сидоров,М.В. Ткачева, Н.Е. Федорова, М.И. Шабунин Алгебра 11 класс.

Подобные документы

Определение понятий множества и факториала. Условия равности двух кортежей. Содержание основных разделов комбинаторики - перечислительного, экстремального и вероятностного. Сущность теории Рамсея. Сведения о размещении, перестановке и сочетании элементов.

реферат [509,5 K], добавлен 21.02.2012

Содержание правил суммы и произведения; их применение с целью решения комбинаторных задач. Виды комбинаторных соединений. Обозначение и свойства факториала. Формулы расчета всех возможных перестановок и размещений. Понятие и разновидности сочетаний.

реферат [22,1 K], добавлен 08.09.2014

Основные принципы и формулы классической комбинаторики. Использование методов комбинаторики в теории вероятностей. Формулы числа перестановок, сочетаний, размещений. Формула бинома Ньютона. Свойства биномиальных коэффициентов. Решение комбинаторных задач.

учебное пособие [659,6 K], добавлен 07.05.2012

Возникновение комбинаторики как раздела математики. Исследование на практических примерах особенностей чисел размещений с повторениями и без них. Анализ задач, решение которых опирается на правила комбинаторики и относящиеся к ней вычислительные формулы.

курсовая работа [175,3 K], добавлен 05.01.2018

дипломная работа [508,5 K], добавлен 26.01.2011

Знакомство с основными понятиями и формулами комбинаторики как науки. Методы решения комбинаторных задач. Размещение и сочетание элементов, правила их перестановки. Характеристики теории вероятности, ее классическое определение, свойства и теоремы.

презентация [1,3 M], добавлен 21.01.2014

Рассмотрение различных примеров комбинаторных задач в математике. Описание способов перебора возможных вариантов. Использование комбинаторного правила умножения. Составление дерева вариантов. Перестановки, сочетания, размещения как простейшие комбинации.

Реферат на тему:

средней школы №53

Глухов Михаил Александрович

г. Набережные Челны

Из истории комбинаторики_________________________________________	3
Правило суммы___________________________________________________	4
Примеры задач____________________________________________________	-
Правило произведения_____________________________________________	4
Примеры задач____________________________________________________	-
Пересекающиеся множества________________________________________	5
Примеры задач____________________________________________________	-
Круги Эйлера_____________________________________________________	-
Размещения без повторений________________________________________	6
Примеры задач____________________________________________________	-
Перестановки без повторений_______________________________________	7
Примеры задач____________________________________________________	-
Сочетания без повторений__________________________________________	8
Примеры задач____________________________________________________	-
Размещения и сочетания без повторений______________________________	9
Примеры задач____________________________________________________	-
Перестановки с повторениями_______________________________________	9
Примеры задач____________________________________________________	-
Задачи для самостоятельного решения________________________________	10
Список используемой литературы___________________________________	11

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

Комбинаторика занимается различного вида соединениями, которые можно образовать из элементов конечного множества. Некоторые элементы комбинаторики были известны в Индии еще во II в. до н. э. Нидийцы умели вычислять числа, которые сейчас называют "сочетания". В XII в. Бхаскара вычислял некоторые виды сочетаний и перестановок. Предполагают, что индийские ученые изучали соединения в связи с применением их в поэтике, науке о структуре стиха и поэтических произведениях. Например, в связи с подсчетом возможных сочетаний ударных (долгих) и безударных (кратких) слогов стопы из n слогов. Как научная дисциплина, комбинаторика сформировалась в XVII в. В книге "Теория и практика арифметики" (1656 г.) французский автор А. Также посвящает сочетаниям и перестановкам целую главу.
Б. Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. П. Ферма знал о связях математических квадратов и фигурных чисел с теорией соединений. Термин "комбинаторика" стал употребляться после опубликования Лейбницем в 1665 г. работы "Рассуждение о комбинаторном искусстве", в которой впервые дано научное обоснование теории сочетаний и перестановок. Изучением размещений впервые занимался Я. Бернулли во второй части своей книги "Ars conjectandi" (искусство предугадывания) в 1713 г. Современная символика сочетаний была предложена разными авторами учебных руководств только в XIX в.

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

Правило суммы

Если конечные множества не пересекаются, то число элементов X U Y равно сумме числа элементов множества X и числа элементов множества Y.

То есть, если на первой полке стоит X книг, а на второй Y, то выбрать книгу из первой или второй полки, можно X+Y способами.

Примеры задач

Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?

Решение: X=17, Y=13

По правилу суммы X U Y=17+13=30 тем.

Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи?

Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10=16 вариантов.

Правило произведения

Если элемент X можно выбрать k способами, а элемент Y-m способами то пару (X,Y) можно выбрать k*m способами.

То есть, если на первой полке стоит 5 книг, а на второй 10, то выбрать одну книгу с первой полки и одну со второй можно 5*10=50 способами.

Примеры задач

Переплетчик должен переплести 12 различных книг в красный, зеленый и коричневые переплеты. Сколькими способами он может это сделать?

Решение: Имеется 12 книг и 3 цвета, значит по правилу произведения возможно 12*3=36 вариантов переплета.

Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево?

Решение: В таких числах последняя цифра будет такая же, как и первая, а предпоследняя - как и вторая. Третья цифра будет любой. Это можно представить в виде XYZYX , где Y и Z -любые цифры, а X - не ноль. Значит по правилу произведения количество цифр одинаково читающихся как слева направо, так и справа налево равно 9*10*10=900 вариантов.

Пересекающиеся множества

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

Примеры задач

20 человекзнаютанглийскийи 10 - немецкий, изних 5 знаютианглийский, инемецкий. СколькоЧеловеквсего?

Ответ: 10+20-5=25 человек.

Также часто для наглядного решения задачи применяются круги Эйлера. Например:

Из 100 туристов, отправляющихся в заграничное путешествие, немецким языком владеют 30 человек, английским - 28, французским - 42. Английским и немецким одновременно владеют 8 человек, английским и французским - 10, немецким и французским - 5, всеми тремя языками - 3. Сколько туристов не владеют ни одним языком?

Решение: Выразим условие этой задачи графически. Обозначим кругом тех, кто знает английский, другим кругом - тех, кто знает французский, и третьим кругом - тех, кто знают немецкий.

Всеми тремя языками владеют три туриста, значит, в общей части кругов вписываем число 3. Английским и французским языком владеют 10 человек, а 3 из них владеют еще и немецким. Следовательно, только английским и французским владеют 10-3=7 человек.

Определим теперь, сколько человек владеют только одним из перечисленных языков. Немецкий знают 30 человек, но 5+3+2=10 из них владеют и другими языками, следовательно, только немецкий знают 20 человек. Аналогично получаем, что одним английским владеют 13 человек, а одним французским - 30 человек.

Размещения без повторений.

Сколько можно составить телефонных номеров из 6 цифр каждый, так чтобы все цифры были различны?

Это пример задачи на размещение без повторений. Размещаются здесь 10 цифр по 6. А варианты, при которых одинаковые цифры стоят в разном порядке считаются разными.

Если X-множество, состоящие из n элементов, m≤n, то размещением без повторений из n элементов множества X по m называется упорядоченное множество X, содержащее m элементов называется упорядоченное множество X, содержащее m элементов.

Количество всех размещений из n элементов по m обозначают

n! - n-факториал (factorial анг. сомножитель) произведение чисел натурального ряда от 1 до какого либо числа n

Значит, ответ на вышепоставленную задачу будет

Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец?

Решение : два юноши не могут одновременно пригласить одну и ту же девушку. И варианты, при которых одни и те же девушки танцуют с разными юношами считаются, разными, поэтому:

Возможно 360 вариантов.

Перестановки без повторений

В случае n=m (см. размещения без повторений) из n элементов по m называется перестановкой множества x.

Количество всех перестановок из n элементов обозначают P_n.

Действительно при n=m:

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

1) Найдем количество всех перестановок из этих цифр: P₆ =6!=720

2) 0 не может стоять впереди числа, поэтому от этого числа необходимо отнять количество перестановок, при котором 0 стоит впереди. А это P₅ =5!=120.

Да косолапый Мишка

Затеяли играть квартет

Стой, братцы стой! –

Кричит Мартышка, - погодите!

Как музыке идти?

Ведь вы не так сидите…

И так, и этак пересаживались – опять музыка на лад не идет.

Тут пуще прежнего пошли у низ раздоры

Кому и как сидеть…

Вероятно, крыловские музыканты так и не перепробовали всех возможных мест. Однако способов не так уж и много. Сколько?

Здесь идет перестановка из четырех, значит, возможно

P₄ =4!=24 варианта перестановок.

Сочетания без повторений

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

Всякое подмножество X состоящее из m элементов, называется сочетанием из n элементов по m.

Таким образом, количество вариантов при сочетании будет меньше количества размещений.

Число сочетаний из n элементов по m обозначается .

Примеры задач

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

Так как кнопки нажимаются одновременно, то выбор этих трех кнопок – сочетание. Отсюда возможно вариантов.

У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги.

Так как надо порядок следования книг не имеет значения, то выбор 2_ух книг - сочетание. Первый человек может выбрать 2 книги способами. Второй человек может выбрать 2 книги . Значит всего по правилу произведения возможно 21*36=756 вариантов.

При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?

Часто в задачах по комбинаторике встречаются множества, в которых какие-либо компоненты повторяются. Например: в задачах на числа – цифры. Для таких задач при размещениях используется формула , а для сочетаний .

Примеры задач

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

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

В кондитерском магазине продавались 4 сорта пироженных: эклеры, песочные, наполеоны и слоеные. Сколькими способами можно купить 7 пироженных.

Решение : Покупка не зависит от того, в каком порядке укладывают купленные пироженные в коробку. Покупки будут различными, если они отличаются количеством купленных пирожных хотя бы одного сорта. Следовательно, количество различных покупок равно числу сочетаний четырех видов пироженных по семь - .

Решение : порядок букв имеет значение. Буквы могут повторяться. Значит, всего есть вариантов.

Перестановки с повторениями

, где n-количество всех элементов, n₁ ,n₂ ,…,n_r -количество одинаковых элементов.

Примеры задач

Задачи для самостоятельного решения

Имеется пять различных стульев и семь рулонов обивочной ткани различных цветов. Сколькими способами можно осуществить обивку стульев.

Сколькими способами можно расставить на шахматной доске 8 ладей так, чтобы на одна из них не могла бить другую?

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

Ответ: .

В течении 30 дней сентября было 12 дождливых дней, 8 ветреных, 4 холодных, 5 дождливых и ветреных, 3 дождливых и холодных, а один день был и дождливым, и ветреным, и холодным. В течение скольких дней в сентябре стояла хорошая погода.

На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?

Сколько существует четных пятизначных чисел, начинающихся нечетной цифрой?

Ответ:: 2985
Список используемой литературы

Комбинаторика-ветвь математики, изучающая комбинации и перестановки предметов, - возникла в XVII в. Долгое время казалось, что комбинаторика лежит вне основного русла развития математики и ее приложений. Положение дел резко изменилось после появления быстродействующих вычислительных машин и связанного с этим расцвета конечной математики. Сейчас комбинаторные методы применяются в теории случайных процессов, статистике, математическом программировании, вычислительной математике, планировании экспериментов и т.д. В математике комбинаторика используется при изучении конечных геометрий, комбинаторной геометрии, теории представлений групп, неассоциативных алгебр и т.д.

Содержание работы

Файлы: 1 файл

реферат по комбинаторике6.docx

История комбинаторики…………………………………………… ……..4
Разделы комбинаторики ….…………………………………..…….…. 7
Основные понятия……………………………………………………….. ..8
Машинное представление графов………………………………………..13
Поиск в глубину в графе………………………………………………….17
Поиск в ширину в графе………………………………………………….20
Заключение…………………………………………………… …………..23
Список использованной литературы…………. . 24

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

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

История комбинаторики освещает развитие комбинаторики — раздела конечной математики, который исследует в основном различные способы выборки заданного числа m элементов из заданного конечного множества: размещения, сочетания, перестановки, а также перечисление и смежные проблемы. Начав с анализа головоломок и азартных игр, комбинаторика оказалась исключительно полезной для решения практических задач почти во всех разделах математики. Кроме того, комбинаторные методы оказались полезными в статистике, генетике, лингвистике и многих других науках.

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

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

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

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

Новое время

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

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

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

Задача о ходе коня

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

Построение греко-латинских квадратов

Кроме перестановок и сочетаний, Эйлер изучал разбиения, а также сочетания и размещения с условиями.

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

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

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

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

Типичным примером задач данного раздела является подсчёт количества перестановок. Другой пример — известная Задача о письмах.

К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.

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

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

в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы.

В терминах структурной комбинаторики это же утверждение формулируется так:

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.

Этот раздел отвечает на вопросы вида: какова вероятность присутствия определённого свойства у заданного множества.

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

3. Основные понятия комбинаторики

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

Начнем с логических и теоретико-множественных понятий. Мы будем употреблять логические связки , , , , . Тот факт, что есть элемент множества , будем записывать в виде , его отрицание — в виде . Множество тех элементов множества , которые удовлетворяют условию , будем обозначать через (или , если известно, о каком множестве идет речь), запись же будет обозначать множество, элементы которого суть (в частности, единственным элементом множества является ). Теоретико-множественные операции объединения, пересечения и разности обозначаются соответственно пустое множество обозначается . Тот факт, что множество содержится в множестве (т.е. есть подмножество множества ), будет записываться в виде или (всегда имеют место включения ); символ зарезервирован для случая, когда исключается равенство (при этом будем говорить, что есть собственное подмножество множества ). Множество всех подмножеств множества будем обозначать через , мощность множества (т.е. число его элементов) — через .

С комбинаторными задачами приходится встречаться в самых разных областях знаний и деятельности человека. Это: информатика, математика, физика, биология. лингвистика и др.: Много комбинаторных задач используется при организации и приведения досуга: фокусы, шарады, лотереи и др. Игра в шахматы, шашки, нарды, карты и др. связаны с комбинаторикой.
Люди с глубокой древности интересовались комбинаторными задачами. Так, в пирамиде Тутанхамона, построенной более, чем 35 веков назад обнаружена доска с тремя горизонтальными и десятью вертикалями линиями для игры в “сенет”, прототип игры в шахматы и шашки. Правила в эту игру, к сожалению, обнаружить до сих пор не удалось.

Вложенные файлы: 1 файл

Документ Microsoft Office Word.docx

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

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

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

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

Люди с глубокой древности интересовались комбинаторными задачами. Так, в пирамиде Тутанхамона, построенной более, чем 35 веков назад обнаружена доска с тремя горизонтальными и десятью вертикалями линиями для игры в “сенет”, прототип игры в шахматы и шашки. Правила в эту игру, к сожалению, обнаружить до сих пор не удалось.

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

1 Правило суммы и произведения.

Пусть множество A содержит m элементов, n(A)=m, множество B содержит k элементов, n(B)=k объединяются в новое множество. Возникает вопрос о числе элементов в объединении этих множеств, n(A∪B). Имеются две возможности:

1. Данные множества не имеют общих элементов. Они не пересекаются, n(A∩B).=0. Поэтому n n(A∪B).= n(A) + n(B)= m + k. Формула справедлива для любого числа множеств.

2. Данные два множества имеют d общих элементов, n(A∩B).=d . Они пересекаются, n(A∩B).=0. Поэтому n(A∪B).= n(A) + n(B) – n(A∩B)= m + k.- d

Если учувствуют в объединении три множества: n(A)=m , n(B)=k, n(C)=s, n(A∩B).=d₁, n(B∩C).=d₂, n(A∩C).=d₃, n(A∩B∩C)=g, то формула имеет вид:

n(A∪B∪C).= n(A) + n(B)+ n(C)- n(A∩B)- n(A∩C)- n(A∩C)+n(A∩B∩C) или

Правила суммы и произведения можно иллюстрировать помощь кругов.

Пусть множество A содержит m элементов, n(A)=m, множество B содержит k элементов, n(B)=k из элементов которых необходимо записать множество W, состоящее из пар, первый элемент которых принадлежит множеству A, второй – множеству B. При этом справедлива формула: n(W)=n(AxB)=n(A)·n(B)=m·k. Множества W yназывается декартовым произведение множеств A и B. Формула справедлива для любого числа множеств, в том числе при умножении множества само на себя.

2 Размещения, перестановки, и сочетания без повторений.

Перестановки, размещения и сочетания считаются основными задачами (операциями) комбинаторики, которые подразделяются на два раздела: “без повторений“, когда элементы множества используются единожды и “с повторениями“, когда элементы множества могут использоваться не однократно. Операции перестановки и размещения в результате их выполнения дают упорядоченных подмножеств. Множества, в которых установлен порядок следования называются кортежами. Длина кортежа – есть число элементов в нем. Сочетания дают не упорядоченное множество.

Размещения без повторения.

Пусть дано множество, содержащее n элементов.

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

=n(n-1)(n-2) …(n-m+1) – число размещений без повторения

Перестановки без повторений

Перестановкой из n элементов называется любая комбинация (кортеж) из n элементов, отличающаяся от других только порядком следования. Под перестановкой понимается любое упорядоченное множество, составленное из n элементов данного множества. Обозначается P(n), P_n

Р= n(n-1)(n-2) …3·2·1 – число перестановок без повторения

Произведение n последовательных натуральных чисел называется факториалом и обозначается Р!, 5!, 10!

Сочетания без повторений

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

– число сочетаний без повторения

- другая формула, которая легко получается из предыдущей формулы.

При вычислении сочетаний легко усмотреть свойства, которое упрощает вычисления:

3. Размещения, перестановки, сочетания с повторениями.

Примеры ситуаций, приводящих к рассмотрению комбинаторных задач с повторениями:

1. У продавца цветов имеется гвоздики: 10 – красных, 15 белых, 20 оранжевых. Необходимо составить букеты по 5 гвоздик каждый, в которых должны присутствовать гвоздики разного цвета. Сколькими способами можно это сделать.

2. В компьютерах вся информация шифруется с помощью двух знаков: 0 и 1 кортежами, в которых 8, 16, 32 знака . Естественно нули и единицы повторяются.

3. Из десяти цифр можно составить число, содержащее сколь угодно знаков.

Размещения, с повторениями

Размещением из n элементов по k с повторениями – кортежи, содержащая m элементов, взятых из данного множества, отличающихся либо элементами, либо их порядком следования, причем элементы в комбинациях могут повторяться от 1 до m раз.

Дано множество X=. составить все размещения из этого четыре элементного множества по два с повторениями. Эта записывается в виде: Ā _n k .

Запишем некоторые кортежи длины 2. (a; a ), (a; b). (a; c), (a; d), (b; b) …Всего таковых кортежей = 4·4=16. С другой стороны это есть численность декартового произведения =т(АхА)= 4·4=16

Запишем некоторые кортежи длины 3. (a; a; a), (a; a; b) …. Всего таковых кортежей = 4·4·4=64

Общая задача. Найти число кортежей дины k, которые можно составить из элементов множества, содержащего n элементов.

– число размещений с повторения из n элементов по k

Перестановки с повторениями

Необходимо составить шеренгу из 20 физкультурников, среди которых 10 имеют белые майки, 4- синие, 6 – красные. Сколькими способами это можно сделать? Если бы цвета не повторялись, то это можно сделать P(20)=20!. В виду того, что цвета будут повторяться, то перестановок с повторениями будет меньше в 10!·41·61· раз.

Общая задача. Имеются элементы k видов. Причем k₁ вида n₁ штук, k₂ вида n₂штук и т.д. Сколько перестановок можно сделать из этих элементов?

, где n = n₁+n₂+…=n – сумма всех элементов.

Сочетания с повторениями

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

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

Ситуации такого характера приводят к сочетаниям с повторениями, Обозначается.

Общая задача. Требуется составить k наборов (кортежей) из элементов данных n множеств d₁. d₂, d₃,…d_n. Число элементов в каждом из множеств d_i не меньше числа k.

Формула вычисления числа сочетаний с повторениями имеет несколько разновидностей:

=. = . =P(n-1;k). . Наиболее предпочтительнее первая формула, сведенная к вычислению сочетаний без повторения.

4. Примеры комбинаторных задач из различных областей знаний.Комбинаторика в древней Греции. Комбинаторика в биологии, генетике, химии и др.

В древне Греции философы, служители религии, астрологи, гадалки много внимания уделяли науке нумерологии – науке о числах. Они устанавливали различные закономерности числе, изучали влияние чисел и их комбинаций на человека, природу, мироздание.

Модель строения ДНК была расшифрована методами комбинаторики в 1953 году в Кембридже Ф.Криком и Дж. Уотсоном. Ими была изготовлена спиральная модель ДНК после рассмотрения различных комбинаций связи нуклеотидов, аминокислот и других объектов между собой. При этом был открыт генетический код, который содержит информацию о виде растения или животного, в том числе наследственную и иную информацию.

Без комбинаторных задач не было бы информатики, компьютера, сотового телефона. Например, установления кодов в ЭВМ для записи информации, такими, что бы они ни были избыточными и были достаточными для записи любой информации. Соединение элементов в ЭВМ, установление связей в кристалле, и микросхеме рассчитывается с помощью комбинаторных задач.

С точки зрения теории множеств, комбинаторика изучает подмножества конечных множеств, и операции над ними.

Приведем несколько общих таковых задач:

1.Найти конфигурацию элементов, обладающих заранее заданными свойствами.

2. Доказать существование или отсутствие конфигурации с заданным свойством.

3. Найти число конфигураций с заданным свойством

4. Описать все способы решения указанных выше задач.

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

К перечисленным задачам подходят такие ситуации как:

1.Соеденить некоторое число точек на плоскости не пересекающими (пересекающими в одной, двух и более точках) линиями.

2. Транспортные задачи, связанные перевозками.

3. Задачи массового обслуживания

4.Определить число выпускаемых лотерейных биолитов, что бы были заинтересованы покупатели и авторы лотереи..

Практические замятия. Решение комбинаторных задач

Требования к знаниям умениям и навыкам Студент должен знать: основные комбинаторные объекты (типы выборок); формулы и правила количества выборок (для каждого из типов выборок) уметь: определять тип комбинаторного объекта (тип выборки); рассчитывать количество выборок заданного типа в заданных условиях.

При решении задач комбинаторики используют следующие правила:

Правило суммы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами.

Правило произведения. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана m*n способами.

Пример. Наряд студентки состоит из блузки, юбки и туфель. Девушка имеет в своем гардеробе четыре блузки, пять юбок и трое туфель. Сколько нарядов может иметь студентка?

Решение. Пусть сначала студентка выбирает блузку. Этот выбор может быть совершен четырьмя способами, так как студентка имеет четыре блузки, затем пятью способами произойдет выбор юбки и тремя способами выбор туфель. По принципу умножения получается 4*5*3=60 нарядов (комбинаций).

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

Типичным примером задач данного раздела является подсчёт количества перестаново к. Другой пример — известная Задача о письмах.

К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов.

Основная статья: Теория Рамсея

В терминах структурной комбинаторики это же утверждение формулируется так:

в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.

Читайте также:

Реферат на тему комбинаторика

Похожие работы

Введение

1. Общие правила комбинаторики

2. Факториал числа

3. Перестановки

5. Сочетания

6. Решение комбинаторных задач

Подобные документы

Содержание работы

Файлы: 1 файл

реферат по комбинаторике6.docx

Вложенные файлы: 1 файл

Документ Microsoft Office Word.docx