Duodecimalt sätt

Duodecimalvägen eller tolv scenarier är en systematisk klassificering av 12 relaterade numerativa problem som rör två ändliga uppsättningar, som inkluderar de klassiska problemen med att räkna permutationer , kombinationer , multiuppsättningar och partitioner av antingen en uppsättning eller ett nummer . Idén om klassificering tillskrivs Gian-Carlo Roth, och namnet duodecimal väg föreslogs av Joel Spencer [1] i analogi med termen åttafaldig väg från fysiken, som i sin tur kommer från konceptet om den åttafaldiga vägen i buddhismen [2] . Namnet antyder att med samma tillvägagångssätt i 12 fall, men med små förändringar i förhållandena, får vi 12 olika resultat.

Översikt

Låt och vara ändliga mängder . Ange med och kardinaliteten av dessa uppsättningar (antalet element). Vi kommer att säga att det är -set och är -set. $N$ $X$ $n=|N|$ $x=|X|$ $N$ $n$ $X$ $x$

Huvuduppgiften som vi kommer att överväga är att beräkna ekvivalensklasserna av funktioner . $f:N\to X$

Funktioner faller under en av de tre följande begränsningarna:

Det finns inga begränsningar: alla element från kan mappas av funktionen till vilket element från , och varje element kan förekomma flera gånger. $a$ $N$ $f$ $b$ $X$ $b$
$f$ är en injektion : varje värde för från måste skilja sig från alla andra, så att varje element av från högst kan förekomma en gång i bilden av funktionen . $fa)$ $a$ $N$ $b$ $X$ $f$
$f$ är en surjection : för varje element därifrån måste det finnas minst ett element från så att , det vill säga varje element kommer att förekomma minst en gång i bilden av funktionen . $b$ $X$ $a$ $N$ $f(a)=b$ $b$ $f$

(Tillståndet " är en bijektion " är bara möjligt om , men då motsvarar det både " injektion" och " är en injektion".) $f$ $n=x$ $f$ $f$

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

jämlikhet;
jämlikhet upp till permutation av element ; $N$
jämlikhet upp till en permutation av mängden ; $X$
jämlikhet upp till en permutation av uppsättningarna och . $N$ $X$

Vilken som helst av dessa ekvivalensrelationer ger en uppdelning av uppsättningen funktioner i ekvivalensklasser.

(Ekvivalensklassen är omloppsbanan för funktionen under verkan av gruppen som övervägs: f , eller , eller , eller , där är den symmetriska gruppen på N och är den symmetriska gruppen på X .) $f$ ${\displaystyle f\circ S_{n))$ $S_{x}\circ f$ $S_{x}\circ f\circ S_{n}$ $S_{n}$ $S_{x}$

Tre villkor för funktioner och fyra ekvivalensrelationer kan kombineras till scenarier. $3\times 4=12$

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

Klassiska räkneproblem överensstämmer med dessa inställningar enligt följande.

Att räkna n -permutationer (det vill säga partiella permutationer eller sekvenser utan upprepningar) av en uppsättning X är ekvivalent med att räkna injektiva funktioner $N\to X$ .
Att räkna n -kombinationer av en mängd X är ekvivalent med att räkna injektionsfunktioner upp till en permutation av mängden N $N\to X$ .
Att räkna permutationer av en mängd X är likvärdigt med att räkna injektiva funktioner , där , liksom att räkna surjektiva funktioner , där . $N\to X$ $n=x$ $N\to X$ $n=x$
Att räkna multiuppsättningar av storlek n (även känd som n -kombinationer med upprepningar) av element från X är ekvivalent med att räkna alla funktioner upp till permutationer av mängden N $N\to X$ .
Att räkna partitioner av en mängd N till x delmängder är ekvivalent med att räkna alla surjektiva funktioner upp till permutationer av mängden X $N\to X$ .
Att räkna expansionerna av ett tal n till x delar är ekvivalent med att räkna alla surjektiva funktioner upp till permutationer av mängden N $N\to X$ .

Synpunkter

De olika uppgifterna i de tolv scenarierna kan ses ur olika perspektiv.

Bollar och lådor

