30
правок
Изменения
м
== Определение ==
'''Комбинаторные объекты''' — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.
2) '''Перестановки''' — это упорядоченный набор чисел <tex>1, 2,\ldots, n,</tex> обычно трактуемый как биекция на множестве <tex>\{ 1{Определение|definition = Если два комбинаторных объекта, 2различающихся только порядком элементов,\ldotsсчитаются различными, n \}</tex>, которая числу то они называются '''упорядоченными'i'' ставит соответствие (англ. ''iordered''-й элемент из набора).}}
3) '''Сочетания''' из '== Примеры комбинаторных объектов ===== Битовые вектора ==={{Определение|definition='n'' [[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''k'' — это набор (англ. ''kbit vectors'' элементов, выбранных из данных ''n'' элементов. 4) '''Размещение''' из ''n'' по ''k'' — это упорядоченный набор из ''k'' различных элементов некоторого n-элементного множества. 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'') — упорядоченный набор чисел <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='''Размещение с повторениями''' (англ. ''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> экземплярах. Сколькими способами может быть сделан выбор книг из числа на слагаемые удовлетворяют рекуррентному соотношению:данных?
Оно выражается числами == Число комбинаторных объектов =={| 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= Примечания ==<references/tex>, для ''n'' > 0,
<tex>S(n, k) = S(n = Источники информации ==* [http://hijos.ru/izuchenie-matematiki/algebra- 1, k 10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula- 1) + k \cdot S(n vklyucheniya- 1isklyucheniya/ Математика, k)</tex> для 0 < ''k'' < ''n''которая мне нравится — Размещения, перестановки, сочетания с повторениями.Формула включения – исключения]
== Источники ==[[Категория: Дискретная математика и алгоритмы]][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 Комбинаторика - Википедиа]][[Категория: Комбинаторные объекты ]]
Нет описания правки
{{Определение|definition == Примеры комбинаторных объектов ==1) '''Битовые вектораКомбинаторные объекты''' (англ. ''combinatorial objects'' — последовательность нулей ) — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и единиц заданной длиныт. п.}}
== Подсчет числа комбинаторных объектов = Перестановки с помощью рекуррентных формул повторениями ===Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи {{Определение|definition='''Перестановки с повторениями''n'(англ. ' предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения'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='''Сочетания<texref>A(0, t) = 0[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия — Сочетания]</texref>, где ''t' (англ. ''combinations'' ) из <tex>n</tex> 0по <tex>k</tex> — набор <tex>k</tex> элементов,выбранных из данных <tex>n</tex> элементов.}}Примером сочетания может служить задача о выборе <tex>k</tex> книг из <tex>n</tex> вариантов.
=== Сочетания с повторениями ==={{Определение|definition='''Сочетания с повторениями''' (англ. ''combinations with repetitions'') — те же сочетания, только теперь даны <tex>A(1n</tex> типов элементов, 1) = 1из которых нужно выбрать <tex>k</tex>элементов,причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.}}В пример можно привести следующую задачу: имеется <tex>n</tex> пирожных. Сколько способов купить <tex>k</tex> пирожных?
=== Разбиение на неупорядоченные слагаемые ==={{Определение|definition=[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] (англ. ''partition'') — представление числа <tex>A(n, t) = A(n, t - 1) + A(n - t, t)</tex>, где первый параметр - это число, которое мы разбиваем, а второй - это максимальное слагаемое в разбиениивиде суммы слагаемых.}}{{main|Нахождение количества разбиений числа на слагаемые}}
=== Разбиение на подмножества ==={{Определение|definition=[[Числа Стирлинга второго рода | '''Количество неупорядоченных разбиений Разбиение''n' множества <math>X</math> '''-элементного множества на подмножества''k']] (англ. ' непустых подмножеств.'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|Числа Стирлинга второго рода}}
