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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Удаление вывода формул, добавление таблицы)
Строка 1: Строка 1:
  
 
{{Определение
 
{{Определение
−
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
+
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
  
 
{{Определение
 
{{Определение
−
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными'''.
+
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными''' (англ. ''ordered'').
 
}}
 
}}
  
 
== Примеры комбинаторных объектов ==
 
== Примеры комбинаторных объектов ==
 
=== Битовые вектора ===
 
=== Битовые вектора ===
−
'''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' &mdash; последовательность нулей и единиц заданной длины. Количество таких объектов вычисляется по формуле <tex>2^{n}</tex>, так как на каждое из <tex>n</tex> мест мы можем поставить один из двух элементов.
+
'''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' &mdash; последовательность нулей и единиц заданной длины.
  
 
=== Перестановки ===
 
=== Перестановки ===
−
'''Перестановки<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>''' &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>[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>''' &mdash; упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора.
  
 
=== Перестановки с повторениями ===
 
=== Перестановки с повторениями ===
−
'''Перестановки с повторениями''' — это те же перестановки, однако некоторые элементы могут встречаться несколько раз. Число различных перестановок с повторениями из элементов <tex>{a_1, a_2, ..., a_n}</tex>, в которых эти элементы повторяются соответственно <tex>k_1, k_2, ..., k_n</tex> раз, равно <tex dpi = "150">\frac{(k_1 + k_2 + ... + k_n)!}{k_1!k_2!...k_n!}</tex>. Выведем формулу. Всего перестановок <tex>(k_1 + k_2 + ... + k_n)!</tex>, однако среди них есть и повторяющиеся. Такие попадаются, когда мы переставляем местами одинаковые элементы. Тогда всего повторяющихся перестановок будет в <tex>k_1!k_2!...k_n!</tex> раз. В итоге получаем необходимую формулу.
+
'''Перестановки с повторениями''' — те же перестановки, однако некоторые элементы могут встречаться несколько раз.
  
 
=== Размещения ===
 
=== Размещения ===
−
'''Размещение'''<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> из <tex>n</tex> по <tex>k</tex> &mdash; это упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества. Таких наборов <tex dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>. Выведем формулу подобно тому, как выводили для '''перестановок''': на первое место можно поставить один из <tex>n</tex> элементов, на следующее один из <tex>n - 1</tex>,... и на последнее один из <tex>n - k + 1</tex>. Всего получится <tex dpi = "150">n \times (n - 1) \times ... \times (n - k + 1) = \frac{n!}{(n - k)!}</tex>.
+
'''Размещение'''<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> из <tex>n</tex> по <tex>k</tex> &mdash; упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества.
  
 
=== Размещения с повторениями ===
 
=== Размещения с повторениями ===
−
'''Размещение с повторениями''', составленное из данных <tex>n</tex> элементов по <tex>k</tex> — это отображение множества <tex>k</tex> первых натуральных чисел <tex>1, 2, ..., k</tex> в данное множество <tex>\{a_1, a_2, ..., a_n\}</tex>. Всего таких элементов <tex>n^k</tex>. Формула выводится так же, как и для битовых векторов.
+
'''Размещение с повторениями''', составленное из данных <tex>n</tex> элементов по <tex>k</tex> — отображение множества <tex>k</tex> первых натуральных чисел <tex>1, 2, \ldots, k</tex> в данное множество <tex>\{a_1, a_2, \ldots, a_n\}</tex>.
  
 
=== Сочетания ===
 
=== Сочетания ===
−
'''Сочетания<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>''' из <tex>n</tex> по <tex>k</tex> &mdash; это набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов. Количество таких наборов вычисляется по формуле <tex dpi = "150">C^{k}_n = \frac{n!}{k!(n - k)!}</tex>. Выведем данную формулу из формулы размещений, а именно заметим, что в размещениях порядок элементов имеет значение, а в сочетаниях нет. Это значит, что наборы <tex>\{1, 2\}</tex> и <tex>\{2, 1\}</tex> эквивалентны. То есть в размещениях любой вариант сочетания повторяется столько же раз, сколько можно сделать перестановок для <tex>k</tex> мест. Тогда <tex dpi = "150">C^{k}_n = \frac{A^{k}_n}{k!} = \frac{n!}{k!(n - k)!}</tex>.
+
'''Сочетания<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>''' из <tex>n</tex> по <tex>k</tex> &mdash; набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов.
  
 
=== Сочетания с повторениями ===
 
=== Сочетания с повторениями ===
−
'''Сочетания с повторениями''' — это те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом. Способов таких выборов всего <tex dpi = "150">\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>. Чтобы вывести формулу, давайте различные элементы в перестановке разделим перегородками, а каждый элемент назовем <tex>1</tex>, тогда, чтобы получить новую перестановку просто будем менять местами перегородки и <tex>1</tex>, причем таких перегородок будет <tex>n - 1</tex>, даже если мы не брали некоторые типы элементов. Таких перестановок <tex>(n - 1 + k)!</tex>, а за вычетом перестановок одинаковых элементов (перегородок и <tex>1</tex>), коих в <tex>k!(n - 1)!</tex> раз больше необходимых, получаем необходимую формулу.
+
'''Сочетания с повторениями''' — те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.
  
 
=== Разбиение на неупорядоченные слагаемые ===
 
=== Разбиение на неупорядоченные слагаемые ===
−
[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] &mdash; это представление числа <tex>n</tex> в виде суммы слагаемых. Всего таких разбиений:
+
[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] &mdash; представление числа <tex>n</tex> в виде суммы слагаемых.
−
:<p>
 
−
<tex>P_{n,k} = \left \{ 
 
−
\begin{array}{ll}  P_{n,k - 1} + P_{n - k, k}, & 0 < k \leqslant n \\ 
 
−
P_{n, n}, & k > n \\
 
−
1, & n = 0, k = 0 \\
 
−
0, & n \neq 0 , k = 0,  \end{array}  \right.</tex>
 
−
</p>
 
−
где <tex>k</tex> — число, не превышаемое слагаемыми, причем начальное значение <tex>k = 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>;
 
# <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.
 
# <math>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.
−
Если задано множество из <tex>n</tex> элементов, которое необходимо разбить на <tex>k</tex> непустых частей, то последний элемент исходного множества можно либо поместить  в отдельную часть (<tex dpi = "180">\lbrace{n-1\atop k-1}\rbrace</tex> способами), либо поместить его в некоторое подмножество (<tex>k</tex><tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способами, поскольку каждый из <tex dpi = "180">\lbrace{n-1\atop k}\rbrace</tex> способов распределения первых <tex>n-1</tex> элементов по <tex>k</tex> непустым частям дает <tex>k</tex> подмножеств, с которыми можно объединить последний элемент).
 
−
 
−
<tex>\begin{Bmatrix}
 
−
n \\
 
−
k
 
−
\end{Bmatrix} = \begin{cases}
 
−
k\begin{Bmatrix}
 
−
n-1 \\
 
−
k
 
−
\end{Bmatrix} + \begin{Bmatrix}
 
−
n-1 \\
 
−
k-1
 
−
\end{Bmatrix}, 0<k<n \\
 
−
0, k = 0 \\
 
−
0, n = 0 \\
 
−
0, k > n \\
 
−
1, k = n
 
−
\end{cases}
 
−
</tex>
 
  
−
Подробнее можно прочитать на странице о [[Числа Стирлинга второго рода | числах Стирлинга второго порядка]].
+
== Количество комбинаторных объектов ==
−
 
+
{| class="wikitable" border = 1
−
== Источники информации ==
+
|'''Тип объекта'''||'''Число объектов'''
−
* [http://hijos.ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Размещения, перестановки, сочетания с повторениями]
+
|-
 +
|Битовые вектора||<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>
 +
|-
 +
|Разбиение на неупорядоченные слагаемые||[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]]
 +
|-
 +
|Разбиение на подмножества||[[Числа Стирлинга второго рода | Числа Стирлинга второго порядка]]
 +
|}
  
 
== Примечания ==
 
== Примечания ==
 
<references/>
 
<references/>
 +
 +
== Источники информации ==
 +
* [http://hijos.ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Математика, которая мне нравится — Размещения, перестановки, сочетания с повторениями. Формула включения – исключения]
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]

Версия 16:09, 31 декабря 2016


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


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


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

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

Битовые вектора — последовательность нулей и единиц заданной длины.

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

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

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

Перестановки с повторениями — те же перестановки, однако некоторые элементы могут встречаться несколько раз.

Размещения

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

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

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

Сочетания

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

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

Сочетания с повторениями — те же сочетания, только теперь даны [math]n[/math] типов элементов, из которых нужно выбрать [math]k[/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]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=58448»