Tolvfaldiga vägen

Den tolvfaldiga vägen är en klassificering av tolv närliggande problem inom kombinatoriken. Klassificeringen utgår från två mängder X och N med storlekarna |N| = n och |X| = x. De tolv problemen består i, att räkna hur många funktioner det finns från N till X under olika villkor. Det finns tre villkor som kan ställas på en funktion: Fri, surjektiv eller injektiv. Vidare kan elementen i N och X betraktas som särskiljbara eller icke särskiljbara, oberoende av varandra, vilket ger fyra olika möjligheter. Kombinerat med de tre funktionsalternativen, ger detta totalt tolv problem.

De tre villkor, som kan ställas på en funktion f från N till X är:

1. Inget villkor, dvs f kan vara vilken funktion som helst från N till X.
2. f är injektiv, inga två element i N avbildas på samma element i X av f.
3. f är surjektiv, för varje element i X finns ett element i N som avbildas på elementet i X.

De ekvivalensrelationer under vilka två funktioner g och f anses vara ekvivalenta definieras av om elementen i N och X är särskiljbara eller ej särskiljbara (man räknar alltså mer exakt ekvivalensklasser av funktioner):

1. Likhet. f = g.
2. Likhet upp till en permutation på N. f och g är ekvivalenta om det finns en permutation σ på N så att f(σ(a))) = g(a).
3. Likhet upp till en permutation på X. f och g är ekvivalenta om det finns en permutation π på X så att π(f(a))) = g(a).
4. Likhet upp till permutation på N och X. f och g är ekvivalenta om det finns permutationer σ och π på N och X respektive, så att π(f(σ(a))) = g(a).

De olika kombinationerna av villkoren på funktionerna och typerna av ekvivalensrelationer ger sammanlagt 12 olika problem.

Tolkning

De tolv problemen kan beskrivas med en modell där kulor fördelas i lådor. Elementen i mängden N är kulor och elementen i mängden X är lådor. Kulorna kan fördelas helt fritt, med restriktionen att varje låda måste innehålla minst en kula (surjektiv funktion) eller med restriktionen att varje låda får innehålla högst en kula (injektiv funktion). För vart och ett av dessa tre fall kan fördelningen ske med eller utan hänsyn till om kulor och lådor är särskiljbara eller inte, dvs fyra möjligheter. Alltså totalt 12 fall.

Exemplifiering av de tolv fallen; Antag att vi har två kulor (n = 2) och tre lådor (x = 3) och att kulorna får fördelas fritt. Om både kulorna och lådorna är särskiljbara, fall I, säg N = {a, b} och X = {1, 2, 3}, så finns totalt 9 möjligheter att fördela kulorna i lådorna, som syns i tabellen till vänster. Om kulorna inte är särskiljbara, fall IV, finns bara 6 möjligheter, vilket syns i andra tabellen. Om kulorna, men inte lådorna, är särskiljbara, fall VII, finns två möjligheter. Om varken lådorna eller kulorna är särskiljbara, fall X, finns bara två möjligheter, illustrerat i tabellen till höger.

Fri fördelning av kulor

2 särskiljbara kulor, 3 särskiljbara lådor Låda 1 Låda 2 Låda 3 a, b a b b a a b a, b a b b a b a a, b

2 ej särskiljbara kulor, 3 särskiljbara lådor Låda 1 Låda 2 Låda 3 2 kulor 1 kula 1 kula 1 kula 1 kula 2 kulor 1 kula 1 kula 2 kulor

2 särskiljbara kulor, 3 ej särskiljbara lådor Låda Låda Låda a, b a b

2 ej särskiljbara kulor, 3 ej särskiljbara lådor Låda Låda Låda 1 kula 1 kula 2 kulor

Om både kulor och lådor är särskiljbara, men det kravet ställs att varje låda får innehålla högst en kula, fall II, finns 6 möjligheter. Om kulorna inte är särskiljbara, fall V, finns 3 möjligheter. Om lådorna, men inte kulorna, är särskiljbara, fall VIII, finns en möjlighet. Om varken kulor eller lådor är särskiljbara, fall XI, finns återigen bara en möjlighet.

Högst en kula i varje låda

2 särskiljbara kulor, 3 särskiljbara lådor Låda 1 Låda 2 Låda 3 a b a b b a a b b a b a

2 ej särskiljbara kulor, 3 särskiljbara lådor Låda 1 Låda 2 Låda 3 1 kula 1 kula 1 kula 1 kula 1 kula 1 kula

2 särskiljbara kulor, 3 ej särskiljbara lådor Låda Låda Låda a b

2 ej särskiljbara kulor, 3 ej särskiljbara lådor Låda Låda Låda 1 kula 1 kula

Om man istället använder kravet att varje låda måste innehålla minst en kula finns inga möjligheter med två kulor och tre lådor, eftersom man inte har tillräckligt många kulor. Säg att man istället har tre kulor, a, b och c, och två lådor, 1 och 2. Om både lådor och kulor är särskiljbara, fall III, finns 6 möjligheter. Om lådorna, men inte kulorna, är särskiljbara, fall VI, finns 2 möjligheter. Om kulorna, men inte lådorna, är särskiljbara, fall IX, finns tre möjligheter. Om varken lådor eller kulor är särskiljbara, fall XII, finns en möjlighet.

Minst en kula varje låda

3 särskiljbara kulor, 2 särskiljbara lådor Låda 1 Låda 2 a, b c a b, c a, c b c a, b b, c a b a, c

3 ej särskiljbara kulor, 2 särskiljbara lådor Låda 1 Låda 2 1 kula 2 kulor 2 kulor 1 kula

