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.