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

Введение

На сегодняшний день комбинаторика представляет собой одним из главных разделов математической науки. Комбинаторные методы обширно применяются для решения практико-ориентированных и теоретических задач. Данный раздел математики непосредственно связан с рядом других разделов дискретной математики. К ним относятся теории вероятностей, теории графов, теории чисел, теории групп и т.д.

В математический обиход термин «комбинаторика» был введен в 1666 Г. В. Лейбницем году в сочинении «Рассуждения о комбинаторном искусстве».

Анализ литературы подтверждает, что возникновение комбинаторики как науки произошло в XVI веке. Изначально в ней исследовались комбинаторные задачи, которые были связаны с азартными играми. В ходе освоения этих задач были сформированы некоторые подходы к их решению, выявлены формулы для вычисления числа разнообразных комбинаций.

Исследованием комбинаторных задач занимались многиевыдающиеся математики. Так, в работах Я. Бернулли и Г. В. Лейбницаизучены основныекомбинаторные конфигурации: сочетания, размещения, перестановки [16]. В сочинении «Рассуждения о комбинаторном искусстве» Г. В. Лейбниц определяет все k-сочетания из n элементов и выводит свойства сочетаний. Я. Бернулли опубликовал свое сочинение «Искусство предположений» в 1713 году. Систематичность, простота методов и строгость изложения позволили сочинению стать популярным в течение XVIII века научным трактатом и учебно-справочным изданием.

В конце XVIII века учёные комбинаторной школы К. Ф. Гинденбурга занимались построением общей комбинаторной теорией, применяя бесконечныеряды. Исследователи этой школы изучили значительное количествопреобразований рядов. В комбинаторике особо значимым представляется использование производящих функций [2].

В XX веке комбинаторика подверглась мощному процессуалгебраизации благодаря работам Дж.-К. Рота и Р. Стенли.Ими была выявлена значимость частично упорядоченных множеств, свойств функцииМёбиуса, абстрактных свойств линейной зависимости при решении комбинаторных задач. Это способствовало приумножениюкомбинаторных методов, а также дальнейшей интеграциикомбинаторики в современную математику.

Основоположником комбинаторики современности является Пал Эрдёш, который ввел в нее вероятностный анализ. Заинтересованность к комбинаторике значительно повысилась с появлением компьютеров (2-я половина ХХ века). Сегодня это содержательная и быстроразвивающаяся область математики. Области ее применения разнообразны: астрология (анализ расположения планет и созвездий), биология (расшифровка кода ДНК), химия (анализ возможных связей между химическими элементами), лингвистика, экономика и др.

Комбинаторика направлена на решение задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами и ограничениями. Любое такое правило определяет способ построения определенной комбинаторной конфигурации. Комбинаторика изучает свойства комбинаторных конфигураций, условия их существования, алгоритмы построения, а также оптимизацию этих алгоритмов [5].

Все выше указанное позволило сформулировать цель курсового исследования.

Цель: систематизация теоретического материала и его применение к решению комбинаторных задач.

Цель работы определила объект и предмет исследования.

Объект исследования: дискретная математика.

Предмет исследования: методы и приемы решения комбинаторных задач.

Задачиисследования:

Изучить теоретические положения по теме «Соединения и их свойства в комбинаторике».

Рассмотреть решения комбинаторных задач.

Результаты исследования были представлены на конференциях:

V внутривузовская студенческая научно-практическая конференция «Молодежь в мире науки» Сургутского государственного педагогического университета (24 ноября 2017 г., г. Сургут), по итогам которой доклад занял второе место в секции.

XXII студенческая научно-практическая конференция «Студенчество в научном поиске» (20 апреля 2018 г, г. Сургут), по итогам которой доклад занял первое место в секции.

Имеется 2 публикации.

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

Глава 1. Основные теоретические положения комбинаторики

Разделы комбинаторики

Определение 1. Комбинаторикаявляется разделом дискретной математики, ориентированным на решение задач выбора и расположения элементов некоторого множества в соответствии с заданными правилами и ограничениями.

Основным понятием комбинаторики является «соединение».