Traditionellt är många av problemen i de tolv scenarierna formulerade i termer av att placera bollar i lådor (eller andra liknande visualiseringar) istället för att definiera funktioner. Uppsättningen N kan identifieras med bollar och uppsättningen X med lådor. Funktionen beskriver sedan hur bollarna fördelas till boxarna, nämligen bollen a placeras i boxen . Då reflekteras egenskapen att funktionen tilldelar en unik bild till varje värde i domänen av egenskapen att vilken boll som helst kan gå in i endast en låda (tillsammans med kravet att inga bollar får lämnas utanför rutorna), där vilken låda som helst kan acceptera (i princip) godtyckligt antal bollar. Att kräva att ƒ är injektiv betyder att ingen låda kan innehålla mer än en boll, medan att kräva att ƒ är surjektiv betyder att varje låda måste innehålla minst en boll. $f:N\to X$ $f'(a)$

Beräkningen av ekvivalensförhållandena för permutationer av mängden N och/eller mängden X återspeglas i igenkännandet av bollar och lådor som "oskiljbara". Detta erkännande är inte ett exakt uttalande (i praktiken kan enskilda bollar och lådor särskiljas genom sin position och olika bollar kan placeras i olika lådor), men indikerar att olika konfigurationer inte anses vara separata om en av dem kan omvandlas till en annan genom att byta bollar eller lådor. Detta är precis vad som formaliseras genom att permutera uppsättningarna N och/eller X . Oskiljbara lådor är svårare att föreställa sig än oskiljbara bollar, eftersom konfigurationen oundvikligen innebär en viss ordning av lådorna. Omarrangemanget av lådorna kommer att visas som ett utbyte av deras innehåll.

Val

Ett annat tillvägagångssätt för att hantera samma fall är i form av stickprov i statistiken . Föreställ dig en population av X objekt (eller personer) från vilka vi väljer N . Två scheman anses allmänt, kända som " provtagning med tillbakadragning" och "provtagning utan ersättning" . I det första fallet (selektion med retur), efter urvalet av objektet, returnerar vi det till populationen, så att det kan träffa oss igen. Resultatet av varje sådant urval är oberoende av alla andra urval, och urvalsuppsättningen anses tekniskt vara oberoende identiskt fördelade slumpvariabler . I det andra fallet, efter att ha valt objektet, lägger vi det åt sidan och objektet kan inte visas en andra gång. Det betyder att det faktum att ett objekt väljs har en effekt på alla efterföljande samplingar (ett visst objekt kan inte träffas en andra gång), så att våra samplingar blir beroende av varandra.

I fallet med sampling med backtracking kommer vi att säga "Any f' " nedan, medan vi för sampling utan backtracking säger "Injective f' ". Varje ruta anger hur många olika urval av uppsättningar som gjordes i ett visst schema. En rad med ordet "Annorlunda" betyder att ordningen beaktas. Till exempel, om vi har objekt från vilka vi väljer två, så skiljer sig urvalet (4,7) från (7,4). Å andra sidan betyder raden märkt "S n order" att ordningen inte spelar någon roll; i detta fall är valen (4.7) och (7.4) likvärdiga. När det gäller en sannolikhetsfördelning är prover på återinträde, där ordningsföljd beaktas, jämförbara med att beskriva den gemensamma fördelningen av N individuella slumpvariabler , var och en med en X -faldig kategorisk fördelning . Fallet där ordning inte beaktas är jämförbart med att beskriva en enda multinomial fördelning av N sampel från en X - faldig kategori, där endast antalet av varje kategori har betydelse. Det fall där ordningen inte beaktas och proverna görs utan ersättning är jämförbart med en separat multivariat hypergeometrisk fördelning , och jämförelsen av den fjärde möjligheten med något är inte synlig. Observera att i alla "injektiva" fall (d.v.s. prover utan ersättning) är antalet provuppsättningar noll om inte . (Ordet "jämförbar" i ovanstående fall betyder att varje element i det elementära händelseutrymmet i motsvarande distribution motsvarar en separat uppsättning sampel, och därför anger numret i cellen storleken på händelseutrymmet för denna distribution.) $N\leqslant X$

