Duodecimální způsob

Duodecimální cesta neboli dvanáct scénářů je systematická klasifikace 12 souvisejících výčtových problémů týkajících se dvou konečných množin, které zahrnují klasické problémy počítání permutací , kombinací , multimnožin a dělení buď množiny nebo čísla . Myšlenka klasifikace je připisována Gian-Carlo Rothovi a název duodecimální cesta navrhl Joel Spencer [1] analogicky s termínem osmidílná cesta z fyziky, který zase pochází z konceptu osmidílné cesty v buddhismu . [2]. Název napovídá, že použitím stejných přístupů ve 12 případech, ale s mírnými změnami podmínek, dostaneme 12 různých výsledků.

Přehled

Dovolit a být konečné množiny . Označte a mohutnost těchto množin (počet prvků). Řekneme, že je -set a je -set. $N$ $X$ $n=|N|$ $x=|X|$ $N$ $n$ $X$ $X$

Hlavním úkolem, který budeme zvažovat, je vypočítat třídy ekvivalence funkcí . $f:N\to X$

Funkce spadají pod jedno ze tří následujících omezení:

Neexistují žádná omezení: jakýkoli prvek z může být mapován funkcí na jakýkoli prvek z a každý prvek se může vyskytovat vícekrát. $A$ $N$ $F$ $b$ $X$ $b$
$F$ je injekce : každá hodnota pro from se musí lišit od všech ostatních, takže každý prvek z se může v obrázku funkce vyskytnout nejvýše jednou . $f(a)$ $A$ $N$ $b$ $X$ $F$
$F$ je surjekce : pro jakýkoli prvek z tam musí být alespoň jeden prvek z takové , to znamená, že každý prvek se v obrázku funkce objeví alespoň jednou . $b$ $X$ $A$ $N$ $f(a)=b$ $b$ $F$

(Podmínka " je bijekce " je možná pouze v případě , ale pak je ekvivalentní jak " injekci ", tak " je surjekce".) $F$ $n=x$ $F$ $F$

Existují čtyři různé vztahy ekvivalence , které lze definovat na množině funkcí od do : $F$ $N$ $X$

rovnost;
rovnost až permutace prvků ; $N$
rovnost až do permutace množiny ; $X$
rovnost až po permutaci množin a . $N$ $X$

Kterýkoli z těchto vztahů ekvivalence poskytuje rozdělení množiny funkcí do tříd ekvivalence.

(Třída ekvivalence je orbita funkce při působení uvažované grupy: f , nebo , nebo , nebo , kde je symetrická grupa na N a je symetrická grupa na X .) $F$ ${\displaystyle f\circ S_{n))$ $S_{x}\circ f$ $S_{x}\circ f\circ S_{n}$ $S_{n}$ $S_{x}$

Tři podmínky o funkcích a čtyři vztahy ekvivalence lze kombinovat do scénářů. $3\times 4=12$

Dvanáct problémů tříd ekvivalence počítání funkcí není ekvivalentních co do složitosti a neexistuje jediná systematická metoda pro jejich řešení. Dva problémy jsou triviální (počet tříd ekvivalence je 0 nebo 1), pět problémů má odpověď z hlediska multiplikativního vzorce v n a x a zbývajících pět problémů má odpověď z hlediska kombinatorických funkcí ( Stirlingova čísla druhý druh a rozdělovací funkce pro daný počet dílů).

Klasické problémy počítání jsou konzistentní s těmito nastaveními následovně.

Počítání n -permutací (tj. částečné permutace nebo sekvence bez opakování) množiny X je ekvivalentní počítání injektivních funkcí $N\to X$ .
Počítání n -kombinací množiny X je ekvivalentní počítání injektivních funkcí až do permutace množiny N $N\to X$ .
Počítání permutací množiny X je ekvivalentní počítání injektivních funkcí , kde , stejně jako počítání surjektivních funkcí , kde . $N\to X$ $n=x$ $N\to X$ $n=x$
Počítání multimnožin o velikosti n (také známé jako n -kombinace s opakováním) prvků z X je ekvivalentní počítání všech funkcí až po permutace množiny N $N\to X$ .
Počítání dělení množiny N do x podmnožin je ekvivalentní počítání všech surjektivních funkcí až po permutace množiny X $N\to X$ .
Počítání rozšíření čísla n do x částí je ekvivalentní počítání všech surjektivních funkcí až po permutace množiny N $N\to X$ .