Определение 2. Соединение (множество) – группа, составленная из каких-либо элементов (любой, но одинаковой природы: буквы, числа, геометрические фигуры, детали и т. д.).

Прежде чем непосредственно перейти к формулам комбинаторики и рассмотрению задач, стоит обратить внимание на то, что комбинаторика, как и другие разделы математики, имеет свои подразделы.Характеристика основных разделов комбинаторики представлена в таблице 1.

Таблица 1

Основные разделы комбинаторики

Раздел науки	Характеристика раздела
Перечислительная (исчисляющая) комбинаторика	Анализирует задачи о перечислении и исчислении количества многообразных конфигураций, которые образуются  элементами конечных множеств. На эти множества могут накладываться определенные ограничения, такие как: различимость, неразличимость элементов, возможность повторения одинаковых элементов и т. п.
Структурная комбинаторика	К данному разделу относятся некоторые вопросы теории графов.

Продолжение таблицы 1

Теория Рамсея	Изучает существование регулярных структур в случайных конфигурациях.
Вероятностная комбинаторика	Этот раздел отвечает на вопросы следующего вида: какова вероятность присутствия определённого свойства у заданного множества.
Топологическая комбинаторика	Используется при изучении дерева принятия решений, частично упорядоченных множеств и др.
Экстремальная комбинаторика	Данный раздел применяется для нахождения максимальной размерности графа, который удовлетворяет определенным свойствам.
Инфинитарная комбинаторика	Изучает использование методов комбинаторики к бесконечным множествам.

Стоит отметить, что такая классификация разделов является условной, так как у разных авторов встречаются различные типологии разделов.

Комбинаторные соединения и основные правила решения комбинаторных задач

Комбинаторика исследует многообразные количества комбинаций, которые подчинены конкретным условиям и которые можно составить из элементов любой природы заданного конечного множества. При непосредственном вычислении искомых способов используют формулы различных соединений [1]. Подробно рассмотрим каждое из них.

Перестановки без повторений. Перестановки с повторениями

Определение 3. Перестановки – это последовательности, каждая из которых состоит из n различных элементов.

Число возможных перестановок из n различных элементов находят по формулам:

без повторений

(1)

с повторениями

(2)

Размещения без повторений. Размещения с повторениями

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

Число возможных размещений из n различных элементов по k находят по формулам:

без повторений

(3)

или

(4)

с повторениями

(5)

При n = kполучим

(6)

Сочетания без повторений. Сочетания с повторениями

Определение 7. Сочетания – это комбинации, формируемые из nразличных элементов по k элементов в каждой и отличающиеся одна от другой только составом элементов.

Число возможных сочетаний из n различных элементов по k находят по формулам:

без повторений

(7)

с повторениями

(8)

При

(9)

Нижеуказанные свойства сочетаний без повторений рационально применять для упрощения подсчётов и для доказательства некоторых утверждений [15],[21].

Свойства сочетаний:

1)		(10)
2)		(11)
3)		(12)
4)		(13)
5)		(14)

В комбинаторике особое место занимают два общих правила решения комбинаторных задач. Данные правила позволяют решать различные комбинаторные задачи, практически не прибегая к использованию формул. Они также дают возможность овладеть основными комбинаторными идеями [17]. Разберем подробно каждое из них.

Правила суммы и произведения

Правило суммы: если объект а можно выбрать m способами, а объект b – k способами (не такими, как a), то выбор «либо а, либо b» можно осуществить (m+k) способами [18].

Пример. Ученица должна выполнить практическую работу по математике. Ей предложили на выбор 20 тем по алгебре и 17 тем по геометрии. Сколькими способами ученик может выбрать одну тему?

Решение. По условию задачи алгебраическую тему можно выбрать 20 способами, а геометрическую – 17 способами. Поскольку в задаче говорится о выборе «либо тема по алгебре, либо тема по геометрии», то его, согласно правилу суммы, можно осуществить:

способами.

Ответ: 37 способами ученик может выбрать одну тему для практической работы.

Правило произведения: если объект а можно выбрать m способами, а объект b – k способами, то пару (a, b) можно выбрать b·k способами [18].

