Комбінаторна схема

Теорія комбінаторних схем — частина комбінаторики (розділу математики), що розглядає існування, побудову та властивості сімейств скінченних множин, структура яких задовольняє узагальненим концепціям рівноваги та/або симетрії. Ці концепції точно не визначені, так що розглядатися як комбінаторні схеми можуть об'єкти широкого діапазону. Так, в одному випадку комбінаторні схеми можуть являти собою перетини числових множин, як у блок-схемах, а в іншому випадку можуть відображати розташування елементів у судоку.

Теорію комбінаторних схем можна використовувати при плануванні експериментів. Деякі з основних комбінаторних схем наведено в роботі Рональда Фішера з теорії біологічних експериментів. Зараз комбінаторні схеми можна знайти в багатьох галузях, зокрема в скінченній геометрії, створенні графіків турнірів, лотереях, математичній біології, , обчислювальних мережах, ^[en] та криптографії.

Визначення

Нехай ${\displaystyle v}$ — множина елементів ${\displaystyle m_{1},m_{2},...,m_{v}}$. Розподілимо елементи цієї множини за підмножинами ${\displaystyle M_{1},M_{2},...,M_{b}}$, перетин яких не обов'язково порожній. Кожну підмножину ${\displaystyle M_{j}}$ назвемо блоком, а число елементів множини ${\displaystyle M_{j}}$ в ньому — об'ємом блоку ${\displaystyle k_{j}}$. Елемент може потрапити в декілька блоків. Нехай ${\displaystyle r_{i}}$ — число підмножин ${\displaystyle M}$, що містять елемент ${\displaystyle m_{i}}$. Число повторень (невпорядкованих пар) позначимо як ${\displaystyle \lambda _{p}}$. Тоді множина блоків ${\displaystyle M_{1},M_{2},...,M_{b}}$ утворює комбінаторну схему (або блок-схему) із параметрами ${\displaystyle v,b,r_{i},k_{j},\lambda _{p}}$.

Приклад

Площина Фано

Якщо є n людей, чи можна скласти з них множини, такі, щоб кожна людина належала принаймні одній множині, кожна пара належала рівно одній множині, кожні дві множини мали в перетині тільки одну людину і жодна з множин не складалася зі всіх людей, всіх людей без однієї чи рівно однієї людини? Відповідь залежить від n.

Відповідь позитивна, якщо n має вигляд q² + q + 1. Складніше довести, що розв'язок існує, якщо q є степенем простого числа. Існує гіпотеза, що інших розв'язків немає. Доведено, що якщо розв'язок існує для q порівнянних з 1 або 2 за модулем 4 то q є сумою двох повних квадратів. Цей результат, теорему Брука — Райзера — Човли, доведено комбінуванням методів побудови, що ґрунтуються на скінченних полях, та застосування квадратичних форм.

Коли така структура існує, її називають скінченною проєктивною площиною. Це показує, як перетинаються теорія скінченних геометрій та комбінаторика. У разі q = 2, проєктивну площину називають площиною Фано.

Історія

