Теория комбинаторных схем — это часть комбинаторики (раздела математики), рассматривающая существование, построение и свойства семейств конечных множеств, структура которых удовлетворяет обобщённым концепциям равновесия и/или симметрии. Эти концепции не определены точно, так что объекты широкого диапазона могут пониматься как комбинаторные схемы. Так, в одном случае комбинаторные схемы могут представлять собой пересечения множеств чисел, как в блок-схемах, а в другом случае могут отражать расположение элементов в судоку.

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

Определение Обозначим - множество элементов . Рассмотрим подмножества этого множества . Каждое подмножество называется блоком, а число элементов множества в нем называется объемом блока и обозначается как . Пусть - число подмножеств , содержащих этот элемент. Число повторений (неупорядоченных пар) обозначается как . Тогда множество блоков образует комбинаторную схему (или блок-схему) с параметрами .

Пример

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

Ответ положителен, только если n имеет вид q2 + q + 1. Сложнее доказать, что решение существует, если q является степенью простого числа. Существует гипотеза, что других решений нет. Было доказано, что если решение существует для q, сравнимых с 1 или 2 по модулю 4, то q является суммой двух полных квадратов. Этот результат, теорема Брука — Райзера — Човла, был доказан путём комбинации методов построения, основывающихся на конечных полях, и квадратичных формах.

Когда такая структура существует, она называется конечной проективной плоскостью. Это показывает, как пересекаются теория конечных геометрий и комбинаторика. В случае q = 2, проективная плоскость называется плоскостью Фано.

История Комбинаторные схемы известны ещё со времён античности в виде квадрата Ло Шу, который являлся ранней версией магического квадрата. Комбинаторные схемы развивались с развитием комбинаторики начиная с 18-го столетия, например, в виде латинских квадратов в 18-м веке и систем Штейнера в 19-м веке. Комбинаторные схемы популярны также в занимательной математике, как, например, в задаче Киркмана о школьницах (1850), и практических задачах, таких как составление расписания круговых турниров (решение опубликовано в 1880-х годах). В 20-м веке комбинаторные схемы были применены к планированию экспериментов, конечным геометриям и схемам отношений и привели к возникновению .

Фундаментальные комбинаторные схемы

Классическое ядро предмета комбинаторных схем строится вокруг сбалансированных неполноблочных схем (en:Balanced Incomplete Block Design, BIBD), матриц и схем Адамара, симметричных BIBD, латинских квадратов, разрешимых BIBD, и попарно сбалансированных схем (en: Pairwise Balanced Design, PBD). Другие комбинаторные схемы связаны с перечисленными или основываются на этих схемах.

Сбалансированная неполноблочная схема (BIBD), которую для краткости называют блок-схемами, это набор B из b подмножеств (которые называются блоками) конечного множества X из v элементов, такой, что любой элемент множества X содержится в некотором числе r блоков, каждый блок имеет одинаковое число элементов (= k) и каждая пара различных элементов появляется в одинаковом числе () блоков. Схемы BIBD известны также как 2-схемы и часто обозначаются как схемы. В качестве примера, для случая и b = v мы получаем проективную плоскость — X в этом случае является множеством точек на плоскости, а блоки являются прямыми. Симметричная сбалансированная неполноблочная схема или SBIBD (en:Symmetric Balanced Incomplete Block Design) — это BIBD, в которой v  =  b (число точек равно числу блоков). Это наиболее важный и хорошо изученный подкласс BIBD. Проективные плоскости, биплоскости и 2-схемы Адамара являются SBIBD-схемами. Эти схемы представляют интерес как экстремальные примеры неравенства Фишера (). Разрешимая сбалансированная неполная блок-схема — это BIBD, блоки которого могут быть разбиты на множества (называемые параллельными классами), каждое из которых образует разбиение точек BIBD. Множество параллельных классов называется разрешением схемы. Решение знаменитой задачи о 15 школьниках является разрешением BIBD с v  = 15, k  = 3 и . — это r × n ( r ≤ n) матрица, имеющая в качестве элементов числа 1, 2, 3, ..., n (или любое другое множество n различных символов), в которой никакое число не появляется дважды в любой строке или столбце. Латинский прямоугольник с размерами n × n называется латинским квадратом. Если r < n, то можно добавить n − r строк к латинскому прямоугольнику с размерами r × n, чтобы сформировать латинский квадрат, используя теорему Холла о свадьбах theorem.

Говорят, что два латинских квадрата порядка n ортогональны если множество всех упорядоченных пар, состоящих из соответствующих элементов двух квадратов, состоит из n2 различных пар (то есть встречаются все возможные упорядоченные пары). Множество латинских квадратов одного порядка образует множество взаимно ортогональных латинских квадратов (en: Mutually Orthogonal Latin Squares, MOLS)), если любая пара латинских квадратов в множестве ортогональна. Может существовать максимум n − 1 квадратов в таком множестве квадратов порядка n. Множество n − 1 квадратов MOLS порядка n можно использовать для построения проективной плоскости порядка n (и наоборот).

— это подмножество D группы G порядка v, имеющее размер k, а любой не равный единице элемент группы G может быть представлен в виде произведения d1d2−1 элементов D в точности способами (если G представлено операцией умножения)Если G — абелева группа (или записывается с операцией сложения) определение приобретает вид d1 –d2, откуда и возник термин разностное множество..

Если D — разностное множество и g принадлежит G, то также является разностным множеством и называется переносом множества D. Множество переносов разностного множества D образует симметричную блок-схему. В такой схеме имеется v элементов и v блоков. Каждый блок схемы состоит из k точек, каждая точка содержится в k блоках. Любые два блока имеют в точности общих элементов и любые две точки появляются вместе в блоках. Эта схема SBIBD называется развитием множества D.