Пример.Ученица должна выполнить практическую работу по математике. Ему предложили на выбор 20 тем по алгебре и 17 тем по геометрии. Сколькими способами ученик может выбрать одну тему по алгебре и одну тему по геометрии?

Решение. По условию задачи алгебраическую тему можно выбрать 20 способами, а геометрическую – 17 способами. Так как в задаче речь идет о выборе «тема по алгебре и тема по геометрии», то его, согласно правилу произведения, можно осуществить:

способами.

Ответ: 340 способами ученик может выбрать две темы для практической работы.

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

Методы решения комбинаторных задач

Анализ литературы показал, что комбинаторные задачи можно решить не только с помощью основных комбинаторных соединений и правил сложения и умножения, но и с помощью следующих методов: перебор, составление таблицы, построение графов, построение «дерева» вариантов, использование правила треугольника Паскаля.

Рассмотрим характеристику данных методов решения комбинаторных задач (таблица 2).

Таблица 2

Метод	Характеристика метода
Перебор	Полный перебор всех возможных вариантов, их подсчет.
Составление таблицы	Внесение всех условий в таблицу, выполнение решения непосредственно внутри таблицы.
Построение графов (см. определение 9 )	Вместо отрезков в качестве ребер графов рассматриваются также кривые линии на плоскости. С помощью вершин изображают элементы некоторого множества, а с помощью ребер – определенные связи между элементами.
Построение «дерева» вариантов	В случае, когда число возможных выборов на каждом шагу зависит от того, какие элементы были выбраны ранее, можно изобразить процесс составления комбинаций в виде «дерева».
Использование правила треугольника Паскаля	Числа можно расположить по строкам треугольника Паскаля (рис.1). Боковые стороны треугольника стоят из единиц. Внутри треугольника размещены числа. Каждое внутреннее число равно

Продолжение таблицы 2

сумме двух чисел, расположенных над ним. Строки треугольника нумеруются сверху, причем первая строка является нулевой. Числа в строках нумеруются слева, первое из которых считается нулевым по счету. Число стоит в n-й строке k-м по счёту. Рис. 1. Треугольник Паскаля

Определение 9. Граф – это некотороемножество, имеющее в своем составе конечное число точек, некоторые пары которых соединены дугами или стрелками.

Рассмотрев основные методы, следует сформулировать порядок действий для решения задач по комбинаторике.

Способы действий для решения задач

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

Для определения вида соединения, о котором идет речь, нужно:

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

Схема без повторений:

Если соединение состоит из того же числа различных элементов, что и исходное множество, то речь идет о перестановках (формула 1).

Если выборка содержит меньшее число элементов, то определяем либо размещения, либо сочетания. Если важен порядок элементов, определяем размещения (формула 3,4), в противном случае – сочетания (формула 7).

Схема с повторениями:

Если соединение состоит из всех элементов множества, разбитых на группы, причем элементы группы одинаковы между собой и различны от элементов другой группы, то речь идет о перестановках (формула 2).

Если предложено n множеств, каждое из которых состоит из одинаковых объектов, то соединения из k объектов – это либо размещения, либо сочетания. Если важен порядок расположения в выборке, то речь идет о размещениях (формула 5). В противном случае говориться о сочетаниях (формула 8). Причем возможны случаи k> n.

Для использования правил комбинаторики необходимо пользоваться их содержательным смыслом. Знак «+» в правиле суммы следует понимать как союз «ИЛИ», а знак «·» в правиле произведения как союз «И». Проанализировав вопрос, принимается решение о применении того или иного правила [19]. Для того, чтобы правильно выбрать необходимое для решения задачи соединение, можно воспользоваться следующей схемой (схема 1).

Схема 1

Выбор соединения

Определите количество элементов множества n, из которого выбирается k элементов

Порядок выбранных элементов важен

нет

да

Среди выбранных элементов есть повторения?

Выбираем все nэлементов?

нет

да

да

нет

Сочетания без повторений

Сочетания с повторениями

Среди выбранных элементов есть повторения?

Среди выбранных элементов есть повторения?

нет

да

да

нет

Перестановки с повторениями

Перестановки без повторений

