Комбинаторика — раздел математики. Основные понятия и формулы комбинаторики как науки применяются во всех сферах жизни.
Неудивительно, что она включена в программу 11 класса, а также во вступительные испытания во многих ВУЗах РФ. Ее основы лежат в прикладном искусстве многих сфер деятельности человека.
Ее история насчитывает более 6 веков. Первые комбинаторные задачи появились в трудах философов и математиков Средневековья.
Представители того научного мира пытались найти методы решения таких задач, их базовые правила и понятия, утвердить уникальные формулы и уравнения для тех, кто ещё не встречался с ними. Такая информация в наше время называется информацией «для чайников».
Попытаемся разобраться в аспектах этой области науки: каковы элементы, свойства, правила, методы и основное ее применение в нашей жизни? Конечно, всю область в одной статье невозможно охватить. Поэтому ниже будет представлено всё самое основное.
Что такое комбинаторика в математике
Суть этого термина дают книги прошлых лет: это раздел математики, занимающийся операциями со множеством элементов.
В интернете есть учебники по информатике и математике для детей, школьников, сборники материалов и задач для начинающих, где в доступном виде объяснена «занимательная» комбинаторика. Нужно твердо выяснить, как решать подобные задачи.
В младших классах задачи на эту тему решают на дополнительных кружках, а в школах с углубленным изучением математики на основных уроках. К тому же, задачи по комбинаторике включены в олимпиады всех уровней.
Основные понятия
Их несколько:
- Элемент – любой объект или явление, входящий в искомое множество.
- Сочетание – подмножества, находящиеся в произвольном порядке в исходном множестве.
- Перестановка – элементы во множестве находятся в строго определенном порядке.
- Размещение – упорядоченные подмножества в исходном множестве.
Правило произведения
Является одним из основных правил при решении таких задач и звучит так:
При выборе элемента А из n способов и выборе элемента В из m способов верно утверждение, что выбрать пару А и В одновременно можно n*m способами.
Рассмотрим на конкретных примерах.
Задача №1.
В коробке лежит 2 мяча и 6 скакалок. Сколько существует способов достать 1 мяч и 1 скакалку?
Ответ прост: 2 * 6 = 12.
Задача №2.
Есть 1 кубик, 2 шарика, 3 цветка и 4 конфеты. Сколькими способами можно вытянуть кубик, шарик, цветок и конфету?
Решение аналогично: 1 * 2 * 3 * 4 = 24.
Причем левую часть можно записать гораздо проще: 4!
! в данном случае является не знаком препинания, а факториалом. С помощью него можно вычислить более сложные варианты и решать трудные задачи (существуют разные формулы, но об этом позже).
Задача №3.
Сколько двузначных чисел можно составить из 2 цифр?
Ответ: 2! = 2.
Задача №4.
Сколько десятизначных чисел можно составить из 10 цифр?
10! = 3628800.
Правило суммы
Тоже является базовым правилом комбинаторики.
Если А можно выбрать n раз, а В — m раз, то А или В можно выбрать (n + m) раз.
Задача №5.
В коробке лежат 5 красных, 3 желтых, 7 зеленых, 9 черных карандашей. Сколько есть способов вытащить 1 любой карандаш?
Ответ: 5 + 3 + 7 + 9 = 24.
Сочетания с повторениями и без повторений
Под этим термином понимают комбинации в произвольном порядке из множества n по m элементов.
Число сочетаний равно количеству таких комбинаций.
Задача №6.
В коробке находится 4 разных фрукта. Сколькими способами можно достать одновременно 2 разных фрукта?
Решение простое:
Где 4! – комбинация из 4 элементов.
С повторениями чуть сложней, комбинации считаются по такой формуле:
Задача №7.
Возьмем тот же самый случай, но при условии, что один фрукт возвращается в коробку.
В этом случае:
Размещения с повторениями и без повторений
Под этим определением понимают набор m элементов из множества n элементов.
Задача №8.
Из 3 цифр надо выбрать 2, чтобы получались разные двузначные числа. Сколько вариантов?
Ответ прост:
А как же быть с повторениями? Здесь каждый элемент может размещаться несколько раз! В таком случае общая формула будет выглядеть следующим образом:
Задача №9.
Из 12 букв латинского алфавита и 10 цифр натурального ряда надо найти все варианты составления автомобильного кода региона.
Решение:
Перестановки с повторениями и без повторений
Под этим термином понимают все возможные комбинации из n элементного множества.
Задача №10.
Сколько возможных пятизначных чисел можно составить из 5цифр? А шестизначных из 6 цифр? Семизначных из 7 цифр?
Решения, согласно вышеприведенной формуле, следующие:
5! = 120,
6! = 720,
7! = 5040.
А как же быть с повторениями? Если в таком множестве есть одинаковые по своей значимости элементы, то перестановок будет меньше!
Задача №11.
В коробке есть 3 одинаковых карандаша и одна ручка. Сколько перестановок можно сделать?
Ответ прост: 4! / (3! * 1!) = 4.
Комбинаторные задачи с решениями
Примеры всех возможных типов задач с решениями были даны выше. Здесь попробуем разобраться с более сложными случаями, встречающимися в нашей жизни.
Типы задач | Что требуется найти | Методы решения |
Магический квадрат | Фигура, в которой сумма чисел в рядах и столбцах должна быть одинакова (его разновидность – латинский квадрат). | Рекуррентные соотношения. Решается подобная же задача, но с гораздо меньшим множеством элементов по известным правилам и формулам. |
Задача размещения | Стандартная производственная задача (например, в лоскутной технике) найти возможные способы разложения количества продуктов в ячейки в определенном порядке. | Включения и исключения. Как правило, применяется при доказательстве различных выражений. |
Задачи про торговцев | Суть найти все возможные пути прохождения людей из пункта А в пункт В. | Траектории. Для этого вида задач характерно геометрическое построение возможных способов решения. |
Заключение
Стоит изучать эту науку, поскольку в век быстрой модернизации технологий потребуются специалисты, способные предоставить различные решения тех или иных практических задач.