А́лгебра — раздел математики, который можно нестрого охарактеризовать как обобщение и расширение арифметики; в этом разделе числа и другие математические объекты обозначаются буквами и другими символами, что позволяет записывать и исследовать их свойства в самом общем виде. Слово «алгебра» также употребляется в общей алгебре в названиях различных алгебраических систем. В более широком смысле под «алгеброй» понимают раздел математики, посвящённый изучению операций над элементами множеств произвольной природы, обобщающий обычные операции сложения и умножения чисел.
Вероя́тность — степень возможности наступления некоторого события. Когда основания для того, чтобы какое-нибудь возможное событие произошло в действительности, перевешивают противоположные основания, то это событие называют вероятным, в противном случае — маловероятным или невероятным. Перевес положительных оснований над отрицательными, и наоборот, может быть в различной степени, вследствие чего вероятность бывает большей либо меньшей. Поэтому часто вероятность оценивается на качественном уровне, особенно в тех случаях, когда более или менее точная количественная оценка невозможна или крайне затруднена. Возможны различные градации «уровней» вероятности.
Мно́жество — одно из ключевых понятий математики, представляющее собой набор, совоку́пность каких-либо объектов — элеме́нтов этого множества. Два множества равны тогда и только тогда, когда содержат в точности одинаковые элементы.
Комбинато́рика — раздел математики, посвящённый решению задач, связанных с выбором и расположением элементов некоторого множества в соответствии с заданными правилами. Каждое такое правило определяет некоторую выборку из элементов исходного множества, которая называется комбинаторной конфигурацией. Простейшими примерами комбинаторных конфигураций являются перестановки, сочетания и размещения.
Информацио́нная энтропи́я — мера неопределённости некоторой системы, в частности, непредсказуемость появления какого-либо символа первичного алфавита. В последнем случае при отсутствии информационных потерь энтропия численно равна количеству информации на символ передаваемого сообщения.
Аксио́мой вы́бора, англ. аббр. AC называется следующее высказывание теории множеств:
Ма́трица — математический объект, записываемый в виде прямоугольной таблицы элементов кольца или поля, который представляет собой совокупность строк и столбцов, на пересечении которых находятся его элементы. Количество строк и столбцов задаёт размер матрицы. Матрицу можно также представить в виде функции двух дискретных аргументов. Хотя исторически рассматривались, например, треугольные матрицы, в настоящее время говорят исключительно о матрицах прямоугольной формы, так как они являются наиболее удобными и общими.
Пра́вила Ки́рхгофа — соотношения, которые выполняются между токами и напряжениями на участках любой электрической цепи.
Правило сложения — одно из основных правил комбинаторики, утверждающее, что, если элемент A можно выбрать n способами, а элемент B можно выбрать m способами, то выбрать A или B можно n + m способами.
Кристаллографическая группа — дискретная группа движений -мерного евклидова пространства, имеющая ограниченную фундаментальную область.
Части́чно упоря́доченное мно́жество — математическое понятие, которое формализует интуитивные идеи упорядочения, расположения элементов в определённой последовательности. Неформально, множество частично упорядочено, если указано, какие элементы следуют за какими. В общем случае может оказаться так, что некоторые пары элементов не связаны отношением «следует за».
Теория групп — раздел общей алгебры, изучающий алгебраические структуры, называемые группами, и их свойства. Группа является центральным понятием в общей алгебре, так как многие важные алгебраические структуры, такие как кольца, поля, векторные пространства, являются группами с расширенным набором операций и аксиом. Группы возникают во всех областях математики, и методы теории групп оказывают сильное влияние на многие разделы алгебры. В процессе развития теории групп построен мощный инструментарий, во многом определивший специфику общей алгебры в целом, сформирован собственный глоссарий, элементы которого активно заимствуются смежными разделами математики и приложениями. Наиболее развитые ветви теории групп — линейные алгебраические группы и группы Ли — стали самостоятельными областями математики.
Конкатена́ция — операция склеивания объектов линейной структуры, обычно строк. Например, конкатенация слов «микро» и «мир» даст слово «микромир».
Ориента́ция — обобщение и формализация понятий направления обхода и направления на прямой на более сложные геометрические объекты, многообразия, векторные расслоения и так далее.
Взаимно простые числа — целые числа, не имеющие никаких общих делителей, кроме ±1. Равносильное определение: целые числа взаимно просты, если их наибольший общий делитель (НОД) равен 1.
Биективное доказательство — это техника доказательства, при которой находится биективная функция f : A → B между двумя конечными множествами A и B или сохраняющая размер биективная функция между двумя комбинаторными классами, чем доказывается одинаковость числа элементов, |A| = |B|. Место, где техника полезна — когда мы хотим знать размер A, но не можем найти прямого пути подсчёта элементов множества. В этом случае установление биекции между A и некоторым множеством B решает задачу, если число элементов множества B вычислить проще. Другое полезное свойство этой техники — природа биекции само по себе часто даёт мощную информацию о каждом из двух множеств.
Аддитивная комбинаторика — междисциплинарная область математики, изучающая взаимозависимость различных количественных интерпретаций понятия структурированности подмножества группы, а также аналогичные свойства производных от множества структур, использующихся при этих интерпретациях. Кроме того, аддитивная комбинаторика изучает структурированность в различных смыслах некоторых специфических множеств или классов множеств.
Теория комбинаторных схем — это часть комбинаторики, рассматривающая существование, построение и свойства семейств конечных множеств, структура которых удовлетворяет обобщённым концепциям равновесия и/или симметрии. Эти концепции не определены точно, так что объекты широкого диапазона могут пониматься как комбинаторные схемы. Так, в одном случае комбинаторные схемы могут представлять собой пересечения множеств чисел, как в блок-схемах, а в другом случае могут отражать расположение элементов в судоку.
При доказательстве комбинаторных теорем обычно признаются и используются несколько полезных комбинаторных правил, или комбинаторных принципов. Примеры:
- Правило сложения, правило умножения и принцип включения-исключения часто используются для целей перечисления.
- Принцип Дирихле часто устанавливает существование чего-либо или используется для определения минимального либо максимального количества чего-либо в дискретном контексте.
- Биективное доказательство используется, чтобы убедиться, что два множества имеют одинаковое количество элементов.
- Многие комбинаторные тождества возникают из метода двойного счёта или метода выделенного элемента.
- Производящие функции и рекуррентные соотношения — мощные инструменты, которые можно использовать для управления последовательностями, и они могут быть полезны при исследовании многих комбинаторных ситуаций.