Ur denna synvinkel ser fallet märkt "Surjektiv f' " konstigt ut. I huvudsak fortsätter vi att välja tillbaka tills vi har valt varje element minst en gång. Nu räknar vi hur många gånger vi har dragit kulorna, och om detta nummer inte är lika med N slänger vi hela provet och upprepar. Detta påminner vagt om problemet med kupongplockning , där processen går ut på att "plocka" (hämta och returnera) en uppsättning av X kuponger tills vi har en uppsättning där varje kupong visas minst en gång. Observera att i alla "surjektiva fall" är antalet provuppsättningar lika med noll om inte . $N\geqslant X$

Urval, markering, gruppering

En funktion kan ses i termer av X eller N . Detta leder till olika synpunkter: $f:N\to X$

funktionen ƒ markerar varje element i mängden N med ett element från X .
funktionen ƒ väljer ett element av mängden X för varje element i mängden N , och får n sampel totalt.
funktionen ƒ grupperar element i mängd N tillsammans om de mappar till samma element i mängd X .

Dessa synpunkter gäller inte lika i alla fall. Synpunkterna "etikett" och "selektion" är inte helt kompatibla med permutationen av elementen i uppsättningen X , eftersom de ändrar etiketter och val. Å andra sidan ger "grupperings"-synpunkten inte fullständig information om konfigurationen om elementen i uppsättningen X inte kan permuteras. "Sampling" och "selektions" synpunkter är mer eller mindre ekvivalenta när N inte är permuterad, men i detta fall är "selektions" synpunkten mer lämplig. Samplet kan sedan ses som ett oordnat sampel - en (multi-)uppsättning av n element från uppsättningen X väljs .

Märkning och provtagning med eller utan upprepningar

Om vi tänker på ƒ som märkning av elementen i mängden N , kan bokstäverna ses som ordnade i en sekvens, och etiketterna som sekventiellt tilldelade elementen. Kravet på att funktionen ƒ ska vara injektiv innebär att ingen etikett kan användas två gånger. Resultatet blir en sekvens av etiketter utan upprepningar . I avsaknad av detta krav används terminologin "sekvenser med upprepningar", vilket innebär att etiketter kan användas mer än en gång (även om sekvenser där det inte finns några upprepningar också är tillåtna).

För ett oordnat prov gäller samma sorts distinktion. Om ƒ ska vara injektiv måste valet involvera n distinkta element i mängden X , så det blir en delmängd av mängden X av storlek n , den så kallade n - kombinationen . Utan detta krav kan samma element i mängden X förekomma i urvalet flera gånger, så att resultatet blir en multiuppsättning av n element i mängden X , som också kallas en n - multi -matchning eller en n -matchning med upprepning.

I dessa fall innebär kravet att ƒ ska vara surjektiv att vilken etikett som helst måste användas minst en gång, eller att något element av X måste ingå i provet minst en gång. Ett sådant krav är mindre naturligt i matematisk övervägande, och dessutom är det tidigare fallet lättare att betrakta som en gruppering av element av N med tillägg av gruppetiketter för element i mängden X .

Partitioner av uppsättningar och nummer

Om vi betraktar ƒ som en gruppering av element i mängden N (vilket innebär identifiering genom permutationer av mängden X ), innebär kravet att ƒ är surjektiv att antalet grupper måste vara exakt lika med x . Utan detta krav kan antalet grupper inte överstiga x . Kravet på att ƒ ska vara injektiv innebär att varje element i N i sig måste vara en grupp, vilket bara lämnar en giltig gruppering och är därför inte ett intressant räkneproblem.

Om dessutom identifiering görs genom permutationer av mängden N leder detta till att grupperna glöms bort, bara deras storlekar kvarstår. Dessa mått visas inte i någon särskild ordning, och själva måtten kan förekomma mer än en gång. Du kan sortera storlekarna i en något minskande lista med tal som summerar till n [3] . Detta ger en kombinatorisk representation av att dela talet n i exakt x (för ett surjektiv ƒ ) eller högst x (för en godtycklig ƒ ) delar.

Formler

Formlerna för de olika fallen av de tolv scenarierna är sammanfattade i en tabell, där varje element i tabellen är länkat till ett avsnitt nedan som förklarar formeln.