Pohledy

Na různé úkoly ve dvanácti scénářích lze nahlížet z různých perspektiv.

Míče a boxy

Tradičně je mnoho problémů ve dvanácti scénářích formulováno z hlediska umístění míčků do krabic (nebo jiných podobných vizualizací) namísto definování funkcí. Sadu N lze identifikovat s kuličkami a sadu X s krabicemi. Funkce pak popisuje, jak jsou koule distribuovány do boxů, konkrétně je míč a umístěn v boxu . Pak se vlastnost, že funkce přiřadí každé hodnotě v doméně jedinečný obrázek, projeví vlastností, že jakýkoli míč může jít pouze do jednoho boxu (spolu s požadavkem, že žádné míčky nesmí zůstat mimo boxy), kde může jakýkoli box přijímat (v zásadě) libovolný počet míčků. Požadavek , aby ƒ byl injektivní znamená, že žádný box nemůže obsahovat více než jednu kouli, zatímco požadavek ƒ musí být surjektivní znamená, že každý box musí obsahovat alespoň jednu kouli. $f:N\to X$ $f'(a)$

Výpočet ekvivalenčních vztahů permutací množiny N a/nebo množiny X se odráží v uznání koulí a krabic jako „nerozlišitelné“. Toto rozpoznání není přesným prohlášením (v praxi lze jednotlivé míčky a boxy rozlišit podle jejich polohy a různé míčky mohou být umístěny v různých boxech), ale naznačuje, že různé konfigurace nejsou považovány za samostatné, pokud lze jednu z nich přeměnit na jinou. výměnou míčků nebo krabic. To je přesně to, co je formalizováno permutací množin N a/nebo X . Nerozlišitelné krabice je těžší si představit než nerozlišitelné koule, protože konfigurace nevyhnutelně znamená určité uspořádání krabic. Přeskupení krabic se projeví jako výměna jejich obsahu.

Výběry

Jiný přístup k řešení stejných případů je z hlediska vzorků ve statistice . Představte si populaci X objektů (nebo lidí), z nichž vybereme N . Běžně se uvažují o dvou schématech, známých jako „ vzorkování se zatažením“ a „vzorkování bez výměny“ . V prvním případě (výběr s návratem) po výběru objektu jej vrátíme populaci, aby nás mohl znovu zasáhnout. Výsledek každého takového vzorku je nezávislý na všech ostatních vzorcích a soubor vzorků je technicky považován za nezávislé identicky rozdělené náhodné proměnné . Ve druhém případě jej však po výběru objektu odložíme a objekt se nemůže objevit podruhé. To znamená, že skutečnost, že je vybrán jeden objekt, má vliv na všechny následující vzorky (konkrétní objekt nelze trefit podruhé), takže se naše vzorky stanou na sobě závislými.

V případě vzorkování s backtrackingem řekneme níže „Any f' “, zatímco pro vzorkování bez backtrackingu řekneme „Injective f' “. Každý rámeček označuje, kolik různých výběrů sad bylo provedeno v konkrétním schématu. Řádek se slovem "Jiné" znamená, že objednávka je zohledněna. Pokud máme například objekty, ze kterých vybereme dva, pak se vzorek (4,7) liší od (7,4). Na druhé straně řádek označený „S n order“ znamená, že na pořadí nezáleží; v tomto případě jsou volby (4.7) a (7.4) ekvivalentní. Z hlediska rozdělení pravděpodobnosti jsou vzorky opětovného vstupu, kde se bere v úvahu uspořádání, srovnatelné s popisem společného rozdělení N jednotlivých náhodných proměnných , z nichž každá má X - násobné kategorické rozdělení . Případ, kdy se nebere v úvahu pořadí, je srovnatelný s popisem jediné multinomiální distribuce N vzorků z X - násobné kategorie, kde záleží pouze na počtu každé kategorie. Případ, kdy se nebere v úvahu pořadí a vzorky jsou vyrobeny bez náhrady, je srovnatelný se samostatným vícerozměrným hypergeometrickým rozložením a srovnání čtvrté možnosti s něčím není vidět. Všimněte si, že ve všech "injektivních" případech (tj. vzorky bez náhrady) je počet sad vzorků nula, pokud . (Slovo „srovnatelné“ ve výše uvedených případech znamená, že každý prvek prostoru elementárních událostí odpovídající distribuce odpovídá samostatné sadě vzorků, a proto číslo v buňce udává velikost prostoru událostí pro toto rozložení.) $N\leqslant X$

