Комбинаторное моделирование - Combinatorial modelling - Wikipedia

Комбинаторное моделирование это процесс, который позволяет нам определить подходящую математическую модель для переформулирования проблемы. Эти комбинаторные модели обеспечат через комбинаторика теории, операции, необходимые для решения проблемы.

Неявные комбинаторные модели

Простые комбинаторные задачи - это те, которые можно решить, применяя всего одну комбинаторную операцию (вариации, перестановки, комбинации,…). Эти проблемы можно разделить на три разные модели, называемые неявными комбинаторными моделями.

Выбор

Задача выбора требует выбрать образец k элементы из набора п элементы. Необходимо знать, имеет ли значение порядок, в котором выбираются объекты, и можно ли выбирать объект более одного раза или нет. В этой таблице показаны операции, которые модель предоставляет для получения количества различных выборок для каждого из вариантов выбора:

Репетиция

не положено

Репетиция

допустимый

Упорядоченный

образец

Не заказано

образец

Примеры

1.- На вечеринке 50 человек. Каждый раз всем пожимает руку. Как часто в целом рукопожатие?Что нам нужно сделать, так это подсчитать количество всех возможных пар гостей вечеринки, что означает выборку 2 человек из 50 гостей, поэтому и . Пара будет одинаковой вне зависимости от порядка расположения двух человек. Рукопожатие должны выполнять два разных человека (без повторения). Итак, требуется выбрать упорядоченную выборку из 2 элементов из набора из 50 элементов, в котором повторение не допускается. Это все, что нам нужно знать, чтобы выбрать правильную операцию, и результат будет:

2.- К сожалению, вы не можете вспомнить код своего четырехзначного замка. Вы только знаете, что не использовали цифру более одного раза. Сколько разных способов вы должны попробовать?Нам нужно выбрать образец из 4 цифр из набора 10 цифр (основание 10), поэтому и . Цифры должны быть упорядочены определенным образом, чтобы получить правильный номер, поэтому мы хотим выбрать заказанный образец. Как сказано в заявлении, ни одна цифра не была выбрана более одного раза, поэтому в нашем образце не будет повторяющихся цифр. Итак, требуется выбрать упорядоченную выборку из 4 элементов из набора из 10 элементов, в котором повторение не допускается. Это все, что нам нужно знать, чтобы выбрать правильную операцию, и результат будет:

3.- Мальчик хочет купить 20 пригласительных билетов, чтобы подарить их друзьям на день рождения. В магазине есть 3 типа карточек, и все они ему нравятся. Какими способами он может купить 20 карт? Из набора из 3-х видов карт необходимо выбрать образец из 20 пригласительных билетов, поэтому и . Порядок, в котором вы выбираете различные типы приглашений, не имеет значения. Поскольку тип карты необходимо выбирать более одного раза, в наших пригласительных билетах будут повторения. Итак, мы хотим выбрать неупорядоченную выборку из 20 элементов () из набора из 3 элементов (), в которых допускается повторение. Это все, что нам нужно знать, чтобы выбрать правильную операцию, и результат будет:

Распределение

В задаче распределения необходимо разместить k объекты в п коробки или получатели. Чтобы выбрать нужную операцию из тех, что предусмотрены моделью, необходимо знать:

  • Различимы ли предметы или нет.
  • Независимо от того, различимы ли коробки или нет.
  • Если порядок, в котором объекты помещены в коробку, имеет значение.
  • Условия, которым должно соответствовать распределение. В зависимости от этого раздача может быть:
    1. Инъективное распределение: в каждой коробке должно быть не более 1 объекта ()
    2. Сюръективное распределение: в каждом ящике должен быть хотя бы 1 объект ()
    3. Биективное распределение: в каждой коробке должен быть ровно 1 объект ()
    4. Распространение без ограничений

В следующей таблице показаны операции, которые предоставляет модель для получения количества различных способов распределения объектов для каждого из распределений:

Распределение k объекты в п коробки
Неупорядоченное распространениеЗаказное распространение
Отличительные объектыНеразличимые объектыОтличительные объекты
Отличительные коробкиНеразличимые коробкиОтличительные коробкиНеразличимые коробкиОтличительные коробкиНеразличимые коробки
Любой

распределение

Инъекционный

распределение

Сюръективный

распределение

Биективный

распределение

Числа Стирлинга второго рода
Количество разделов целого числа k в п части
Числа Ла (числа Стирлинга третьего вида)

Примеры

