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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
(не показаны 24 промежуточные версии 7 участников)
Строка 1: Строка 1:
−
== Определение ==
 
−
'''Комбинаторные объекты''' — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.
 
  
−
== Примеры комбинаторных объектов ==
+
{{Определение
−
1) '''Битовые вектора''' — последовательность нулей и единиц заданной длины.
+
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
  
−
2) '''Перестановки''' &mdash; это упорядоченный набор чисел <tex>1, 2,\ldots, n,</tex> обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу ''i'' ставит соответствие ''i''-й элемент из набора.
+
{{Определение
 +
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными''' (англ. ''ordered'').
 +
}}
  
−
3) '''Сочетания''' из ''n'' по ''k'' &mdash; это набор ''k'' элементов, выбранных из данных ''n'' элементов.
+
== Примеры комбинаторных объектов ==
−
 
+
=== Битовые вектора ===
−
4) '''Размещение''' из ''n'' по ''k'' &mdash; это упорядоченный набор из ''k'' различных элементов некоторого n-элементного множества.
+
{{Определение
−
 
+
|definition='''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' (англ. ''bit vectors'') &mdash; последовательность нулей и единиц заданной длины.
−
5) '''Разбиение''' числа '''на слагаемые'''.
+
}}
−
 
 
−
6) Все возможные подмножества заданного множества.
 
  
−
7) '''Разбиение''' множества '''на подмножества''' такие, что в объединении они дают исходное множество, но при этом ни одно из них не пересекается с любым другим.
+
=== Перестановки ===
 +
{{Определение
 +
|definition='''Перестановки<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0 Википедия — Перестановки]</ref>''' (англ. ''permutations'') &mdash; упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора.
 +
}}
 +
Примером перестановки может служить задача о рассадке <tex>n</tex> человек за стол по <tex>n</tex> местам.
  
−
== Подсчет числа комбинаторных объектов с помощью рекуррентных формул ==
+
=== Перестановки с повторениями ===
−
Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с ''n'' предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится.
+
{{Определение
 +
|definition='''Перестановки с повторениями''' (англ. ''permutations with repetitions'') — те же перестановки, однако некоторые элементы могут встречаться несколько раз.
 +
}}
 +
В пример можно привести следующую задачу: имеется набор книг <tex>\{a_1, a_2, \ldots, a_n\}</tex>, каждая из которых имеется в <tex>k_1, k_2, \ldots, k_n</tex> экземплярах соответственно. Сколько существует способов переставить книги на полке?
  
−
'''Количество разбиений числа на слагаемые'''
+
=== Размещения ===
 +
{{Определение
 +
|definition='''Размещение'''<ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5 Википедия — Размещения]</ref> (англ. ''arrangement'') из <tex>n</tex> по <tex>k</tex> &mdash; упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества.
 +
}}
 +
Примером размещения может служить задача о рассадке <tex>k</tex> человек за стол по <tex>n</tex> местам, где <tex>n > k</tex>.
  
−
Количество разбиений числа на слагаемые удовлетворяют рекуррентному соотношению:
+
=== Размещения с повторениями ===
 +
{{Определение
 +
|definition='''Размещение с повторениями''' (англ. ''arrangement with repetitions''), составленное из данных <tex>n</tex> элементов по <tex>k</tex> — отображение множества <tex>k</tex> первых натуральных чисел <tex>1, 2, \ldots, k</tex> в данное множество <tex>\{a_1, a_2, \ldots, a_n\}</tex>.
 +
}}
 +
В пример можно привести следующую задачу: имеется <tex>n</tex> книг, каждая в <tex>k</tex> экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?
  
−
<tex>A(0, t) = 0</tex>, где ''t'' > 0,
+
=== Сочетания ===
 +
{{Определение
 +
|definition='''Сочетания<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия — Сочетания]</ref>''' (англ. ''combinations'') из <tex>n</tex> по <tex>k</tex> &mdash; набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов.
 +
}}
 +
Примером сочетания может служить задача о выборе <tex>k</tex> книг из <tex>n</tex> вариантов.
  
−
<tex>A(1, 1) = 1</tex>,
+
=== Сочетания с повторениями ===
 +
{{Определение
 +
|definition='''Сочетания с повторениями''' (англ. ''combinations with repetitions'') — те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.
 +
}}
 +
В пример можно привести следующую задачу: имеется <tex>n</tex> пирожных. Сколько способов купить <tex>k</tex> пирожных?
  
−
<tex>A(n, t) = A(n, t - 1) + A(n - t, t)</tex>, где первый параметр - это число, которое мы разбиваем, а второй - это максимальное слагаемое в разбиении.
+
=== Разбиение на неупорядоченные слагаемые ===
 +
{{Определение
 +
|definition=[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] (англ. ''partition'') &mdash; представление числа <tex>n</tex> в виде суммы слагаемых.
 +
}}
 +
{{main|Нахождение количества разбиений числа на слагаемые}}
  
−
'''Количество неупорядоченных разбиений ''n''-элементного множества на ''k'' непустых подмножеств.'''
+
=== Разбиение на подмножества ===
 +
{{Определение
 +
|definition=[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] (англ. ''partition of a set'') — семейство непустых множеств <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>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.
 +
}}
 +
{{main|Числа Стирлинга второго рода}}
  