Z tohoto pohledu vypadá případ označený jako "Surjective f' " zvláštně. V podstatě stále vybíráme zpět, dokud nevybereme každý prvek alespoň jednou. Nyní spočítáme, kolikrát jsme kuličky vytáhli, a pokud toto číslo není rovno N , celý vzorek zahodíme a opakujeme. Vágně to připomíná problém s výběrem kuponů , kde proces zahrnuje „vyzvednutí“ (vyzvednutí a vrácení) sady X kuponů, dokud nemáme sadu, ve které se každý kupon objeví alespoň jednou. Všimněte si, že ve všech "surjektivních případech" je počet sad vzorků roven nule, pokud ne . $N\geqslant X$

Výběr, označení, seskupení

Na funkci lze nahlížet jako na X nebo N . To vede k různým úhlům pohledu: $f:N\to X$

funkce ƒ označí každý prvek množiny N prvkem z X .
funkce ƒ vybere prvek množiny X pro každý prvek množiny N , čímž získá celkem n vzorků.
funkce ƒ seskupuje prvky množiny N dohromady, pokud se mapují na stejný prvek množiny X .

Tato hlediska neplatí stejně pro všechny případy. Hlediska „návěští“ a „výběru“ nejsou zcela kompatibilní s permutací prvků množiny X , protože mění štítky a výběry. Na druhou stranu, hledisko "seskupení" neposkytuje úplnou informaci o konfiguraci , pokud prvky množiny X nelze permutovat. Hlediska „vzorkování“ a „výběru“ jsou víceméně ekvivalentní, když N není permutováno, ale v tomto případě je vhodnější hledisko „výběru“. Vzorek pak může být viděn jako neuspořádaný vzorek - vybere se (multi-)množina n prvků z množiny X .

Označování a vzorkování s opakováním nebo bez opakování

Uvažujeme -li o ƒ jako o označení prvků množiny N , lze si písmena představit jako uspořádaná v sekvenci a označení jako sekvenční přiřazená prvkům. Požadavek, aby funkce ƒ byla injektivní, znamená, že žádný štítek nelze použít dvakrát. Výsledkem bude sekvence štítků bez opakování . Pokud tento požadavek neexistuje, používá se terminologie "sekvence s opakováním", což znamená, že značky lze použít více než jednou (ačkoli sekvence, ve kterých nejsou žádná opakování, jsou také povoleny).

Pro neuspořádaný vzorek platí stejné rozlišení. Pokud má být ƒ injektivní, pak výběr musí zahrnovat n odlišných prvků množiny X , bude to tedy podmnožina množiny X o velikosti n , tzv. n - kombinace . Bez tohoto požadavku se může stejný prvek množiny X objevit ve vzorku vícekrát, takže výsledkem je multimnožina n prvků množiny X , které se také říká n - multi -shoda nebo n -shoda s opakování.

V těchto případech požadavek, aby ƒ bylo surjektivní , znamená, že jakýkoli štítek musí být použit alespoň jednou nebo že jakýkoli prvek X musí být zahrnut ve vzorku alespoň jednou. Takový požadavek je v matematickém uvažování méně přirozený a navíc je předchozí případ snáze považován za seskupení prvků N s přidáním skupinových značek prvků množiny X .

Rozdělení množin a čísel

Uvažujeme -li ƒ jako seskupení prvků množiny N (což implikuje identifikaci pomocí permutací množiny X ), požadavek, aby ƒ bylo surjektivní, znamená, že počet skupin musí být přesně roven x . Bez tohoto požadavku nesmí počet skupin překročit x . Požadavek, aby ƒ bylo injektivní , znamená, že každý prvek N musí být sám o sobě grupou, což ponechává pouze jedno platné seskupení, a proto není zajímavým problémem počítání.

Pokud se navíc identifikace provádí permutacemi množiny N , vede to k zapomenutí skupin, zůstávají pouze jejich velikosti. Tyto rozměry se neobjevují v žádném konkrétním pořadí a samotné rozměry se mohou vyskytovat více než jednou. Velikosti můžete seřadit do mírně klesajícího seznamu čísel, jejichž součet je n [3] . To dává kombinatorickou reprezentaci rozdělení čísla n na přesně x (pro surjektivní ƒ ) nebo nanejvýš x (pro libovolné ƒ ) části.