Tolv kombinatoriska objekt och deras formler.

f -klass	Alla f	Injektiv f	Surjektiv f
f	n -sekvens i X $x^n$	n -permutation av mängden X $x^{\underline {n))$	sammansättning N med x delmängder $\textstyle x!\{{n \top x}\}$
${\displaystyle f'\circ S_{n))$	n -multisubset av X ${\binom {x+n-1}{n))$	n -delmängd av mängden X ${\binom {x}{n))$	sammansättning n med x medlemmar ${\binom {n-1}{nx))$
$S_{x}\circ f$	partitionering av N i delmängder $\leqslant x$ ${\displaystyle \sum _{k=0}^{x}\left\{{n \atop k}\right\))$	dela upp N i element $\leqslant x$ $[n\leqslant x]$	partitionering av N i delmängder $\leqslant x$ $\left\{{n \top x}\right\}$
$S_{x}\circ f\circ S_{n}$	dela n i delar $\leqslant x$ $p_{x}(n+x)$	dela upp n i delar 1 $\leqslant x$ $[n\leqslant x]$	dela n i x delar $p_{x}(n)$

Använd notation:

Minskande faktor , $x^{\underline {n}}={\frac {x!}{(xn)!}}=x(x-1)(x-2)\cdots (x-n+1)$
Ökande faktorial , $x^{\overline {n}}={\frac {(x+n-1)!}{(x-1)!}}=x(x+1)(x+2)\cdots ( x+n-1)$
Faktoriell $n!=n^{\underline {n}}=n(n-1)(n-2)\cdots 1$
Stirlingtal av det andra slaget uttrycker antalet sätt att dela upp en uppsättning av n element i k delmängder $\textstyle \{{n \atop k}}\}$
Binomial koefficient $\textstyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!)}}$
Iverson parentes kodar sanningen eller falskheten i ett påstående (som 1 eller 0)
antal partitioner av ett nummer n till k delar $p_{k}(n)$

Intuitiv betydelse av rader och kolumner

Här är en kort sammanfattning av vad varje klass betyder. Klasserna beskrivs i detalj nedan.

Betrakta en uppsättning av X numrerade element (siffror från 1 till x ), från vilka vi väljer n , vilket ger en ordnad lista med element. Till exempel, om det finns element från vilka vi väljer kan resultatet bli en lista (5,2,10). Vi räknar nu hur många sådana distinkta listor det finns, ibland först transformerar vi listorna på ett sådant sätt att antalet distinkta möjligheter minskar. $x=10$ $n=3$

Då betyder kolumnerna:

Any f : När vi har valt ett element staplar vi tillbaka det så att vi kan välja det igen.
Injektiv f : Efter att vi har valt ett element lägger vi det åt sidan så att vi inte kan välja det igen. Därför slutar vi med n distinkta element. Naturligtvis, i det här fallet, om vi inte är nöjda , kommer vi inte att få någon lista. $n\leqslant x$
Surjektiv f : Efter att vi har valt ett element lägger vi tillbaka det så att vi kan dra ut det igen, men i slutändan måste vi välja varje element minst en gång. Naturligtvis, i det här fallet, om vi inte är nöjda , kommer vi inte att få någon lista. $n\geqslant x$

Raderna betyder:

Övrigt: Lämna listorna som de är, räkna dem direkt.
S n -banor: Innan du räknar, sortera listorna efter antalet valda element, så att ordningen inte spelar någon roll, t.ex. (5,2,10), (10,2,5), (2,10,5) etc. alla → (2,5,10).
S x banor: Innan du räknar, numrera om elementen så att det första elementet i listan är nummer 1, det andra (om inte lika) är nummer 2, och så vidare. Tal kan upprepas om ett element förekommer mer än en gång i lista till exempel (3,5,3), (5,2,5), (4,9,4), etc. → (1,2,1), medan (3,3,5), ( 5,5,3), (2,2,9), etc. → (1,1,2).

$\mathbf {S} _{n}\times \mathbf {S} _{x}$ banor: Före räkning sorteras listan och numreras om enligt beskrivningen ovan. (Obs: Omnumrering följt av sortering kan ge olika listor i vissa fall, men antalet möjliga listor kommer inte att ändras.)

