Комбинаторные объекты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Примеры комбинаторных объектов)
м (Примеры комбинаторных объектов)
Строка 6: Строка 6:
 
* '''Сочетания''' из ''n'' по ''k'' — это набор ''k'' элементов, выбранных из данных ''n'' элементов.
 
* '''Сочетания''' из ''n'' по ''k'' — это набор ''k'' элементов, выбранных из данных ''n'' элементов.
 
* '''Размещение''' из ''n'' по ''k'' — это упорядоченный набор из ''k'' различных элементов некоторого n-элементного множества.
 
* '''Размещение''' из ''n'' по ''k'' — это упорядоченный набор из ''k'' различных элементов некоторого n-элементного множества.
* '''Разбиение''' числа '''на слагаемые'''.
+
* '''Разбиение''' числа '''на слагаемые''' — это представление числа ''n'' в виде суммы слагаемых.
* '''Разбиение''' множества '''на подмножества''' такие, что в объединении они дают исходное множество, но при этом ни одно из них не пересекается с любым другим.
+
* '''Разбиение''' множества на '''подмножества''' называется представление множества, как объединения одного или более попарно не пересекающихся подмножеств.
  
 
== Подсчет числа комбинаторных объектов с помощью рекуррентных формул ==
 
== Подсчет числа комбинаторных объектов с помощью рекуррентных формул ==

Версия 22:44, 16 декабря 2013

Определение:
Комбинаторные объекты (combinatorial objects) — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.

Примеры комбинаторных объектов

  • Битовые вектора — последовательность нулей и единиц заданной длины.
  • Перестановки — это упорядоченный набор чисел [math]1, 2,\ldots, n,[/math] обычно трактуемый как биекция на множестве [math]\{ 1, 2,\ldots, n \}[/math], которая числу i ставит соответствие i-й элемент из набора.
  • Сочетания из n по k — это набор k элементов, выбранных из данных n элементов.
  • Размещение из n по k — это упорядоченный набор из k различных элементов некоторого n-элементного множества.
  • Разбиение числа на слагаемые — это представление числа n в виде суммы слагаемых.
  • Разбиение множества на подмножества называется представление множества, как объединения одного или более попарно не пересекающихся подмножеств.

Подсчет числа комбинаторных объектов с помощью рекуррентных формул

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

Количество разбиений числа на слагаемые

Количество разбиений числа на слагаемые удовлетворяют рекуррентному соотношению:

[math]A(0, t) = 0[/math], где t > 0,

[math]A(1, 1) = 1[/math],

[math]A(n, t) = A(n, t - 1) + A(n - t, t)[/math], где первый параметр - это число, которое мы разбиваем, а второй - это максимальное слагаемое в разбиении.

Количество неупорядоченных разбиений n-элементного множества на k непустых подмножеств.

Оно выражается числами Стирлинга второго рода, которые удовлетворяют следующему рекуррентному соотношению:

[math]S(n, n) = 1[/math], для n ≥ 0,

[math]S(n, 0) = 0[/math], для n > 0,

[math]S(n, k) = S(n - 1, k - 1) + k \cdot S(n - 1, k)[/math] для 0 < k < n.

Источники