Vzorce

Vzorce pro různé případy dvanácti scénářů jsou shrnuty v tabulce, přičemž každý prvek tabulky je propojen s částí níže, která vysvětluje vzorec.

Dvanáct kombinatorických objektů a jejich vzorce.

f -třída	Jakékoliv f	Injektivní f	Surjektivní f
F	n -sekvence v X $x^n$	n -permutace množiny X $x^{\underline {n))$	složení N s x podmnožinami $\textstyle x!\{{n \atop x}\}$
${\displaystyle f'\circ S_{n))$	n -multipodmnožina X ${\binom {x+n-1}{n))$	n -podmnožina množiny X ${\binom {x}{n))$	složení n s x členy ${\binom {n-1}{nx))$
$S_{x}\circ f$	rozdělení N do podmnožin $\leqslant x$ ${\displaystyle \sum _{k=0}^{x}\left\{{n \atop k}\right\))$	rozdělení N na prvky $\leqslant x$ $[n\leqslant x]$	rozdělení N do podmnožin $\leqslant x$ $\left\{{n \atop x}\right\}$
$S_{x}\circ f\circ S_{n}$	rozdělení n na části $\leqslant x$ $p_{x}(n+x)$	rozdělení n na části 1 $\leqslant x$ $[n\leqslant x]$	rozdělení n na x částí $p_{x}(n)$

Použitý zápis:

klesající faktoriál , $x^{\underline {n}}={\frac {x!}{(xn)!}}=x(x-1)(x-2)\cdots (x-n+1)$
rostoucí faktoriál , $x^{\overline {n}}={\frac {(x+n-1)!}{(x-1)!}}=x(x+1)(x+2)\cdots ( x+n-1)$
Faktorový $n!=n^{\underline {n}}=n(n-1)(n-2)\cdots 1$
Stirlingova čísla druhého druhu vyjadřují počet způsobů, jak rozdělit množinu n prvků do k podmnožin $\textstyle \{{n \atop k}}\}$
Binomický koeficient $\textstyle {\binom {n}{k}}={\frac {n^{\underline {k}}}{k!)}}$
Iversonovy závorky kódují pravdivost nebo nepravdivost výroku (jako 1 nebo 0)
počet rozdělení čísla n na k dílů $p_{k}(n)$

Intuitivní význam řádků a sloupců

Zde je stručný přehled toho, co jednotlivé třídy znamenají. Třídy jsou podrobně popsány níže.

Uvažujme množinu X očíslovaných prvků (čísla od 1 do x ), z nichž vybereme n , což dává uspořádaný seznam prvků. Pokud například existují prvky, ze kterých vybíráme , výsledkem může být seznam (5,2,10). Nyní spočítáme, kolik takových odlišných seznamů existuje, někdy nejprve seznamy transformujeme takovým způsobem, aby se snížil počet různých možností. $x=10$ $n=3$

Pak sloupce znamenají:

Any f : Poté, co vybereme prvek, složíme jej zpět, abychom jej mohli znovu vybrat.
Injective f : Poté, co jsme vybrali prvek, odložíme jej stranou, abychom jej nemohli vybrat znovu. Proto skončíme s n odlišnými prvky. Samozřejmě, že v tomto případě, pokud nebude spokojen , žádný seznam nedostaneme. $n\leqslant x$
Surjective f : Poté, co máme vybraný prvek, vložíme jej zpět, abychom jej mohli znovu vytáhnout, ale nakonec musíme každý prvek vybrat alespoň jednou. Samozřejmě, že v tomto případě, pokud nebude spokojen , žádný seznam nedostaneme. $n\geqslant x$

Řádky znamenají:

Různé: Nechte seznamy tak, jak jsou, počítejte je přímo.
S n oběžné dráhy: Před počítáním seřaďte seznamy podle čísel vybraných prvků, takže na pořadí nezáleží, např. (5,2,10), (10,2,5), (2,10,5) atd. vše → (2,5,10).
S x oběžné dráhy: Před počítáním přečíslujte prvky tak, aby první prvek v seznamu měl číslo 1, druhý (pokud se nerovná) číslo 2 atd. Čísla se mohou opakovat, pokud se prvek v seznamu vyskytuje více než jednou. seznam, například (3,5,3), (5,2,5), (4,9,4) atd. → (1,2,1), zatímco (3,3,5), ( 5,5,3), (2,2,9) atd. → (1,1,2).