Detaljer om olika fall

Fallen nedan ordnas allt eftersom de räknas, vilket inte är samma ordning i tabellen.

Funktioner från N till X

Detta fall är ekvivalent med att räkna sekvenser av n element i mängden X utan begränsningar: funktionen definieras av n bilder av element från N , som oberoende kan väljas från spårelement av x . Detta ger totalt x n möjligheter. $f:N\to X$

Exempel:

${\displaystyle X=\{a,b,c\},N=\{p,q\))$ , då

$\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 motsvarar att räkna sekvenser av n olika element i mängden X , som också kallas n -permutationer av mängden X , eller sekvenser utan upprepning . Återigen bildas sekvensen av n mönster av element från N . Detta fall skiljer sig från obegränsade sekvenser (ovan) genom att valet av det andra elementet är ett mindre, det andra är två mindre, och så vidare. Därför, istället för potensen av x , kommer resultatet att ges av en minskande faktor på x , där varje nästa faktor är en mindre än den föregående. Formel för antalet kombinationer

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

Observera att i fallet när , kommer en av faktorerna att vara lika med noll, så i det här fallet finns det inga injektiva funktioner . Detta är helt enkelt en omformulering av Dirichlet-principen . $n>x$ $N\to X$

Exempel:

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

$\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^{\understryka {2}}=4\ggr 3=12$

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

Detta fall är ekvivalent med att räkna delmängder med n element från X , även kallade n - kombinationer av X- bland sekvenser av n olika element av X , de som skiljer sig endast i ordningen av element identifieras med permutationer av N. Eftersom i alla fall alla dessa grupper har exakt n ! olika sekvenser kan vi dividera antalet sådana sekvenser med n ! för att få antalet n -kombinationer av mängden X. Detta tal är känt som binomialkoefficienten och ges av formeln ${\tbinom {x}{n))$

{\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\}$ , då

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

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

Detta fall motsvarar att räkna multiset med n element från X (som kallas n -multikombinationer). Anledningen är att för varje element i mängden X bestäms kombinationen av hur många element i mängden N som mappas till det elementet av funktionen f , medan två funktioner som ger samma antal "multiplikitet" för varje element i mängden X kan alltid omvandlas från en till en annan genom att permutera elementen i mängden N . Formeln som räknar alla funktioner är värdelös här, eftersom antalet grupperade element genom permutationer av N varierar från funktion till funktion. Snarare, som förklarats i Kombinationer med upprepningar , kan antalet n -multikombinationer från en mängd med x element ses som antalet n -kombinationer från en mängd med x + n - 1 element. Detta reducerar problemet till ett annat fall på "duodecimalt sätt", och ger resultatet $N\to X$