−
Оно выражается числами Стирлинга второго рода, которые удовлетворяют следующему рекуррентному соотношению:
+
== Число комбинаторных объектов ==
 +
{| class="wikitable" border = 1
 +
|'''Тип объекта'''||'''Число объектов'''
 +
|-
 +
|Битовые вектора||<tex>2^{n}</tex>
 +
|-
 +
|Перестановки||<tex>P_n = n!</tex>
 +
|-
 +
|Перестановки с повторениями||<tex dpi = "150">\frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>
 +
|-
 +
|Размещения||<tex dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>
 +
|-
 +
|Размещения с повторениями||<tex>n^k</tex>
 +
|-
 +
|Сочетания||<tex dpi = "150">C^{k}_n = \frac{n!}{k!(n - k)!}</tex>
 +
|-
 +
|Сочетания с повторениями||<tex dpi = "150">\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>
 +
|-
 +
|Разбиение на неупорядоченные слагаемые||[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]]
 +
|-
 +
|Разбиение на подмножества||[[Числа Стирлинга второго рода | Числа Стирлинга второго порядка]]
 +
|}
  
−
<tex>S(n, n) = 1</tex>, для ''n'' ≥ 0,
+
== См. также ==
 +
*[[Генерация комбинаторных объектов в лексикографическом порядке | Генерация комбинаторных объектов в лексикографическом порядке]]
 +
*[[Получение следующего объекта | Получение следующего объекта]]
 +
*[[Получение номера по объекту | Получение номера по объекту]]
 +
*[[Получение объекта по номеру | Получение объекта по номеру]]
  
−
<tex>S(n, 0) = 0</tex>, для ''n'' > 0,
+
== Примечания ==
 +
<references/>
  
−
<tex>S(n, k) = S(n - 1, k - 1) + k \cdot S(n - 1, k)</tex> для 0 < ''k'' < ''n''.
+
== Источники информации ==
 +
* [http://hijos.ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Математика, которая мне нравится — Размещения, перестановки, сочетания с повторениями. Формула включения – исключения]
  
−
== Источники ==
+
[[Категория: Дискретная математика и алгоритмы]]
−
[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 Комбинаторика - Википедиа]
+
[[Категория: Комбинаторика ]]
 +
[[Категория: Комбинаторные объекты ]]

Версия 15:36, 5 января 2017


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


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


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

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

Определение:
Битовые вектора (англ. bit vectors) — последовательность нулей и единиц заданной длины.


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

Определение:
Перестановки[1] (англ. permutations) — упорядоченный набор чисел [math]1, 2,\ldots, n[/math], обычно трактуемый как биекция на множестве [math]\{ 1, 2,\ldots, n \}[/math], которая числу [math]i[/math] ставит соответствие [math]i[/math]-й элемент из набора.

Примером перестановки может служить задача о рассадке [math]n[/math] человек за стол по [math]n[/math] местам.

Перестановки с повторениями

Определение:
Перестановки с повторениями (англ. permutations with repetitions) — те же перестановки, однако некоторые элементы могут встречаться несколько раз.

В пример можно привести следующую задачу: имеется набор книг [math]\{a_1, a_2, \ldots, a_n\}[/math], каждая из которых имеется в [math]k_1, k_2, \ldots, k_n[/math] экземплярах соответственно. Сколько существует способов переставить книги на полке?

Размещения

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

Примером размещения может служить задача о рассадке [math]k[/math] человек за стол по [math]n[/math] местам, где [math]n \gt k[/math].

Размещения с повторениями

Определение:
Размещение с повторениями (англ. arrangement with repetitions), составленное из данных [math]n[/math] элементов по [math]k[/math] — отображение множества [math]k[/math] первых натуральных чисел [math]1, 2, \ldots, k[/math] в данное множество [math]\{a_1, a_2, \ldots, a_n\}[/math].

В пример можно привести следующую задачу: имеется [math]n[/math] книг, каждая в [math]k[/math] экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?

Сочетания

Определение:
Сочетания[3] (англ. combinations) из [math]n[/math] по [math]k[/math] — набор [math]k[/math] элементов, выбранных из данных [math]n[/math] элементов.

Примером сочетания может служить задача о выборе [math]k[/math] книг из [math]n[/math] вариантов.

Сочетания с повторениями

Определение:
Сочетания с повторениями (англ. combinations with repetitions) — те же сочетания, только теперь даны [math]n[/math] типов элементов, из которых нужно выбрать [math]k[/math] элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.

В пример можно привести следующую задачу: имеется [math]n[/math] пирожных. Сколько способов купить [math]k[/math] пирожных?

Разбиение на неупорядоченные слагаемые

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


Основная статья: Нахождение количества разбиений числа на слагаемые

Разбиение на подмножества

Определение:
Разбиение множества [math]X[/math] на подмножества (англ. partition of a set) — семейство непустых множеств [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]2^{n}[/math]
Перестановки [math]P_n = n![/math]
Перестановки с повторениями [math]\frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}[/math]
Размещения [math]A^{k}_n = \frac{n!}{(n - k)!}[/math]
Размещения с повторениями [math]n^k[/math]
Сочетания [math]C^{k}_n = \frac{n!}{k!(n - k)!}[/math]
Сочетания с повторениями [math]\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}[/math]
Разбиение на неупорядоченные слагаемые Нахождение количества разбиений числа на слагаемые
Разбиение на подмножества Числа Стирлинга второго порядка

См. также

Примечания

  1. ↑ Википедия — Перестановки
  2. ↑ Википедия — Размещения
  3. ↑ Википедия — Сочетания

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Комбинаторные_объекты&oldid=58780»