${\displaystyle \mathbf {S} _{n}\times \mathbf {S} _{x))$ oběžné dráhy: Před počítáním je seznam setříděn a přečíslován, jak je popsáno výše. (Poznámka: Přečíslování a následné řazení může v některých případech vést k různým seznamům, ale počet možných seznamů se nezmění.)

Podrobnosti o různých případech

Níže uvedené případy jsou seřazeny tak, jak jsou počítány, což není stejné pořadí v tabulce.

Funkce od N do X

Tento případ je ekvivalentní počítání posloupností n prvků množiny X bez omezení: funkce je definována n obrazy prvků z N , které lze nezávisle vybrat ze stopových prvků x . To dává celkem x n možností. $f:N\to X$

Příklad:

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

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

Injektivní funkce od N do X

Tento případ je ekvivalentní počítání sekvencí n různých prvků množiny X , které se také nazývají n -permutace množiny X nebo sekvence bez opakování . Posloupnost je opět tvořena n vzory prvků z N . Tento případ se liší od neomezených sekvencí (výše) tím, že výběr druhého prvku je o jeden méně, druhý je o dva méně a tak dále. Místo mocniny x bude tedy výsledek dán klesajícím faktoriálem x , ve kterém je každý další faktor o jeden menší než ten předchozí. Vzorec pro počet kombinací

x^{\podtržení {n}}=x(x-1)\cdots (x-n+1).

Všimněte si, že v případě, kdy , bude jeden z faktorů roven nule, takže v tomto případě neexistují žádné injektivní funkce . Toto je jednoduše přeformulování Dirichletova principu . $n>x$ $N\to X$

Příklad:

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

$\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)\}\vpravo\vert =4^{\podtržení {2}}=4\krát 3=12$

Injektivní funkce od N do X až do permutace množiny N

Tento případ je ekvivalentní počítání podmnožin s n prvky z X , nazývaných také n - kombinace X- mezi sekvencemi n různých prvků X , ty, které se liší pouze v pořadí prvků, jsou identifikovány s permutacemi N. Protože ve všech případech mají všechny tyto skupiny právě n ! různých sekvencí, můžeme počet takových sekvencí vydělit n !, abychom dostali počet n -kombinací množiny X. Toto číslo je známé jako binomický koeficient a je dáno vzorcem ${\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}}.

Příklad:

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

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

Funkce od N do X až do permutace N

Tento případ je ekvivalentní počítání multimnožin s n prvky z X (které se nazývají n -multikombinace). Důvodem je, že pro každý prvek množiny X je kombinace určena tím, kolik prvků množiny N je na tento prvek mapováno funkcí f , zatímco dvě funkce, které dávají stejný počet „násobnosti“ pro každý prvek množiny X , mohou být vždy transformovány z jednoho na druhý permutací prvků množiny N . Vzorec, který počítá všechny funkce , je zde k ničemu, protože počet seskupených prvků podle permutací N se liší od funkce k funkci. Spíše, jak je vysvětleno v části Kombinace s opakováním , počet n -multikombinací ze sady s x prvky lze považovat za počet n -kombinací ze sady s x + n − 1 prvky. To redukuje problém na jiný případ "duodecimálním způsobem" a dává výsledek $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!}}.

Příklad:

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

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

Surjektivní funkce od N do X až po permutaci N

Tento případ je ekvivalentní počítání multimnožin s n prvky z X , pro které se každý prvek X vyskytuje alespoň jednou. To je ekvivalentní počítání expanzí čísla n do x (nenulových) prvků , vypisování násobnosti x prvků ve vzestupném pořadí. Korespondence mezi funkcemi a multimnožinami je stejná jako v předchozím případě a požadavek surjektivity znamená, že všechny násobnosti jsou alespoň jedna. Když se všechny násobky sníží o 1, problém se redukuje na předchozí případ. Protože taková změna snižuje hodnotu n o x , výsledkem je

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

Všimněte si, že v tomto případě neexistují vůbec žádné surjektivní funkce . To je ve vzorci zohledněno, pokud jsou binomické koeficienty považovány za vždy 0, pokud je dolní index záporný. Stejnou hodnotu má také výraz $n<x$ $N\to X$

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