1.- Учитель математики должен выделить своим ученикам 3 стажировки. Семеро из них получили оценку «отлично», поэтому они являются кандидатами на ее получение. Каким образом он может распределить гранты?Давайте рассмотрим 3 студенческих стипендии - это объекты, которые нужно распределить по 7 ящикам, которые являются студентами. Поскольку объекты являются идентичными студентами, они неотличимы. Ящики различимы, так как это разные ученики. Каждое студенческое место должно быть отдано другому студенту, поэтому в каждой коробке должно быть не более 1 предмета. Более того, порядок, в котором объекты размещаются в ящиках, не имеет значения, потому что на каждом ящике не может быть больше одного. Итак, это неупорядоченное инъективное распределение 3 неразличимых объектов () в 7 различимых ящиков (). Это все, что нам нужно знать, чтобы выбрать правильную операцию, и результат будет:

2.- Группа из 8 друзей снимает 5-комнатный коттедж для отдыха. Если комнаты идентичны и никто не может быть пустым, сколькими способами они могут быть распределены в коттедже?Давайте рассмотрим друзей - это объекты, которые нужно распределить по 5 ящикам, которые являются комнатами. Поскольку объекты принадлежат разным людям, они различимы. Ящики неотличимы, так как это одинаковые комнаты. Мы можем рассматривать это как неупорядоченную раздачу, потому что порядок, в котором все размещены по комнатам, не имеет значения. Ни одна комната не может быть пустой, поэтому в каждой коробке должен быть хотя бы 1 предмет. Итак, это неупорядоченное сюръективное распределение 8 различимых объектов () в 5 неразличимых ящиков (). Это все, что нам нужно знать, чтобы выбрать правильную операцию, и результат будет:

3.- 12 человек сделали покупки в супермаркете, где сейчас работают 4 кассира. Какими различными способами они могут быть распределены по кассам?Давайте рассмотрим людей как объекты, которые нужно распределить по коробкам, которые являются кассами. Поскольку люди и кассы разные, предметы и коробки различимы. Порядок, в котором объекты помещаются в коробки, имеет значение, потому что это люди, попадающие в очереди. В заявлении не упоминается никаких ограничений. Итак, это упорядоченное распределение без ограничений 12 различимых объектов () в 4 различимых ящика (). Это все, что нам нужно знать, чтобы выбрать правильную операцию, и результат будет:

Раздел

Задача разделения требует разделения набора k элементы в п подмножества. Эта модель связана с распределительной, так как мы можем рассматривать объекты внутри каждого ящика как подмножества набора объектов для распределения. Таким образом, каждое из 24 описанных ранее распределений имеет соответствующий вид разделения на подмножества. Итак, проблему разделения можно решить, преобразовав ее в проблему распределения и применив соответствующую операцию, предусмотренную моделью распределения (предыдущая таблица). Следуя этому методу, мы получим количество возможных способов разделения множества. Связь между этими двумя моделями описана в следующей таблице:

РаспределениеРаздел
УпорядоченныйПодмножества упорядоченных элементов
Не заказаноПодмножества неупорядоченных элементов
Отличительные объектыОтличительные элементы
Неразличимые объектыНеразличимые элементы
Отличительные коробкиЗаказанные перегородки
Неразличимые коробкиНеупорядоченные разделы
Инъективное распределениеПодмножества из 1 элемента или пустые
Сюръективное распределениеНет пустых подмножеств
Биективное распределениеПодмножества ровно 1 элемента
Нет ограниченийПодмножества из 1 или более элементов или пустые

Это соотношение позволяет нам преобразовать таблицу, предоставленную моделью распределения, в новую, которая может быть использована для определения различных способов разделения набора k элементы в п подмножества:

Перегородка набора k элементы в п подмножества
Неупорядоченные элементы,
Отличительные элементыНеразличимые элементыОтличительные элементы
Упорядоченные подмножестваНеупорядоченные подмножестваУпорядоченные подмножестваНеупорядоченные подмножестваУпорядоченные подмножестваНеупорядоченные подмножества
Любые подмножества
Пустые или одноэлементные подмножества
Нет пустых подмножеств
Подмножества 1 элемента

Примеры

1.- Группа из 3 одноклассников должна написать диссертацию по 8 различным математическим темам. Сколько способов они могут разделить работу?Нам нужно разделить набор из 8 тем на 3 подмножества. Эти подмножества будут темами, над которыми будет работать каждый из студентов. Элементы в наборе (темы) различимы. Разделы должны быть упорядочены, потому что каждый из них будет соответствовать разному студенту, но темы внутри каждого подмножества не нужно упорядочивать, потому что каждый студент может решить, в каком порядке следовать при работе над диссертацией. В заявлении не упоминается какое-либо ограничение подмножеств. Итак, требуется разделить набор из 8 элементов () на 3 упорядоченных подмножества () неупорядоченных элементов. Это все, что нам нужно знать, чтобы выбрать правильную операцию, и результат будет:

Смотрите также

Источники