Tolv gange - Twelvefold way

I kombinatorik er den tolvfoldige måde en systematisk klassificering af 12 relaterede opregningsproblemer vedrørende to begrænsede sæt, som omfatter de klassiske problemer med at tælle permutationer , kombinationer , multisæt og partitioner enten af et sæt eller et tal . Ideen om klassificeringen krediteres Gian-Carlo Rota , og navnet blev foreslået af Joel Spencer .

Oversigt

Lad $N$ og $X$ være endelige sæt . Lad og vær sætternes kardinalitet . Således er $N$ et $n$ -sæt, og $X$ er et $x$ -sæt. ${\ displaystyle n = | N |}$ ${\ displaystyle x = | X |}$

Det generelle problem, vi overvejer, er optællingen af ækvivalensklasser af funktioner . ${\ displaystyle f: N \ til X}$

Funktionerne er underlagt en af de tre følgende begrænsninger:

Ingen betingelse: hver $a$ i $N$ kan sendes af $f$ til en hvilken som helst $b$ i $X$ , og hver $b$ kan forekomme flere gange.
$f$ er injektiv : hver værdi for $a$ i $N$ skal være forskellig fra hinanden, og derfor kan hver $b$ i $X$ højst forekomme én gang i billedet af $f$ . ${\ displaystyle f (a)}$
$f$ er surjektiv : for hver $b$ i $X$ skal der være mindst én $et$ i $N$ , således at , således hver $b$ vil forekomme mindst en gang i billedet af $f$ . ${\ displaystyle f (a) = b}$

(Betingelsen " $f$ er bijektiv " er kun en mulighed, når ; men så svarer det til både " $f$ er injektiv" og " $f$ er surjektiv".) ${\ displaystyle n = x}$

Der er fire forskellige ækvivalensforhold, der kan defineres på funktionsmængden $f$ fra $N$ til $X$ :

lighed;
lighed op til en permutation af $N$ ;
lighed op til en permutation af $X$ ;
lighed op til permutationer af $N$ og $X$ .

De tre betingelser for funktionerne og de fire ækvivalensforhold kan parres på $3 \times 4 = 12$ måder.

De tolv problemer med at tælle ækvivalensklasser af funktioner involverer ikke de samme vanskeligheder, og der er ikke én systematisk metode til at løse dem. To af problemerne er trivielle (antallet af ækvivalensklasser er 0 eller 1), fem problemer har et svar i form af en multiplikativ formel for n og x , og de resterende fem problemer har et svar med hensyn til kombinatoriske funktioner ( Stirling -tal og partitionsfunktionen for et givet antal dele).

Indarbejdelsen af klassiske opregningsproblemer i denne indstilling er som følger.

Tælling n -permutations (dvs. partielle permutationer eller sekvenser uden gentagelse) af X svarer til tælling injektive funktioner $N \to X$ .
Tælling n -enhed bestaaende af X svarer til tælling injektive funktioner $N \to X$ op til permutationer af N .
Tælling af permutationer af sættet X svarer til at tælle injektive funktioner $N \to X$ når n = x, og også at tælle surjektive funktioner $N \to X$ når $n = x$ .
Tælle multimængder af størrelse n (også kendt som n -enhed bestaaende med gentagelser) af elementer i X svarer til at tælle alle funktioner $N \to X$ op til permutationer af N .
Counting skillevægge i sættet N i x delmængder svarer til at tælle alle Surjective funktioner $N \to X$ op til permutationer af X .
Tælle sammensætninger af antallet n i x dele svarer til tælle alle Surjective funktioner $N \to X$ op til permutationer af N .

Synspunkter

De forskellige problemer på den tolvfoldige måde kan betragtes fra forskellige synsvinkler.

Bolde og kasser

Traditionelt er mange af problemerne på den tolvfoldige måde blevet formuleret i form af at placere bolde i kasser (eller en lignende visualisering) i stedet for at definere funktioner. Sættet N kan identificeres med et sæt bolde og X med et sæt kasser; funktionen ƒ : $N \to X$ beskriver derefter en måde at fordele boldene i kasserne, nemlig ved at putte hver bold a i kasse ƒ ( a ). En funktion tilskriver et unikt billede til hver værdi i sit domæne; denne egenskab afspejles ved den egenskab, at enhver bold kun kan gå ind i en kasse (sammen med kravet om, at ingen bold skal forblive uden for kasserne), hvorimod enhver kasse kan rumme (i princippet) et vilkårligt antal bolde. Kræver derudover ƒ for at være injektiv betyder at forbyde at lægge mere end én bold i en hvilken som helst kasse, mens at kræve ƒ at være subjektiv betyder at insistere på at hver kasse indeholder mindst en kugle.

Tælling af modulo -permutationer af N eller X reflekteres ved at kalde kuglerne eller kasserne henholdsvis "ikke skelnes". Dette er en upræcis formulering, der har til formål at indikere, at forskellige konfigurationer ikke skal tælles separat, hvis den ene kan omdannes til den anden ved en eller anden udveksling af bolde eller kasser. Denne mulighed for transformation formaliseres af handlingen ved hjælp af permutationer.