S výjimkou extrémního případu , ve kterém předchozí vzorec dává správnou hodnotu , ale poslední vzorec dává . $n=x=0$ ${\tbinom {-1}{0}}=1$ ${\tbinom {-1}{-1}}=0$

Tento výsledný vzorec navrhuje hledat asociaci surjektivních funkcí přímo s podmnožinou n − x prvků vybraných z n − 1 prvků, což lze provést následovně. Nejprve zvolíme kompletní uspořádání množin N a X a všimneme si, že aplikací vhodné permutace množiny N lze libovolnou surjektivní funkci transformovat na jedinou pomalu rostoucí [4] (a samozřejmě stále surjektivní) funkci. Spojíme-li prvky množiny N (podle pořadí) o n − 1 oblouků do spojnicového grafu , pak výběrem libovolné podmnožiny n − x oblouků a smazáním zbytku vznikne graf s x připojenými komponentami a jejich mapováním do postupných prvků množiny X dá pomalu rostoucí surjektivní funkci . Také rozměry spojených komponent dávají složení n v x dílech. Tento argument je v podstatě stejný jako pro hvězdičky a pomlčky , kromě toho, že je na výběr z x − 1 "oddělovačů" $N\to X$ $N\to X$ $N\to X$

Příklad:

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

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

Injektivní funkce od N do X až po permutace X

V tomto případě uvažujeme posloupnosti n různých prvků z X , ale funkce získané jedna od druhé identifikujeme permutací prvků množiny X . Je snadné vidět, že vždy lze identifikovat dvě různé takové sekvence - permutace musí mapovat člen i první sekvence na člen i druhé sekvence, a protože se hodnota vyskytuje dvakrát v obou posloupnostech, tyto požadavky si navzájem neodporují . Mapování zbývá mapovat prvek nenalezený v první sekvenci na prvek nenalezený ve druhé sekvenci. Jediné, co dělá výsledek závislým na n a x , je existence takových posloupností, což je vyjádřeno jako požadavek podle Dirichletova principu. Počet permutací je tedy vyjádřen jako při použití Iversonovy závorky . $n\leqslant x$ $[n\leqslant x]$

Injektivní funkce od N do X až po permutace množin N a X

Tento případ se redukuje na předchozí - protože všechny posloupnosti n různých prvků z X mohou být transformovány do sebe pomocí permutací množiny X , což umožňuje měnit pořadí prvků bez vytváření nových entit, číslo zůstává . $[n\leqslant x]$

Surjektivní funkce od N do X až po permutaci množiny X

Tento případ je ekvivalentní počítání oddílů N do x (neprázdných) podmnožin nebo počítání vztahů ekvivalence na N s přesně x třídami. Navíc pro jakoukoli surjektivní funkci je vztah mít stejný obraz při zobrazení funkcí f takovým vztahem ekvivalence a tento vztah se nemění, když jsou postupně aplikovány permutace množiny X . Na druhou stranu lze takový vztah ekvivalence proměnit v surjektivní funkci tím , že prvkům x množiny X přiřadíme určité třídy ekvivalence . Počet takových oddílů nebo relací ekvivalence je podle definice Stirlingovo číslo druhého druhu S ( n , x ), které se také zapisuje jako . Hodnoty lze popsat pomocí relace opakování nebo pomocí generujících funkcí , ale na rozdíl od binomických koeficientů pro tato čísla neexistuje žádný výraz v uzavřeném tvaru , který nepoužívá sčítání . $N\to X$ $\textstyle \{{n \atop x}}\}$

Surjektivní funkce od N do X

Pro každou surjektivní funkci má její orbita nad permutacemi množiny X x ! prvků, protože složení (vlevo) se dvěma různými permutacemi množiny X nikdy nedává stejnou funkci na N (permutace se musí lišit na některém prvku množiny X , což lze vždy pro některé zapsat jako f ( i ) a kompozice se pak budou lišit na prvku i ). Z toho vyplývá, že číslo pro tento případ v x ! krát číslo v předchozím případě, tzn $N\to X$ $i\in N$ $\textstyle x!\{{n \atop x}\}.$

Příklad:

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

$\left\vert \{(a,a,b),(a,b,a),(a,b,b),\ (b,b,a),(b,a,b), (b,a,a)\}\vpravo\vert =\textový styl 2!\{{3 \nahoře 2}\}=2\krát 3=6$

Funkce od N do X s přesnou permutací množiny X

