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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
  
 
{{Определение
 
{{Определение
|definition = '''Комбинаторные объекты''' ''(combinatorial objects)'' — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
+
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
  
 
{{Определение
 
{{Определение
Строка 8: Строка 8:
  
 
== Примеры комбинаторных объектов ==
 
== Примеры комбинаторных объектов ==
* '''Битовые вектора''' — последовательность нулей и единиц заданной длины.
+
=== Битовые вектора ===
* '''Перестановки''' &mdash; это упорядоченный набор чисел <tex>1, 2,\ldots, n,</tex> обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу ''i'' ставит соответствие ''i''-й элемент из набора.
+
'''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' &mdash; последовательность нулей и единиц заданной длины. Количество таких объектов вычисляется по формуле <tex>2^{n}</tex>, так как на каждое из <tex>n</tex> мест мы можем поставить один из двух элементов.
* '''Сочетания''' из ''n'' по ''k'' &mdash; это набор ''k'' элементов, выбранных из данных ''n'' элементов.
+
 
* '''Размещение''' из ''n'' по ''k'' &mdash; это упорядоченный набор из ''k'' различных элементов некоторого n-элементного множества.
+
=== Перестановки ===
* '''Разбиение''' числа '''на неупорядоченные слагаемые''' &mdash; это представление числа ''n'' в виде суммы слагаемых.
+
'''Перестановки<ref>[http://www.mathelp.spb.ru/book2/tv3.htm/]</ref>''' &mdash; это упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора. Количество перестановок равно <tex>P_n = n!</tex>. Получить эту формулу можно следующим образом: поставим один из <tex>n</tex> элементов на первое место, далее поставим на второе один из <tex>n - 1</tex> оставшихся элементов,... один из <tex>1</tex> элемента на последнее. Всего таких выборов можно совершить <tex>n \times (n - 1) \times ... \times 1 = n!</tex>.
 +
 
 +
=== Сочетания ===
 +
'''Сочетания<ref>[http://www.mathelp.spb.ru/book2/tv3.htm/]</ref>''' из <tex>n</tex> по <tex>k</tex> &mdash; это набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов. Количество таких наборов вычисляется по формуле <tex>C^{k}_n = \frac{n!}{k!(n - k)!}</tex>.  
 +
 
 +
=== Размещения ===
 +
* '''Размещение''' из <tex>n</tex> по <tex>k</tex> &mdash; это упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества.
 +
 
 +
=== Разбиение ===
 +
* '''Разбиение''' числа '''на неупорядоченные слагаемые''' &mdash; это представление числа <tex>n</tex> в виде суммы слагаемых.
 +
 
 +
=== Разбиение ===
 
* '''Разбиение''' множества <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>;
Строка 18: Строка 29:
  
 
== Подсчет числа комбинаторных объектов с помощью рекуррентных формул ==
 
== Подсчет числа комбинаторных объектов с помощью рекуррентных формул ==
Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с ''n'' предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится.
+
Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с <tex>n</tex> предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится.
  
 
'''Количество разбиений числа на неупорядоченные слагаемые'''
 
'''Количество разбиений числа на неупорядоченные слагаемые'''
Строка 34: Строка 45:
  
 
== Источники ==
 
== Источники ==
 +
<references/>
 
*[http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%B8%D0%BA%D0%B0 Википедия - Комбинаторика]
 
*[http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%B8%D0%BA%D0%B0 Википедия - Комбинаторика]
 
*[http://en.wikipedia.org/wiki/Combinatorics Wikipedia - Combinatorics]
 
*[http://en.wikipedia.org/wiki/Combinatorics Wikipedia - Combinatorics]

Версия 17:42, 11 декабря 2016


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


Определение:
Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются упорядоченными.


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

Битовые вектора

Битовые вектора — последовательность нулей и единиц заданной длины. Количество таких объектов вычисляется по формуле [math]2^{n}[/math], так как на каждое из [math]n[/math] мест мы можем поставить один из двух элементов.

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

Перестановки[1] — это упорядоченный набор чисел [math]1, 2,\ldots, n[/math], обычно трактуемый как биекция на множестве [math]\{ 1, 2,\ldots, n \}[/math], которая числу [math]i[/math] ставит соответствие [math]i[/math]-й элемент из набора. Количество перестановок равно [math]P_n = n![/math]. Получить эту формулу можно следующим образом: поставим один из [math]n[/math] элементов на первое место, далее поставим на второе один из [math]n - 1[/math] оставшихся элементов,... один из [math]1[/math] элемента на последнее. Всего таких выборов можно совершить [math]n \times (n - 1) \times ... \times 1 = n![/math].

Сочетания

Сочетания[2] из [math]n[/math] по [math]k[/math] — это набор [math]k[/math] элементов, выбранных из данных [math]n[/math] элементов. Количество таких наборов вычисляется по формуле [math]C^{k}_n = \frac{n!}{k!(n - k)!}[/math].

Размещения

  • Размещение из [math]n[/math] по [math]k[/math] — это упорядоченный набор из [math]k[/math] различных элементов некоторого [math]n[/math]-элементного множества.

Разбиение

  • Разбиение числа на неупорядоченные слагаемые — это представление числа [math]n[/math] в виде суммы слагаемых.

Разбиение

  • Разбиение множества [math]X[/math] на подмножества называется семейство непустых множеств [math]\{U_{\alpha}\},{\alpha \in A}[/math], где [math]A[/math] — некоторое множество индексов, если:
  1. [math]U_{\alpha} \cap U_{\beta} = \emptyset[/math] для любых [math]\alpha, \beta \in A[/math], таких что [math]\alpha \not= \beta[/math];
  2. [math]X = \bigcup\limits_{\alpha \in A} U_{\alpha}[/math].

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

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

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

Пусть [math]n[/math] - число, которое мы разбиваем, а [math]t[/math] - максимальное слагаемое в разбиении, тогда количество разбиений числа на слагаемые удовлетворяет рекуррентному соотношению:

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

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

[math]A(n, t) = A(n, t - 1) + A(n - t, t)[/math]

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

Источники