Размещения с повторениями

Размещения без повторений

Таким образом, изучив теоретические основы, мы установили, что в основе решения комбинаторных задач лежат различные соединения и правила, а также выявили методы их решения. Мы разработали способы действия для решения задач и схематизировали выбор комбинаторного соединения.

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

Глава 2. Примеры решения комбинаторных задач

Решение задач с применением методов

Нижеприведенная задача иллюстрирует применение метода перебора.

Задача 1. Сколько двузначных чисел можно составить из цифр 1, 2, 3, 4, 5 [7]?

Решение. Последовательно перебирая все числа, получим следующие комбинации: 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.

Всего чисел 25.

Ответ: 25 чисел.

В следующей задаче представлен метод составления таблицы.

Задача 2. Сколько нечетных двузначных чисел можно составить из цифр 1, 2, 3, 5, 6, 7, 8, 9 [7]?

Решение. Составим таблицу (табл. 3): первый слева столбец – первые цифры искомых чисел, первая строка сверху – вторые цифры [13]. Далее необходимо подсчитать количество комбинаций, соответствующих требованию задачи.

Таблица 3

	1	3	5	7	9
1	11	13	15	17	19
2	21	23	25	27	29
3	31	33	35	37	39
5	51	53	55	57	59
6	61	63	65	67	69
7	71	73	75	77	79
8	81	83	85	87	89
9	91	93	95	97	99

Ответ: 40 чисел.

Применение метода построения графов проиллюстрировано в следующей задаче.

Задача 3.Четыре человека обменялись рукопожатиями. Сколько было рукопожатий?

Решение. Для решения этой задачи удобно воспользоваться построением схемы (рис. 3). Отметим такое количество точек, которое соответствует числу людей. Затем соединим все точки между собой. В результате количество отрезков и будет равно количеству рукопожатий. В данном случае имеется 6 рукопожатий.

Рис. 3

Ответ: 6.

Для решения задачи 4 обратимся к методу построения «дерева» вариантов.

Задача 4.На дне портфеля лежат неразличимые на ощупь карандаши: два простых и три цветных. Ученик вынимает их по одному. Ему нужны цветные карандаши, и вынутый простой карандаш он отправляет обратно на дно портфеля, а цветной оставляет на столе. Такая операция повторяется трижды. а) Нарисуйте дерево возможных вариантов. б) В скольких случаях все вынутые карандаши будут простыми? в) В скольких случаях все вынутые карандаши будут цветными? г) В скольких случаях среди вынутых карандашей цветных будет больше, чем простых [10]?

Решение. Составим дерево возможных комбинаций (рис. 4) и найдем искомые количества вариантов [9].

Рис. 4

Ответ: а) рис. 4; б) 1; в) 1; г) 4.

Нижеприведенную задачу решим, применяя правило треугольника Паскаля.

Задача 5. На прямой взяли 8 точек. Сколько всего получилось отрезков, концами которых являются эти точки [11]?

Решение. Искомое количество отрезков является числом сочетаний без повторений из 8 элементов по 2. Найдем это число на треугольнике Паскаля.

Число стоит в 8-й строке 2-м по счёту (рис. 5).

Рис. 5

Ответ: 28 отрезков.

Рассмотрев данные задачи, разберем типовые задачи, решаемые по формулам комбинаторных соединений.

Задачи, решаемые по формулам комбинаторных соединений.

Использование формулы перестановки без повторений представлено в нижеизложенной задаче.

Задача 1. Сколькими способами можно расставить на полке 12 книг, из которых 5 книг – это сборники стихотворений, так, чтобы сборники стояли рядом [12]?

Решение. Условимся, что 5 стоящих рядом сборников равны одной книге. Поскольку в искомом соединении порядок существенен, все элементы используются, то  это соединение является перестановками без повторений из 8 элементов (7 книг + условная 1 книга). Их количество равно

Найдем количество перестановок между собой 5 сборников:

Так как нам нужно расставить сборники и остальные книги, то воспользуемся правилом произведения. Тогда искомое количество способов равно

Ответ: 4 838 400.

Следующая задача иллюстрирует применение формулы перестановки с повторениями.

