Tolvfaldigt sätt

I kombinatorik är det tolvfaldiga sättet en systematisk klassificering av 12 relaterade numerativa problem rörande två ändliga uppsättningar, som inkluderar de klassiska problemen med att räkna permutationer , kombinationer , multiset och partitioner antingen av en uppsättning eller ett nummer . Idén med klassificeringen krediteras Gian-Carlo Rota , och namnet föreslogs av Joel Spencer .

Översikt

Låt $N$ och $X$ vara ändliga mängder . Låt $n=|N|$ och $x=|X|$ är uppsättningarnas kardinalitet . Sålunda är $N en$ $n$ -mängd och $X$ är en $x$ -mängd.

Det allmänna problemet vi överväger är uppräkningen av ekvivalensklasser av funktioner $f:N\to X$ .

Funktionerna är föremål för en av de tre följande begränsningarna:

Inget villkor: varje $a$ i $N$ kan skickas av $f$ till valfritt $b$ i $X$ och varje $b$ kan förekomma flera gånger.
$f$ är injektiv : varje värde $f(a)$ för $a$ i $N$ måste vara skild från alla andra, och därför kan varje $b$ i $X$ förekomma högst en gång i bilden av $f$ .
$f$ är surjektiv : för varje $b$ i $X$ måste det finnas minst ett $a$ i $N$ så att $f(a)=b$ , därför kommer varje $b$ att förekomma minst en gång i bilden av $f$ .

(Villståndet " $f$ är bijektivt " är bara ett alternativ när $n=x$ ; men då motsvarar det både " $f$ är injektiv" och " $f$ är surjektiv".)

Det finns fyra olika ekvivalensrelationer som kan definieras på uppsättningen funktioner $f$ från $N$ till $X$ :

jämlikhet;
likhet upp till en permutation av $N$ ;
likhet upp till en permutation av $X$ ;
likhet upp till permutationer av $N$ och $X$ .

De tre villkoren för funktionerna och de fyra ekvivalensrelationerna kan paras ihop på $3 \times 4 = 12$ sätt.

De tolv problemen med att räkna ekvivalensklasser av funktioner innebär inte samma svårigheter, och det finns inte en systematisk metod för att lösa dem. Två av problemen är triviala (antalet ekvivalensklasser är 0 eller 1), fem problem har ett svar i form av en multiplikativ formel av n och x , och de återstående fem problemen har ett svar i termer av kombinatoriska funktioner ( Stirlingtal och partitionsfunktionen för ett givet antal delar).

Införlivandet av klassiska uppräkningsproblem i denna inställning är som följer.

Att räkna n -permutationer (dvs. partiella permutationer eller sekvenser utan upprepning) av X är ekvivalent med att räkna injektionsfunktioner $N \to X$ .
Att räkna n -kombinationer av X är ekvivalent med att räkna injektiva funktioner $N \to X$ upp till permutationer av N .
Att räkna permutationer av mängden X är ekvivalent med att räkna injektiva funktioner $N \to X$ när n = x, och även med att räkna surjektiva funktioner $N \to X$ när $n = x$ .
Att räkna multiuppsättningar av storlek n (även känd som n -kombinationer med upprepningar) av element i X är ekvivalent med att räkna alla funktioner $N \to X$ upp till permutationer av N .
Att räkna partitioner av mängden N till x delmängder är ekvivalent med att räkna alla surjektiva funktioner $N \to X$ upp till permutationer av X .
Att räkna sammansättningar av antalet n till x delar motsvarar att räkna alla surjektiva funktioner $N \to X$ upp till permutationer av N .

Synpunkter

De olika problemen på det tolvfaldiga sättet kan betraktas ur olika synvinklar.

Bollar och lådor

Traditionellt har många av problemen på det tolvfaldiga sättet formulerats i termer av att placera bollar i lådor (eller någon liknande visualisering) istället för att definiera funktioner. Uppsättningen N kan identifieras med en uppsättning bollar och X med en uppsättning lådor; funktionen ƒ : $N \to X$ beskriver sedan ett sätt att fördela bollarna i rutorna, nämligen genom att lägga varje boll a i rutan ƒ ( a ). En funktion tillskriver en unik bild till varje värde i dess domän; denna egenskap återspeglas av egenskapen att vilken boll som helst kan gå in i endast en låda (tillsammans med kravet att ingen boll ska vara utanför fälten), medan varje låda kan rymma ett godtyckligt antal bollar. Att dessutom kräva ƒ är injektiv betyder att man förbjuder att lägga mer än en boll i en låda, medan att kräva att ƒ är surjektiv betyder att man insisterar på att varje låda innehåller minst en boll.

