블록 설계 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''블록 설계'''(block設計, {{llang|en|block design|블록 디자인}})는 같은 크기의 일련의 [[부분 집합]]들이 주어져 있는 [[유한 집합]]이다.<ref>{{서적 인용|first1=Thomas|last1=Beth|first2=Dieter|last2=Jungnickel|first3=Hanfried|last3=Lenz|title=Design theory. Volume 1|publisher=Cambridge University Press|year=1999|판=2|isbn=978-0-521-44432-3|doi=10.1017/CBO9780511549533|총서= Encyclopedia of Mathematics and its Applications|권=69|언어=en}}</ref><ref>{{서적 인용|first1=Thomas|last1=Beth|first2=Dieter|last2=Jungnickel|first3=Hanfried|last3=Lenz|title=Design theory. Volume 2|publisher=Cambridge University Press|year=1999|판=2|isbn=978-0-521-77231-0|doi=10.1017/CBO9781139507660|총서= Encyclopedia of Mathematics and its Applications|권=78|언어=en}}</ref><ref>{{서적 인용|last=Stinson|first=Douglas R.|title=Combinatorial designs: constructions and analysis|year=2003|publisher=Springer-Verlag|isbn=978-0-387-95487-5|doi=10.1007/b97564|url=https://archive.org/details/springer_10.1007-b97564|언어=en}}</ref><ref>{{서적 인용
|title=Block designs: analysis, combinatorics and applications
|성=Raghavarao|이름=Damaraju |성2=Padgett | 이름2= Lakshmi V.
|year=2005-10
|publisher=World Scientific | 총서=Series on Applied Mathematics | 권=17| doi=10.1142/5846 | isbn=978-981-256-360-6  |언어=en
}}</ref> 이 경우, 이러한 부분 집합을 '''블록'''({{llang|en|block}})이라고 하며, 블록 설계는 (예를 들어) “<math>k</math>개의 원소들을 포함하는 블록의 수는 원소의 선택에 상관없이 <math>\lambda</math>개”와 같은 꼴의 조건을 만족시켜야 한다.

== 정의 ==
=== 존슨 결합 도식 속의 블록 설계 ===
세 [[자연수]] <math>t,k,n\in\mathbb N</math>가 주어졌다고 하자. '''<math>(t,k,n)</math>-블록 설계''' <math>(X,\mathcal B)</math>는 다음과 같은 데이터로 주어진다.
* 크기 <math>n</math>의 [[유한 집합]] <math>X</math>. 그 원소를 '''점'''(點, {{llang|en|point}})이라고 한다.
* <math>X</math>의, 크기 <math>k</math>의 부분 집합들의 족 <math>\mathcal B\subseteq\operatorname{Pow}_k(X)</math>. 그 원소를 '''블록'''({{llang|en|block}})이라고 한다. (여기서 <math>\operatorname{Pow}_k(X)</math>는 <math>X</math>의 부분 집합들 가운데 크기가 <Math>k</math>인 것들로 구성된, [[멱집합]]의 부분 집합이다.)
이는 다음 조건을 만족시켜야 한다.
* <math>t</math>개의 서로 다른 점들이 주어졌을 때, 이 점들을 모두 포함하는 블록의 개수는 선택한 점들에 상관없는 값 <Math>\lambda_t>0</math>이다. (0을 제외하는 것은 피셔 부등식 등을 따르지 않는 <math>(X,\mathcal B=\varnothing)</math>를 배제하기 위함이다.)

두 <math>(t,k,n)</math>-블록 설계 <math>(X,\mathcal B)</math>, <math>(X',\mathcal B')</math>가 주어졌다고 하자. 만약 이 둘 사이에 [[전단사 함수]]
:<math>\iota\colon X\to X'</math>
가 존재하여
:<math>\{\iota(B)\}_{B\in\mathcal B}=\mathcal B'</math>
라면, <math>(X,\mathcal B)</math>와 <math>(X',\mathcal B')</math>가 서로 '''동형'''이라고 한다.

<math>\lambda_t=1</math>인 <math>(t,k,n)</math>-블록 설계는 '''<math>(t,k,n)</math>-슈타이너 계'''(Steiner系, {{llang|en|Steiner system|스타이너 시스템}})라고 한다. 보통, <math>\lambda_t=1</math>인 <math>(t,k,n)</math>-블록 설계 <math>(X,\mathcal B)</math>는 <math>\operatorname S(t,k,n)</math>로 표기된다.

=== 일반적 결합 도식 속의 블록 설계 ===
위 정의는 [[결합 도식]]의 개념을 통해 일반화된다.<ref>{{서적 인용| last=Zieschang | first=Paul-Hermann |  title=Theory of association schemes |  publisher=Springer-Verlag |  year=2005 |doi=10.1007/3-540-30593-9 | 총서=Springer Monographs in Mathematics|isbn=978-3-540-26136-0|issn=1439-7382|언어=en }}</ref><ref name="DL">{{저널 인용|doi=10.1109/18.720545|제목=Association schemes and coding theory|issn=0018-9448|저널= Institute of Electrical and Electronics Engineers Transactions on Information Theory|권=44|호=6|날짜=1998-10|이름=Philippe|성=Delsarte|이름2=Vladimir Iosifovich|성2=Levenshtein|저자링크2=블라디미르 레벤시테인|쪽= 2477–2504|언어=en}}</ref>{{rp|2483–2486, §Ⅲ}}

구체적으로, [[결합 도식]] <math>(X,\{D_i\in\operatorname{Mat}(|X|,|X|;\mathbb Z)\}_{i\in I})</math>이 주어졌다고 하자. 그렇다면, 그 복소수 계수 보스-메스너 대수
:<math>\mathcal A=\operatorname{Span}_{\mathbb C}\{D_i\}_{i\in I}\subseteq\operatorname{Mat}(|X|,|X|;\mathbb C)</math>
는 [[반단순 대수]]이며, 따라서 그 최소 [[멱등원]]들의 집합
:<math>(E_a)_{a\in A}</math>
:<math>E_aE_b=\delta_{ab}E_a</math>
:<math>\sum_{a\in A}E_a=1_{\mathcal A}</math>
를 정의할 수 있다. 특히,
:<math>E_0=\frac1{|X|}\mathsf J_{|X|\times|X|}</math>
는 항상 최소 멱등원이다. (<math>\mathsf J_{|X|\times|X|}</math>는 모든 성분이 1인 <math>|X|\times|X|</math> [[정사각 행렬]]이다.)

이제, 계수
:<math>E_a=\sum_{i=0}^{|I|}Q_{ai}D_i</math>
들을 정의할 수 있다. <math>X</math>의 [[부분 집합]](즉, <math>X</math> 속의 [[블록 부호]]) <math>C\subseteq X</math>가 주어졌을 때, 내부 분포
:<math>\alpha_i=\frac{|C^2\cap R_i|}{|C|}</math>
및 쌍대 내부 분포
:<math>\beta_a=\sum_{i\in I}Q_{ai}\alpha_i</math>
를 정의할 수 있다.

만약 어떤 부분 집합 <math>E\subseteq A</math>가 주어졌을 때, 만약 <math>X</math>의 부분 집합 <math>C\subseteq X</math>가 다음 조건을 만족시킬 경우, '''<math>E</math>-블록 설계'''({{llang|en|<math>E</math>-block design}})라고 한다.<ref name="DL"/>{{rp|2484, Definition 7}}
:임의의 <math>a\not\in E</math>에 대하여, <math>\beta_a=0</math>
만약 <math>X</math>가 [[존슨 결합 대수]]일 때, 이는 첫째 정의로 귀결된다.

== 연산 ==
=== 유도 블록 설계 ===
임의의 <math>(t,k,n)</math>-블록 설계 <math>(X,\mathcal B)</math> 및 점 <math>x\in X</math>가 주어졌다고 하자. 그렇다면,
:<Math>X'=X\setminus\{x\}</math>
:<math>\mathcal B'=\{B\setminus\{x\}\colon x\in B\in\mathcal B\}</math>
는 <math>(t-1,k-1,n-1)</math>-블록 설계를 이루며,
:<math>\lambda'_{t-1}=\lambda_t</math>
이다. 이를 <math>(X,\mathcal B)</math>의 '''유도 블록 설계'''(誘導block設計, {{llang|en|derived block design}})이라고 한다. (서로 다른 점에서 취한 유도 블록 설계는 서로 동형이지 못할 수 있다.)

특히, 슈타이너 계의 유도 블록 설계는 항상 슈타이너 계이다.

=== 결합 행렬 ===
<math>(t,k,n)</math>-블록 설계 <math>(X,\mathcal B)</math>에서, <math>X=\{x_1,\dotsc,x_n\}</math>와 <math>\mathcal B=\{B_1,\dotsc,B_{\lambda_0}\}</math> 위에 각각 임의로 [[전순서]]를 주자. 그렇다면, <math>(X,\mathcal B)</math>의 '''결합 행렬'''({{llang|en|incidence matrix}})은 다음과 같은 <math>n\times\lambda_0</math> 행렬
:<math>M\in\operatorname{Mat}(n,\lambda_0;\mathbb F_2)</math>
이다.
:<math>M_{ij}=\begin{cases}1 & x_i\in B_j \\ 0 & x_i \not\in B_j\end{cases}</math>
정사각 블록 설계의 경우 결합 행렬은 [[정사각 행렬]]이다.

== 성질 ==
임의의 <math>(t,k,n)</math>-블록 설계 <math>(X,\mathcal B)</math>가 주어졌을 때, 다음 정수들을 정의하자.
:<math>\lambda_i=\frac{\lambda_t\binom {n-i}{t-i}}{\binom{k-i}{t-i}}\qquad(i\in\{0,1,\dotsc,t\})</math>
그렇다면, 다음이 성립한다.
* <math>0\le i\le t</math>가 주어졌을 때, <math>i</math>개의 점들을 모두 포함하는 블록의 개수는 정확히 <math>\lambda_i</math>이다.

특히, <math>i=0</math>일 경우,
* 블록의 수는 <math>\textstyle\lambda_0 = \lambda_t \binom nt / \binom kt</math>이다.

이에 따라, 모든 <math>(t,k,n)</math>-블록 설계는 임의의 <math>0\le t'\le t</math>에 대하여 <math>(t',k,n)</math>-블록 설계이다.

=== 존재의 필요 조건 ===
'''피셔 부등식'''(Fisher不等式, {{llang|en|Fisher’s inequality}})에 따르면,<ref name="Fisher"/> 임의의 <math>(2,k,n)</math>-블록 설계 <math>(X,\mathcal B)</math>에 대하여, 다음이 성립한다.
:<math>|X| \ge \lambda_0</math>
:<math>k \ge \lambda_1</math>
(<math>X\lambda_1=k\lambda_0</math>이므로, 두 조건은 사실 동치이다.) 이 부등식을 포화시키는 블록 설계, 즉 점의 수가 블록의 수와 같은 2-블록 설계를 '''정사각 블록 설계'''(正四角block設計, {{llang|en|square block matrix}}) 또는 '''대칭 블록 설계'''(對稱block設計, {{llang|en|symmetric block design}})라고 한다.

보다 일반적으로, 임의의 <math>(t,k,n)</math>-블록 설계 <math>(X,\mathcal B)</math>에 대하여, 다음이 성립한다.<ref>{{저널 인용|first1=Dijen K.|last1=Ray-Chaudhuri|first2=Richard M.|last2=Wilson|title=On ''t''-designs|날짜=1975|journal=Osaka Journal of Mathematics|url=https://projecteuclid.org/euclid.ojm/1200758175|권=12|호=3|pages=737–744|MR=0592624|zbl=0342.05018|언어=en}}</ref>
:<math>\lambda_0 \ge \binom n{\lfloor t/2\rfloor}</math>

'''브룩-라이저-차울라 정리'''(Bruck-Ryser-चावला定理, {{llang|en|Bruck–Ryser–Chowla theorem}})에 따르면,<ref>{{저널 인용
|last1=Bruck |first1=Richard Hubert
|first2=Herbert John |last2=Ryser
|year=1949
|title=The nonexistence of certain finite projective planes
|journal=Canadian Journal of Mathematics | issn=0008-414X
|volume=1
|pages=88–93
 |doi=10.4153/cjm-1949-009-2 | 언어=en}}</ref><ref>{{저널 인용|last1=Chowla |first1=Sarvadaman |first2=Herbert John |last2=Ryser |year=1950 |title=Combinatorial problems |url=https://archive.org/details/sim_canadian-journal-of-mathematics_1950_2_1/page/n96 |journal = Canadian Journal of Mathematics |issn=0008-414X |volume=2 |pages=93–99 |doi=10.4153/cjm-1950-009-8| 언어=en}}</ref> 임의의 <math>(t,k,n)</math>-블록 설계 <math>(X,\mathcal B)</math>에 대하여, 만약 <math>|X| = \lambda_0</math>라면,
* 만약 <math>|X|</math>가 [[짝수]]라면, <math>k-\lambda_2</math>는 [[제곱수]]이다.
* 만약 <math>|X|</math>가 [[홀수]]라면, <math>x^2 = (k-\lambda_2)y^2 + (-1)^{(|X|-1)/2}\lambda_2 z^2</math>를 만족시키는 정수 <math>(x,y,z)\ne(0,0,0)</math>가 존재한다.

=== 개수 ===
작은 크기의 <math>(t=2, k=3, n)</math>-슈타이너 계의 동형류들의 수들은 다음과 같다. {{OEIS|A30129}}
{| class=wikitable
! <math>n</math>
| 1 || 3 || 7 || 9 || 13 || 15 || 19
| rowspan=2 | …
|-
! <math>(2,3,n)</math>-슈타이너 계의 동형류의 수
| 1 || 1 || 1 || 1 || 2 || 80 || 11084874829
|}

작은 크기의 <math>(t=3, k=4, n)</math>-슈타이너 계의 동형류들의 수들은 다음과 같다. {{OEIS|A51390}}
{| class=wikitable
! <math>n</math>
| 1 || 2 || 4 || 8 || 10 || 14 || 16
| rowspan=2 | …
|-
! <math>(3,4,n)</math>-슈타이너 계의 동형류의 수
| 1 || 1 || 1 || 1 || 1 || 4 || 1054163
|}

== 예 ==
다음과 같은 (2,4,8)-블록 설계를 생각하자.
:<math>X=\{0,1,2,3,4,5,6,7\}</math>
:<math>\mathcal B=\{0123, 0124, 0156, 0257, 0345, 0367, 0467, 1267, 1346, 1357, 1457, 2347, 2356, 2456\}</math>
그렇다면,
* 총 8개의 점이 있다 (<math>n=8</math>).
* 모든 블록의 크기는 4이다 (<math>k=4</math>).
* 블록의 수는 14이다 (<math>\lambda_0=14</math>).
* 임의의 한 점은 7개의 블록에 포함된다 (<math>\lambda_1=7</math>).
* 임의의 두 점은 3개의 블록에 포함된다 (<math>\lambda_2=3</math>).

=== 파노 평면 ===
[[파노 평면]] ([[유한체]] <math>\mathbb F_2</math> 위의 [[사영 평면]]) <math>\mathbb P_{\mathbb F_2}^2</math>을 생각하자.
:[[파일:Walsh permutation 124 Fano.svg|300px]]
여기서, 각 선을 블록으로 생각하자. 즉, 다음과 같은 블록 설계를 생각하자.
:<math>X=\{1,2,3,4,5,6,7\}</math>
:<math>\mathcal B=\{123, 145, 167, 246, 257, 347,356\}</math>
이는 <math>(2,3,7)</math>-슈타이너 계를 이룬다.
* 총 7개의 점이 있다 (<math>n=7</math>).
* 모든 블록은 정확히 세 개의 점을 갖는다 (<math>k=3</math>).
* 블록의 수는 7이다 (<math>\lambda_0=7</math>).
* 모든 점은 정확히 세 개의 블록에 포함된다 (<math>\lambda_1=3</math>).
* 임의의 서로 다른 두 점이 주어졌을 때, 이를 포함하는 블록은 정확히 한 개이다. (<math>\lambda_2=1</math>).

=== 이진 골레 부호 ===
{{본문|이진 골레 부호}}
[[이진 골레 부호]] <math>G_{24}\subseteq\mathbb F_2^{24}</math>는 759개의 옥타드(값이 1인 성분이 8개인 벡터)를 가지며, 각 옥타드를 <math>\{1,2,\dotsc,24\}</math>의, 크기 8의 [[부분 집합]]으로 여길 수 있다. 이에 따라, [[이진 골레 부호]]의 옥타드의 집합은 (5,8,24)-슈타이너 계를 이룬다. 이는 '''비트 설계'''(Witt設計, {{llang|en|Witt design}})라고 불린다.

=== 아다마르 설계 ===
{{본문|아다마르 설계}}
<math>4m\times 4m</math> [[아다마르 행렬]]이 주어졌으며, 그 첫 열과 첫 행이 모두 1로 구성돼 있다고 하자. 그렇다면, 첫 열과 첫 행을 제거하고, 나머지 성분 가운데 −1을 0으로 치환한 뒤, 이를 어떤 정사각 블록 설계의 결합 행렬로 해석할 수 있다. 이를 '''[[아다마르 설계]]'''라고 하며, 이는 <math>\lambda_2=m-1</math>인 <math>(2,2m,4m-1)</math>-블록 설계이다.

=== 자명한 블록 설계 ===
임의의 유한 집합 <math>X</math> 및 <math>\varnothing\ne\mathcal B\subseteq\operatorname{Pow}_k(X)</math>에 대하여, <math>(X,\mathcal B)</math>는 <math>\lambda_0=|\mathcal B|</math>인 <math>(0,k,|X|)</math>-블록 설계를 이룬다.

임의의 유한 집합 <math>X</math> 및 양의 정수 <math>1\le k\le|X|</math>에 대하여, <math>(X,\operatorname{Pow}_k(X))</math>는 <math>\textstyle (k, k, |X|)</math>-블록 설계를 이루며, 이 경우
:<math>\lambda_i=\binom{|X|-i}{k-i}\qquad(0\le i\le k)</math>
이다. 이는 <math>t=k</math>이므로 정사각 블록 설계이며, <math>\lambda_t=1</math>이므로 슈타이너 계이다.

== 역사 ==
[[파일:Wesley Woollhouse.jpg|섬네일|오른쪽|웨슬리 스토커 바커 울하우스]]
[[파일:JakobSteiner.jpg|섬네일|오른쪽|야코프 슈타이너]]
1844년에 영국의 [[보험계리인]] 웨슬리 스토커 바커 울하우스({{llang|en|Wesley Stoker Barker Woolhouse}}, 1809~1893)가 자신이 편집자로 있던 잡지 《레이디즈 앤드 젠틀먼즈 다이어리》({{llang|en|Lady’s and Gentleman’s Diary}})에서 블록 설계에 대한 퍼즐을 제시하였다.<ref name="Woolhouse">{{저널 인용|저널=Lady’s and Gentleman’s Diary|권=141|날짜=1844|쪽=84–84|제목=XV. Or PRIZE QUEST. (1733)|저자=The Editor|url=https://babel.hathitrust.org/cgi/pt?id=mdp.39015065987789;view=1up;seq=360|언어=en}}</ref> 그 전문(全文)은 다음과 같다.
{{인용문2|
XV. 상금 문제 (1733번). 편집부 출제.<br>
<math>n</math>개의 기호들로 만들 수 있는, 각각 <math>p</math>개의 기호를 갖는 조합들의 수를 계산하라. 다만, 임의의 <math>q</math>개의 기호들의 조합은 두 개 이상에 속할 수 없다.<br>
XV. Oʀ PRIZE QUEST. (1733) ; ''by the Editor.''<br>
Determine the number of combinations that can be made out of ''n'' symbols, ''p'' symbols in each; with this limitation, that no combination of ''q'' symbols, which may appear in any one of them shall be repeated in any other.
|<ref name="Woolhouse"/>
}}
이는 현대적 용어로는 <math>(q,p,n)</math>-슈타이너 계를 다루는 것이다.

이후 이 문제는 1847년에 영국의 [[잉글랜드 성공회]] [[사제]] 토머스 페닝턴 커크먼({{llang|en|Thomas Penyngton Kirkman}}, 1806~1895)이 해결하였다.<ref>{{저널 인용|성=Kirkman|이름=Thomas P.|날짜=1847|제목=On a problem in combinations|저널=The Cambridge and Dublin Mathematical Journal|권=2|쪽=191–204|언어=en}}</ref> 그러나 이들의 논문은 크게 관심을 불러일으키지 못했다.

이후 울하우스와 커크먼과 독자적으로 [[야코프 슈타이너]]가 1853년에 블록 설계에 대한 논문을 출판하였다.<ref>{{저널 인용|first=Jakob|last=Steiner|저자링크=야코프 슈타이너|title=11. Combinatorische Aufgabe|journal=Journal für die Reine und Angewandte Mathematik|volume=45|year=1853|pages=181–182|issn=0075-4102|url=http://resolver.sub.uni-goettingen.de/purl?GDZPPN002147726|doi=10.1515/crll.1853.45.181|언어=de}}</ref> 이후 그의 이름을 따 <math>\lambda_t=1</math>인 <math>t</math>-블록 설계는 “슈타이너 계”로 불리게 되었다.

비트 설계는 1931년에 [[로버트 대니얼 카마이클]]이 최초로 발견하였으며,<ref>{{저널 인용|last=Carmichael|first=Robert Daniel|저자링크=로버트 대니얼 카마이클|title=Tactical configurations of rank two|url=https://archive.org/details/sim_american-journal-of-mathematics_1931-01_53_1/page/n223|journal=American Journal of Mathematics|volume=53|pages=217–240|year=1931|jstor=10.2307/2370885|doi=10.2307/2370885|언어=en}}</ref> [[에른스트 비트]]가 1938년에 [[마티외 군]]을 연구하던 도중 재발견하였다.<ref>{{저널 인용|last=Witt|first=Ernst|authorlink=에른스트 비트|title=Die 5-Fach transitiven Gruppen von Mathieu|journal=Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg|volume=12|pages=256–264|날짜=1938|doi=10.1007/BF02948947|언어=de}}</ref>

피셔 부등식은 [[로널드 피셔]]가 1940년에 증명하였다.<ref name="Fisher">{{저널 인용|이름=Ronald A.|성=Fisher|저자링크=로널드 피셔|제목=An examination of the different possible solutions of a problem in incomplete blocks|저널=Annals of Eugenics|권=10|호=1|날짜=1940-01|쪽=52–75|doi=10.1111/j.1469-1809.1940.tb02237.x|언어=en}}</ref>

== 각주 ==
{{각주}}
* {{서적 인용
 |last1=Street|first1= Anne Penfold |last2=Street|first2= Deborah J.
 |title=Combinatorics of experimental design
 |url=https://archive.org/details/combinatoricsofe0000stre|publisher=Clarendon Press
 |year=1987
 |isbn=0-19-853256-3
 | 언어=en
}}
* {{저널 인용|doi=10.1016/0012-365X(78)90122-X|제목=Steiner quadruple systems — a survey|이름=Charles C.|성=Lindner|이름2=Alexander|성2=Rosa|저널=Discrete Mathematics|권=22|호=2|날짜=1978|쪽=147-181|언어=en}}

== 외부 링크 ==
* {{eom|title=Block design }}
* {{eom|title=Symmetric design}}
* {{eom|title=Pairwise balanced design}}
* {{eom|title=Design with mutually orthogonal resolutions }}
* {{eom|title=Partially balanced incomplete block design }}
* {{eom|title=Balanced incomplete block design }}
* {{eom|title=Affine design}}
* {{eom|title=Steiner system}}
* {{매스월드|id=BlockDesign|title=Block design}}
* {{매스월드|id=SymmetricBlockDesign|title=Symmetric block design}}
* {{매스월드|id=SteinerSystem|title=Steiner system}}
* {{매스월드|id=SteinerTripleSystem|title=Steiner  triple system}}
* {{매스월드|id=SteinerQuadrupleSystem|title=Steiner  quadruple system}}
* {{매스월드|id=FishersBlockDesignInequality|title=Fisher's block design inequality}}
* {{매스월드|id=Bruck-Ryser-ChowlaTheorem|title=Bruck-Ryser-Chowla theorem}}
* {{nlab|id=block design|title=Block design}}
* {{nlab|id=Steiner system}}
* {{수학노트|title=슈타이너 시스템 S(5, 8, 24)}}
* {{웹 인용|url=http://www.maths.qmul.ac.uk/~leonard/designtheory.org/|제목=DesignTheory.org|출판사=Queen Mary University of London |언어=en}}

[[분류:조합론]]
[[분류:실험 설계]]
[[분류:집합족]]