Задача 2. Сколькими способами можно расставить белые фигуры (короля, ферзя, 2 ладьи, 2 слонов, 2 коней) на первой линии шахматной доски [12]?

Решение. На первой линии имеется 8 мест, количество фигур также равно 8. Из них 2 одинаковых встречаются 3 раза. Количество искомых вариантов находим по формуле числа перестановок с повторениями. Получаем

Ответ: 5040.

Далее рассмотрим задачи на сочетания без повторений.

Задача 3. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили 2 различных числа? Сколько среди них будет правильных дробей [11]?

Решение. Найдем число различных дробей из данных чисел, используя формулу сочетаний без повторений. Получим

Из этих 30 дробей 15 будут правильные.

Ответ: 30; 15.

Задача 4. В некотором государстве не было двух жителей с одинаковым набором зубов. Сколько могло быть жителей в таком государстве, если во рту человека не может быть больше 32 зубов [5]?

Решение. Пользуясь 5 свойством сочетаний (формула 14), найдем искомое число жителей

Ответ: 5.

Разберем задачу, при решении которой используется формула сочетаний без повторений и правило умножения.

Задача 5. Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую — 5 и в третью — 12. Сколькими способами это можно сделать [20]?

Решение. Создавая первую бригаду, отбирают 3 человека из 20, создавая вторую – 5 из оставшихся 17, создавая третью – 12 из оставшихся 12. Для выборок важен только состав (роли членов бригады не различаются). Эти выборки – сочетания без повторений. Создавая сложную выборку, воспользуемся правилом произведения

Ответ: 7054320.

Формула сочетаний с повторениями применяется в следующих задачах.

Задача 6. На почте 5 видов открыток к Новому году. Сколькими способами из них можно выбрать 7 открыток разного вида [22]?

Решение. Чтобы найти искомое число способов, воспользуемся формулой сочетания с повторениями (формула 9). Получим

Ответ: 330.

Рассмотрим задачу, при решении которой используется формула размещений без повторений.

Задача 7. В чемпионате мира по футболу участвуют 16 команд. Разыгрываются 3 медали: золотая, серебряная и бронзовая. Перед началом первенства был объявлен конкурс знатоков, в котором требовалось указатьраспределение медалей. Сколько различных ответов можно дать на этот вопрос [6]?

Решение. Для нахождения числа различных ответов, воспользуемся формулой размещений без повторений

Ответ: 3360.

Формула размещений с повторениями используется при решении нижеприведенной задачи.

Задача 8. Буквы азбуки Морзе состоят из символов – точка и тире. Сколько букв получим, если потребуем, чтобы каждая буква состояла не более чем из пяти указанных символов [10]?

Решение. Вычислим число букв, состоящих из одного символа

Найдем число букв, состоящих из двух символов

Вычислим число букв, состоящих из трех символов

Найдем число букв, состоящих из четырех символов

Вычислим число букв, состоящих из пяти символов

Применив правило суммы, определим искомое количество комбинаций

Ответ: 62.

Итак, мы рассмотрели и представили решения типовых комбинаторных задач на различные соединения. Далее перейдем к решению более сложных задач, при решении которых используется несколько формул, и задач, которые можно решить несколькими способами.

Задачи повышенной сложности

Задача 1. Три автомашины № 1, 2, 3 должны доставить товар в шесть магазинов. Сколькими способами можно использовать машины, если грузоподъемность каждой из них позволяет взять товар сразу для всех магазинов и если две машины в один и тот же магазин не направляются? Сколько вариантов маршрута возможно, если решено использовать только машину № 1 [14]?

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

Если же использовать только автомашину № 1, то количество вариантов маршрута найдем по формуле перестановок без повторений. Их количесвто будет равно

Ответ: ;

Задача 2. В шахматном турнире принимали участие 15 шахматистов, причем каждый из них сыграл только одну партию с каждым из остальных. Сколько всего партий было сыграно в этом турнире [6]?

Решение. Способ 1. В одной игре участвуют 2 человека, значит, нужно вычислить, сколькими способами можно отобрать 2-х человек из 15. Так как порядок не имеет значения, воспользуемся формулой для нахождения числа сочетаний без повторений. Полученное значение будет соответствовать числу искомых партий

