XVI Международная студенческая научная конференция Студенческий научный форум - 2024

Для решения комбинаторных задач применяются формулы комбинаторики (см. рис.1).

Факториалом натурального числа n называется произведение всех натуральных чисел от 1 до n.

Перестановка n объектов/элементов – это способ их последовательного расположения с учётом порядка. Например, abc, bca и cab — это разные перестановки трёх букв [2].

Перестановкой с повторениями из m элементов состава называют кортеж длины суммы , где – число повторений одного элемента множества, – число повторений другого элемента множества и т.д., – количество повторений оставшегося элемента множества [2].

Размещение из n по k – это упорядоченный набор из k различных элементов, взятых из некоторого множества с мощностью n, где k ≤ n. То есть некая перестановка k выбранных элементов из n [2].

Размещение с повторениями — это размещение предметов в предположении, что каждый предмет может участвовать в размещении сколь угодно раз [3].

Сочетание из n по k – это неупорядоченный набор из k различных элементов, взятых из некоторого множества с мощностью n, где k ≤ n. То есть набор, для которого порядок выбора не имеет значения [2].

Сочетание с повторениями — это комбинации, составленные из n различных элементов, среди которых встречаются одинаковые по m элементов и которые отличаются хотя бы одним элементом [1].

Рисунок 1 ­– Формулы комбинаторики

Правила сложения и умножения в комбинаторике.

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе действие n2 способами, третье – n3 способами и так до k-го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены: способами.

Основной комбинаторный принцип. Если некоторый первый выбор можно сделать n способами, для каждого первого выбора некоторый второй можно сделать s способами, для каждой пары первых двух – третий выбор можно сделать m способами и т.д., то число способов для последовательности таких выборов равно n*s*m*…

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

Принцип Дирихле. Пусть есть n ящиков и n+ 1 кролик. Если рассадить всех

кроликов по этим ящикам, то обязательно найдется ящик, в котором не меньше

двух кроликов [4].

Формула включений и исключений. Пусть есть объектов и их свойства, которые мы обозначаем Пусть даны количества объектов в нашем наборе, обладающие различными свойствами:

• – количества объектов, обладающих свойствами соответственно (таких количеств всего n);

• – количества объектов обладающих двумя свойствами (α1, α2), ...,(αn−1, αn) соответственно

• N(α1, ..., αn−1), N(α1, α3, ..., αn),..., N(α2, ..., αn) – количества объектов обладающих n − 1 свойством (α1, ..., αn−1), ...,(α2, ..., αn) соответственно ;

• N(α1, α2, ..., αn) – количество объектов обладающих n свойствами;

• N(α 0 1 , α0 2 , ..., α0 n ) – количество объектов не обладающих ни одним из n свойств.

Тогда справедлива формула:

На применении рассмотренных принципов и методов базируется решение большинства комбинаторных задач.

Список использованных источников

1. Дискретная математика и комбинаторика / Дж. Андерсон. Пер. с англ. — М.: Изд-во Вильямс, 2006. — 960 с.

2. Комбинаторика / М. Холл. Пер. с англ. — М.: Мир, 1970. — 421 с.

3. Комбинаторика / Н. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин. — М.: ФИМА, МЦНМО, 2017. — 400 с.

4. Комбинаторика в жизнедеятельности человека и решение комбинаторных задач / И. И. Роганова // Международный журнал гуманитарных и естественных наук. Педагогические науки. — 2019. — № 3. — С. 20-25.

5. Развитие некоторых классических комбинаторных задач / А. Е. Малых, А.А. Давыдова // Вестник ПГГПУ. Серия № 2. Физико-математические и естественные науки. — 2019. — № 1. — С. 82-102.