Теорія комбінаторних схем — частина комбінаторики (розділу математики), що розглядає існування, побудову та властивості сімейств скінченних множин, структура яких задовольняє узагальненим концепціям рівноваги та/або симетрії. Ці концепції точно не визначені, так що розглядатися як комбінаторні схеми можуть об'єкти широкого діапазону. Так, в одному випадку комбінаторні схеми можуть являти собою перетини числових множин, як у блок-схемах, а в іншому випадку можуть відображати розташування елементів у судоку.
Теорію комбінаторних схем можна використовувати при плануванні експериментів. Деякі з основних комбінаторних схем наведено в роботі Рональда Фішера з теорії біологічних експериментів. Зараз комбінаторні схеми можна знайти в багатьох галузях, зокрема в скінченній геометрії, створенні графіків турнірів, лотереях, математичній біології, розробці та аналізі алгоритмів, обчислювальних мережах, та криптографії.
Визначення Нехай — множина елементів . Розподілимо елементи цієї множини за підмножинами , перетин яких не обов'язково порожній. Кожну підмножину назвемо блоком, а число елементів множини в ньому — об'ємом блоку . Елемент може потрапити в декілька блоків. Нехай — число підмножин , що містять елемент . Число повторень (невпорядкованих пар) позначимо як . Тоді множина блоків утворює комбінаторну схему (або блок-схему) із параметрами .
Приклад
Якщо є n людей, чи можна скласти з них множини, такі, щоб кожна людина належала принаймні одній множині, кожна пара належала рівно одній множині, кожні дві множини мали в перетині тільки одну людину і жодна з множин не складалася зі всіх людей, всіх людей без однієї чи рівно однієї людини? Відповідь залежить від n.
Відповідь позитивна, якщо n має вигляд q2 + q + 1. Складніше довести, що розв'язок існує, якщо q є степенем простого числа. Існує гіпотеза, що інших розв'язків немає. Доведено, що якщо розв'язок існує для q порівнянних з 1 або 2 за модулем 4 то q є сумою двох повних квадратів. Цей результат, теорему Брука — Райзера — Човли, доведено комбінуванням методів побудови, що ґрунтуються на скінченних полях, та застосування квадратичних форм.
Коли така структура існує, її називають скінченною проєктивною площиною. Це показує, як перетинаються теорія скінченних геометрій та комбінаторика. У разі q = 2, проєктивну площину називають площиною Фано.
Історія Комбінаторні схеми відомі ще з часів античності у вигляді квадрата Ло Шу, ранньої версії магічного квадрата. Комбінаторні схеми розвивалися з розвитком комбінаторики починаючи від XVIII століття, наприклад, у вигляді латинських квадратів у XVIII столітті та систем Штейнера у XIX столітті. Комбінаторні схеми популярні також у цікавій математиці, як, наприклад, у задачі Кіркмана про школярок (1850), і практичних задачах, таких як складання розкладу кругових турнірів (розв'язок опубліковано в 1880-х роках). У XX столітті комбінаторні схеми застосовано до планування експериментів, скінченних геометрій і схем відношень, вони привели до виникнення .
Фундаментальні комбінаторні схеми Класичне ядро предмету комбінаторних схем будується навколо зрівноважених неповних блок-схем (), матриць і схем Адамара, симетричних BIBD, латинських квадратів, розв'язних BIBD, і попарно зрівноважених схем (). Інші комбінаторні схеми пов'язані з переліченими або ґрунтуються на цих схемах.
Зрівноважена неповна блок-схема (BIBD), яку для стислості називають блок-схемами, це набір B з b підмножин (які називаються блоками) скінченної множини X з елементів v, такий, що будь-який елемент множини X міститься в деякому числі r блоків, кожен блок має однакове число елементів (= k) і кожна пара різних елементів з'являється в однаковій кількості () блоків. Схеми BIBD відомі також як 2-схеми і часто позначаються як -схеми. Як приклад, для випадку і b = v отримуємо проєктивну площину — X у цьому випадку є множиною точок на площині, а блоки — прямими. Симетрична зрівноважена неповна блок-схема або SBIBD () — це 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, то до латинського прямокутника з розмірами r × n можна додати n − r рядків, щоб сформувати латинський квадрат, використовуючи теорему Холла про весілля.
Кажуть, що два латинські квадрати порядку n ортогональні, якщо множина всіх упорядкованих пар, що складаються з відповідних елементів двох квадратів, складається з n2 різних пар (тобто зустрічаються всі можливі впорядковані пари). Множина латинських квадратів одного порядку утворює множину взаємно ортогональних латинських квадратів (), якщо будь-яка пара латинських квадратів у множині ортогональна. У такій множині квадратів порядку n може існувати максимум n − 1 квадратів. Множина 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, а E m — m × m одинична матриця. Матрицю Адамара можна звести до стандартизованої форми (тобто перетворити на еквівалентну матрицю Адамара), в якій елементи першого рядка і першого стовпця рівні +1. Якщо порядок m > 2, то m має ділитися на 4.
Якщо дано матрицю Адамара порядку 4a в стандартизованій формі, видалимо перший рядок і перший стовпець, а потім замінимо всі −1 на 0. 0–1 матриця M, що вийшла, є матрицею інцидентності симетричної -схеми, званої адамаровою 2-схемою. Ця побудова оборотна, так що матрицю інцидентності симетричної 2-схеми з такими параметрами можна використати для отримання матриці Адамара порядку 4a. У разі a = 2 отримуємо вже знайому площину Фано (як 2-схему Адамара).
Попарно зрівноважена схема () — це множина X разом із сімейством підмножин X (не обов'язково одного розміру і підмножини можуть бути однаковими), таким, що будь-яка пара різних елементів з X міститься рівно в (додатне число) підмножин. Дозволено, щоб множина X входила в сімейство, а якщо всі підмножини є копіями множини X, схему PBD називають тривіальною. Розмір множини X дорівнює v, а число підмножин у сімействі (однакові підмножини підраховують окремо) дорівнює b.
Нерівність Фішера для схем PBD виконується — для будь-якої нетривіальної PBD-схеми виконується .
Цей результат узагальнює знамениту теорему де Брейна — Ердеша: для будь-якої PBD-схеми з , яка не має блоків розміру 1 або v, виконується , при цьому рівність має місце тоді й лише тоді, коли схема є проєктивною площиною або майже пучком.
Інші комбінаторні схеми Книга «Handbook of Combinatorial Designs» (Довідник з комбінаторних схем) Колбурна і Диніца містить, серед інших, 65 розділів, присвячених комбінаторним схемам, відмінним від наведених вище. Нижче перелічено деякі з них.
Зрівноважені трійкові схеми () — розстановка 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 .
Частотний квадрат F 1 порядку n над множиною {s1, s2, …, sm} з частотним вектором і частотний квадрат F2 також порядку n над множиною із частотним вектором ортогональні, якщо будь-яка впорядкована пара (si, tj) з'являється рівно разів, коли F1 і F2 накласти один на одного.
Системи трійок Голла () — це системи трійок Штейнера () (у ній блоки називають прямими) з властивістю, що підструктура, утворена перетином двох прямих ізоморфна скінченній афінній площині AG(2,3).
Будь-який афінний простір AG(n,3) дає приклад схеми HTS, такі схеми називають афінними HTS. Неафінні схеми HTS також існують. Число точок у схемі HTS дорівнює 3m для деякого цілого . Неафінні схеми HTS існують для будь-якого і не існують для або 3. Будь-яка система трійок Штейнера еквівалентна штейнерівській квазігрупі (ідемпотентна, коммутативна і виконується для всіх x та y). Система трійок Голла еквівалентна штейнерівській квазігрупі з властивістю дистрибутивності, тобто виконується для всіх a, x, y у квазігрупі .
Нехай S — множина з 2n елементів. Схема Гавелла, H(s,2n) (на множині символів S) — це масив s × s, такий, що:
кожна комірка масиву або порожня, або містить невпорядковану пару з S, кожен символ з'являється рівно один раз у кожному рядку і кожному стовпці масиву, кожна невпорядкована пара з'являється не більше ніж в одній комірці масиву.
Приклад схеми H(4,6): 0 4 1 3 2 5 2 3 1 4 0 5 3 5 2 4 0 1 1 5 0 2 3 4