Prøveudtagning

En anden måde at tænke på nogle af sagerne er i form af stikprøver , i statistik . Forestil dig en population af X- poster (eller mennesker), hvoraf vi vælger N . To forskellige ordninger beskrives normalt, kendt som " prøveudtagning med udskiftning " og " prøveudtagning uden udskiftning ". I det tidligere tilfælde (prøveudtagning med udskiftning), når vi har valgt et element, sætter vi det tilbage i befolkningen, så vi kan vælge det igen. Resultatet er, at hvert valg er uafhængigt af alle de andre valg, og sættet af prøver betegnes teknisk set som uafhængigt identisk fordelt . I sidstnævnte tilfælde, men når vi har valgt et element, lægger vi det til side, så vi ikke kan vælge det igen. Det betyder, at handlingen med at vælge et emne har en effekt på alle de følgende valg (det bestemte element kan ikke ses igen), så vores valg er afhængige af hinanden.

En anden skelnen mellem prøveudtagningsordninger er, om bestilling har betydning. For eksempel, hvis vi har ti varer, hvoraf vi vælger to, så er valget (4,7) forskelligt fra (7,4), hvis bestilling betyder noget; på den anden side, hvis bestilling ikke betyder noget, så er valgene (4,7) og (7,4) ækvivalente. (En anden måde at tænke på dette er at sortere hvert valg efter varenummeret og smide eventuelle dubletter, der resulterer i det.)

De to første rækker og kolonner i nedenstående tabel svarer til prøveudtagning med og uden udskiftning, med og uden hensyn til rækkefølge. Tilfældene med prøveudtagning med udskiftning findes i kolonnen mærket "Enhver f ", mens tilfælde af prøveudtagning uden udskiftning findes i kolonnen mærket "Injektiv f ". De tilfælde, hvor bestillingsforhold findes i rækken mærket "Distinct", og de tilfælde, hvor bestilling ikke betyder noget, findes i rækken mærket "S _n baner". Hver tabelpost angiver, hvor mange forskellige valgmuligheder der er i et bestemt prøveudtagningsskema. Tre af disse tabelposter svarer også til sandsynlighedsfordelinger . Prøveudtagning med udskiftning, hvor bestilling betyder noget, kan sammenlignes med at beskrive den fælles fordeling af N separate tilfældige variabler , hver med en X -fold kategorisk fordeling . Prøveudtagning med udskiftning, hvor bestilling ikke betyder noget, er dog sammenlignelig med at beskrive en enkelt multinomial fordeling af N, der trækker fra en X -foldet kategori, hvor kun det antal, der ses for hver kategori, har betydning. Prøveudtagning uden udskiftning, hvor bestilling ikke betyder noget, kan sammenlignes med en enkelt multivariat hypergeometrisk fordeling . Prøvetagning uden udskiftning, hvor ordren betyder noget, synes ikke at svare til en sandsynlighedsfordeling. Bemærk, at i alle "injektive" tilfælde (dvs. prøveudtagning uden udskiftning) er antallet af valgmuligheder nul, medmindre $N \leq X$ . ("Sammenlignelig" i ovenstående tilfælde betyder, at hvert element i prøveområdet i den tilsvarende fordeling svarer til et separat sæt valg, og derfor angiver tallet i den relevante boks størrelsen på prøveområdet for den givne fordeling.)

Set fra prøveudtagningsperspektivet er kolonnen mærket "Surjective f " noget underlig: I det væsentlige fortsætter vi med at prøveudtagning med udskiftning, indtil vi har valgt hvert element mindst én gang. Derefter tæller vi, hvor mange valg vi har taget, og hvis det ikke er lig med N , skal du smide hele sættet ud og gentage. Dette kan vagt sammenlignes med kuponopsamlerens problem , hvor processen involverer "indsamling" (ved prøveudtagning med udskiftning) et sæt X -kuponer, indtil hver kupon er set mindst én gang. Bemærk, at der i alle "Surjective" sager, antallet af sæt af valg er nul, medmindre $N \geq X$ .

Mærkning, markering, gruppering

En funktion ƒ : $N \to X$ kan betragtes ud fra X eller N 's perspektiv . Dette fører til forskellige synspunkter:

funktionen ƒ etiketter hvert element af N af et element af X .
funktionen ƒ vælger (vælger) et element i sættet X for hvert element af N , i alt n valg.
funktionens ƒ grupper elementerne af N sammen, der er mappet til det samme element af X .

Disse synspunkter er ikke lige velegnede til alle sager. Mærkning og udvælgelsessynspunkter er ikke godt kompatible med permutation af elementerne i X , da dette ændrer etiketterne eller markeringen; på den anden side giver grupperingens synspunkt ikke fuldstændige oplysninger om konfigurationen, medmindre elementerne i X frit kan permuteres. Mærkning og markering synspunkter er mere eller mindre ækvivalente, når N ikke er permuteret, men når det er, er udvælgelsessynspunktet mere velegnet. Udvælgelsen kan derefter ses som en uordnet valg: et enkelt valg af a (multi) sæt af n elementer fra X er lavet.

