Основы комбинаторики

Размещено на http://www.allbest.ru/

ТЕМА: Комбинаторика

(реферативная работа)



ВВЕДЕНИЕ

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

Дж. Сильвестр

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

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

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

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

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

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

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

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

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

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

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



ОБЩИЕ ПРАВИЛА КОМБИНАТОРИКИ

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

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

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

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

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

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

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

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

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

Типы соединений:

· Перестановки

· Размещения

· Сочетания

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

· Без повторений

· С повторениями



ФАКТОРИАЛ ЧИСЛА

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

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

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

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

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

0! = 1

1! = 1

2! = 1 · 2 = 2

3! = 1 · 2 · 3 = 6

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

Свойство факториала:

(n + 1)! = (n + 1) · n!

Например:

(5 + 1)! = (5 + 1) · 5!

Действительно

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

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

ПЕРЕСТАНОВКИ

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

Формула:

Pn = 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?

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

А = 6 * 5 = 30.

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

СОЧЕТАНИЯ

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



Формула:

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

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

Задача.

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

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

C = 10! / (2! 8!) = 45.

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

РЕШЕНИЕ КОМБИНАТОРНЫХ ЗАДАЧ

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

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

* Сколькими способами…?

* Сколько вариантов…?

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

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

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

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

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



ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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



СПИСОК ЛИТЕРАТУРЫ

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

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

3. http://www.kolasc.net.ru/cdo/books/tv/page13.html

4. http://combinatoric.ru.gg/



ДОПОЛНИТЕЛЬНЫЕ ЗАДАЧИ

№1.

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

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

можно присоединить 63 положения второй шашки. Отсюда общее число различных положений двух шашек на доске: 64 х 63 = 4032.

Ответ: 4032различных положений.

№2.

В магазине "Все для чая'' есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?

Решение: Выберем чашку. В комплект к ней можно выбрать любое из трех блюдец. Поэтому есть 3 разных комплекта, содержащих выбранную чашку. Поскольку чашек всего 5, то число различных комплектов равно 5*3=15.

Ответ: Чашку с блюдцем можно купить 15 способами.

№3.

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

Решение: Пусть верхняя полоса флага - белая (Б). Тогда нижняя полоса может быть красной (К) или синей (С). Получили две комбинации - два варианта флага.

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

Пусть, наконец, верхняя полоса - синяя, тогда нижняя может быть белой или красной. Это ещё два варианта флага.

Всего получим 3 * 2 = 6 комбинаций - шесть вариантов флага.

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

Размещено на Allbest.ru