{\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:

${\displaystyle X=\{a,b,c\},N=\{p,q\))$ , då

$\left\vert \{\{a,a\},\{a,b\},\{a,c\},\{b,b\},\{b,c\},\ {c,c\}\}\right\vert ={\frac {3^{\overline {2}}}{2!}}={\frac {4\times 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 att räkna expansionen av ett tal n till x (icke-noll) element , och lista multipliciteten av x element i stigande ordning. Överensstämmelsen mellan funktioner och multimängder är densamma som i föregående fall, och kravet på surjektivitet innebär att alla multipliciteter är minst en. När alla multipliciteter reduceras med 1, reducerar detta problemet till föregående fall. Eftersom en sådan förändring minskar värdet på n med x , blir resultatet

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

Observera att det i fallet inte finns några surjektiva funktioner alls . Detta tas med i beräkningen i formeln om binomialkoefficienterna anses alltid vara 0 om subskriptet är negativt. Samma värde ges också av uttrycket $n<x$ $N\to X$

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

Förutom i extremfallet , där föregående formel ger rätt värde , men den sista formeln ger . $n=x=0$ ${\tbinom {-1}{0}}=1$ ${\tbinom {-1}{-1}}=0$

Denna resultatformel föreslår att man letar efter en association av surjektiva funktioner direkt med en delmängd av n − x element valda från n − 1 element, vilket kan göras enligt följande. Vi väljer först en fullständig ordning av mängderna N och X och noterar att genom att tillämpa en lämplig permutation av mängden N kan vilken surjektiv funktion som helst omvandlas till en enda långsamt växande [4] (och, naturligtvis, fortfarande surjektiv) funktion. Om vi kopplar elementen i mängden N (enligt ordningen) med n − 1 bågar till en linjegraf , då val av en delmängd av n − x bågar och ta bort resten kommer att ge en graf med x anslutna komponenter, och mappa dem i på varandra följande element i mängden X kommer att ge en långsamt växande surjektiv funktion . De anslutna komponenternas dimensioner ger också en sammansättning av n i x delar. Detta argument är i huvudsak detsamma som för asterisker och bindestreck , förutom att ett val görs av x − 1 "separatorer" $N\to X$ $N\to X$ $N\to X$

Exempel:

$X=\{a,b\},N=\{p,q,r\}$ , då

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

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

I det här fallet betraktar vi sekvenser av n olika element från X , men vi identifierar funktionerna som erhålls från varandra genom att permutera elementen i mängden X . Det är lätt att se att två olika sådana sekvenser alltid kan identifieras - permutationen måste kartlägga term i i den första sekvensen till term i i den andra sekvensen, och eftersom värdet förekommer två gånger i båda sekvenserna motsäger inte dessa krav varandra . Mappningen återstår för att mappa ett element som inte finns i den första sekvensen till ett element som inte finns i den andra sekvensen. Det enda som gör resultatet beroende av n och x är förekomsten av sådana sekvenser, vilket uttrycks som ett krav enligt Dirichlets princip. Antalet permutationer uttrycks därför som när Iverson-parentesen används . $n\leqslant x$ $[n\leqslant x]$

Injektiva funktioner från N till X upp till permutationer av uppsättningarna N och X

Det här fallet reduceras till det föregående - eftersom alla sekvenser av n olika element från X kan omvandlas till varandra med hjälp av permutationer av mängden X , vilket gör att du kan ordna om elementen utan att skapa nya entiteter, numret kvarstår . $[n\leqslant x]$

Surjektiva funktioner från N till X upp till en permutation av mängden 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. Dessutom, för varje surjektiv funktion , är relationen att ha samma bild när den mappas av funktionen f en sådan ekvivalensrelation, och denna relation ändras inte när permutationer av mängden X tillämpas successivt . Å andra sidan kan man förvandla en sådan ekvivalensrelation till en surjektiv funktion genom att tilldela vissa ekvivalensklasser till elementen x i mängden X. Antalet sådana partitioner eller ekvivalensrelationer är per definition Stirlingtalet av det andra slaget S ( n , x ), som också skrivs som . Värden kan beskrivas med en återkommande relation eller med genererande funktioner , men till skillnad från binomialkoefficienter finns det inget sluten formuttryck för dessa tal som inte använder summering . $N\to X$ $\textstyle \{{n \atop x}}\}$

Surjektiva funktioner från N till X

För varje surjektiv funktion har dess bana över permutationer av mängden X x ! element, eftersom sammansättning (vänster) med två olika permutationer av mängden X aldrig ger samma funktion på N (permutationerna måste skilja sig åt på något element i mängden X , som alltid kan skrivas som f ( i ) för vissa , och kompositioner kommer då att skilja sig åt på element i ). Det följer att talet för detta fall i x ! gånger siffran i föregående fall, dvs $N\to X$ $i\in N$ $\textstyle x!\{{n \top x}\}.$

Exempel:

$X=\{a,b\},N=\{p,q,r\}$ , då

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

Fungerar från N till X med den exakta permutationen av uppsättningen X

Det här fallet liknar det motsvarande fallet för surjektiva funktioner, men vissa element i x kanske inte motsvarar någon ekvivalensklass alls (eftersom funktioner anses upp till en permutation av mängden X , spelar det ingen roll vilka element som betraktas, det spelar bara roll hur många ). Som en konsekvens beräknas ekvivalensrelationer på N med högst x -klasser och resultatet erhålls från nämnda fall genom att summera x -värden , vilket ger . I fallet lägger storleken på x inga restriktioner alls och alla ekvivalensrelationer för en uppsättning av n element räknas (motsvarande alla partitioner i en sådan uppsättning). Därför ger det ett uttryck för klocktalet B n . $\textstyle \sum _{k=0}^{x}\{{n \atop k}}\}$ $x\geqslant n$ $\textstyle \sum _{k=0}^{n}\{{n \atop k}}\}$

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