Mærkning og markering med eller uden gentagelse

Når man betragter ƒ som en mærkning af elementerne i N , kan sidstnævnte betragtes som arrangeret i en sekvens, og etiketterne fra X som successivt tildelt dem. Et krav om at ƒ skal være injektiv betyder, at ingen etiket kan bruges anden gang; resultatet er en række etiketter uden gentagelse . I mangel af et sådant krav bruges terminologien "sekvenser med gentagelse", hvilket betyder, at etiketter kan bruges mere end én gang (selvom sekvenser, der tilfældigvis er uden gentagelse, også er tilladt).

Når man betragter ƒ som et uordnet udvalg af elementerne i X , gælder den samme slags skelnen. Hvis ƒ skal være injektiv, skal valget omfatte n adskilte elementer af X , så det er en undersætning af X af størrelse n , også kaldet en n - kombination . Uden kravet kan et og samme element af X forekomme flere gange i markeringen, og resultatet er et multisæt af størrelse n af elementer fra X , også kaldet en n - multikombination eller n -kombination med gentagelse.

Kravet om at ƒ skal være subjektivt set fra mærkningselementerne i N betyder, at hver etiket skal bruges mindst én gang; set fra valg af synspunkt fra X betyder det, at hvert element af X skal inkluderes i markeringen mindst én gang. Mærkning med overgivelse svarer til en gruppering af elementer af N efterfulgt af mærkning af hver gruppe med et element af X , og er derfor noget mere kompliceret at beskrive matematisk.

Opdelinger af sæt og tal

Når man betragter ƒ som en gruppering af elementerne i N (som forudsætter, at man identificerer under permutationer af X ), kræver det, at ƒ skal være subjektivt, at antallet af grupper skal være nøjagtigt x . Uden dette krav kan antallet af grupper højst være x . Kravet om injektiv ƒ betyder, at hvert element i N skal være en gruppe i sig selv, som højst efterlader en gyldig gruppering og derfor giver et ret uinteressant tælleproblem.

Når man derudover identificerer sig under permutationer af N , betyder det, at man glemmer grupperne selv, men kun bevarer deres størrelser. Disse størrelser kommer i øvrigt ikke i nogen bestemt rækkefølge, mens den samme størrelse kan forekomme mere end én gang; man kan vælge at arrangere dem i en svagt faldende liste over tal, hvis sum er tallet n . Dette giver den kombinatoriske forestilling om en opdeling af tallet n i nøjagtigt x (for surjektiv ƒ ) eller højst x (for vilkårlige ƒ ) dele.

Formler

Formler for de tolvfoldige mådees forskellige tilfælde er opsummeret i følgende tabel; hver tabelindgang linker til et underafsnit nedenfor, der forklarer formlen.

De tolv kombinatoriske objekter og deres opregningsformler.
f -klasse	Enhver f	Injektiv f	Subjektiv f
Udpræget $f$	n -følge i X ${\ displaystyle x^{n}}$	n -permutation af X ${\ displaystyle x^{\ understregning {n}}}$	sammensætning af N med x delmængder ${\ displaystyle \ textstyle x! \ {{n \ oven på x} \}}$
S _n kredsløb $f \circ S n$	n -multisubset af X ${\ displaystyle {\ binom {x+n-1} {n}}}$	n -delsæt af X ${\ displaystyle {\ binom {x} {n}}}$	sammensætning af n med x udtryk ${\ displaystyle {\ binom {n-1} {nx}}}$
S _x kredsløb $S x \circ f$	opdeling af N i ≤ x delmængder ${\ displaystyle \ sum _ {k = 0}^{x} \ venstre \ {{n \ oven på k} \ højre \}}$	opdeling af N i ≤ x elementer ${\ displaystyle [n \ leq x]}$	opdeling af N i x delmængder ${\ displaystyle \ venstre \ {{n \ oven på x} \ højre \}}$
S _n × S _x kredsløb $S x \circ f \circ S n$	opdeling af n i ≤ x dele ${\ displaystyle p_ {x} (n+x)}$	opdeling af n i ≤ x dele 1 ${\ displaystyle [n \ leq x]}$	opdeling af n i x dele ${\ displaystyle p_ {x} (n)}$

De særlige betegnelser, der bruges, er:

den faldende factorial magt , ${\ displaystyle x^{\ understregning {n}} = {\ frac {x!} {(xn)!}} = x (x-1) (x-2) \ cdots (x-n+1)}$
den stigende fabriksmagt , ${\ displaystyle x^{\ overline {n}} = {\ frac {(x+n-1)!} {(x-1)!}} = x (x+1) (x+2) \ cdots ( x+n-1)}$
den faktorielle ${\ displaystyle n! = n^{\ understregning {n}} = n (n-1) (n-2) \ cdots 1}$
det Stirling antallet af anden art , som angiver antallet af måder at opdele et sæt af n elementer i k delmængder ${\ displaystyle \ textstyle \ {{n \ atop k} \}}$
den binomialkoefficienten ${\ displaystyle \ textstyle {\ binom {n} {k}} = {\ frac {n^{\ understregning {k}}} {k!}}}$
den Iverson beslaget [] koder for en sandhed værdi som 0 eller 1
antallet af partitioner af n i k dele ${\ displaystyle p_ {k} (n)}$

Intuitiv betydning af rækkerne og kolonnerne

Dette er et hurtigt resumé af, hvad de forskellige sager betyder. Sagerne er beskrevet detaljeret nedenfor.

Tænk på et sæt X -nummererede genstande (nummereret fra 1 til x ), hvorfra vi vælger n , hvilket giver en ordnet liste over emnerne: f.eks. Hvis der er elementer, som vi vælger , kan resultatet være listen (5, 2 , 10). Vi tæller derefter, hvor mange forskellige sådanne lister der findes, nogle gange transformerer vi først listerne på måder, der reducerer antallet af forskellige muligheder. ${\ displaystyle x = 10}$ ${\ displaystyle n = 3}$

Så betyder kolonnerne:

Enhver f : Når vi har valgt en vare, sætter vi den tilbage, så vi kan vælge den igen.
Injektiv f : Efter at vi har valgt et element, sætter vi det til side, så vi ikke kan vælge det igen; derfor ender vi med n forskellige ting. Det er derfor nødvendigt, medmindre der overhovedet ikke kan vælges lister. ${\ displaystyle n \ leq x}$
Subjektiv f : Når vi har valgt et element, sætter vi det tilbage, så vi kan vælge det igen - men i slutningen skal vi ende med at have valgt hvert element mindst én gang. Det er derfor nødvendigt, medmindre der overhovedet ikke kan vælges lister. ${\ displaystyle n \ geq x}$

Og rækkerne betyder:

Distinkt: Lad listerne være i fred; tæl dem direkte.
S _n baner: Inden tælling sorteres listerne efter varenummeret på de valgte emner, så rækkefølgen ikke betyder noget, f.eks. (5, 2, 10), (10, 2, 5), (2, 10, 5) → (2, 5, 10).
S _x kredsløb: Før tælling skal du gennumre de sete elementer, så det første element, der ses, har nummer 1, det andet 2 osv. Tal kan gentages, hvis et element blev set mere end én gang, f.eks. (3, 5, 3), ( 5, 2, 5), (4, 9, 4) → (1, 2, 1) mens (3, 3, 5), (5, 5, 3), (2, 2, 9) → (1, 1, 2).
S _n × S _x baner: To lister tæller som det samme, hvis det er muligt at både omorganisere og ommærke dem som ovenfor og producere det samme resultat. For eksempel tæller (3, 5, 3) og (2, 9, 9) som det samme, fordi de kan omarrangeres som (3, 3, 5) og (9, 9, 2) og derefter ommærkning producerer begge det samme liste (1, 1, 2).

Detaljer om de forskellige sager

Nedenstående sager er ordnet på en sådan måde, at de grupper, som de argumenter, der bruges i tællingen, er relateret til, er grupperet, hvilket ikke er rækkefølgen i den givne tabel.

Funktioner fra N til X

Denne sag svarer til at tælle sekvenser af n elementer af X uden begrænsning: en funktion $f : N \to X$ bestemmes af n -billederne af elementerne i N , som hver kan uafhængigt vælges blandt elementerne i x . Dette giver i alt x ⁿ muligheder.

Eksempel:

${\ displaystyle X = \ {a, b, c \}, N = \ {1,2 \} {\ tekst {, derefter}}}$

${\ displaystyle \ left \ vert \ {(a, a), (a, b), (a, c), (b, a), (b, b), (b, c), (c, a) , (c, b), (c, c) \} \ right \ vert = 3^{2} = 9}$

Injektive funktioner fra N til X

Denne sag svarer til at tælle sekvenser af n adskilte elementer af X , også kaldet n -permutationer af X , eller sekvenser uden gentagelser ; igen denne sekvens er dannet af n billeder af elementerne i N . Denne sag adskiller sig fra den med ubegrænsede sekvenser ved, at der er ét valg færre til det andet element, to færre til det tredje element osv. Derfor i stedet for ved en almindelig effekt på x er værdien givet ved en faldende faktoriel kraft på x , hvor hver successive faktor er en færre end den foregående. Formlen er

{\ displaystyle x^{\ understregning {n}} = x (x-1) \ cdots (x-n+1).}

Bemærk, at hvis $n > x$ så opnår man en faktor nul, så i dette tilfælde er der slet ingen injektive funktioner $N \to X$ ; dette er bare en gentagelse af duehulsprincippet .