Tento případ je podobný odpovídajícímu případu pro surjektivní funkce, ale některé prvky x nemusí odpovídat žádné třídě ekvivalence (protože funkce jsou uvažovány až do permutace množiny X , nezáleží na tom, které prvky jsou uvažovány, záleží jen kolik ). V důsledku toho se vypočítají vztahy ekvivalence na N s nejvýše x třídami a výsledek se získá ze zmíněného případu součtem přes x hodnot , což dává . V případě , velikost x neklade vůbec žádná omezení a počítají se všechny vztahy ekvivalence na množině n prvků (ekvivalentně všechny dělení takové množiny). Proto dává výraz pro Bellovo číslo B n . $\textstyle \sum _{k=0}^{x}\{{n \atop k}}\}$ $x\geqslant n$ $\textstyle \sum _{k=0}^{n}\{{n \atop k}}\}$

Surjektivní funkce od N do X až po permutace N a X

Tento případ je ekvivalentní počítání oddílů čísla n na x nenulových částí . Případ je srovnatelný s případem počítání surjektivních funkcí až do permutací množiny X (pouze přes X , ), v úvahu by měly být brány pouze velikosti tříd ekvivalence, do kterých funkce rozděluje množinu N (včetně násobnosti každá velikost), protože dva vztahy ekvivalence lze transformovat jeden do jiné permutace množiny N právě tehdy, když jsou velikosti tříd stejné. To je přesně to, co odlišuje pojem dělení n od pojmu dělení N , takže výsledek získáme určením počtu p x ( n ) dělení n na x nenulových částí. $\textstyle \{{n \atop x}}\}$

Funkce od N do X až po permutaci množin N a X

Tento případ je ekvivalentní počítání oddílů čísla n na nejvýše x částí . Asociace je stejná jako v předchozím případě, včetně rozdělení části 0 pro každý prvek X , který není zahrnut v obrázku funkce. Každé rozdělení čísla n na maximálně x nenulových částí lze na takovýto oddíl rozšířit přidáním potřebného počtu nul, a to se počítá pro všechny možnosti právě jednou, takže výsledek je dán vzorcem . Přidáním jedné ke každé z x částí získáme rozdělení n + x na x nenulových částí a tato korespondence je bijektivní. Proto lze výraz zjednodušit na zápis (i když tato změna výpočet neusnadňuje). $\textstyle \sum _{k=0}^{x}p_{k}(n)$ $p_{x}(n+x)$

Extrémní případy

Výše uvedené vzorce dávají odpovídající hodnoty pro všechny konečné množiny N a X . V některých případech existují alternativní vzorce, které jsou téměř ekvivalentní, ale které v některých extrémních případech nedávají správný výsledek, jako je prázdné N nebo X . V těchto případech je třeba vzít v úvahu následující.

Pro jakoukoli množinu X existuje právě jedna funkce z prázdné množiny v X (pro tuto funkci nejsou žádné hodnoty), která je vždy injektivní, ale nikdy surjektivní, kromě případů, kdy je X (také) prázdné.
Pro žádnou neprázdnou množinu N neexistuje žádná funkce od N do prázdné množiny (je nutné, aby existovala alespoň jedna hodnota funkce, ale žádná není).
Kdy , není tam žádná injektivní funkce , a pokud , nejsou tam žádné surjektivní funkce . $n>x$ $N\to X$ $n<x$ $N\to X$
Výrazy použité ve vzorcích mají specifické hodnoty

0^{0}=0^{\underline {0}}=0!={\binom {0}{0}}={\binom {-1}{0}}=\left\{{ 0 \nahoře 0}\vpravo\}=p_{0}(0)=1

(první tři jsou zástupci prázdného součinu a význam je určen běžně přijímaným rozšířením binomických koeficientů na libovolné hodnoty horního indexu), zatímco

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

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

někdy , nebo

n>0=x

0\leqslant n<x.

Konkrétně v případě počítání multimnožin s n prvky vybranými z X je výše uvedený výraz ve většině případů ekvivalentní výrazu , ale druhý výraz dává v tomto případě 0 (s obvyklou konvencí, že binomické koeficienty se záporným indexem jsou vždy 0 ). Podobně pro případ počítání složení čísla n s x nenulovými částmi je výše uvedený výraz téměř ekvivalentní výrazu danému přístupem s hvězdičkou a pomlčkou , ale ve druhém případě dostaneme špatný výsledek pro a všechny hodnoty x . V případech, kdy výsledek zahrnuje sečtení, konkrétně při počítání oddílů N nejvýše x neprázdnými podmnožinami nebo rozděleními n nejvýše x nenulovými částmi, index součtu začíná na 0, ačkoli odpovídající člen je nula pro všechny a stane se nenulovým, když . V takovém případě bude výsledek nesprávný, pokud začnete sčítat od 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$