Att räkna modulo- permutationer av N eller X reflekteras genom att man kallar kulorna respektive rutorna "oskiljbara". Detta är en oprecis formulering, avsedd att indikera att olika konfigurationer inte ska räknas separat om den ena kan omvandlas till den andra genom något utbyte av bollar eller lådor. Denna möjlighet till omvandling formaliseras av handlingen genom permutationer.

Provtagning

Ett annat sätt att tänka på några av fallen är i termer av urval , i statistik . Föreställ dig en population av X objekt (eller personer), av vilka vi väljer N . Två olika scheman beskrivs normalt, kända som " provtagning med ersättning " och " provtagning utan ersättning ". I det förra fallet (provtagning med ersättning), när vi väl har valt en artikel lägger vi tillbaka den i populationen så att vi kan välja den igen. Resultatet är att varje val är oberoende av alla andra val, och uppsättningen av prover kallas tekniskt oberoende identiskt fördelade . I det senare fallet, men när vi väl har valt en vara, lägger vi den åt sidan så att vi inte kan välja den igen. Detta betyder att handlingen att välja ett föremål har en effekt på alla följande val (det specifika föremålet kan inte ses igen), så våra val är beroende av varandra.

En andra distinktion mellan provtagningsscheman är huruvida beställning spelar någon roll. Till exempel, om vi har tio artiklar, varav vi väljer två, så är valet (4,7) annorlunda än (7,4) om beställningen är viktig; å andra sidan, om beställning inte spelar någon roll, då är valen (4,7) och (7,4) likvärdiga. (Ett annat sätt att tänka på detta är att sortera varje val efter artikelnummer och kasta ut eventuella dubbletter som blir resultatet.)

De två första raderna och kolumnerna i tabellen nedan motsvarar provtagning med och utan ersättning, med och utan hänsyn till ordning. Fallen med provtagning med ersättning återfinns i kolumnen märkt "Val som helst f ", medan fallen med provtagning utan ersättning finns i kolumnen märkt "Injektiv f ". De fall där ordningsfrågor finns på raden märkt "Distinct" och fallen där ordning inte spelar någon roll finns i raden märkt "S _n orbits". Varje tabellpost anger hur många olika uppsättningar av val som finns i ett visst urvalsschema. Tre av dessa tabellposter motsvarar också sannolikhetsfördelningar . Urval med ersättning där beställning spelar roll är jämförbart med att beskriva den gemensamma fördelningen av N separata slumpvariabler , var och en med en X -faldig kategorisk fördelning . Sampling med ersättning där beställning inte spelar någon roll är dock jämförbar med att beskriva en enda multinomial fördelning av N drag från en X -faldig kategori, där endast antalet sett av varje kategori spelar roll. Sampling utan ersättning där beställning inte spelar någon roll är jämförbar med en enda multivariat hypergeometrisk fördelning . Urval utan ersättning där ordning spelar någon roll verkar inte motsvara en sannolikhetsfördelning. Observera att i alla "injektiva" fall (dvs. sampling utan ersättning) är antalet uppsättningar av val noll om inte $N \leq X$ . ("Jämförbar" i ovanstående fall betyder att varje element i urvalsutrymmet i motsvarande distribution motsvarar en separat uppsättning val, och därför anger numret i lämplig ruta storleken på urvalsutrymmet för den givna fördelningen.)

Ur ett urvalsperspektiv är kolumnen märkt "Surjektiv f " något märklig: I huvudsak fortsätter vi att ta prover med ersättning tills vi har valt varje objekt minst en gång. Sedan räknar vi hur många val vi har gjort, och om det inte är lika med N , kasta ut hela setet och upprepa. Detta är vagt jämförbart med kupongsamlarens problem , där processen går ut på att "samla" (genom provtagning med ersättning) en uppsättning X kuponger tills varje kupong har setts minst en gång. Observera att i alla "surjektiva" fall är antalet uppsättningar av val noll om inte $N \geq X$ .

Märkning, urval, gruppering

En funktion ƒ : $N \to X$ kan betraktas utifrån X eller N . Detta leder till olika synpunkter:

funktionen ƒ betecknar varje element i N med ett element av X .
funktionen ƒ väljer (väljer) ett element av mängden X för varje element av N , totalt n val.
funktionen ƒ grupperar elementen i N tillsammans som är mappade till samma element i X .

Dessa synpunkter är inte lika lämpade för alla fall. Märknings- och urvalssynpunkterna är inte väl kompatibla med permutation av elementen i X , eftersom detta ändrar etiketterna eller urvalet; å andra sidan ger grupperingssynpunkten inte fullständig information om konfigurationen om inte elementen i X kan permuteras fritt. Märknings- och urvalssynpunkterna är mer eller mindre likvärdiga när N inte är permuterad, men när det är det är urvalssynpunkten mer lämpad. Valet kan sedan ses som ett oordnat urval: ett enda val av en (multi-)uppsättning av n element från X görs.

