30
правок
Изменения
Примеры
== Примеры комбинаторных объектов ==
=== Битовые вектора ===
{{Определение|definition='''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' (англ. ''bit vectors'') — последовательность нулей и единиц заданной длины.}}
=== Перестановки ===
{{Определение|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'') — упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора.}}Примером перестановки может служить задача о рассадке <tex>n</tex> человек за стол по <tex>n</tex> местам.
=== Перестановки с повторениями ===
{{Определение|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> — упорядоченный набор из <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> экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?
=== Сочетания ===
{{Определение|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> — набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов.}}Примером сочетания может служить задача о выборе <tex>k</tex> книг из <tex>n</tex> вариантов.
=== Сочетания с повторениями ===
{{Определение|definition='''Сочетания с повторениями''' (англ. ''combinations with repetitions'') — те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.}}В пример можно привести следующую задачу: имеется <tex>n</tex> пирожных. Сколько способов купить <tex>k</tex> пирожных?
=== Разбиение на неупорядоченные слагаемые ===
{{Определение|definition=[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] (англ. ''partition'') — представление числа <tex>n</tex> в виде суммы слагаемых.}}
{{main|Нахождение количества разбиений числа на слагаемые}}
=== Разбиение на подмножества ===
{{Определение|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|Числа Стирлинга второго рода}}