Zobecnění

Můžeme dále zobecnit tím, že necháme jiné permutační skupiny působit na N a X. Jestliže G je permutační grupa množiny N a H je permutační grupa množiny X , pak počítáme třídy ekvivalence funkcí . Dvě funkce a jsou považovány za ekvivalentní tehdy a pouze tehdy, pokud existují , takové, že . Toto rozšíření vede ke konceptům, jako jsou cyklické a dihedrální permutace, stejně jako cyklické a dihedrální rozdělení čísel a množin. $f\colon N\to X$ $F$ $F$ $g\in G,h\in H$ $F=h\circ f\circ g$

Desetinný způsob

Další zobecnění, nazvané 20 way , vyvinul Kenneth P. Bogart ve své knize Combinatorics Through Guided Discovery . V problému rozdělování předmětů do krabic lze předměty a krabice považovat za nerozlišitelné nebo odlišné. Bogart rozlišil 20 případů [5] .

2 desítkový způsob

n objekty a podmínky, jak jsou získávány	x příjemců a distribuční matematický model
n objekty a podmínky, jak jsou získávány	Rozličný	Stejný
1. Různé Žádné podmínky	n -sekvencí v X $x^n$	rozdělení N do podmnožin $\leqslant x$ $\sum _{i=0}^{n}\left\{{x \nahoře i}\right\}$
2. Různé Každý není vybrán více než jednou	n -permutace množiny X $x^{\underline {n))$	${\begin{cases}1&n\leqslant x;\\0&n>x\end{cases))$
3. Různé Každý je vybrán alespoň jednou	kompozice N s x podmnožinami $x!\left\{{n \atop x}\right\}$	rozdělení N do x podmnožin $\left\{{n \atop x}\right\}$
4. Různé Každý je vybrán právě jednou	$n!=x!$ permutace	$1{\begin{cases}1&n=x\\0&n\neq x\end{cases))$
5. Různé, pořádek je respektován	$(n+x-1)^{\underline {n))$ uspořádané funkce	$\sum _{i=1}^{x}L(n,i)$ přerušené permutace (po částech) $\leqslant x$ Kde je Lachovo číslo $L(n,i)$
6. Různé, počítá se objednávka Každá je vybrána alespoň jednou	$(n)^{\underline {x}}(n-1)^{\underline {nx}}$ seřazené ve funkcích	$L(n,x)=\left({n \nahoře x}\right)(n-1)^{\podtržení {nx))$ rozbité permutace (na x částí) kde je Lachovo číslo $L(n,x)$
7. Stejné žádné podmínky	n -multisety množiny X $\left({x+n-1 \atop n}\right)$	$\sum _{i=1}^{x}p_{i}(n)$ počet oddílů (po částech) $\leqslant x$
8. Identické Každý není vybrán více než jednou	n -podmnožiny množiny X $\left({x \atop n}\right)$	${\begin{cases}1&n\leqslant x;\\0&n>x\end{cases))$
9. Stejné Každý je vybrán alespoň jednou	$\left({n-1 \atop x-1}\right)$ kompozice ( x dílů)	rozdělení n na x částí $p_{x}(n)$
10. Stejné Každý je vybrán právě jednou	${\begin{cases}1&n=x\\0&n\neq x\end{cases))$	${\begin{cases}1&n=x;\\0&n\neq x\end{cases))$

Poznámky

↑ Stanley, 1997 , str. 41.
↑ Richard Stanley. Enumerativní kombinatorika. - Mir, 1990. - T. 1. - S. 55.
↑ Slabě klesající seznam je sestupný seznam s možností opakování.
↑ Říká se, že funkce pomalu roste, pokud je monotónní, ale opakování hodnot je možné.
↑ Bogart, 2004 , str. 57.

Literatura

Richard P. Stanley. Enumerativní kombinatorika, svazek I. - Cambridge University Press, 1997. - ISBN 0-521-66351-2 .
Kenneth P. Bogart. Kombinatorika prostřednictvím řízeného objevování . — Dartmouth College, 2004.