Eksempel:

${\ displaystyle X = \ {a, b, c, d \}, N = \ {1,2 \} {\ tekst {, derefter}}}$

${\ displaystyle \ left \ vert \ {(a, b), (a, c), (a, d), (b, a), (b, c), (b, d), (c, a) , (c, b), (c, d), (d, a), (d, b), (d, c) \} \ right \ vert = 4^{\ understregning {2}} = 4 \ gange 3 = 12}$

Injektive funktioner fra N til X , op til en permutation af N

Dette tilfælde er ækvivalent med tælle delmængder med n elementer af X , også kaldet n -enhed bestaaende af X : blandt sekvenserne af n særskilte elementer af X , de, der kun afviger i rækkefølgen af deres vilkår identificeres ved permutationer af N . Da dette i alle tilfælde grupperer nøjagtigt n ! forskellige sekvenser, kan vi dividere antallet af sådanne sekvenser med n ! at få antallet af n -enhed bestaaende af X . Dette tal er kendt som den binomiske koefficient , som derfor er givet af ${\ displaystyle {\ tbinom {x} {n}}}$

{\ displaystyle {\ binom {x} {n}} = {\ frac {x^{\ understregning {n}}} {n!}} = {\ frac {x (x-1) \ cdots (x-n +2) (x-n+1)} {n (n-1) \ cdots 2 \ cdot 1}}.}

Eksempel:

${\ displaystyle X = \ {a, b, c, d \}, N = \ {1,2 \} {\ tekst {, derefter}}}$

${\ displaystyle \ left \ vert \ {\ {a, b \}, \ {a, c \}, \ {a, d \}, \ {b, c \}, \ {b, d \}, \ {c, d \} \} \ højre \ vert = {\ frac {4^{\ understregning {2}}} {2!}} = {\ frac {4 \ gange 3} {2}} = 6}$

Funktioner fra N til X , op til en permutation af N

Denne sag svarer til at tælle multiset med n elementer fra X (også kaldet n -multikombinationer). Årsagen er, at det for hvert element i X er bestemt, hvor mange elementer af N der er knyttet til det med f , mens to funktioner, der giver de samme sådanne "multipliciteter" til hvert element af X, altid kan transformeres til et andet ved en permutation af N . Formlen, der tæller alle funktioner $N \to X,$ er ikke nyttig her, fordi antallet af dem grupperet sammen efter permutationer af N varierer fra en funktion til en anden. Som forklaret under kombinationer , kan antallet af n -multikombinationer fra et sæt med x -elementer ses at være det samme som antallet af n -kombinationer fra et sæt med $x + n -1$ -elementer. Dette reducerer problemet til en anden på den tolvfoldige måde og giver som resultat

{\ displaystyle {\ binom {x+n-1} {n}} = {\ frac {(x+n-1) (x+n-2) \ cdots (x+1) x} {n (n- 1) \ cdots 2 \ cdot 1}} = {\ frac {x^{\ overline {n}}} {n!}}.}

Eksempel:

${\ displaystyle X = \ {a, b, c \}, N = \ {1,2 \} {\ tekst {, derefter}}}$

${\ displaystyle \ left \ vert \ {\ {a, a \}, \ {a, b \}, \ {a, c \}, \ {b, b \}, \ {b, c \}, \ {c, c \} \} \ højre \ vert = {\ frac {3^{\ overline {2}}} {2!}} = {\ frac {4 \ gange 3} {2}} = 6}$

Surjektive funktioner fra N til X , op til en permutation af N

Denne sag svarer til at tælle multisets med n elementer fra X , for hvilke hvert element af X forekommer mindst én gang. Dette svarer også til at tælle sammensætningerne af n med x (ikke-nul) udtryk ved at angive multiplikationerne af elementerne i x i rækkefølge. Korrespondancen mellem funktioner og multisæt er den samme som i det foregående tilfælde, og surjektivitetskravet betyder, at alle multiplikationer er mindst én. Ved at reducere alle multiplikationer med 1 reduceres dette til det foregående tilfælde; da ændringen reducerer værdien af n med x , er resultatet

{\ displaystyle {\ binom {n-1} {nx}}.}

Bemærk, at når n < x der slet ikke er nogen surjektive funktioner $N \to X$ (en slags "tomt duehul" -princip); dette tages i betragtning i formlen ved konventionen, at binomiske koefficienter altid er 0, hvis det lavere indeks er negativt. Den samme værdi er også givet ved udtrykket

{\ displaystyle {\ binom {n-1} {x-1}},}

undtagen i ekstreme tilfælde $n = x = 0$ , hvor med førstnævnte udtryk giver korrekt , mens sidstnævnte giver forkert . ${\ displaystyle {\ tbinom {-1} {0}} = 1}$ ${\ displaystyle {\ tbinom {-1} {-1}} = 0}$

