Теорія комбінаторних схем — частина комбінаторики (розділу математики), що розглядає існування, побудову та властивості сімейств скінченних множин, структура яких задовольняє узагальненим концепціям рівноваги та/або симетрії. Ці концепції точно не визначені, так що розглядатися як комбінаторні схеми можуть об'єкти широкого діапазону. Так, в одному випадку комбінаторні схеми можуть являти собою перетини числових множин, як у блок-схемах, а в іншому випадку можуть відображати розташування елементів у судоку.
Нехай — множина елементів . Розподілимо елементи цієї множини за підмножинами , перетин яких не обов'язково порожній. Кожну підмножину назвемо блоком, а число елементів множини в ньому — об'ємом блоку . Елемент може потрапити в декілька блоків. Нехай — число підмножин , що містять елемент . Число повторень (невпорядкованих пар) позначимо як . Тоді множина блоків утворює комбінаторну схему (або блок-схему) із параметрами [2].
Приклад
Якщо є n людей, чи можна скласти з них множини, такі, щоб кожна людина належала принаймні одній множині, кожна пара належала рівно одній множині, кожні дві множини мали в перетині тільки одну людину і жодна з множин не складалася зі всіх людей, всіх людей без однієї чи рівно однієї людини? Відповідь залежить від n.
Зрівноважена неповна блок-схема (BIBD), яку для стислості називають блок-схемами, це набір B з b підмножин (які називаються блоками) скінченної множини X з елементів v, такий, що будь-який елемент множини X міститься в деякому числі r блоків, кожен блок має однакове число елементів (= k) і кожна пара різних елементів з'являється в однаковій кількості () блоків[2]. Схеми BIBD відомі також як 2-схеми і часто позначаються як -схеми. Як приклад, для випадку і b = v отримуємо проєктивну площину — X у цьому випадку є множиною точок на площині, а блоки — прямими.
Симетрична зрівноважена неповна блок-схема або SBIBD (англ.Symmetric Balanced Incomplete Block Design) — це BIBD, у якій v = b (кількість точок дорівнює кількості блоків). Це найважливіший та добре вивчений підклас BIBD. Проєктивні площини, біплощини та 2-схеми Адамара є SBIBD-схемами. Ці схеми цікаві, як екстремальні приклади нерівності Фішера ().
Розв'язназрівноважена неповна блок-схема — це BIBD, блоки якої можна розбити на множини (звані паралельними класами), кожна з яких утворює розбиття точок BIBD[2]. Множину паралельних класів називають роздільністю схеми. Розв'язок знаменитої задачі про 15 школярок є роздільністю BIBD з v = 15, k = 3 та [4].
Латинський прямокутник[en] — це r × n ( r ≤ n) матриця, що має як елементи числа 1, 2, 3, …, n (або будь-яку іншу множну n різних символів), у якій жодне число не з'являється двічі у будь-якому рядку чи стовпці. Латинський прямокутник із розмірами n × n називають латинським квадратом. Якщо r < n, то до латинського прямокутника з розмірами r × n можна додати n − r рядків, щоб сформувати латинський квадрат, використовуючи теорему Холла про весілля[5].
Кажуть, що два латинські квадрати порядку nортогональні, якщо множина всіх упорядкованих пар, що складаються з відповідних елементів двох квадратів, складається з n2 різних пар (тобто зустрічаються всі можливі впорядковані пари). Множина латинських квадратів одного порядку утворює множину взаємно ортогональних латинських квадратів (англ.Mutually Orthogonal Latin Squares, MOLS), якщо будь-яка пара латинських квадратів у множині ортогональна. У такій множині квадратів порядку n може існувати максимум n − 1 квадратів. Множина n − 1 квадратів MOLS порядку n можна використати для побудови проєктивної площини порядку n (і навпаки).
Різницева множина[en] — це підмножинаDгрупиGпорядкуv, що має розмірk, а будь-який не рівний одиниці елемент групи G можна подати у вигляді добутку d1d2−1 елементів D рівно способами (якщо G подано операцією множення)[6].
Якщо D — різницева множина і g належить G, то також є різницевою множиною і називається переносом множини D. Множина переносів різницевої множини D утворює симетричну блок-схему. В такій схемі є v елементів та v блоків. Кожен блок схеми складається з k точок, кожна точка міститься в k блоках. Будь-які два блоки мають рівно загальних елементів та будь-які дві точки з'являються разом у блоках. Цю схему SBIBD називають розвитком множини D[7].
Зокрема, якщо , різницева множина утворює проєктивну площину. Наприклад, різницева множина (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-схемою[8]. Ця побудова оборотна, так що матрицю інцидентності симетричної 2-схеми з такими параметрами можна використати для отримання матриці Адамара порядку 4a. У разі a = 2 отримуємо вже знайому площину Фано (як 2-схему Адамара).
Попарно зрівноважена схема (англ.Pairwise Balanced Design, PBD) — це множина X разом із сімейством підмножин X (не обов'язково одного розміру і підмножини можуть бути однаковими), таким, що будь-яка пара різних елементів з X міститься рівно в (додатне число) підмножин. Дозволено, щоб множина X входила в сімейство, а якщо всі підмножини є копіями множини X, схему PBD називають тривіальною. Розмір множини X дорівнює v, а число підмножин у сімействі (однакові підмножини підраховують окремо) дорівнює b.
Нерівність Фішера для схем PBD виконується[9] — для будь-якої нетривіальної PBD-схеми виконується .
Книга «Handbook of Combinatorial Designs» (Довідник з комбінаторних схем) Колбурна і Диніца[11] містить, серед інших, 65 розділів, присвячених комбінаторним схемам, відмінним від наведених вище. Нижче перелічено деякі з них.
Зрівноважені трійкові схеми (англ.Balanced Ternary Design) — розстановка V елементів у Bмультимножин (блоків, потужність кожної множини K (K ≤ V)), що задовольняє умовам:
Кожен елемент з'являється разів із кратністю 1 (1 примірник у мультимножині) рівно в блоках, а з кратністю 2 — рівно в блоках.
Кожна пара різних елементів з'являється разів (з урахуванням кратності). Тобто, якщо mvb — кратність елемента v в блоці b, то для будь-якої пари різних елементів v і w виконується .
Наприклад, одна з двох неізоморфних схем BTD(4,8;2,3,8;4,6) (блоками слугують стовпці) — це[12]
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-схем[13].
Зрівноважена турнірна схема порядку n (BTD(n)) — це розміщення всіх різних невпорядкованих пар 2n-множини V в масиві n × (2n − 1), таке що:
кожен елемент множини V з'являється рівно один раз у кожному стовпці;
кожен елемент множини V з'являється не більше двох разів у кожному рядку.
Схеми 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 накласти один на одного.
Системи трійок Голла (англ.Hall Triple Systems, HTS) — це системи трійок Штейнера (англ.Steiner Triple Systems, STS) (у ній блоки називають прямими) з властивістю, що підструктура, утворена перетином двох прямих ізоморфна скінченній афінній площині AG(2,3).
Будь-який афінний простір AG(n,3) дає приклад схеми HTS, такі схеми називають афінними HTS. Неафінні схеми HTS також існують.
Число точок у схемі HTS дорівнює 3m для деякого цілого . Неафінні схеми HTS існують для будь-якого і не існують для або 3[15].
Будь-яка система трійок Штейнера еквівалентна штейнерівській квазігрупі (ідемпотентна, коммутативна і виконується для всіх x та y). Система трійок Голла еквівалентна штейнерівській квазігрупі з властивістю дистрибутивності, тобто виконується для всіх a, x, y у квазігрупі [16] .
Нехай 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
H(2 n − 1, 2 n) — це квадрат Рума[en] зі стороною 2n − 1, тому схеми Гавелла узагальнюють концепцію квадратів Рума.
Пари символів у комірках схеми Гавелла можна розглядати, як ребра s регулярного графа з 2n вершинами, який називають основним графом схеми Гавелла.
Циклічні схеми Гавелла використовують як пересування Гавелла (схема комплектування учасників ігор) у турнірах подвійного бриджу. Рядки схеми подають тури (кола), стовпці подають коробки (з заздалегідь підготовленими роздачами, див. «Бридж — Роздача»), а діагоналі подають столи[17].
Схема лото (n,k,p,t) — це множина V з n елементів разом з набором k-елементних підмножин (блоків), таких, що для будь-якої підмножини P, що складається з p елементів множини V, існує блок B в , для котрого . L(n,k,p,t) означає найменше число блоків у будь-якій схемі лото (n,k,p,t). Схема лото (7,5,4,3) з найменшим можливим числом блоків[18]:
{1,2,3,4,7} {1,2,5,6,7} {3,4,5,6,7}.
Схема лото моделює будь-яку лотерею, що працює за такими правилами. Гравець купує квитки, що містять k чисел, вибрані з множини, що містить n чисел. У деякий момент часу продаж квитків припиняють та вибирають випадковий набір з p чисел, що належать початковій множині з n чисел. Це виграшні числа. Якщо проданий квиток містить t або більше виграшних номерів, власнику квитка надається приз. Що більше збігів, то вищий виграш. Число L(n,k,p,t) цікаве як для гравців, так і для дослідників, оскільки представляє найменшу кількість квитків, які слід купити, щоб гарантувати виграш.
Угорська лотерея — це схема лото (90,5,5,t) і відомо, що L(90,5,5,2) = 100. Лотереї з параметрами (49,6,6,t) популярні у всьому світі і відомо, що L(49,6,6,2) = 19. У загальному випадку ці числа складно обчислити і вони залишаються невідомими[19].
Схема Мендельсона () — це множина V з v елементів і набір упорядкованих k-кортежів різних елементів множини V (званих блоками), таких, що кожна впорядкована пара (x,y) елементів з V (x ≠ y) циклічно суміжна в блоках (упорядкована пара (x,y) різних елементів циклічно суміжна в блоці, якщо елементи з'являються в блоці поруч — або (…,x,y,…), або (y,…,x)). Схема — це система трійок Мендельсона, що має позначення MTS. Приклад MTS(4,1) над V = {0,1,2,3}:
(0,1,2) (1,0,3) (2,1,3) (0,2,3): Будь-яку систему трійок можна перетворити на систему трійок Мендельсона, замінивши невпорядковану трійку {a,b,c} парою впорядкованих трійок (a,b,c) і (a,c,b), але зворотне, як показує приклад, хибне.
Нехай (Q,∗) — ідемпотентна напівсиметрична квазігрупа, тобто в ній виконується x ∗ x = x (ідемпотентність) і x ∗ (y ∗ x) = y (напівсиметричність) для всіх x, y з Q. Нехай . Тоді є системою трійок Мендельсона MTS(|Q|,1). Ця побудова оборотна[20].
Квазі-3 схема — це симетрична схема (SBIBD), в якій кожна трійка блоків перетинається або в x, або в y точках для фіксованих чисел x і y, званих числами перетинів трійок (x < y). Будь-яка симетрична схема з є квазі-3 схемою з і . Схема точка-гіперплощина геометрії PG(n,q) є квазі-3 схемою з і . Якщо для квазі-3 схеми, схема ізоморфна PG(n,q) або проєктивній площині[21].
Схема є квазісиметричною з числами перетину x і y (x < y), якщо будь-які два різних блоки мають у перетині або x або y точок. Ці схеми виникають природно при вивченні двоїстих схем з . Несиметрична схема (b > v) 2-(v,k,1) є квазісиметричною з x = 0 і y = 1. Кратні (блоки повторюються певне число разів) симетричні 2- схеми квазісиметричні з і y = k. 3-схеми Адамара (розширення 2-схем Адамара) квазісиметричні[22].
Тосканський r × nk-прямокутник над n символами має r рядків і n стовпців, при цьому:
кожен рядок є перестановкою n символів;
для будь-яких двох різних символів a і b і для кожного числа m від 1 до k існує не більше одного рядка, в якому b міститься за m кроків правіше від a.
Якщо r = n і k = 1, схеми називають тосканськими квадратами, а в разі r = n і k = n — 1 їх називають флорентійськими квадратами. Римський квадрат — це тосканський квадрат, що є одночасно латинським квадратом (такі квадрати відомі також як повні за рядками латинські квадрати). Ватиканський квадрат — це флорентійський квадрат, що є водночас латинським квадратом.
Приклад тосканського 1-квадрата на 7 символах, що не є 2-квадратом[25]:
6
1
5
2
4
3
7
2
6
3
5
4
7
1
5
7
2
3
1
4
6
4
2
5
1
6
7
3
3
6
2
1
7
4
5
1
3
2
7
5
6
4
7
6
5
3
4
1
2
Тосканський квадрат на n символах еквівалентний декомпозиції повних графів з n вершинами на nгамільтонових орієнтованих шляхів[26].
t-кратна зрівноважена схема (або t BD) типу t- — це множина X із v елементів разом із сімейством підмножин X (званих блоками), розміри яких містяться в наборі K, такому, що будь-яка t-підмножина різних елементів X міститься рівно в блоках. Якщо K — набір додатних цілих чисел строго між t і v, то схему t BD називають власною. Якщо всі k-підмножини X для деякого k є блоками, схему t BD називають тривіальною[27].
Зауважимо, що в прикладі 3-{12,{4,6},1) схеми на множині X = {1,2,…,12} деякі пари з'являються чотири рази (наприклад, пара {1,2}), тоді як інші з'являються п'ять разів (наприклад, пара {6,12})[28].
Неповний латинський квадрат — це k × vпрямокутний масив (k < v) v символів, таких, що кожен символ з'являється рівно один раз у кожному рядку і символи, що з'являються в будь-якому стовпці, утворюють блоки симетричної схеми , всі блоки якої з'являються рівно один раз. Неповний латинський квадрат є латинським прямокутником. Термін «квадрат» у назві з'явився зі старішого визначення, в якому використано квадратний масив[29]. Приклад неповного латинського 4×7 квадрата:
1
2
3
4
5
6
7
2
3
4
5
6
7
1
3
4
5
6
7
1
2
5
6
7
1
2
3
4
Сім блоків (стовпців) утворюють біплощину порядку 2 (симетрична схема (7,4,2)).
Bose R. C. A Note on Fisher's Inequality for Balanced Incomplete Block Designs // Annals of Mathematical Statistics. — 1949. — 20 вересня. — С. 619–620.
Caliński T., Kageyama S. Block designs: A Randomization approach, Volume II: Design. — New York : Springer-Verlag, 2003. — Т. 170. — (Lecture Notes in Statistics) — ISBN 0-387-95470-8.
Colbourn Charles J., Dinitz Jeffrey H. Handbook of Combinatorial Designs. — 2nd. — Boca Raton : Chapman & Hall/ CRC, 2007. — ISBN 1-58488-506-8.
Fisher R. A. An examination of the different possible solutions of a problem in incomplete blocks // Annals of Eugenics. — 1940. — Т. 10 (20 вересня). — С. 52–75.
Hall Marshall, Jr. Combinatorial Theory. — 2nd. — New York : Wiley-Interscience, 1986. — ISBN 0-471-09138-3.
Raghavarao D. Constructions and Combinatorial Problems in Design of Experiments. — corrected reprint of the 1971 Wiley. — New York : Dover, 1988.
Raghavarao D., Padgett L.V. Block Designs: Analysis, Combinatorics and Applications. — World Scientific, 2005.
Ryser Herbert John. Chapter 8: Combinatorial Designs // Combinatorial Mathematics (Carus Monograph #14). — Mathematical Association of America, 1963.
Shrikhande S. S., Vasanti N. B.-N. Non-isomorphic solutions of some balanced incomplete block designs I – // Journal of Combinatorial Theory. — 1970. — 20 вересня.
Stinson Douglas R. Combinatorial Designs: Constructions and Analysis. — New York : Springer, 2003. — ISBN 0-387-95487-2.
Street Anne Penfold, Street Deborah J. Combinatorics of Experimental Design. — Oxford U. P. [Clarendon], 1987. — P. 400+xiv. — ISBN 0-19-853256-3.
van Lint, J.H., and R.M. Wilson. A Course in Combinatorics. — Cambridge, Eng.: Cambridge University Press, 1992.