Märkning och urval med eller utan upprepning

När man ser ƒ som en märkning av elementen i N , kan de senare ses som arrangerade i en sekvens, och etiketterna från X som successivt tilldelade dem. Ett krav på att ƒ ska vara injektiv innebär att ingen etikett kan användas en andra gång; resultatet är en sekvens av etiketter utan upprepning . I avsaknad av ett sådant krav används terminologin "sekvenser med upprepning", vilket innebär att etiketter kan användas mer än en gång (även om sekvenser som råkar vara utan upprepning också är tillåtna).

När du ser ƒ som ett oordnat urval av elementen i X , gäller samma typ av distinktion. Om ƒ måste vara injektiv, måste urvalet involvera n distinkta element av X , så det är en delmängd av X av storlek n , även kallad en n - kombination . Utan kravet kan ett och samma element av X förekomma flera gånger i urvalet, och resultatet blir en multiuppsättning av storleken n av element från X , även kallad en n - multikombination eller n -kombination med upprepning.

Kravet på att ƒ ska vara surjektiv, ur synvinkeln att märka element i N , innebär att varje etikett ska användas minst en gång; ur urvalssynpunkt från X betyder det att varje element i X måste inkluderas i urvalet minst en gång. Märkning med surjection är ekvivalent med en gruppering av element av N följt av märkning av varje grupp med ett element av X , och är följaktligen något mer komplicerat att beskriva matematiskt.

Uppdelningar av uppsättningar och nummer

När man ser ƒ som en gruppering av elementen i N (vilket förutsätter att man identifierar sig under permutationer av X ), innebär kravet på att ƒ är surjektiv att antalet grupper måste vara exakt x . Utan detta krav kan antalet grupper vara högst x . Kravet på injektiv ƒ innebär att varje element i N måste vara en grupp i sig, vilket lämnar högst en giltig gruppering och därför ger ett ganska ointressant räkneproblem.

När man dessutom identifierar under permutationer av N , innebär detta att man glömmer själva grupperna men behåller bara deras storlekar. Dessa storlekar kommer dessutom inte i någon bestämd ordning, medan samma storlek kan förekomma mer än en gång; man kan välja att ordna dem i en svagt minskande lista med tal, vars summa är talet n . Detta ger den kombinatoriska föreställningen om en partition av talet n , i exakt x (för surjektiv ƒ ) eller högst x (för godtyckliga ƒ ) delar.

Formler

Formler för de olika fallen av det tolvfaldiga sättet sammanfattas i följande tabell; varje tabellpost länkar till ett underavsnitt nedan som förklarar formeln.

De tolv kombinatoriska objekten och deras uppräkningsformler
f -klass	Alla f	Injektiv f	Surjektiv f
Distinkt $f$	n -sekvens i X $x^{n}$	n -permutation av X $x^{\underline {n}}$	sammansättning av N med x delmängder $x!\left\{{n \atop x}\right\}$
S _n kretsar $f \circ S n$	n -multisubset av X ${\binom {x+n-1}{n}}$	n -delmängd av X ${\binom {x}{n}}$	sammansättning av n med x termer ${\binom {n-1}{nx}}$
S _x kretsar $S x \circ f$	partition av N i ≤ x delmängder $\sum _{k=0}^{x}\left\{{n \atop k}\right\}$	partition av N i ≤ x element $[n\leq x]$	partition av N i x delmängder $\left\{{n \atop x}\right\}$
S _n × S _x kretsar $S x \circ f \circ S n$	partition av n i ≤ x delar $p_{x}(n+x)$	partition av n i ≤ x delar 1 $[n\leq x]$	partition av n i x delar $p_{x}(n)$

De speciella notationerna som används är:

den fallande faktoreffekten ${\textstil x^{\underline {n}}={\frac {x!}{(xn)!}}=x( x-1)(x-2)\cdots (x-n+1)}$ ,
den stigande faktorialpotentialen ${\textstil x^{\överlinje {n}}={\frac {(x+n-1)!}{(x- 1)!}}=x(x+1)(x+2)\cdots (x+n-1)}$ ,
det faktoriella ${\textstil n!=n^{\underline {n}}=n(n-1)(n-2)\cdots 1}$
Stirlingtalet för den andra typen ${\textstyle \left\{{n \atop k}\right\}} ,$ som anger antalet sätt att dela upp en uppsättning av n element i k delmängder
binomialkoefficienten ${\textstyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!}}}$ _
Iverson -parentesen [ ] som kodar ett sanningsvärde som 0 eller 1
antalet ${\textstyle p_{k}(n)}$ av partitioner av n till k delar