Ответ: 105.

Способ 2. Первый игрок сыграл 14 партий, 2-й игрок – 13 партий, 3-й – 12 партий, 4-й – 11 партий, 5-й – 10 партий, 6-й – 9 партий, 7-й – 8 партий, 8-й – 7 партий, 9-й – 6 партий, 10-й – 5 партий, 11-й – 4 партии, 12-й – 3 партии, 13‑й – 2 партии, 14‑й – 1 партию, 15-й игрок сыграл со всеми. Найдем количество сыгранных партий, пользуясь правилом суммы

Ответ: 105 партий.

Задача 3. Сколькими способами можно переставлять буквы слова «огород» так, чтобы: а) три буквы «о» не стояли рядом? б) если запрещается, чтобы две буквы «о» стояли рядом [11]?

Решение. а) Количество перестановок букв данного слова найдем по формуле перестановок с повторениями. Получим

Обозначим 3 рядом стоящие буквы за одну. Тогда количество перестановок полученных букв равно

Так как полученные способы запрещены в задаче, то их количество необходимо вычесть общего количества перестановок. Получим

б) Вариантов перестановок согласных букв равно

Для 3-х букв «о» остаётся 4 места. Их можно расставить

По правилу умножения найдем искомое количество вариантов

Ответ: 96; 24.

Задача 4. Шесть ящиков различных материалов доставляют на восемь этажей стройки. Сколькими способами можно распределить материалы по этажам? В скольких из них на восьмой этаж будет доставлено не менее двух материалов  [14]?

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

Количество вариантов распределения материалов, когда на восьмой этаж не попадает ни одного ящика равно .

Количество вариантов распределения материалов, когда на восьмой этаж попадает один ящик, равно

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

Ответ: ; .

Задача 5. Каких чисел от 1 до 1 000 000 больше: тех, в записи которых встречается единица, или тех, в которых она не встречается [12]?

Решение.

Способ 1. Произведем подсчет количества чисел от 1 до 999 999 (так как число 1000000 содержит единицу), в записи которых отсутствуют единицы. Каждую цифру можно выбрать 9 способами (любая цифра, кроме 1). Применяя правило произведения, найдем количество таких способов. Получим

вариантов.

Нужно отметить, что случай 000000 не рассматривается. Необходимо вычесть его из общего количества вариантов. Получим

Найдем количество чисел, в записи которого имеется единица

Ответ: посреди чисел от 1 до 1 000 000 чисел без единиц больше.

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

Количество однозначных – 8 цифр (все, кроме 0 и 1).

Количество двузначных – 8·9 чисел (на первом месте все цифры, кроме 0 и 1, на втором – кроме 1).

Количество трехзначных – 8·9·9 чисел;

Количество четырехзначных – 8·9·9·9 чисел;

Количество пятизначных – 8·9·9·9·9 чисел;

Количество шестизначных – 8·9·9·9·9·9 чисел.

Применяя правило суммы, найдем искомое количество чисел

Значит количество чисел, в записи которых имеется единица, равно

Ответ: посреди чисел от 1 до 1 000 000 чисел без единиц больше.

Задача 6. План города имеет схему, изображенную на рисунке. На всех улицах введено одностороннее движение: можно ехать только «вправо» или «вверх». Сколько есть разных маршрутов, ведущих из точки A в точку B (рис.  6) [4]?

В

А

Рис. 6

Решение.Пусть улица обозначена отрезком изображенной сетки, который соединяет два соседних узла. Проанализировав схему, нужно отметить, что каждый маршрут содержит 13 улиц, 8 из которых расположены по горизонтали, а 5 – по вертикали. Сопоставим каждому маршруту последовательность букв Г и В следующим образом: при прохождении «горизонтальной» улицы маршрута будем дописывать в последовательность букву Г, а при прохождении «вертикальной» улицы – букву В. Каждая последовательность будет содержать 13 букв, из которых 8 букв Г и 5 букв В. Пять мест из 13 можно выбрать   способами. Поэтому число возможных последовательностей, а значит, и число возможных маршрутов, равно