Resultatet form foreslår, at man leder efter en måde at knytte en klasse af surjektive funktioner $N \to X$ direkte til et delsæt af $n - x$ elementer valgt fra i alt $n - 1$ , hvilket kan gøres som følger. Vælg først en samlet rækkefølge af sætene N og X , og bemærk, at ved at anvende en passende permutation af N , kan hver surjektiv funktion $N \to X$ omdannes til en unik svagt stigende (og naturligvis stadig surjektiv) funktion. Hvis man forbinder elementerne i N i rækkefølge med $n - 1$ buer til en lineær graf , så vælger du en hvilken som helst delmængde af $n - x$ buer og fjerner resten, opnår du en graf med x tilsluttede komponenter, og ved at sende disse til de efterfølgende elementer af X opnår man en svagt stigende surjektiv funktion $N \to X$ ; også størrelserne på de tilsluttede komponenter giver en sammensætning af n i x dele. Dette argument er dybest set det, der er givet på stjerner og søjler , bortset fra at der foretages det komplementære valg af $x - 1$ "adskillelser".

Eksempel:

${\ displaystyle X = \ {a, b \}, N = \ {1,2,3 \} {\ tekst {, derefter}}}$

${\ displaystyle \ left \ vert \ {\ {a, a, b \}, \ {a, b, b \} \} \ right \ vert = {\ binom {3-1} {3-2}} = {\ binom {2} {1}} = {\ frac {2!} {1! \ times (2-1)!}} = 2}$

Injektive funktioner fra N til X , op til en permutation af X

I dette tilfælde ser vi sekvenser af n særskilte elementer fra X , men identificere dem, der opnås fra hinanden ved for hver element en permutation af X . Det er let at se, at to forskellige sådanne sekvenser altid kan identificeres: permutationen skal kortlægge termen i den første sekvens til termen i den anden sekvens, og da der ikke forekommer nogen værdi to gange i begge sekvenser, modsiger disse krav ikke hinanden; det er stadig at kortlægge de elementer, der ikke forekommer i den første sekvens, vedectivt til dem, der ikke forekommer i den anden sekvens på en vilkårlig måde. Det eneste faktum, der får resultatet til at afhænge af n og x overhovedet, er, at eksistensen af sådanne sekvenser til at begynde med kræver $n \leq x$ , efter duehulsprincippet. Tallet udtrykkes derfor som ved hjælp af Iverson -beslaget . ${\ displaystyle [n \ leq x]}$

Injektive funktioner fra N til X , op til permutationer af N og X

Denne sag er reduceret til den forrige: da alle sekvenser af n adskilte elementer fra X allerede kan transformeres til hinanden ved at anvende en permutation af X til hvert af deres udtryk, giver det heller ikke nogen ny identifikation at tillade omlægning af udtrykkene; tallet forbliver . ${\ displaystyle [n \ leq x]}$

Surjektive funktioner fra N til X , op til en permutation af X

Denne sag svarer til at tælle partitioner af N i x (ikke-tomme) undersæt eller tælle ækvivalensrelationer på N med nøjagtigt x klasser. For enhver surjektiv funktion $f : N \to X$ er forholdet mellem at have det samme billede under f sådan en ækvivalensrelation, og det ændres ikke, når en permutation af X efterfølgende anvendes; omvendt kan man gøre en sådan ækvivalensrelation til en surjektiv funktion ved at tildele elementerne i X på en eller anden måde til x ækvivalensklasserne. Antallet af sådanne partitioner eller ækvivalensforhold er pr. Definition Stirling -nummeret af den anden slags S ( n , x ), også skrevet . Dens værdi kan beskrives ved hjælp af en rekursionsrelation eller ved hjælp af genererende funktioner , men i modsætning til binomiske koefficienter er der ingen lukket formel for disse tal, der ikke indebærer en summering . ${\ displaystyle \ textstyle \ {{n \ oven på x} \}}$

Surjektive funktioner fra N til X

For hver Surjektiv $f : N \to X$ , sit kredsløb under permutationer af X har x ! elementer, da sammensætning (til venstre) med to forskellige permutationer af X aldrig giver den samme funktion på N (permutationerne skal variere ved et element af X , som altid kan skrives som f ( i ) for nogle i ∈ N , og sammensætningerne vil derefter variere ved i ). Det følger heraf, at tallet for denne sag er x ! gange tallet for den forrige sag, altså ${\ displaystyle \ textstyle x! \ {{n \ oven på x} \}.}$

Eksempel:

${\ displaystyle X = \ {a, b \}, N = \ {1,2,3 \} {\ tekst {, derefter}}}$

${\ displaystyle \ left \ vert \ {(a, a, b), (a, b, a), (a, b, b), (b, a, a), (b, a, b), ( b, b, a) \} \ right \ vert = \ textstyle 2! \ {{3 \ atop 2} \} = 2 \ times 3 = 6}$

Funktioner fra N til X , op til en permutation af X