Intuitiv betydelse av raderna och kolumnerna

Detta är en snabb sammanfattning av vad de olika fallen betyder. Fallen beskrivs i detalj nedan.

Tänk på en uppsättning av X numrerade objekt (numrerade från 1 till x ), från vilka vi väljer n , vilket ger en ordnad lista över objekten: t.ex. om det finns $x=10$ objekt av vilka vi väljer $n=3$ , resultatet kan vara listan (5, 2, 10). Vi räknar sedan hur många olika sådana listor som finns, ibland omvandlar vi listorna först på ett sätt som minskar antalet distinkta möjligheter.

Då betyder kolumnerna:

Alla f: När vi har valt ett föremål lägger vi tillbaka det, så att vi kanske väljer det igen.
Injektiv f: Efter att vi valt ett föremål lägger vi det åt sidan, så vi kan inte välja det igen; därför kommer vi att sluta med n distinkta objekt. Med nödvändighet, såvida inte $n\leq x$ , kan inga listor väljas alls.
Surjektiv f: När vi har valt ett objekt lägger vi tillbaka det, så vi kanske väljer det igen - men i slutet måste vi ha valt varje objekt minst en gång. Med nödvändighet, såvida inte $n\geq x$ , kan inga listor väljas alls.

Och raderna betyder:

Distinkt: Lämna listorna ifred; räkna dem direkt.
S _n orbits: Innan du räknar, sortera listorna efter artikelnumret på de valda objekten, så att ordningen inte spelar någon roll, t.ex. (5, 2, 10), (10, 2, 5), (2, 10, 5) ) → (2, 5, 10).
S _x banor: Innan du räknar, numrera om objekten som ses så att det första objektet har nummer 1, det andra 2, etc. Siffror kan upprepas om ett objekt har setts mer än en gång, t.ex. (3, 5, 3), (5) , 2, 5), (4, 9, 4) → (1, 2, 1) medan (3, 3, 5), (5, 5, 3), (2, 2, 9) → (1, 1 , 2).
S _n × S _x banor: Två listor räknas som samma om det är möjligt att både ordna om och märka om dem enligt ovan och ge samma resultat. Till exempel, (3, 5, 3) och (2, 9, 9) räknas som samma eftersom de kan ordnas om till (3, 3, 5) och (9, 9, 2) och sedan ommärkning båda ger samma lista (1, 1, 2).

Intuitiv betydelse av diagrammet med hjälp av Balls and Boxes scenario

Diagrammet nedan liknar diagrammet ovan, men istället för att visa formlerna ger det en intuitiv förståelse av deras betydelse med hjälp av exemplet med välbekanta bollar och lådor. Raderna representerar bollarnas och lådornas distinkta. Kolumnerna representerar om flerpack (mer än en boll i en låda) eller tomma lådor är tillåtna. Cellerna i diagrammet visar frågan som besvaras genom att lösa formeln som ges i formeldiagrammet ovan.

Tabell över de 12 kombinatoriska objekten - intuitivt diagram med bollar och lådor
	Alla f (inga regler om placering)	Injektiv f (inga multipack tillåtna)	Surjektiv f (inga tomma lådor tillåtna)
f (bollar och lådor märkta)	n -sekvens i X På hur många sätt kan du placera n markerade bollar i x markerade lådor, utan andra regler för placering?	n -permutation i X På hur många sätt kan du placera n markerade bollar i x markerade lådor, utan flerpack?	sammansättning av N med x delmängder På hur många sätt kan du placera n markerade bollar i x markerade lådor, utan tomma lådor?
f ∘ S _n (Släta bollar, lådor markerade)	n -multisubset av X Hur många sätt kan du placera n vanliga bollar i x markerade lådor, utan andra regler för placering?	n -delmängd av X På hur många sätt kan du placera n vanliga bollar i x markerade lådor, utan att tillåta flera förpackningar?	sammansättning av n med x termer Hur många sätt kan du placera n vanliga bollar i x markerade lådor, utan tomma lådor?
S _x ∘ f (Bolar markerade, lådor enkla)	partition av N i ≤ x delmängder På hur många sätt kan du placera n markerade bollar i x vanliga lådor, utan andra regler för placering?	uppdelning av N i ≤ x element På hur många sätt kan du placera n markerade bollar i x vanliga lådor, utan att tillåta flera förpackningar?	partition av N i x delmängder På hur många sätt kan du placera n markerade bollar i x vanliga lådor, utan tomma lådor?
S _x ∘ f ∘ S _n (bollar och lådor vanliga)	partition av n i ≤ x delar Hur många sätt kan du placera n vanliga bollar i x vanliga lådor, utan andra regler för placering?	partition av n i ≤ x delar 1 På hur många sätt kan du placera n enkla bollar i x vanliga lådor, utan att tillåta flera förpackningar?	partition av n i x delar Hur många sätt kan du placera n enkla bollar i x vanliga lådor, utan tomma lådor?