Ответ: 1278.

Задача 7. За круглым столом короля Артура сидят 12 рыцарей. Из них каждый враждует со своим соседом. Надо выбрать 5 рыцарей, чтобы освободить заколдованную принцессу. Сколькими способами это можно сделать так, чтобы среди выбранных рыцарей не было врагов [12]?

Решение. Возьмем одного рыцаря В. Тогда все варианты комбинирования рыцарей разбиваются на две группы. В одной из них будет состоять В, а в другой – нет. Если рыцарь В будет освобождать принцессу, то сосед, сидящий справа, и сосед, сидящий слева, уже не будут участвовать в этом освобождении. В результате останутся 9 рыцарей. Из них нужно выбрать 4-х товарищей рыцаря В. Необходимо, чтобы среди выбранных 4-х спутников не было врагов, т.е. тех, кто сидит рядом за столом. Найдем возможные комбинации, применяя формулу сочетаний. Получаем

Вычислим, какое количество походов может быть выполнено, если в них рыцарь В участвовать не будет. В этом случае останется 11 рыцарей, из которых нужно выбрать 5-х так, чтобы никакие 2 из них не сидели рядом. Это можно сделать

Общее число допустимых вариантов будет равно

Ответ: 36.

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

Задача 8. По пустыне идет караван из 9 верблюдов. Сколькими способами можно переставить верблюдов так, чтобы впереди каждого из них шел иной верблюд, чем раньше [12]?

Решение. Пронумеруем верблюдов от конца каравана к его началу следующим образом: 1, 2, 3, 4, 5, 6, 7, 8, 9. Необходимо найти все перестановки данных чисел, в которой исключены пары (1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 7), (7, 8), (8, 9). Вычислим, в каком количестве перестановок будет считаться пара (1,2). Обозначим ее за один элемент. Тогда количество таких перестановок равно

Такой же результат получим при перестановке всех остальных пар.

Теперь необходимо рассмотреть перестановки, которые содержат две запрещенные пары. В этом варианте возможны 2 случая. В первом из них две запрещенные пары не будут иметь общих элементов. Во втором случае эти пары будут иметь один общий элемент. В первом случае останется 7 переставляемых элементов (2 пары и 5 оставшихся элементов, которые не входят в эти пары). Число таких перестановок равно

Во втором случае 3 элемента, которые содержатся в запрещенных парах, должны идти подряд. Объединим эти элементы. Тогда необходимо переставить объединенные элементы и оставшиеся 6. Количество вариантов равно

Какие бы k запрещенных пар мы не брали, количество перестановок, которые содержат k пар, равно

Но k пар из 8 можно выбрать способами. Тогда число перестановок, не содержащих ни одной запрещенной пары, равно

Ответ: 148329.

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

Заключение

В данной работе изложены вопросы, касающиеся понятия комбинаторных соединений и их свойств.

В курсовом исследовании были выделены способы, применяемые в решении задач по теме «Соединения и их свойства в комбинаторике». А именно:

использование основных правил комбинаторики и формул комбинаторных соединений;

применение методов перебора, составления таблицы, построения графов и «дерева» вариантов, использование правила треугольника Паскаля.

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

Таким образом, нами были выполнены поставленные задачи исследования, цель курсовой работы была достигнута.

Приведённая типология задач, а также описанные приёмы и методы могут быть использованы в разработке методических рекомендаций к осуществлению дополнительных занятий по математике в курсе средней общеобразовательной школы, а также на уроках в школах и классах с углублённым изучением математики. Обоснованием этого является факт о том, что комбинаторика развивает такие качества мышления, как системность, вариативность, гибкость. В ее основе лежит умение обучаемого определять, рассматривать и учитывать все возможные варианты сочетания каких-либо признаков или событий, которая служит предпосылкой полноценного логического рассуждения [3].

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

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

Гмурман В. Е. Теория вероятностей и математическая статистика: учебник для прикладного бакалавриата/В. Е. Гмурман. – 12-е изд. – М.: Издательство Юрайт, 2016. – 479 с. – Серия: Бакалавр. Прикладной курс.