Detta fall motsvarar att räkna partitionerna för numret n till x delar som inte är noll . Fallet är jämförbart med fallet med att räkna surjektiva funktioner upp till permutationer av mängden X (endast över X , ), endast storlekarna på ekvivalensklasserna i vilka funktionspartitionerna Mängden N bör beaktas (inklusive mångfalden av varje storlek), eftersom två ekvivalensrelationer kan omvandlas till en annan permutation av mängden N om och endast om storleken på klasserna är densamma. Detta är exakt vad som skiljer begreppet partition av n från begreppet partition av N , så att resultatet erhålls genom att bestämma antalet p x ( n ) av partitioner av n till x delar som inte är noll. $\textstyle \{{n \atop x}}\}$

Fungerar från N till X upp till en permutation av uppsättningarna N och X

Detta fall motsvarar att räkna partitionerna av numret n till högst x delar . Associationen är densamma som i föregående fall, inklusive att dela 0-delen för varje element av X som inte ingår i bilden av funktionen. Varje partition av numret n till högst x icke-noll delar kan utökas till en sådan partition genom att lägga till det nödvändiga antalet nollor, och detta räknas för alla möjligheter exakt en gång, så att resultatet ges av formeln . Genom att lägga till en till var och en av x - delarna får vi en partition av n + x till x delar som inte är noll, och denna korrespondens är bijektiv. Därför kan uttrycket förenklas till en notation (även om denna ändring inte gör beräkningen lättare). $\textstyle \sum _{k=0}^{x}p_{k}(n)$ $p_{x}(n+x)$

Extremfall

Ovanstående formler ger motsvarande värden för alla finita mängder N och X. I vissa fall finns det alternativa formler som är nästan likvärdiga, men som inte ger rätt resultat i vissa extrema fall, som tomt N eller X . Följande bör beaktas i dessa fall.

För varje uppsättning X finns det exakt en funktion från den tomma mängden i X (det finns inga värden för denna funktion), som alltid är injektiv, men aldrig surjektiv, förutom när X (också) är tomt.
För en icke-tom mängd N finns det ingen funktion från N till den tomma mängden (det är nödvändigt att det finns minst ett värde på funktionen, men det finns inget).
När , det finns ingen injektiv funktion , och om , det finns inga surjektiva funktioner . $n>x$ $N\to X$ $n<x$ $N\to X$
Uttryck som används i formler har specifika värden

0^{0}=0^{\underline {0}}=0!={\binom {0}{0}}={\binom {-1}{0}}=\left\{{ 0 \atop 0}\right\}=p_{0}(0)=1

(de första tre är representanter för den tomma produkten , och innebörden bestäms av den allmänt accepterade utvidgningen av de binomialkoefficienter till godtyckliga värden för upphöjden), medan

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

\left\{{n \atop x}\right\}=p_{x}(n)=0

någonsin , eller

n>0=x

0\leqslant n<x.

Speciellt för fallet med räkning av multiset med n element valda från X , är uttrycket ovan i de flesta fall ekvivalent med , men det senare uttrycket ger 0 i fallet (med den vanliga konventionen att binomialkoefficienter med en negativ sänkning alltid är 0 ). På liknande sätt, för fallet med att räkna sammansättningar av talet n med x delar som inte är noll, är uttrycket ovan nästan ekvivalent med uttrycket som ges av asterisk- och bindestrecksargumentmetoden , men i det senare fallet får vi fel resultat för och alla värden på x . För fall där resultatet involverar summering, nämligen när man räknar partitioner av N med högst x icke-tomma delmängder eller partitioner av n med högst x icke-nolldelar, börjar summeringsindexet på 0, även om motsvarande term är noll för alla och det blir icke-noll när . I så fall blir resultatet felaktigt om du börjar summera från 1. ${\tbinom {n+x-1}{n))$ ${\tbinom {n+x-1}{x-1))$ $n=x=0$ ${\tbinom {n-1}{nx))$ ${\tbinom {n-1}{x-1))$ $n=0$ $n>0$ $n=0$ $n=0$