Detaljer om de olika fallen

Fallen nedan är ordnade på ett sådant sätt att de grupperar de fall för vilka argumenten som används vid räkningen är relaterade, vilket inte är ordningen i tabellen.

Fungerar från N till X

Detta fall är ekvivalent med att räkna sekvenser av n element i X utan begränsning: en funktion $f : N \to X$ bestäms av de n bilderna av elementen i N , som var och en oberoende kan väljas bland elementen i x . Detta ger totalt x ⁿ möjligheter.

Exempel:

$X=\{a,b,c\},N=\{1,2\}{\text{, sedan } }$

$\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$

Injektiva funktioner från N till X

Detta fall är ekvivalent med att räkna sekvenser av n distinkta element av X , även kallade n -permutationer av X , eller sekvenser utan upprepningar ; återigen bildas denna sekvens av de n bilderna av elementen i N . Det här fallet skiljer sig från det med obegränsade sekvenser genom att det finns ett val färre för det andra elementet, två färre för det tredje elementet, och så vidare. Därför i stället för med en vanlig potens av x , ges värdet av en fallande faktorial potens av x , där varje successiv faktor är en mindre än den föregående. Formeln är

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

Observera att om $n > x$ så får man en faktor noll, så i detta fall finns det inga injektiva funktioner $N \to X$ alls; detta är bara en omformulering av duvhålsprincipen .

Exempel:

$X=\{a,b,c,d\},N=\{1,2\}{\text {, sedan }}$

$\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^{ \underline {2}}=4\ gånger 3=12$

Injektiva funktioner från N till X , upp till en permutation av N

Detta fall är ekvivalent med att räkna delmängder med n element av X , även kallade n -kombinationer av X : bland sekvenserna av n distinkta element i X identifieras de som skiljer sig endast i ordningen av deras termer av permutationer av N . Eftersom detta i alla fall grupperar sig exakt n ! olika sekvenser kan vi dividera antalet sådana sekvenser med n ! för att få antalet n -kombinationer av X . Detta tal är känt som binomialkoefficienten ${\displaystyle {\tbinom {x}{n}}} ,$ som därför ges av

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

Exempel:

$X=\{a,b,c,d\},N=\{1,2\}{\text {, sedan }}$

$\left\vert \{\{a,b\},\{a,c\},\{a,d\},\{b,c\},\{ b,d\},\{c,d\}\}\right\vert ={\frac {4^{\underline {2}}}{2!}}={\frac {4\ gånger 3}{ 2}}=6$

Fungerar från N till X , upp till en permutation på N

Detta fall motsvarar att räkna multiset med n element från X (även kallat n -multikombinationer). Anledningen är att det för varje element i X bestäms hur många element av N som mappas till det av f , medan två funktioner som ger samma sådana "multiplicitationer" till varje element i X alltid kan omvandlas till ett annat genom en permutation av N . Formeln som räknar alla funktioner $N \to X$ är inte användbar här, eftersom antalet av dem grupperade tillsammans med permutationer av N varierar från en funktion till en annan. Snarare, som förklarats under kombinationer , kan antalet n -multikombinationer från en mängd med x element ses vara detsamma som antalet n -kombinationer från en mängd med $x + n - 1$ element. Detta reducerar problemet till ett annat på det tolvfaldiga sättet och ger som resultat

{\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!}}.

Exempel:

$X=\{a,b,c\},N=\{1,2\}{\text{, sedan } }$

$\left\vert \{\{a,a\},\{a,b\},\{a,c\},\{b,b\},\{ b,c\},\{c,c\}\}\right\vert ={\frac {3^{\overline {2}}}{2!}}={\frac {4\ gånger 3}{ 2}}=6$

Surjektiva funktioner från N till X , upp till en permutation av N

Detta fall motsvarar att räkna multiset med n element från X , för vilka varje element av X förekommer minst en gång. Detta motsvarar också att räkna sammansättningarna av n med x (icke-noll) termer genom att lista multipliciteten av elementen i x i ordning. Överensstämmelsen mellan funktioner och multiuppsättningar är densamma som i föregående fall, och surjektivitetskravet innebär att alla multipliciteter är minst en. Genom att minska alla multipliciteter med 1 reduceras detta till föregående fall; eftersom ändringen minskar värdet på n med x blir resultatet

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