Denne sag ligner den tilsvarende for surjektive funktioner, men nogle elementer af x svarer muligvis slet ikke til nogen ækvivalensklasse (da man betragter funktioner op til en permutation af X , er det ligegyldigt hvilke elementer der er tale om, bare hvor mange) . Som en konsekvens tæller man ækvivalensrelationer på N med højst x klasser, og resultatet opnås fra det nævnte tilfælde ved summering over værdier op til x , giver . I tilfælde x ≥ n udgør størrelsen af x slet ingen begrænsninger, og man tæller alle ækvivalensforhold på et sæt n elementer (ækvivalent alle partitioner af et sådant sæt); giver derfor et udtryk for Bell nummer B _n . ${\ displaystyle \ textstyle \ sum _ {k = 0}^{x} \ {{n \ oven på k} \}}$ ${\ displaystyle \ textstyle \ sum _ {k = 0}^{n} \ {{n \ atop k} \}}$

Surjektive funktioner fra N til X , op til permutationer af N og X

Denne sag svarer til at tælle partitioner af tallet n i x ikke-nul dele . Sammenlignet med tilfældet med at tælle surjektive funktioner op til permutationer af kun X ( ), bevarer man kun størrelserne på ækvivalensklasser, som funktionen opdeler N i (inklusive multipliciteten af hver størrelse), da to ækvivalensforhold kan omdannes til en en anden ved en permutation af N, hvis og kun hvis størrelserne på deres klasser matcher. Det er netop det, der adskiller begrebet partition af n fra partitionen af N , så som et resultat får man pr. Definition antallet p _x ( n ) af partitioner af n i x ikke-nul dele. ${\ displaystyle \ textstyle \ {{n \ oven på x} \}}$

Funktioner fra N til X , op til permutationer af N og X

Denne sag svarer til at tælle partitioner af tallet n i ≤ x dele . Sammenslutningen er den samme som for det foregående tilfælde, bortset fra at nu kan nogle dele af partitionen være lig med 0. (Specifikt svarer de til elementer af X, der ikke er i billedet af funktionen.) Hver partition af n i højst x ikke-nul dele kan udvides til en sådan partition ved at tilføje det krævede antal nuller, og dette tegner sig for alle muligheder nøjagtigt en gang, så resultatet er givet ved . Ved at tilføje 1 til hver af x -delene opnår man en opdeling af $n$ $+$ $x$ i x dele uden nul, og denne korrespondance er bijektiv; derfor kan det givne udtryk forenkles ved at skrive det som . ${\ displaystyle \ textstyle \ sum _ {k = 0}^{x} p_ {k} (n)}$ ${\ displaystyle p_ {x} (n+x)}$

Ekstreme sager

Ovenstående formler giver de korrekte værdier for alle endelige mængder N og X . I nogle tilfælde er der alternative formler, der er næsten ækvivalente, men som ikke giver det korrekte resultat i nogle ekstreme tilfælde, f.eks. Når N eller X er tomme. Følgende overvejelser gælder for sådanne sager.

For hvert sæt X er der nøjagtigt en funktion fra det tomme sæt til X (der er ingen værdier for denne funktion at angive), som altid er injektiv, men aldrig surjektiv, medmindre X (også) er tom.
For hvert ikke-tomt sæt N er der ingen funktioner fra N til det tomme sæt (der skal mindst angives en værdi af funktionen, men det kan ikke).
Når $n > x$ er der ingen injektive funktioner $N \to X$ , og hvis $n < x$ er der ingen Surjective funktioner $N \to X$ .
De udtryk, der bruges i formlerne, har særlige værdier

{\ displaystyle 0^{0} = 0^{\ understregning {0}} = 0! = {\ binom {0} {0}} = {\ binom {-1} {0}} = \ venstre \ {{ 0 \ oven på 0} \ højre \} = p_ {0} (0) = 1}

(de tre første er forekomster af et tomt produkt , og værdien er givet ved den konventionelle udvidelse af binomiske koefficienter til vilkårlige værdier af det øvre indeks), mens

{\ displaystyle {\ tbinom {-1} {0}} = {\ tfrac {(-1)^{\ understregning {0}}} {0!}} = 1}

{\ displaystyle \ left \ {{n \ atop x} \ right \} = p_ {x} (n) = 0 \ quad {\ hbox {hver gang enten}} n> 0 = x {\ hbox {eller}} 0 \ leq n <x.}

