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

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

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

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

Выбор

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

	Репетиция не положено	Репетиция допустимый
Упорядоченный образец	${\displaystyle V_{n,k}}$	${\displaystyle VR_{n,k}}$
Не заказано образец	${\displaystyle C_{n,k}}$	${\displaystyle CR_{n,k}}$

Примеры

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

${\displaystyle C_{50,2}={\frac {50!}{2!\cdot (50-2)!}}=1225}$

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

${\displaystyle V_{10,4}={\frac {10!}{(10-4)!}}=5040}$

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

${\displaystyle CR_{3,20}=C_{22,20}={\frac {22!}{20!\cdot (22-20)!}}=231}$

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

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

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

• 

  Инъективное распределение

• 

  Уверенное распространение

• 

  Биективное распределение

• 

  Распространение без ограничений

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

Распределение k объекты в п коробки

	Неупорядоченное распространение				Заказное распространение
	Отличительные объекты		Неразличимые объекты		Отличительные объекты
	Отличительные коробки	Неразличимые коробки	Отличительные коробки	Неразличимые коробки	Отличительные коробки	Неразличимые коробки
Любой распределение	${\displaystyle VR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}S(k,i)}$	${\displaystyle CR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}P(k,i)}$	${\displaystyle k!\cdot CR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}L(k,i)}$
Инъекционный распределение	${\displaystyle V_{n,k}}$	${\displaystyle 1}$	${\displaystyle C_{n,k}}$	${\displaystyle 1}$	${\displaystyle V_{n,k}}$	${\displaystyle 1}$
Сюръективный распределение	${\displaystyle n!\cdot S(k,n)}$	${\displaystyle S(k,n)}$	${\displaystyle CR_{n,k-n}}$	${\displaystyle P(k,n)}$	${\displaystyle k!\cdot CR_{n,k-n}}$	${\displaystyle L(k,n)={\frac {k!}{n!}}\cdot {k-1 \choose n-1}}$
Биективный распределение	${\displaystyle n!}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle n!}$	${\displaystyle 1}$

${\displaystyle S(k,n)=\left\{{k \atop n}\right\}:}$ Числа Стирлинга второго рода

${\displaystyle P(k,n):}$ Количество разделов целого числа k в п части

${\displaystyle L(k,n):}$ Числа Ла (числа Стирлинга третьего вида)

Примеры

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

${\displaystyle C_{7,3}={\frac {7!}{3!\cdot (7-3)!}}=35}$

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

${\displaystyle S(8,5)=\left\{{8 \atop 5}\right\}={\frac {1}{5!}}\sum _{i=0}^{5}(-1)^{i}{\binom {5}{i}}(5-i)^{8}=1050}$

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

${\displaystyle 12!\cdot CR_{4,12}=12!\cdot C_{15,12}=12!\cdot {\frac {15!}{12!\cdot (15-12)!}}=217945728000}$

Раздел

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

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

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

Перегородка набора k элементы в п подмножества

	Неупорядоченные элементы				,
	Отличительные элементы		Неразличимые элементы		Отличительные элементы
	Упорядоченные подмножества	Неупорядоченные подмножества	Упорядоченные подмножества	Неупорядоченные подмножества	Упорядоченные подмножества	Неупорядоченные подмножества
Любые подмножества	${\displaystyle VR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}S(k,i)}$	${\displaystyle CR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}P(k,i)}$	${\displaystyle k!\cdot CR_{n,k}}$	${\displaystyle \sum _{i=1}^{n}L(k,i)}$
Пустые или одноэлементные подмножества	${\displaystyle V_{n,k}}$	${\displaystyle 1}$	${\displaystyle C_{n,k}}$	${\displaystyle 1}$	${\displaystyle V_{n,k}}$	${\displaystyle 1}$
Нет пустых подмножеств	${\displaystyle n!\cdot S(k,n)}$	${\displaystyle S(k,n)}$	${\displaystyle CR_{n,k-n}}$	${\displaystyle P(k,n)}$	${\displaystyle k!\cdot CR_{n,k-n}}$	${\displaystyle L(k,n)={\frac {k!}{n!}}\cdot CR_{n,k-n}}$
Подмножества 1 элемента	${\displaystyle n!}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle 1}$	${\displaystyle n!}$	${\displaystyle 1}$

Примеры

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

${\displaystyle VR_{3,8}=3^{8}=6561}$

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

• Двенадцатикратный путь

Источники

• Дюбуа, Жан-Ги. Une systématique des configurations combinatoires simples. Образовательные исследования по математике 15, 37–57 (1984) doi: 10.1007 / BF00380438
• В. Наварро-Пелайо; Кармен Батанеро; Хуан Д. Годино (1996). Razonamiento Combinatorio en Alumnos de Secundaria.
• Рафаэль Роа (2000). Razonamiento Combinatorio en Estudiantes con Preparación Matemática Avanzada.
• Тан Миншу (2011). Некоторые комбинаторные тождества и объяснения, основанные на модели занятости.