Комбинаторные объекты — различия между версиями
Mogikan (обсуждение | вклад) (→Примеры комбинаторных объектов) |
Dantesto (обсуждение | вклад) м |
||
(не показано 15 промежуточных версий 3 участников) | |||
Строка 1: | Строка 1: | ||
+ | |||
{{Определение | {{Определение | ||
− | |definition = '''Комбинаторные объекты''' '' | + | |definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}} |
+ | |||
+ | {{Определение | ||
+ | |definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными''' (англ. ''ordered''). | ||
+ | }} | ||
+ | |||
== Примеры комбинаторных объектов == | == Примеры комбинаторных объектов == | ||
− | + | === Битовые вектора === | |
− | + | {{Определение | |
− | + | |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>. | ||
− | <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> вариантов. | ||
− | <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|Числа Стирлинга второго рода}} | ||
+ | |||
+ | == Число комбинаторных объектов == | ||
+ | {| 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> | ||
+ | |- | ||
+ | |Разбиение на неупорядоченные слагаемые||[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]] | ||
+ | |- | ||
+ | |Разбиение на подмножества||[[Числа Стирлинга второго рода | Числа Стирлинга второго порядка]] | ||
+ | |} | ||
− | + | == См. также == | |
+ | *[[Генерация комбинаторных объектов в лексикографическом порядке | Генерация комбинаторных объектов в лексикографическом порядке]] | ||
+ | *[[Получение следующего объекта | Получение следующего объекта]] | ||
+ | *[[Получение номера по объекту | Получение номера по объекту]] | ||
+ | *[[Получение объекта по номеру | Получение объекта по номеру]] | ||
− | + | == Примечания == | |
+ | <references/> | ||
− | + | == Источники информации == | |
+ | * [http://hijos.ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Математика, которая мне нравится — Размещения, перестановки, сочетания с повторениями. Формула включения – исключения] | ||
− | |||
− | |||
− | |||
[[Категория: Дискретная математика и алгоритмы]] | [[Категория: Дискретная математика и алгоритмы]] | ||
− | |||
[[Категория: Комбинаторика ]] | [[Категория: Комбинаторика ]] | ||
+ | [[Категория: Комбинаторные объекты ]] |
Версия 15:36, 5 января 2017
Определение: |
Комбинаторные объекты (англ. combinatorial objects) — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п. |
Определение: |
Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются упорядоченными (англ. ordered). |
Содержание
Примеры комбинаторных объектов
Битовые вектора
Определение: |
Битовые вектора (англ. bit vectors) — последовательность нулей и единиц заданной длины. |
Перестановки
Определение: |
Перестановки[1] (англ. permutations) — упорядоченный набор чисел , обычно трактуемый как биекция на множестве , которая числу ставит соответствие -й элемент из набора. |
Примером перестановки может служить задача о рассадке
человек за стол по местам.Перестановки с повторениями
Определение: |
Перестановки с повторениями (англ. permutations with repetitions) — те же перестановки, однако некоторые элементы могут встречаться несколько раз. |
В пример можно привести следующую задачу: имеется набор книг
, каждая из которых имеется в экземплярах соответственно. Сколько существует способов переставить книги на полке?Размещения
Определение: |
Размещение[2] (англ. arrangement) из по — упорядоченный набор из различных элементов некоторого -элементного множества. |
Примером размещения может служить задача о рассадке
человек за стол по местам, где .Размещения с повторениями
Определение: |
Размещение с повторениями (англ. arrangement with repetitions), составленное из данных | элементов по — отображение множества первых натуральных чисел в данное множество .
В пример можно привести следующую задачу: имеется
книг, каждая в экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?Сочетания
Определение: |
Сочетания[3] (англ. combinations) из по — набор элементов, выбранных из данных элементов. |
Примером сочетания может служить задача о выборе
книг из вариантов.Сочетания с повторениями
Определение: |
Сочетания с повторениями (англ. combinations with repetitions) — те же сочетания, только теперь даны | типов элементов, из которых нужно выбрать элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.
В пример можно привести следующую задачу: имеется
пирожных. Сколько способов купить пирожных?Разбиение на неупорядоченные слагаемые
Определение: |
Разбиение числа на неупорядоченные слагаемые (англ. partition) — представление числа в виде суммы слагаемых. |
Разбиение на подмножества
Определение: |
Разбиение множества (англ. partition of a set) — семейство непустых множеств на подмножества , где — некоторое множество индексов, если:
|
Число комбинаторных объектов
Тип объекта | Число объектов |
Битовые вектора | |
Перестановки | |
Перестановки с повторениями | |
Размещения | |
Размещения с повторениями | |
Сочетания | |
Сочетания с повторениями | |
Разбиение на неупорядоченные слагаемые | Нахождение количества разбиений числа на слагаемые |
Разбиение на подмножества | Числа Стирлинга второго порядка |
См. также
- Генерация комбинаторных объектов в лексикографическом порядке
- Получение следующего объекта
- Получение номера по объекту
- Получение объекта по номеру