Steinertrippelsystem

Ett Steinertrippelsystem är en kombinatorisk konfiguration, det vill säga en indelning i delmängder av elementen i en mängd, enligt bestämda regler. Ett Steinertrippelsystem är en uppdelning av mängden X i delmängder om tre element, sådana att varje par av element i X tillhör en och endast en av dessa delmängder. Systemet är uppkallat efter Jakob Steiner.

Geometrisk representation av S(7). Varje linje, inklusive cirkeln, innehåller 3 punkter och varje punktpar tillhör en unik linje.

Om mängden X har v element har man ett Steinertrippelsystem, S(v), av ordning v , som existerar om och endast om v Ξ 1 eller 3 (mod 6). Följande är exempel på system av ordning 1, 2 respektive 3.

S(3) = {{${1,2,3}$}}

S(7) = {{1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {5,6,1}, {6,7,2}, {7,1,3}}

S(9) = {{1,2,3}, {4,5,6}, {7,8,9},

{1,4,7}, {2,5,8}, {3,6,9},

{1,5,9}, {2,6,7}, {3,4,8},

{1,6,8}, {2,4,9}, {3,5,7}}.

Systemet S(9) är här uppdelat i 4 komponenter om vardera 3 trippler.

Antalet delmängder i ett trippelsystem av ordning $v$ är $v(v-1)/6$.

De tre Steinertrippelsystemen ovan är unika så när som på isomorfier, det vill säga permutationer av elementen i mängden X. För v = 13 finns 2 och för v = 15 exakt 80 icke-isomorfa Steinertrippelsystem.

Kirkmantrippelsystem

Ett Kirkmantrippelsystem av ordningen v = 6n + 3, är ett Steinertrippelsystem av ordning v sådant att systemets delmängder kan delas upp på 3n + 1 komponenter om vardera 2n + 1 trippler och att varje element i X förekommer en och endast en gång i varje komponent.

S(9) ovan, är ett Kirkmantrippelsystem uppdelat i 4 komponenter om vardera 3 trippler. Det berömda problemet om, "Pensionatsdamernas promenad", kan lösas med ett sådant system av ordning 15, där damerna delas upp i 7 komponenter om vardera 5 trippler.

Problemet lyder: Femton damer boende på ett pensionat under en vecka, skall i grupper om tre varje dag ta en promenad. Det är ett villkor att i ingen av promenadgrupperna får ett och samma par förekomma.

Problemet att finna Kirkmantrippelsystem ställdes 1847 av T.P. Kirkman. Bland andra, bidrog matematikerna William Burnside, Arthur Cayley och James Joseph Sylvester med dellösningar. Det allmänna problemet löstes först 1968.

Källor

• Ryser, H. J. Combinatorial Mathematics, Buffalo, NY, 1963.
• Bernt Lindström, Elementa nr. 4, 1972.