Сетевая библиотекаСетевая библиотека

kombinatorika

Дата публикации: 19.01.2016
Тип: Текстовые документы DOCX
Размер: 27 Кбайт
Идентификатор документа: -111831908_437213398
Файлы этого типа можно открыть с помощью программы:
Microsoft Word из пакета Microsoft Office
Для скачивания файла Вам необходимо подтвердить, что Вы не робот


Не то что нужно?


Вернуться к поиску


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

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

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

Пример: В классе 16 девочек и 11 мальчиков. Сколькими способами можно выбрать старосту класса?

Решение: Одну старосту из множества девочек можно выбрать 16 способами, а из множества мальчиков 11 способами. По правилу суммы число способов выбора старосты равно 16+11=27.

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

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

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

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

Рассмотрим некоторое множество Х, состоящее из n элементов X=x1,x2,…,xn.Будем выбирать из этого множества различные упорядоченные подмножества Y из k элементов.

Размещения.

Размещением из n элементов множества Х по k элементам назовем любой упорядоченный набор  элементов множества Х.

Если выбор элементов множества Y из Х происходит с возвращением, т.е. каждый элемент множества Х может быть выбран несколько раз, то число размещений из n по k находится по формуле Ank=nk (размещения с повторениями).

Если же выбор делается без возвращения, т.е. каждый элемент множества Х можно выбирать только один раз, то количество размещений из n по k обозначается  Ank и определяется равенством (размещения без повторений).

Пример. Пусть даны шесть цифр: 1; 2; 3; 4; 5; 6. Определить: сколько трехзначных чисел можно составить из этих цифр.

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

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

Частный случай размещения при n=k называется перестановкой из n элементов. Число всех перестановок из n элементов по n равно . (перестановки без повторений).

В тех случаях, когда среди образующих перестановки элементов имеются одинаковые, то получаются соединения, называемые перестановками с повторениями, которые вычисляются по формуле Pnn1,…,nk=n!n1!…nk!Пример. 30 книг стоит на книжной полке, из них 27 различных книг и одного автора три книги. Сколькими способами можно расставить эти книги на полке так, чтобы книги одного автора стояли рядом?

Решение. Будем считать три книги одного автора за одну книгу, тогда число перестановок будет . А три книги можно переставлять между собой  способами, тогда по правилу произведения имеем, что искомое число способов равно: *=3!*28!

Сочетания.

Пусть теперь из множества Х выбирается неупорядоченное подмножество Y (порядок элементов в подмножестве не имеет значения). Сочетаниями без повторений из n элементов по k называются подмножества из k элементов. Общее число всех сочетаний из n по k обозначается Cnk и равноCnk=Ankk!=n!(n-k)!k!.

k-элементные подмножества n-элементного множества, элементы которых могут повторяться, называют сочетаниями с повторениями из n по k и определяются формулой: Cnk=Cn+k-1k=(n+k-1)!k!(n-1)!.

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

Решение. Так как порядок студентов не важен, используем формулу для числа сочетаний: .