Især i tilfælde af tælling af multisæt med n elementer taget fra X er det givne udtryk i de fleste tilfælde ækvivalent med , men sidstnævnte udtryk ville give 0 for sagen $n$ $=$ $x$ $= 0$ (ved den sædvanlige konvention, at binomiske koefficienter med en negative lavere indeks er altid 0). Tilsvarende for tælling af sammensætninger af n med x ikke-nul dele, er det givne udtryk næsten ækvivalent med udtrykket givet af stjernerne og søjler argumentet, men sidstnævnte giver forkerte værdier for $n$ $= 0$ og alle værdier af x . I de tilfælde, hvor resultatet indebærer en summering, nemlig at tælle partitioner af N i højst x ikke-tomme undersæt eller partitioner af n i højst x ikke-nul dele, tages summeringsindekset til at starte ved 0; selvom det tilsvarende udtryk er nul, når $n$ $> 0$ , er det det unikke ikke-nul-udtryk, når $n$ $= 0$ , og resultatet ville være forkert for disse tilfælde, hvis summeringen blev taget til at starte ved 1. ${\ displaystyle {\ tbinom {n+x-1} {n}}}$ ${\ displaystyle {\ tbinom {n+x-1} {x-1}}}$ ${\ displaystyle {\ tbinom {n-1} {nx}}}$ ${\ displaystyle {\ tbinom {n-1} {x-1}}}$

Generaliseringer

Vi kan generalisere yderligere ved at tillade andre grupper af permutationer til at virke på N og X . Hvis G er en gruppe af permutationer af N , og H er en gruppe af permutationer af X , tæller vi ækvivalensklasser af funktioner . To funktioner $f$ og $F$ betragtes som ækvivalente, hvis og kun hvis der findes sådan . Denne udvidelse fører til forestillinger såsom cykliske og dihedrale permutationer samt cykliske og dihedrale partitioner af tal og sæt. ${\ displaystyle f \ colon N \ højre pil X}$ ${\ displaystyle g \ i G, h \ i H}$ ${\ displaystyle F = h \ circ f \ circ g}$

Den tyve gange

En anden generalisering kaldet den tyvefoldige måde blev udviklet af Kenneth P. Bogart i sin bog "Combinatorics Through Guided Discovery". I problemet med at distribuere objekter til kasser kan både objekterne og æskerne være identiske eller forskellige. Bogart identificerer 20 tilfælde.

Den tyve gange
n objekter og betingelser for, hvordan de modtages	x modtagere og matematisk model til distribution
n objekter og betingelser for, hvordan de modtages	Udmærket	identisk
1. Distinkt Ingen betingelser	n -følge i X ${\ displaystyle x^{n}}$	opdeling af N i ≤ x delmængder ${\ displaystyle \ sum _ {i = 0}^{x} \ venstre \ {{n \ oven på i} \ højre \}}$
2. Distinkt Hver får højst én	n -permutation af X ${\ displaystyle x^{\ understregning {n}}}$	${\ displaystyle {\ begin {cases} 1 & {\ text {if}} n \ leq x \\ 0 & {\ text {ellers}} \ end {cases}}}$
3. Distinkt Hver får mindst en	sammensætning af N med x delmængder ${\ displaystyle x! \ venstre \ {{n \ oven på x} \ højre \}}$	opdeling af N i x delmængder ${\ displaystyle \ venstre \ {{n \ oven på x} \ højre \}}$
4. Distinkt Hver får præcis en	${\ displaystyle n! = x!}$ permutationer	${\ displaystyle {\ begin {cases} 1 & {\ text {if}} n = x \\ 0 & {\ text {ellers}} \ end {cases}}}$
5. Distinkt, orden betyder noget	${\ displaystyle (n+x-1)^{\ understregning {n}}}$ bestilte funktioner	${\ displaystyle \ sum _ {i = 1}^{x} L (n, i)}$ brudte permutationer ( dele) Hvor er Lah -tallet ${\ displaystyle \ leq x}$ ${\ displaystyle L (n, i)}$
6. Distinkt, orden betyder noget Hver får mindst en	${\ displaystyle (n)^{\ understregning {x}} (n-1)^{\ understregning {nx}}}$ bestilt på funktioner	${\ displaystyle L (n, x) = \ venstre ({n \ oven på x} \ højre) (n-1)^{\ understregning {nx}}}$ brudte permutationer ( x dele) Hvor er Lah -tallet ${\ displaystyle L (n, x)}$
7. Identisk Ingen betingelser	n -multisubset af X ${\ displaystyle \ venstre ({x+n-1 \ oven på n} \ højre)}$	${\ displaystyle \ sum _ {i = 1}^{x} p_ {i} (n)}$ nummerpartitioner ( dele) ${\ displaystyle \ leq x}$
8. Identisk Hver får højst én	n -delsæt af X ${\ displaystyle \ left ({x \ atop n} \ right)}$	${\ displaystyle {\ begin {cases} 1 & {\ text {if}} n \ leq x \\ 0 & {\ text {ellers}} \ end {cases}}}$
9. Identisk Hver får mindst en	${\ displaystyle \ venstre ({n-1 \ oven på x-1} \ højre)}$ kompositioner ( x dele)	opdeling af n i x dele ${\ displaystyle p_ {x} (n)}$
10. Identisk Hver får præcis en	${\ displaystyle {\ begin {cases} 1 & {\ text {if}} n = x \\ 0 & {\ text {ellers}} \ end {cases}}}$	${\ displaystyle {\ begin {cases} 1 & {\ text {if}} n = x \\ 0 & {\ text {ellers}} \ end {cases}}}$