Observera att när n < x finns det inga surjektiva funktioner $N \to X$ alls (en sorts "tomt hål"-princip); detta beaktas i formeln, enligt konventionen att binomialkoefficienter alltid är 0 om det lägre indexet är negativt. Samma värde ges också av uttrycket

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

förutom i extremfallet $n = x = 0$ , där med det förra uttrycket korrekt ger ${\tbinom {-1}{0}}=1$ , medan det senare felaktigt ger ${\tbinom {-1}{-1}}=0$ .

Resultatets form föreslår att man letar efter ett sätt att associera en klass av surjektiva funktioner $N \to X$ direkt till en delmängd av $n - x$ element valda från totalt $n - 1$ , vilket kan göras enligt följande. Välj först en total ordning av mängderna N och X , och notera att genom att tillämpa en lämplig permutation av N kan varje surjektiv funktion $N \to X$ omvandlas till en unik svagt ökande (och givetvis fortfarande surjektiv) funktion. Om man kopplar elementen i N i ordning med $n - 1$ bågar till en linjär graf , sedan väljer någon delmängd av $n - x$ bågar och tar bort resten, får man en graf med x anslutna komponenter, och genom att skicka dessa till de successiva elementen av X får man en svagt ökande surjektiv funktion $N \to X$ ; även storlekarna på de anslutna komponenterna ger en sammansättning av n till x delar. Detta argument är i princip det som ges vid stjärnor och staplar , förutom att det kompletterande valet av $x - 1 "$ separationer" görs.

Exempel:

$X=\{a,b\},N=\{1,2,3\}{\text{, sedan } }$

$\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$

Injektiv fungerar från N till X , upp till en permutation av X

I det här fallet betraktar vi sekvenser av n distinkta element från X , men identifierar de som erhålls från varandra genom att tillämpa en permutation av X på varje element . Det är lätt att se att två olika sådana sekvenser alltid kan identifieras: permutationen måste mappa term i för den första sekvensen till term i i den andra sekvensen, och eftersom inget värde förekommer två gånger i någon av sekvenserna motsäger dessa krav inte varandra; det återstår att kartlägga de element som inte förekommer i den första sekvensen bijektivt till de som inte förekommer i den andra sekvensen på ett godtyckligt sätt. Det enda faktum som gör att resultatet överhuvudtaget beror på n och x är att förekomsten av sådana sekvenser till att börja med kräver $n \leq x$ , enligt duvhålsprincipen. Antalet uttrycks därför som $[n\leq x]$ , med Iverson-parentesen .

Injektiva funktioner från N till X , upp till permutationer av N och X

Detta fall reduceras till det föregående: eftersom alla sekvenser av n distinkta element från X redan kan omvandlas till varandra genom att applicera en permutation av X på var och en av deras termer, ger inte heller en omordning av termerna några nya identifikationer; numret förblir $[n\leq x]$ .

Surjektiva funktioner från N till X , upp till en permutation av X

Detta fall motsvarar att räkna partitioner av N till x (icke-tomma) delmängder eller att räkna ekvivalensrelationer på N med exakt x klasser. För varje surjektiv funktion $f : N \to X$ , är förhållandet att ha samma bild under f en sådan ekvivalensrelation, och den ändras inte när en permutation av X därefter tillämpas; omvänt kan man förvandla en sådan ekvivalensrelation till en surjektiv funktion genom att tilldela elementen i X på något sätt till x -ekvivalensklasserna. Antalet sådana partitioner eller ekvivalensrelationer är per definition Stirlingtalet av det andra slaget S ( n , x ), även skrivet $\textstyle \{{n \atop x}\}$ . Dess värde kan beskrivas med hjälp av en rekursionsrelation eller med genererande funktioner , men till skillnad från binomialkoefficienter finns det ingen sluten formel för dessa tal som inte innefattar en summering .

Surjektiva funktioner från N till X

För varje surjektiv funktion $f : N \to X ,$ har dess omloppsbana under permutationer av X x ! element, eftersom sammansättning (till vänster) med två distinkta permutationer av X aldrig ger samma funktion på N (permutationerna måste skilja sig vid något element av X , som alltid kan skrivas som f ( i ) för vissa i ∈ N , och kompositionerna kommer då att skilja sig vid i ). Det följer att talet för detta fall är x ! gånger talet för föregående fall, det vill säga $\textstyle x!\{{n \top x}\}.$

Exempel:

$X=\{a,b\},N=\{1,2,3\}{\text{, sedan } }$

$\left\vert \{(a,a,b),(a,b,a),(a,b,b),(b,a,a) ,(b,a,b),(b,b,a)\}\right\vert =2!\left\{{3 \atop 2}\right\}=2\ gånger 3=6$

