Комбинаторное моделирование

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

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

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

Выбор

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

	Повторение не разрешено	Повторение допустимый
Заказал образец	$V_{n,k}$	$VR_{n,k}$
Не заказанный образец	$C_{n,k}$	$CR_{n,k}$

Примеры

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

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

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

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

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

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

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

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

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

• 
  Инъективное распределение
• 
  Сурективное распределение
• 
  Биективное распределение
• 
  Распространение без ограничений

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

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

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

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

$P(k,n):$ Количество разбиений целого числа k на n частей

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

Примеры

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

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

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

$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 различимых объектов ( $k=12$) на 4 различимых прямоугольника ( $n=4$). Это все, что нам нужно знать, чтобы выбрать правильную операцию, и результат:

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

Раздел

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

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

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

Разделение набора из k элементов на n подмножеств

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

Примеры

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

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

См. также

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

Источники

• Дюбуа, Жан-Ги. Систематика простых комбинаторных конфигураций. Образовательные исследования по математике 15 , 37–57 (1984) doi:10.1007/BF00380438
• В. Наварро-Пелайо; Кармен Батанеро Хуан Д. Годино (1996). Комбинаторное мышление у учащихся средних школ.
• Рафаэль Роа (2000). Комбинаторное мышление у студентов с продвинутой математической подготовкой.
• Тан Миншу (2011). Некоторые комбинаторные тождества и объяснения, основанные на модели занятости.