Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата

Доказано, что магический квадрат можно построить для любого n Є 3. Уже в средние века был известен алгоритм построения магических квадратов нечетного порядка. Существуют магические квадраты, удоволетворяющие ряду дополнительных условий, например магический квадрат с n=8 , который можно разделить на четыре меньших магических квадрата 4x4. В Индии и некоторых других странах магические квадраты употреблялись как талисманы. Однако общей теории магических квадратов не существует. Неизвестно даже общее число магических квадратов порядка n.
2. Латинский квадрат - квадратная матрица порядка n, каждая строка и каждый столбец которой являются перестановками элементов конечного множества S, состоящего из n элементов.
3. Задача размещения - одна из классических комбинаторных задач, в которой требуется определить число способов размещения m различных предметов в n различных ячейках с заданным числом r пустых ячеек. Это число равно r n-r m

C (r)=C дельта O , r=0,1,2,...,n, nm n где

k m k j j m дельта O =сигма (-1) C (k-j) j=0 k

4. Задача коммивояжера, задача о бродячем торговце – комбинаторная задача теории графов. В простейшем случае формулируется следующим образом: даны n городов и известно расстояние между каждыми двумя городами; коммивояжер, выходящий из какого-нибудь города, должен посетить n-1 других городов и вернуться в исходный. В каком порядке должен он посещать города (по одному разу каждый) чтобы общее пройденное расстояние было минимальным?

Методы решения задачи коммивояжера, по существу, сводятся к организации полного перебора вариантов.

МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ
1. Метод рекуррентных соотношений.

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

Пусть N(A) - число элементов множества A. Тогда методом математической индукции можно доказать, что
N(A1 U A2 U ... An) = N(A1) + ... + N(An) -
- {N(A1 П A2) + ... + N(An-1 П An)} +
+ {N(A1 П A2 П A3) + ... + N(An-2 П An-1 П An)} - ...
... +(-1)^n-1*N(A1 П A2 П ... П An-1 П An).

Метод подсчета числа элементов объединения множеств по этой формуле, состоящий в поочередном сложении и вычитании, называется методом включения и исключения.
3. Метод траекторий.

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

Основные формулы комбинаторики

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

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

Pn = n!,

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

Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.

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

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

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

С mn = n! / (m! (n - m)!).

примеры перестановок, размещений, сочетаний

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

Amn = PmC mn.

З а м е ч а н и е. Выше предполагалось, что все n элементов различны.
Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Например, если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида и т.д., то число перестановок с повторениями

Pn (n1, n2, ...) = n! / (n1! n2! ... ),

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





Предыдущая страница реферата | 1  2  3  4  5  6  7  8 | Следующая страница реферата