Fungerar från N till X , upp till en permutation av X

Det här fallet är som det motsvarande för surjektiva funktioner, men vissa element i x kanske inte motsvarar någon ekvivalensklass alls (eftersom man betraktar funktioner upp till en permutation av X spelar det ingen roll vilka element det handlar om, bara hur många) . Som en konsekvens räknar man ekvivalensrelationer på N med högst x klasser, och resultatet erhålls från det nämnda fallet genom summering över värden upp till x , vilket ger $\textstyle \sum _ {k=0}^{x}\{{n \atop k}\}$ . I fallet x ≥ n , utgör storleken på x ingen begränsning alls, och man räknar alla ekvivalensrelationer på en uppsättning av n element (motsvarande alla partitioner i en sådan mängd); därför $\textstyle \sum _{k=0}^{n}\{{n \atop k}\}$ ett uttryck för Bellnumret B _n .

Surjektiva funktioner från N till X , upp till permutationer av N och X

Detta fall motsvarar att räkna partitioner av antalet n till x delar som inte är noll . Jämfört med fallet med att räkna surjektiva funktioner upp till permutationer av X ( endast $\textstyle \{{n \atop x}\}$ ), behåller man bara storlekarna på ekvivalensklasserna som funktionen partitionerar N till (inklusive multipliciteten av varje storlek), eftersom två ekvivalensrelationer kan omvandlas till varandra genom en permutation av N om och endast om storleken på deras klasser matchar. Det är just detta som skiljer begreppet partition av n från begreppet partition av N , så som ett resultat får man per definition antalet p _x ( n ) av partitioner av n till x delar som inte är noll.

Fungerar från N till X , upp till permutationer av N och X

Detta fall motsvarar att räkna partitioner av antalet n till ≤ x delar . Associationen är densamma som för föregående fall, förutom att nu vissa delar av partitionen kan vara lika med 0. (Specifikt motsvarar de element av X som inte finns i bilden av funktionen.) Varje partition av n in i högst x delar som inte är noll kan utökas till en sådan partition genom att lägga till det nödvändiga antalet nollor, och detta står för alla möjligheter exakt en gång, så resultatet ges av ∑ $\displaystyle \textstyle \ summa _{k=0}^{x}p_{k}(n)}$ . Genom att lägga till 1 till var och en av x -delarna får man en partition av $n + x$ till x delar som inte är noll, och denna överensstämmelse är bijektiv; därför kan uttrycket som ges kan förenklas genom att skriva det som $p_{x}(n+x)$ .

Extrema fall

Ovanstående formler ger de rätta värdena för alla finita mängder N och X . I vissa fall finns alternativa formler som är nästan likvärdiga, men som inte ger rätt resultat i vissa extrema fall, som när N eller X är tomma. Följande överväganden gäller för sådana fall.

För varje uppsättning X finns det exakt en funktion från den tomma mängden till X (det finns inga värden för denna funktion att specificera), som alltid är injektiv, men aldrig surjektiv om inte X är (också) tomt.
För varje icke-tom uppsättning N finns det inga funktioner från N till den tomma uppsättningen (det finns minst ett värde för funktionen som måste anges, men det kan det inte).
När $n > x$ finns det inga injektiva funktioner $N \to X$ , och om $n < x$ finns det inga surjektiva funktioner $N \to X$ .
Uttrycken som används i formlerna har som särskilda värden

{\displaystyle 0^{0}=0^{\underline {0}}=0!={\binom {0}{0}}= {\binom {-1}{0}}=\left\{{0 \atop 0}\right\}=p_{0}(0)=1} (de tre första är instanser

av en tom produkt , och värde

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

ges av den konventionella utvidgningen av binomialkoefficienter till godtyckliga värden för det övre indexet), medan

\left\{{n \atop x}\right\}=p_{x}(n)=0\quad {\hbox{när antingen }}n>0=x{\hbox{ eller }}0 \leq n<x.

I synnerhet när det gäller att räkna multiset med n element hämtade från X , är det givna uttrycket ${\tbinom {n+x-1}{n}}$ i de flesta fall ekvivalent med ${\displaystyle {\tbinom {n+x-1}{x-1}}} ,$ men det senare uttrycket skulle ge 0 för fallet $n = x = 0$ (som vanligt konventionen att binomialkoefficienter med ett negativt lägre index alltid är 0). På liknande sätt är det givna uttrycket ${\tbinom {n-1}{nx}}$ nästan ekvivalent med uttrycket när det gäller att räkna sammansättningar av n med x delar som inte är noll ${\tbinom {n-1}{x-1}}$ ges av argumentet stjärnor och staplar , men det senare ger felaktiga värden för $n = 0$ och alla värden på x . För de fall där resultatet involverar en summering, nämligen de att räkna partitioner av N till högst x icke-tomma delmängder eller partitioner av n i högst x icke-nolldelar, antas summeringsindexet börja vid 0; även om motsvarande term är noll närhelst $n > 0$ , är det den unika termen som inte är noll när $n = 0$ , och resultatet skulle bli fel för dessa fall om summeringen skulle börja vid 1.