Generaliseringar

Vi kan generalisera ytterligare genom att tillåta andra permutationsgrupper att agera på N och X. Om G är permutationsgruppen för mängden N , och H är permutationsgruppen för mängden X , så räknar vi funktionernas ekvivalensklasser . Två funktioner och anses likvärdiga om och endast om det finns , så att . Denna utvidgning leder till begrepp som cykliska och dihedriska permutationer, såväl som cykliska och dihedriska partitioner av tal och mängder. $f\colon N\to X$ $f$ $F$ $g\in G,h\in H$ $F=h\circ f\circ g$

Decimal sätt

En annan generalisering, kallad 20-vägen , utvecklades av Kenneth P. Bogart i sin bok Combinatorics Through Guided Discovery . I problemet med att fördela objekt i lådor kan objekt och lådor anses vara omöjliga att särskilja eller olika. Bogart särskiljde 20 fall [5] .

2 decimaler sätt

n objekt och villkor, hur de erhålls	x mottagare och distribution matematisk modell
n objekt och villkor, hur de erhålls	Olika	Det samma
1. Diverse Inga villkor	n -sekvenser i X $x^n$	partitionering av N i delmängder $\leqslant x$ ${\displaystyle \sum _{i=0}^{n}\left\{{x \atop i}\right\))$
2. Diverse Varje väljs inte mer än en gång	n -permutationer av mängden X $x^{\underline {n))$	${\begin{cases}1&n\leqslant x;\\0&n>x\end{cases))$
3. Diverse Varje väljs minst en gång	kompositioner N med x delmängder $x!\left\{{n \top x}\right\}$	dela upp N i x delmängder $\left\{{n \top x}\right\}$
4. Olika Varje väljs exakt en gång	$n!=x!$ permutationer	$1{\begin{cases}1&n=x\\0&n\neq x\end{cases))$
5. Diverse, ordning respekteras	$(n+x-1)^{\underline {n))$ beställda funktioner	$\sum _{i=1}^{x}L(n,i)$ brutna permutationer (i delar) $\leqslant x$ Var är Lach-numret $L(n,i)$
6. Olika, ordningsräknade Varje väljs minst en gång	$(n)^{\underline {x}}(n-1)^{\underline {nx}}$ ordnade i funktioner	$L(n,x)=\left({n \atop x}\right)(n-1)^{\underline {nx))$ brutna permutationer (i x delar) var är Lach-numret $L(n,x)$
7. Samma inga villkor	n -multiset av mängden X $\left({x+n-1 \atop n}\right)$	$\sum _{i=1}^{x}p_{i}(n)$ antal partitioner (i delar) $\leqslant x$
8. Identisk Var och en väljs inte mer än en gång	n -delmängder av mängden X $\left({x \atop n}\right)$	${\begin{cases}1&n\leqslant x;\\0&n>x\end{cases))$
9. Samma Varje väljs minst en gång	$\left({n-1 \top x-1}\right)$ kompositioner ( x delar)	dela n i x delar $p_{x}(n)$
10. Samma Varje väljs exakt en gång	${\begin{cases}1&n=x\\0&n\neq x\end{cases))$	${\begin{cases}1&n=x;\\0&n\neq x\end{cases))$

Anteckningar

↑ Stanley, 1997 , sid. 41.
↑ Richard Stanley. Enumerativ kombinatorik. - Mir, 1990. - T. 1. - S. 55.
↑ En svagt minskande lista är en fallande lista med möjlighet till upprepning.
↑ En funktion sägs växa långsamt om den är monoton, men upprepning av värden är möjlig.
↑ Bogart, 2004 , sid. 57.

Litteratur

Richard P Stanley. Enumerativ kombinatorik, volym I. - Cambridge University Press, 1997. - ISBN 0-521-66351-2 .
Kenneth P. Bogart. Kombinatorik genom guidad upptäckt . – Dartmouth College, 2004.