Комбинаторные объекты — различия между версиями
YanaZimka (обсуждение | вклад) |
YanaZimka (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | |||
{{Определение | {{Определение | ||
|definition = '''Комбинаторные объекты''' ''(combinatorial objects)'' — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}} | |definition = '''Комбинаторные объекты''' ''(combinatorial objects)'' — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}} | ||
| + | |||
| + | {{Определение | ||
| + | |definition = '''Упорядоченным множеством''' называется множество, на элементах которого установлено отношение, обладающее следующими свойствами: | ||
| + | 1. Для любых двух элементов <tex>a</tex> и <tex>b</tex> данного множества существует только одно из следующих соотношений: | ||
| + | <tex>a < b, ~a > b, ~a = b</tex> | ||
| + | 2. Для любых трех элементов данного множества <tex>a, b, c</tex>: <tex>~(a < b</tex> & <tex>b < c) => a < c</tex> | ||
| + | }} | ||
| + | |||
== Примеры комбинаторных объектов == | == Примеры комбинаторных объектов == | ||
* '''Битовые вектора''' — последовательность нулей и единиц заданной длины. | * '''Битовые вектора''' — последовательность нулей и единиц заданной длины. | ||
| Строка 6: | Строка 15: | ||
* '''Сочетания''' из ''n'' по ''k'' — это набор ''k'' элементов, выбранных из данных ''n'' элементов. | * '''Сочетания''' из ''n'' по ''k'' — это набор ''k'' элементов, выбранных из данных ''n'' элементов. | ||
* '''Размещение''' из ''n'' по ''k'' — это упорядоченный набор из ''k'' различных элементов некоторого n-элементного множества. | * '''Размещение''' из ''n'' по ''k'' — это упорядоченный набор из ''k'' различных элементов некоторого n-элементного множества. | ||
| − | * '''Разбиение''' числа '''на слагаемые''' — это представление числа ''n'' в виде суммы слагаемых. | + | * '''Разбиение''' числа '''на неупорядоченные слагаемые''' — это представление числа ''n'' в виде суммы слагаемых. |
* '''Разбиение''' множества <math>X</math> на '''подмножества''' называется семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если: | * '''Разбиение''' множества <math>X</math> на '''подмножества''' называется семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если: | ||
# <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>; | # <math>U_{\alpha} \cap U_{\beta} = \emptyset</math> для любых <math>\alpha, \beta \in A</math>, таких что <math>\alpha \not= \beta</math>; | ||
| Строка 14: | Строка 23: | ||
Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с ''n'' предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится. | Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с ''n'' предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится. | ||
| − | '''Количество разбиений числа на слагаемые''' | + | '''Количество разбиений числа на неупорядоченные слагаемые''' |
Пусть <tex>n</tex> - число, которое мы разбиваем, а <tex>t</tex> - максимальное слагаемое в разбиении, тогда количество разбиений числа на слагаемые удовлетворяет рекуррентному соотношению: | Пусть <tex>n</tex> - число, которое мы разбиваем, а <tex>t</tex> - максимальное слагаемое в разбиении, тогда количество разбиений числа на слагаемые удовлетворяет рекуррентному соотношению: | ||
Версия 11:14, 4 января 2014
| Определение: |
| Комбинаторные объекты (combinatorial objects) — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п. |
| Определение: |
| Упорядоченным множеством называется множество, на элементах которого установлено отношение, обладающее следующими свойствами:
1. Для любых двух элементов и данного множества существует только одно из следующих соотношений: 2. Для любых трех элементов данного множества : & |
Примеры комбинаторных объектов
- Битовые вектора — последовательность нулей и единиц заданной длины.
- Перестановки — это упорядоченный набор чисел обычно трактуемый как биекция на множестве , которая числу i ставит соответствие i-й элемент из набора.
- Сочетания из n по k — это набор k элементов, выбранных из данных n элементов.
- Размещение из n по k — это упорядоченный набор из k различных элементов некоторого n-элементного множества.
- Разбиение числа на неупорядоченные слагаемые — это представление числа n в виде суммы слагаемых.
- Разбиение множества на подмножества называется семейство непустых множеств , где — некоторое множество индексов, если:
- для любых , таких что ;
- .
Подсчет числа комбинаторных объектов с помощью рекуррентных формул
Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится.
Количество разбиений числа на неупорядоченные слагаемые
Пусть - число, которое мы разбиваем, а - максимальное слагаемое в разбиении, тогда количество разбиений числа на слагаемые удовлетворяет рекуррентному соотношению:
, где ,
,
Количество неупорядоченных разбиений -элементного множества на непустых подмножеств.