Generaliseringar

Vi kan generalisera ytterligare genom att tillåta andra grupper av permutationer att verka på N och X . Om G är en grupp av permutationer av N , och H är en grupp av permutationer av X , så räknar vi ekvivalensklasser av funktioner $f\colon N\rightarrow X$ . Två funktioner $f$ och $F$ anses vara ekvivalenta om, och endast om, det finns $g\in G,h\in H$ så att $F= h\circ f\circ g$ . Denna utvidgning leder till föreställningar som cykliska och dihedriska permutationer, såväl som cykliska och dihedriska partitioner av tal och mängder.

Den tjugofaldiga vägen

En annan generalisering som kallas det tjugofaldiga sättet utvecklades av Kenneth P. Bogart i sin bok "Combinatorics Through Guided Discovery". I problemet med att distribuera objekt till lådor kan både objekten och lådorna vara identiska eller distinkta. Bogart identifierar 20 fall.

Den tjugofaldiga vägen; modeller för fördelning av n objekt bland x mottagare
№	Föremål	Villkor för distribution	Mottagare
№	Föremål	Villkor för distribution	Distinkt	Identisk
1	Distinkt	Ingen begränsning	n -sekvens i X $x^{n}$	partition av N i ≤ x delmängder $\sum _{i=0}^{x}\left\{{n \atop i}\right\}$
2		Högst en var	n -permutation av X $x^{\underline {n}}$	${\begin{cases}1&{\text{if }}n\leq x\\0&{\text{annat}}\end{cases}}$
3		Minst en vardera	sammansättning av N med x delmängder $x!\left\{{n \atop x}\right\}$	partition av N i x delmängder $\left\{{n \atop x}\right\}$
4		Exakt en var	$n!=x!$ permutationer	${\begin{cases}1&{\text{if }}n=x\\0&{\text{annat}}\end{cases}}$
5	Distinkt, beställt	Ingen begränsning	$x^{\overline {n}}$ ordnade funktioner	$\sum _{i=1}^{x}L(n,i)$ brutna permutationer ( $\leq x$ delar) Där $L(n,i)$ är Lah-talet
6	Distinkt, beställt	Minst en vardera	$(n)^{\underline {x}}(n-1)^{\underline {nx}}$ ordnade på funktioner	$L(n,x)=\left({n \top x}\right)(n-1)^{\ understryka {nx}}$ brutna permutationer ( x delar) Där $L(n,x)$ är Lah-talet
7	Identisk	Ingen begränsning	n -multisubset av X $\left({x+n-1 \atop n}\right)$	$\sum _{i=1}^{x}p_{i}(n)$ nummerpartitioner ( $\leq x$ delar)
8		Högst en var	n -delmängd av X $\left({x \atop n}\right)$	${\begin{cases}1&{\text{if }}n\leq x\\0&{\text{annat}}\end{cases}}$
9		Minst en vardera	$\left({n-1 \atop x-1}\right)$ kompositioner ( x delar)	partition av n i x delar $p_{x}(n)$
10		Exakt en var	${\begin{cases}1&{\text{if }}n=x\\0&{\text{annat}}\end{cases}}$	${\begin{cases}1&{\text{if }}n=x\\0&{\text{annat}}\end{cases}}$

Se även

Stjärnor och staplar (kombinatorik)

^ Richard P. Stanley (1997). Enumerativ kombinatorik , volym I. Cambridge University Press. ISBN 0-521-66351-2 . s.41
^ Robert V. Hogg och Elliot A. Tanis (2001). Sannolikhet och statistisk slutledning . Prentice-Hall, Inc. ISBN 0-13-027294-9 . s.81
^ Kenneth P. Bogart (2004). Combinatorics Through Guid Discovery , s.57

[1] Richard P. Stanley (1997). Enumerativ kombinatorik , volym I. Cambridge University Press. ISBN 0-521-66351-2 . s.41

[2] Robert V. Hogg och Elliot A. Tanis (2001). Sannolikhet och statistisk slutledning . Prentice-Hall, Inc. ISBN 0-13-027294-9 . s.81

[3] Kenneth P. Bogart (2004). Combinatorics Through Guid Discovery , s.57