В частности, если , разностное множество образует проективную плоскость. Например, разностное множество (7,3,1) над группой (абелева группа с аддитивной записью) — это подмножество {1,2,4}. Развитие этого разностного множества даёт плоскость Фано. Поскольку любое разностное множество даёт SBIBD, множество параметров должно удовлетворять теореме Брука – Райзера – Човла, но не любая SBIBD-схема даёт разностное множество.

Матрица Адамара порядка m — это m × m матрица H с элементами ±1, такая, что HH⊤  = mEm, где H⊤ является транспонированной к H, а Em — m × m единичная матрица. Матрицу Адамара можно привести к стандартизованной форме (то есть преобразовать в эквивалентную матрицу Адамара), в которой элементы первой строки и первого столбца равны +1. Если порядок m > 2, то m должно делиться на 4.

Если дана матрица Адамара порядка 4a в стандартизованной форме, удалим первую строку и первый столбец, а затем заменим все −1 на 0. Получившаяся 0–1 матрица M является матрицей инцидентности симметричной схемы, называемой адамаровой 2-схемой. Это построение обратимо, так что матрица инцидентности симметричной 2-схемы с такими параметрами может быть использована для получения матрицы Адамара порядка 4a. В случае a = 2 мы получаем уже знакомую плоскость Фано (как 2-схему Адамара).

Попарно сбалансированная схема (en:Pairwise Balanced Design, PBD) — это множество X вместе с семейством подмножеств X (не обязательно одного размера и подмножества могут быть одинаковыми), таком, что любая пара различных элементов из X содержится точно в (положительное число) подмножеств. Разрешается, чтобы множество X входило в семейство, а если все подмножества являются копиями множества X, схема PBD называется тривиальной. Размер множества X равен v, а число подмножеств в семействе (одинаковые подмножества подсчитываются отдельно) равно b.

Неравенство Фишера для схем PBD выполняется — для любой нетривиальной PBD-схемы выполняется .

Этот результат обобщает знаменитую теорему де Брёйна — Эрдёша — для любой PBD-схемы с , не имеющей блоков размера 1 или v, выполняется , при этом равенство имеет место тогда и только тогда, когда схема является проективной плоскостью или почти пучком.

Другие комбинаторные схемы Книга «Handbook of Combinatorial Designs» (справочник по комбинаторным схемам) Колбурна и Диница содержит, среди прочих, 65 глав, посвящённых комбинаторным схемам, отличным от приведённых выше. Частичный список дан ниже.

Сбалансированные троичные схемы (en: Balanced Ternary Design) — расстановка V элементов в B мультимножеств (блоков, мощность каждого множества K (K ≤ V)), удовлетворяющая условиям: Каждый элемент появляется раз с кратностью 1 (1 экземпляр в мультимножестве) точно в блоках, а с кратностью 2 — точно в блоках. Каждая пара различных элементов появляется раз (учитывая кратность). То есть, если mvb — кратность элемента v в блоке b, то для любой пары различных элементов v и w выполняется . Например, одна из двух неизоморфных схем BTD(4,8;2,3,8;4,6) (блоками служат столбцы) — это 1 1 1 2 2 3 1 1 1 1 1 2 2 3 2 2 2 3 4 3 4 4 3 3 2 3 4 3 4 4 4 4 Матрица инцидентности BTD схемы (элементами которой служат кратности элементов в блоках) может быть использована для образования троичных исправляющих ошибки кодов аналогично построению двоичных кодов из матриц инцидентности BIBD схем.

порядка n (BTD(n)) — это размещение всех различных неупорядоченных пар 2n-множества V в массиве n × (2n − 1), такое что каждый элемент множества V появляется ровно один раз в каждом столбце каждый элемент множества V появляется не более двух раз в каждой строке. Пример схемы BTD(3) 1 6 3 5 2 3 4 5 2 4 2 5 4 6 1 4 1 3 3 6 3 4 1 2 5 6 2 6 1 5 Столбцы схемы BTD(n) дают 1-факторизацию полного графа с 2n вершинами, K2n. Схемы BTD(n) могут быть использованы для составления расписания круговых турниров — строки представляют места, столбцы представляют туры (раунды, круги), а элементы таблицы задают игроков или команды.

Бент-функции Массивы Костаса Полные факторные эксперименты Частотный квадрат (F-квадрат) является обобщением латинского квадрата. Пусть S = {s1,s2, ..., sm} — множество различных символов, а — частотный вектор положительных чисел. Частотный квадрат порядка n — это n × n массив, в котором каждый символ si встречается раз (i = 1,2,...,m) в каждой строке и в каждом столбце. Частотный квадрат имеет стандартный вид, если в первой строке и первом столбце элементы si предшествуют sj при i < j. Частотный квадрат F1 порядка n над множеством {s1,s2, ..., sm} с частотным вектором и частотный квадрат F2 также порядка n над множеством с частотным вектором ортогональны, если любая упорядоченная пара (si, tj) появляется ровно раз, когда F1 и F2 налагаются друг на друга.

Системы троек Холла (en:Hall Triple Systems, HTS) — это системы троек Штейнера (en:Steiner Triple Systems, STS) (в ней блоки называются прямыми) со свойством, что подструктура, образованная пересечением двух прямых изоморфна конечной аффинной плоскости AG(2,3). Любое аффинное пространство AG(n,3) даёт пример схемы HTS, такие схемы называются аффинными HTS. Неаффинные схемы HTS также существуют.