Комбінаторні схеми відомі ще з часів античності у вигляді (квадрата Ло Шу), ранньої версії магічного квадрата. Комбінаторні схеми розвивалися з розвитком комбінаторики починаючи від XVIII століття, наприклад, у вигляді латинських квадратів у XVIII столітті та систем Штейнера у XIX столітті. Комбінаторні схеми популярні також у цікавій математиці, як, наприклад, у задачі Кіркмана про школярок (1850), і практичних задачах, таких як складання розкладу кругових турнірів (розв'язок опубліковано в 1880-х роках). У XX столітті комбінаторні схеми застосовано до планування експериментів, скінченних геометрій і , вони привели до виникнення ^[en].

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

Класичне ядро предмету комбінаторних схем будується навколо зрівноважених неповних блок-схем (англ. Balanced Incomplete Block Design, BIBD), матриць і схем Адамара, (симетричних BIBD), латинських квадратів, (розв'язних BIBD), ^[en] і попарно зрівноважених схем (англ. Pairwise Balanced Design, PBD). Інші комбінаторні схеми пов'язані з переліченими або ґрунтуються на цих схемах.

• Зрівноважена неповна блок-схема (BIBD), яку для стислості називають блок-схемами, це набір B з b підмножин (які називаються блоками) скінченної множини X з елементів v, такий, що будь-який елемент множини X міститься в деякому числі r блоків, кожен блок має однакове число елементів (= k) і кожна пара різних елементів з'являється в однаковій кількості (${\displaystyle =\lambda }$) блоків. Схеми BIBD відомі також як 2-схеми і часто позначаються як ${\displaystyle 2-(v,k,\lambda )}$-схеми. Як приклад, для випадку ${\displaystyle \lambda =1}$ і b = v отримуємо проєктивну площину — X у цьому випадку є множиною точок на площині, а блоки — прямими.
• Симетрична зрівноважена неповна блок-схема або (SBIBD) (англ. Symmetric Balanced Incomplete Block Design) — це BIBD, у якій v = b (кількість точок дорівнює кількості блоків). Це найважливіший та добре вивчений підклас BIBD. Проєктивні площини, біплощини та 2-схеми Адамара є SBIBD-схемами. Ці схеми цікаві, як екстремальні приклади нерівності Фішера (${\displaystyle b\geqslant v}$).
• (Розв'язна) (зрівноважена) неповна блок-схема — це BIBD, блоки якої можна розбити на множини (звані паралельними класами), кожна з яких утворює розбиття точок BIBD. Множину паралельних класів називають роздільністю схеми. Розв'язок знаменитої задачі про 15 школярок є роздільністю BIBD з v = 15, k = 3 та ${\displaystyle \lambda =1}$.
• ^[en] — це r × n ( r ≤ n) матриця, що має як елементи числа 1, 2, 3, …, n (або будь-яку іншу множну n різних символів), у якій жодне число не з'являється двічі у будь-якому рядку чи стовпці. Латинський прямокутник із розмірами n × n називають латинським квадратом. Якщо r < n, то до латинського прямокутника з розмірами r × n можна додати n − r рядків, щоб сформувати латинський квадрат, використовуючи теорему Холла про весілля.

Кажуть, що два латинські квадрати порядку n ортогональні, якщо множина всіх упорядкованих пар, що складаються з відповідних елементів двох квадратів, складається з n² різних пар (тобто зустрічаються всі можливі впорядковані пари). Множина латинських квадратів одного порядку утворює множину (англ. Mutually Orthogonal Latin Squares, MOLS), якщо будь-яка пара латинських квадратів у множині ортогональна. У такій множині квадратів порядку n може існувати максимум n − 1 квадратів. Множина n − 1 квадратів MOLS порядку n можна використати для побудови проєктивної площини порядку n (і навпаки).

• ^[en] ${\displaystyle (v,k,\lambda )}$ — це підмножина D групи G порядку v, що має розмір k, а будь-який не рівний одиниці елемент групи G можна подати у вигляді добутку d₁d₂⁻¹ елементів D рівно ${\displaystyle \lambda }$ способами (якщо G подано операцією множення).

Якщо D — різницева множина і g належить G, то ${\displaystyle g\mathbf {D} ={gd\colon d\in \mathbf {D} }}$ також є різницевою множиною і називається переносом множини D. Множина переносів різницевої множини D утворює симетричну блок-схему. В такій схемі є v елементів та v блоків. Кожен блок схеми складається з k точок, кожна точка міститься в k блоках. Будь-які два блоки мають рівно ${\displaystyle \lambda }$ загальних елементів та будь-які дві точки з'являються разом у ${\displaystyle \lambda }$ блоках. Цю схему SBIBD називають розвитком множини D.

Зокрема, якщо ${\displaystyle \lambda =1}$, різницева множина утворює проєктивну площину. Наприклад, різницева множина (7,3,1) над групою ${\displaystyle \mathbb {Z} /7\mathbb {Z} }$ (абелева група з адитивним записом) — це підмножина {1,2,4}. Розвиток цієї різницевої множини дає площину Фано.

Оскільки будь-яка різницева множина дає SBIBD, множина параметрів має задовольняти теоремі Брука — Райзера — Човли, але не будь-яка SBIBD-схема дає різницеву множину.

• Матриця Адамара порядку m — це m × m матриця H з елементами ±1, така, що HH^⊤ = mE_m, де H^⊤ є транспонованою до H, а E _m — m × m одинична матриця. Матрицю Адамара можна звести до стандартизованої форми (тобто перетворити на еквівалентну матрицю Адамара), в якій елементи першого рядка і першого стовпця рівні +1. Якщо порядок m > 2, то m має ділитися на 4.

Якщо дано матрицю Адамара порядку 4a в стандартизованій формі, видалимо перший рядок і перший стовпець, а потім замінимо всі −1 на 0. 0–1 матриця M, що вийшла, є матрицею інцидентності симетричної ${\displaystyle 2-(4a-1,2a-1,a-1)}$-схеми, званої адамаровою 2-схемою. Ця побудова оборотна, так що матрицю інцидентності симетричної 2-схеми з такими параметрами можна використати для отримання матриці Адамара порядку 4a. У разі a = 2 отримуємо вже знайому площину Фано (як 2-схему Адамара).

• Попарно зрівноважена схема (англ. Pairwise Balanced Design, PBD) — це множина X разом із сімейством підмножин X (не обов'язково одного розміру і підмножини можуть бути однаковими), таким, що будь-яка пара різних елементів з X міститься рівно в ${\displaystyle \lambda }$ (додатне число) підмножин. Дозволено, щоб множина X входила в сімейство, а якщо всі підмножини є копіями множини X, схему PBD називають тривіальною. Розмір множини X дорівнює v, а число підмножин у сімействі (однакові підмножини підраховують окремо) дорівнює b.

Нерівність Фішера для схем PBD виконується — для будь-якої нетривіальної PBD-схеми виконується ${\displaystyle v\leqslant b}$.

Цей результат узагальнює знамениту теорему де Брейна — Ердеша: для будь-якої PBD-схеми з ${\displaystyle \lambda =1}$, яка не має блоків розміру 1 або v, виконується ${\displaystyle v\leqslant b}$, при цьому рівність має місце тоді й лише тоді, коли схема є проєктивною площиною або (майже пучком).

Інші комбінаторні схеми

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

• ^[en]
• Зрівноважені трійкові схеми (англ. Balanced Ternary Design) ${\displaystyle BTD(V,B;\rho _{1},\rho _{2},R;K,\Lambda )}$ — розстановка V елементів у B мультимножин (блоків, потужність кожної множини K (K ≤ V)), що задовольняє умовам:

1. Кожен елемент з'являється ${\displaystyle R=\rho _{1}+2\rho _{2}}$ разів із кратністю 1 (1 примірник у мультимножині) рівно в ${\displaystyle \rho _{1}}$ блоках, а з кратністю 2 — рівно в ${\displaystyle \rho _{2}}$ блоках.
2. Кожна пара різних елементів з'являється ${\displaystyle \Lambda }$ разів (з урахуванням кратності). Тобто, якщо m_vb — кратність елемента v в блоці b, то для будь-якої пари різних елементів v і w виконується ${\displaystyle \sum _{b=1}^{B}m_{vb}m_{wb}=\Lambda }$.

Наприклад, одна з двох неізоморфних схем 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), таке що:

1. кожен елемент множини V з'являється рівно один раз у кожному стовпці;
2. кожен елемент множини 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 вершинами, K_2n.

Схеми BTD(n) можна використати для складання розкладу кругових турнірів — рядки представляють місця, стовпці представляють тури (раунди, круги), а елементи таблиці задають гравців або команди.

• Бент-функції
• Масиви Костаса
• Повні факторні експерименти
• Частотний квадрат (F-квадрат) є узагальненням латинського квадрата. Нехай S = {s₁, s₂, …, s_m} — множина різних символів, а ${\displaystyle (\lambda _{1},\lambda _{2},...,\lambda _{m})}$ — частотний вектор додатних чисел. Частотний квадрат порядку n ${\displaystyle (n=\lambda _{1}+\lambda _{2}+...+\lambda _{m})}$ — це масив n × n, у якому кожен символ s_i зустрічається ${\displaystyle \lambda _{i}}$ разів (i = 1,2,…,m) у кожному рядку і кожному стовпці. Частотний квадрат має стандартний вигляд, якщо в першому рядку та першому стовпці елементи s_i передують s_j при i < j .

Частотний квадрат F ₁ порядку n над множиною {s₁, s₂, …, s_m} з частотним вектором ${\displaystyle (\lambda _{1},\lambda _{2},...,\lambda _{m})}$ і частотний квадрат F₂ також порядку n над множиною ${\displaystyle \{t_{1},t_{2},...,t_{k}\}}$ із частотним вектором ${\displaystyle (\mu _{1},\mu _{2},...,\mu _{k})}$ ортогональні, якщо будь-яка впорядкована пара (s_i, t_j) з'являється рівно ${\displaystyle \lambda _{i}\mu _{j}}$ разів, коли F₁ і F₂ накласти один на одного.

• Системи трійок Голла (англ. Hall Triple Systems, HTS) — це системи трійок Штейнера (англ. Steiner Triple Systems, STS) (у ній блоки називають прямими) з властивістю, що підструктура, утворена перетином двох прямих ізоморфна скінченній афінній площині AG(2,3).

Будь-який афінний простір AG(n,3) дає приклад схеми HTS, такі схеми називають афінними HTS. Неафінні схеми HTS також існують.

Число точок у схемі HTS дорівнює 3^m для деякого цілого ${\displaystyle m\geqslant 2}$. Неафінні схеми HTS існують для будь-якого ${\displaystyle m\geqslant 4}$ і не існують для ${\displaystyle m=2}$ або 3.

Будь-яка система трійок Штейнера еквівалентна штейнерівській квазігрупі (ідемпотентна, коммутативна і виконується ${\displaystyle (xy)y=x}$ для всіх x та y). Система трійок Голла еквівалентна штейнерівській квазігрупі з властивістю дистрибутивності, тобто виконується ${\displaystyle a(xy)=(ax)(ay)}$ для всіх a, x, y у квазігрупі .

• Нехай S — множина з 2n елементів. Схема Гавелла, H(s,2n) (на множині символів S) — це масив s × s, такий, що:

1. кожна комірка масиву або порожня, або містить невпорядковану пару з S,
2. кожен символ з'являється рівно один раз у кожному рядку і кожному стовпці масиву,
3. кожна невпорядкована пара з'являється не більше ніж в одній комірці масиву.

Приклад схеми 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 вершинами, який називають основним графом схеми Гавелла.

Циклічні схеми Гавелла використовують як пересування Гавелла (схема комплектування учасників ігор) у турнірах подвійного бриджу. Рядки схеми подають тури (кола), стовпці подають коробки (з заздалегідь підготовленими роздачами, див. («Бридж — Роздача»)), а діагоналі подають столи.

• Лінійні простори
• Схема лото (n,k,p,t) — це множина V з n елементів разом з набором ${\displaystyle \beta }$ k-елементних підмножин (блоків), таких, що для будь-якої підмножини P, що складається з p елементів множини V, існує блок B в ${\displaystyle \beta }$, для котрого ${\displaystyle |P\cap B|\geqslant t}$. L(n,k,p,t) означає найменше число блоків у будь-якій схемі лото (n,k,p,t). Схема лото (7,5,4,3) з найменшим можливим числом блоків:

{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. У загальному випадку ці числа складно обчислити і вони залишаються невідомими.

Геометричну побудову однієї з таких схем наведено в статті «Трансильванська лотерея».

• Магічні квадрати
• Схема Мендельсона ${\displaystyle (\mathbf {v} ,\mathbf {k} ,{\boldsymbol {\lambda }})}$ (${\displaystyle MD(\mathbf {v} ,\mathbf {k} ,{\boldsymbol {\lambda }})}$) — це множина V з v елементів і набір ${\displaystyle \beta }$ упорядкованих k-кортежів різних елементів множини V (званих блоками), таких, що кожна впорядкована пара (x,y) елементів з V (x ≠ y) циклічно суміжна в ${\displaystyle \lambda }$ блоках (упорядкована пара (x,y) різних елементів циклічно суміжна в блоці, якщо елементи з'являються в блоці поруч — або (…,x,y,…), або (y,…,x)). Схема ${\displaystyle MD(\mathbf {v} ,\mathbf {3} ,{\boldsymbol {\lambda }})}$ — це система трійок Мендельсона, що має позначення MTS${\displaystyle (\mathbf {v} ,{\boldsymbol {\lambda }})}$. Приклад 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. Нехай ${\displaystyle \beta =\{(x,y,x\ast y)\colon x,y\in Q\}}$. Тоді ${\displaystyle (Q,\beta )}$ є системою трійок Мендельсона MTS(|Q|,1). Ця побудова оборотна.

• Квазі-3 схема — це симетрична схема (SBIBD), в якій кожна трійка блоків перетинається або в x, або в y точках для фіксованих чисел x і y, званих числами перетинів трійок (x < y). Будь-яка симетрична схема з ${\displaystyle \lambda \leqslant 2}$ є квазі-3 схемою з ${\displaystyle x=0}$ і ${\displaystyle y=1}$. Схема точка-гіперплощина геометрії PG(n,q) є квазі-3 схемою з ${\displaystyle x=(q^{n-2}-1)/(q-1)}$ і ${\displaystyle y=\lambda =(q^{n-1}-1)/(q-1)}$. Якщо ${\displaystyle y=\lambda }$ для квазі-3 схеми, схема ізоморфна PG(n,q) або проєктивній площині.
• Схема ${\displaystyle Dt-(v,k,\lambda )}$ є квазісиметричною з числами перетину x і y (x < y), якщо будь-які два різних блоки мають у перетині або x або y точок. Ці схеми виникають природно при вивченні двоїстих схем з ${\displaystyle \lambda =1}$. Несиметрична схема (b > v) 2-(v,k,1) є квазісиметричною з x = 0 і y = 1. Кратні (блоки повторюються певне число разів) симетричні 2-${\displaystyle (v,k,\lambda )}$ схеми квазісиметричні з ${\displaystyle x=\lambda }$ і y = k. 3-схеми Адамара (розширення (2-схем Адамара)) квазісиметричні.

Будь-яка квазісиметрична блок-схема породжує сильно регулярний граф (як її блоковий граф), але не всі схеми SRG породжуються в такий спосіб.

Матриця інцидентності квазісиметричної схеми 2-${\displaystyle (v,k,\lambda )}$ з k ≡ x ≡ y (mod 2) утворює двійковий самоортогональний код.

• ^[en]
• ^[en] — це скінченна множина X точок на (d − 1)-вимірній сфері, така, що для деякого цілого t, середнє значення на X полинома

${\displaystyle f(x_{1},\ldots ,x_{d})\ }$

зі степенем, що не перевищує t, дорівнює середньому значенню f на всій сфері (тобто інтегралу функції f, поділеному на площу сфери).

• ^[en]
• Тосканський r × n k-прямокутник над n символами має r рядків і n стовпців, при цьому:

1. кожен рядок є перестановкою n символів;
2. для будь-яких двох різних символів a і b і для кожного числа m від 1 до k існує не більше одного рядка, в якому b міститься за m кроків правіше від a.

Якщо r = n і k = 1, схеми називають тосканськими квадратами, а в разі r = n і k = n — 1 їх називають флорентійськими квадратами. Римський квадрат — це тосканський квадрат, що є одночасно латинським квадратом (такі квадрати відомі також як повні за рядками латинські квадрати). Ватиканський квадрат — це флорентійський квадрат, що є водночас латинським квадратом.

Приклад тосканського 1-квадрата на 7 символах, що не є 2-квадратом:

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 гамільтонових орієнтованих шляхів.

• t-кратна зрівноважена схема (або t BD) типу t-${\displaystyle (v,K,\lambda )}$ — це множина X із v елементів разом із сімейством підмножин X (званих блоками), розміри яких містяться в наборі K, такому, що будь-яка t-підмножина різних елементів X міститься рівно в ${\displaystyle \lambda }$ блоках. Якщо K — набір додатних цілих чисел строго між t і v, то схему t BD називають власною. Якщо всі k-підмножини X для деякого k є блоками, схему t BD називають тривіальною.

Зауважимо, що в прикладі 3-{12,{4,6},1) схеми на множині X = {1,2,…,12} деякі пари з'являються чотири рази (наприклад, пара {1,2}), тоді як інші з'являються п'ять разів (наприклад, пара {6,12}).

1 2 3 4 5 6         1 2 7 8    1 2 9 11    1 2 10 12    3 5 7 8    3 5 9 11    3 5 10 12    4 6 7 8    4 6 9 11    4 6 10 12

7 8 9 10 11 12    2 3 8 9    2 3 10 7    2 3 11 12    4 1 8 9    4 1 10 7    4 1 11 12    5 6 8 9    5 6 10 7    5 6 11 12

                        3 4 9 10    3 4 11 8    3 4 7 12    5 2 9 10    5 2 11 8    5 2 7 12    1 6 9 10    1 6 11 8    1 6 7 12

                        4 5 10 11    4 5 7 9    4 5 8 12    1 3 10 11    1 3 7 9    1 3 8 12    2 6 10 11    2 6 7 9    2 6 8 12

                        5 1 11 7    5 1 8 10    5 1 9 12    2 4 11 7    2 4 8 10    2 4 9 12    3 6 11 7    3 6 8 10    3 6 9 12

• Неповний латинський квадрат — це k × v прямокутний масив (k < v) v символів, таких, що кожен символ з'являється рівно один раз у кожному рядку і символи, що з'являються в будь-якому стовпці, утворюють блоки симетричної схеми ${\displaystyle (v,k,\lambda )}$, всі блоки якої з'являються рівно один раз. Неповний латинський квадрат є латинським прямокутником. Термін «квадрат» у назві з'явився зі старішого визначення, в якому використано квадратний масив. Приклад неповного латинського 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)).

Примітки

1. Stinson, 2003, с. 1.
2. Рыбников, 1972, с. 130.
3. Stinson, 2003, с. IX.
4. Beth, Jungnickel, Lenz, 1999, с. 40, приклад 5.8.
5. Ryser, 1963, с. 52, теорема 3.1.
6. Якщо G — абелева група (або записується з операцією додавання) визначення набуває вигляду d₁–d₂, звідки й виник термін різницева множина.
7. Beth, Jungnickel, Lenz, 1999, с. 262 теорема 1.6.
8. Stinson, 2003, с. 74, теорема 4.5.
9. Stinson, 2003, с. 193, теорема 8.20.
10. Stinson, 2003, с. 183,, теорема 8.5.
11. Colbourn, Dinitz, 2007.
12. Colbourn, Dinitz, 2007, с. 331, приклад 2.2.
13. Colbourn, Dinitz, 2007, с. 331, зауваження 2.8.
14. Colbourn, Dinitz, 2007, с. 333, зауваження 3.3.
15. Colbourn, Dinitz, 2007, с. 496, теорема 28.5.
16. Colbourn, Dinitz, 2007, с. 497, теорема 28.15.
17. Colbourn, Dinitz, 2007, с. 503, зауваження 29.38.
18. Colbourn, Dinitz, 2007, с. 512, приклад 32.4.
19. Colbourn, Dinitz, 2007, с. 512, зауваження 32.3.
20. Colbourn, Dinitz, 2007, с. 530, теорема 35.15.
21. Colbourn, Dinitz, 2007, с. 577, теорема 47.15.
22. Colbourn, Dinitz, 2007, с. 578-579.
23. Colbourn, Dinitz, 2007, с. 579, теорема 48.10.
24. Colbourn, Dinitz, 2007, с. 580, лема 48.22.
25. Colbourn, Dinitz, 2007, с. 652, приклад 62.4.
26. Colbourn, Dinitz, 2007, с. 655, теорема 62.24.
27. Colbourn, Dinitz, 2007, с. 657.
28. Colbourn, Dinitz, 2007, с. 658, приклад 63.5.
29. Colbourn, Dinitz, 2007, с. 669, зауваження 65.3.

Література

• Рыбников К.А. Введение в комбинаторный анализ. — МГУ, 1972.
• Комбинаторные свойства дискретных структур и приложения к криптологии. — МЦНМО, 2011. — .
• Холл М. Комбинаторика. — МИР, 1966.
• Assmus E.F., Key J.D. Designs and Their Codes. — Cambridge : Cambridge University Press, 1992. — .
• Beth T., Jungnickel D., Lenz H. Design Theory. — Cambridge : Cambridge University Press, 1999. — .
• Bose R. C. A Note on Fisher's Inequality for Balanced Incomplete Block Designs // . — 1949. — 9 липня. — С. 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) — .
• Colbourn Charles J., Dinitz Jeffrey H. Handbook of Combinatorial Designs. — 2nd. — Boca Raton : Chapman & Hall/ CRC, 2007. — .
• Fisher R. A. An examination of the different possible solutions of a problem in incomplete blocks // . — 1940. — Т. 10 (9 липня). — С. 52–75.
• Hall Marshall, Jr. Combinatorial Theory. — 2nd. — New York : Wiley-Interscience, 1986. — .
• Hughes D.R., Piper E.C. Design theory. — Cambridge : Cambridge University Press, 1985. — .
• Lander E. S. Symmetric Designs: An Algebraic Approach. — Cambridge : Cambridge University Press, 1983.
• Lindner C.C., Rodger C.A. Design Theory. — Boca Raton : CRC Press, 1997. — .
• 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 – // . — 1970. — 9 липня.
• Stinson Douglas R. Combinatorial Designs: Constructions and Analysis. — New York : Springer, 2003. — .
• Street Anne Penfold, Street Deborah J. Combinatorics of Experimental Design. — Oxford U. P. [Clarendon], 1987. — P. 400+xiv. — .
• van Lint, J.H., and R.M. Wilson. A Course in Combinatorics. — Cambridge, Eng.: Cambridge University Press, 1992.