Kombinatorik ar den gren av matematiken som studerar kombinationer, permutationer och upprakningar av element i mangder och de relationer som karakteriserar dessas egenskaper. Metoderna for detta ar grundlaggande i den diskreta matematiken . Foregangsman inom omradet ar bland andra Blaise Pascal , Pierre de Fermat , Pierre Remond de Montmort , James Stirling och broderna Jacob och Johann Bernoulli .

Ett enkelt exempel pa ett kombinatoriskt problem ar fragan, om hur manga olika ordningsfoljder det finns av en 52-korts kortlek . Losningsmetoden ar kand sedan 2500 ar tillbaka och antalet foljder ar 52! (utlases " fakulteten av 52" eller "52 fakultet"), alltsa 52·51·50· ··· ·3·2·1 vilket ar ungefar lika med 8·10 ⁶⁷ , eller en atta foljd av 67 nollor.

Tarningskast [ redigera | redigera wikitext ]

Kombinatoriken utvecklades jamsides med sannolikhetsteorin och kom att initieras hosten 1654 av Pascal i samband med att en van till honom, chevalier de Mere , stallde fragor rorande bland annat tarningsspel. Exempelvis kan man, vid kast med ett godtyckligt antal tarningar, med hjalp av Pascals binomialkoefficienter och Stirlingtal , skriva antalet mojliga utfall, som en strukturerad summa. Om antalet tarningar ar fyra fas foljande:

${\displaystyle 6^{4}=1\cdot {\tbinom {6}{1}}\cdot 1!+7\cdot {\tbinom {6}{2}}\cdot 2!+6\cdot {\tbinom {6}{3}}\cdot 3!+1\cdot {\tbinom {6}{4}}\cdot 4!=6+210+720+360=1296}$,

dar koefficienterna 1, 7, 6 och 1 ar Stirlingtal av andra slaget . For handelsen, att alla tarningar visar lika, en kvadrupel , ar saledes antalet utfallsmojligheter lika med 6, for en trippel eller tva par ar antalet 210, for exakt ett par ar antalet 720 och for att alla tarningar visar olika ar antalet 360.

Hattproblemet [ redigera | redigera wikitext ]

Ett klassiskt problem harstammar fran den franske matematikern de Montmort . Problemet, som har en mangd olika formuleringar, kan uttryckas sa har: N herrar, som skall bevista en bankett lamnar sina hattar pa en hylla och nar de gar hem valjer de, av nagon anledning, en hatt helt slumpmassigt. Den fraga de Montmort stallde sig var: Pa hur manga olika satt kan hattarna valjas utan att nagon far ratt hatt? Han brevvaxlade, i fragan, med matematikern Nicholas Bernoulli under aren 1710-1712 och de lyckades finna en berakningsmetod. I det speciella fall da N = 5, blir det sokta antalet:

M(5) ${\displaystyle =5!-{\tbinom {5}{1}}\cdot 4!+{\tbinom {5}{2}}\cdot 3!-{\tbinom {5}{3}}\cdot 2!+{\tbinom {5}{4}}\cdot 1!-{\tbinom {5}{5}}\cdot 0!=120-120+60-20+5-1=44.}$

Som synes ar de tva forsta termerna overflodiga, men tas med har av symmetriskal. Talen har fatt namn efter de Montmort och for N = 1, 2, 3, 4, 5, 6.... ar dessa M = 0, 1, 2, 9, 44, 265,.... Det visar sig att kvoten M/N! snabbt gar mot ${\displaystyle e^{-1}}$ da N vaxer.

Generell metod [ redigera | redigera wikitext ]

For en systematisk behandling av kombinatoriska problem valjer man ofta en modell, dar kulor under givna forutsattningar fordelas i lador. Beroende pa egenskaperna hos kulorna och ladorna, om de ar sarskiljbara eller inte sarskiljbara, sa varierar antalet fordelningsmojligheter .

I nedanstaende tabell kallar vi antalet kulor for n , antalet lador for m och Stirlingtalet av andra slaget for S ( n , m ).

Kulorna ar sarskiljbara	Ladorna ar sarskiljbara	Lador far vara tomma	Antal mojligheter
Ja	Ja	Ja	m n
Ja	Ja	Nej	m !· S ( n , m )
Ja	Nej	Ja	S ( n , 1) + S ( n , 2) + ··· + S ( n , m )
Ja	Nej	Nej	S ( n , m )
Nej	Ja	Ja	${\displaystyle n+m-1 \choose n}$
Nej	Ja	Nej	${\displaystyle n-1 \choose m-1}$

Centrala begrepp inom kombinatoriken ar kombination , permutation och Dirichlets ladprincip .

Kombinatorikens verktyg ar av stor betydelse inom datavetenskap , sannolikhetslara och statistik . Med kombinatorikens hjalp kan man, utifran givna fakta, uttala sig med sakerhet. Till exempel: Det finns helt sakert minst tio svenskar som ar lika langa pa mikrometern nar (se exempel i Dirichlets ladprincip ). For en systematisk och mer fullstandig beskrivning av de grundlaggande kombinatoriska metoderna, se artikeln, " Tolvfaldiga vagen ".

Delomraden [ redigera | redigera wikitext ]

Partitionsteori [ redigera | redigera wikitext ]

Partitionsteori undersoker problem relaterade till heltalspartitioner, och ar nara relaterat till q-serier , speciella funktioner och ortogonala polynom . Ursprungligen var partitionsteori ett delomrade av talteori och analys , men betraktas numera som en del av kombinatorik eller ett helt eget omrade. Den anvander bijektiva bevis och flera verktyg fran analys och analytisk talteori , och har aven samband med statistisk mekanik .

Kallor [ redigera | redigera wikitext ]

Den har artikeln ingar i boken:  Matematik

• Alan Tucker, Applied Combinatorics, John Wiley & Sons, New York, 1980.
• A. Hald, A History of Probability and Statistics and their Applications before 1750, Wiley, New York, 1990.