3 särskiljbara kulor, 2 ej särskiljbara lådor Låda Låda a, b c a b, c a, c b

3 ej särskiljbara kulor, 2 ej särskiljbara lådor Låda Låda 1 kula 2 kulor

De tolv problemen

I. Funktioner från N till X

Detta fall är ekvivalent med att räkna följder av n element från X. Varje element i följden kan väljas på x sätt, det totala antalet funktioner är alltså xⁿ.

II. Injektiva funktioner från N till X

Detta fall är ekvivalent med att räkna följder av n distinkta element från X, dvs följder utan upprepningar. Det första elementet kan väljas på n sätt, det andra på n - 1 sätt, osv, för varje element fås en valmöjlighet mindre. Svaret är alltså den fallande potensen:

$x^{\underline {n}}=x(x-1)(x-2)\cdots (x-n+1)={\frac {x!}{(x-n)!}}$

III. Surjektiva funktioner från N till X

För att räkna surjektiva funktioner partitionerar man först N i x delmängder, vilket kan göras på S(n, x) sätt, där S(n, x) är ett Stirlingtal av andra slaget. Sedan tas ett element i X så att alla element i en delmängd i partitioneringen av N avbildas på det elementet, vilket kan göras på x! sätt. Det totala antalet funktioner är alltså x!S(n, x).

IV. Funktioner från N till X, upp till permutationer på N

Detta fall är ekvivalent med att räkna multimängder av storlek n med element från X, eftersom, för varje element i X så bestämmer f hur många element från N som avbildas på detta elementet, och funktioner som har samma "multipliciteter" för varje element i X är ekvivalenta under permutationer. Antalet multikombinationer av storlek n från en mängd med X element är samma tal som antalet kombinationer av storlek n från en mängd med x + n - 1 element. Svaret kan alltså uttryckas som en binomialkoefficient:

${\binom {x+n-1}{n}}={\frac {(x+n-1)(x+n-2)\cdots (x+1)x}{n!}}={\frac {(x+n-1)^{\underline {n}}}{n!}}$

V. Injektiva funktioner från N till X, upp till permutationer på N

Det här fallet är likartat det föregående fallet, men för varje element i x måste det finnas ett element i N som avbildas på elementet i x, multimängderna blir alltså vanliga mängder. Vi ska alltså hitta ur många delmängder av X med n element det finns, så svaret kan alltså återigen uttryckas som en binomialkoefficient:

${\binom {x}{n}}={\frac {x^{\underline {n}}}{n!}}$

VI. Surjektiva funktioner från N till X, upp till permutationer på N

Detta fallet är ekvivalent med att räkna multimängder av storlek n med element från X, där varje element i X förekommer minst en gång. Detta är alltså liknande fallet med funktioner från N till X, upp till permutationer på N, dock måste varje multiplicitet vara minst ett, dvs man har mindre valmöjlighet. Om vi antar att vi har minst en kula i varje låda (dvs kravet på surjektivitet är uppfyllt) kan vi tänka oss att vi tar bort en kula från varje låda, då de resterande kulorna kan tolkas som en multikombination på n - x element. Svaret är alltså:

${\binom {n-1}{n-x}}={\binom {n-1}{x-1}}$.

En annan tolkning är antalet heltalskompositioner av talet n med längden x, dvs antalet sätt som talet n kan skrivas som en summa av x positiva heltal, med hänsyn tagen till dessas inbördes ordning. Enklast uttryckt som antalet ordnade x-partitioner av talet n.

VII. Funktioner från N till X, upp till permutationer på X

Detta fallet kan ses som antalet partitioner av N bestående av maximalt x delmänger, så att alla element i en delmängd avbildas på samma element i X. Detta kan alltså uttryckas som en summa av Stirlingtal:

$\sum _{k=0}^{x}S(n,k)$

Om x = n får man ett Belltal.

VIII. Injektiva funktioner från N till X, upp till permutationer på X

Antalet injektiva funktioner från N till X tolkades som antalet följder med längd n av element i X utan upprepningar. För att detta ska vara möjligt måste n vara mindre än eller lika med x, om n är större än x finns inga följder utan upprepningar med längd n av element i X. Permutationerna på X gör vidare så att vilken följd med längd n utan upprepning som helst är ekvivalent med någon annan. Därför finns det exakt en funktion som uppfyller kravet om n ≤ x, ingen annars. Detta kan uttryckas som talet $[n\leq x]$ med hjälp av Iversonklammer.

IX. Surjektiva funktioner från N till X, upp till permutationer på X

Detta är ekvivalent med att räkna partitioner av N i exakt x delmängder, alla i element i en delmängd avbildas på samma element i x. Svaret är alltså Stirlingtalet av andra slaget, S(n, x).

X. Funktioner från N till X, upp till permutationer på N och X

Detta fallet kan tolkas som en heltalspartition av talet n i x eller färre delar. Om p_k(x) är antalet partitioner av n i k delar är alltså svaret:

$\sum _{k=0}^{x}p_{k}(n)$

XI. Injektiva funktioner från N till X, upp till permutationer på N och X

Detta fallet kan reduceras till fallet med injektiva funktioner upp till permutationer på X, så svaret är detsamma, $[n\leq x]$.

XII. Surjektiva funktioner från N till X, upp till permutationer på N och X

Detta fallet är ekvivalent med antalet heltalspartitioner av n i exakt x delar, så svaret är p_x(n).

Referenser

• Stanley, Richard P. (1986). Enumerative Combinatorics. ISBN 0-534-06546-5 
• Knuth, Donald (2011). The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. sid. 390. ISBN 978-0-201-03804-0