Дискретная математика. Комбинаторика: методические указания для студентов экономических специальностей всех форм обучения/Сост. С. В. Соколова. – Юрга: Изд-во Юргинского технологического института (филиала) Томского политехнического университета, 2011 – 32 с.

Драгныш Н. В. Визуализация комбинаторных задач теории вероятностей//Молодой ученый. – 2016. – №15. – С. 129 – 133.

Дрозина, В. В. Механизм творчества решения нестандартных задач [Текст]: учебное пособие для учащихся средних общеобразовательных учебных заведений, студентов педагогических университетов и учителей математики/В. В. Дрозина, В. Л. Дильман – 2-е изд. (эл.) – Москва: БИНОМ. Лаборатория знаний, 2012. – 255 с.

Ерош И. Л. Е78 Дискретная математика. Комбинаторика: Учеб. пособие/СПбГУАП.СПб., 2001. – 37 c.

Лебедева С. В. Элементарная математика: часть 4. Элементы комбинаторики, теории вероятностей и математической статистики: Практико-ориентированное учебное пособие/С. В. Лебедева – Саратов, 2012. – 51 с.

Ленинградские математические кружки: пособие для внеклассной работы. Киров, издательство «АСА», 1994. – 272 с.

Математический энциклопедический словарь/Под ред. Ю. В. Прохорова. М.: Советская энциклопедия, 1988.

Мир математики: в 45 т. Т. 34: Хуанхо Руэ. Искусство подсчета. Комбинаторика и перечисление./Пер. с исп.–М.: Де Агостини, 2014. – 144 с.

Мордкович А. Г. Алгебра и начала математического анализа 10-11 кл. В 2 ч. Ч. 1: Учебник для общеобразоват. учреждений. – М.: Мнемозина, 2009.

Новоселов О. В. Комбинаторика и вероятность: учебн. пособие для слушателей подготовит. курсов/О. В. Новоселов, Л. П. Скиба. СибГАУ, Красноярск, 2009. – 78 с.

Популярная комбинаторика. Виленкин Н. Я. М.: Наука, 1975. – 208 с. 

С. Н. Дроздов. Комбинаторные задачи и элементы теории вычислительной сложности: Учебное пособие. Таганрог: Изд-во ТРТУ, 2000. – 62с.

Сборник задач по математике для поступающих во втузы/В. К. Егерев, В. В. Зайцев, Б. А. Кордемский и др., под. ред. М. И. Сканави. – М.: Мир и образование, 2013.

Сканави М. И. Элементарная математика. 2-е изд., перераб. и доп., – М.: Наука, 1974 г.

Справочник по математики для средних учебных заведений. Цыпкин А. Г./Под ред. С. А. Степанова. – 3-е изд. – М.: Наука. Главная редакция физико-математической литературы, 1983. – 480 стр.

Статистика.Вероятность. Комбинаторика.БродскийЯ. С. М.: 2008.– 544 с.

Стойлова Л. П. Математика: Учебник для студ. высш. пед. учеб. Заведений. – М.: Издательский центр «Академия», 1999. – 424 стр.

Суханова, Н. В. Типовые расчеты: теория вероятностей: учебн.-метод. пособие: направление подг. 44.03.01 Педагогическое образование, направленность «Математика» (уровень бакалавриата)/Н. В. Суханова, Г. Р. Прозорова; Бюджет. Учреждение высш. Образования ХМАО-Югры «Сургут. пед. ун-т». – Сургут: РИО БУ «Сургутский государственный педагогический университет», 2017. – 173 с.

Теория вероятностей в примерах и задачах: Часть 1. Комбинаторика. Случайные события и их вероятности/Е. В. Михайлов, Н. Н. Патронова, В. В. Тепляков; САФ У имени М. В. Ломоносова. – Архангельск; САФУ, 2013 – 141 с.

Шишмарев Ю. Е. Дискретная математика: Конспект лекций. Ч. 1. – 2-е изд. – Владивосток: Изд-во ВГУЭС, 2001.

Яблонский С. В. Введение в дискретную математику. М.: Высшая школа, 2001.

Код для цитирования: Скопировать