Kombinatorik

Kombinatorik är den gren av matematiken som studerar kombinationer, permutationer och uppräkningar av element i mängder och de relationer som karakteriserar dessas egenskaper. Metoderna för detta är grundläggande i den diskreta matematiken. Föregångsmän inom området är bland andra Blaise Pascal, Pierre de Fermat, Pierre Rémond de Montmort, James Stirling och bröderna Jacob och Johann Bernoulli.

Ett enkelt exempel på ett kombinatoriskt problem är frågan, om hur många olika ordningsföljder det finns av en 52-korts kortlek. Lösningsmetoden är känd sedan 2500 år tillbaka och antalet följder är 52! (utläses "fakulteten av 52" eller "52 fakultet"), alltså 52·51·50· ··· ·3·2·1 vilket är ungefär lika med 8·10⁶⁷, eller en åtta följd av 67 nollor.

Tärningskast

Kombinatoriken utvecklades jämsides med sannolikhetsteorin och kom att initieras hösten 1654 av Pascal i samband med att en vän till honom, chevalier de Méré, ställde frågor rörande bland annat tärningsspel. Exempelvis kan man, vid kast med ett godtyckligt antal tärningar, med hjälp av Pascals binomialkoefficienter och Stirlingtal, skriva antalet möjliga utfall, som en strukturerad summa. Om antalet tärningar är fyra fås följande:

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

där koefficienterna 1, 7, 6 och 1 är Stirlingtal av andra slaget. För händelsen, att alla tärningar visar lika, en kvadrupel, är således antalet utfallsmöjligheter lika med 6, för en trippel eller två par är antalet 210, för exakt ett par är antalet 720 och för att alla tärningar visar olika är antalet 360.

Hattproblemet

Ett klassiskt problem härstammar från den franske matematikern de Montmort. Problemet, som har en mängd olika formuleringar, kan uttryckas så här: N herrar, som skall bevista en bankett lämnar sina hattar på en hylla och när de går hem väljer de, av någon anledning, en hatt helt slumpmässigt. Den fråga de Montmort ställde sig var: På hur många olika sätt kan hattarna väljas utan att någon får rätt hatt? Han brevväxlade, i frågan, med matematikern Nicholas Bernoulli under åren 1710-1712 och de lyckades finna en beräkningsmetod. I det speciella fall då N = 5, blir det sökta antalet:

M(5) $=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 är de två första termerna överflödiga, men tas med här av symmetriskäl. Talen har fått namn efter de Montmort och för N = 1, 2, 3, 4, 5, 6.... är dessa M = 0, 1, 2, 9, 44, 265,.... Det visar sig att kvoten M/N! snabbt går mot $e^{-1}$ då N växer.

Generell metod

För en systematisk behandling av kombinatoriska problem väljer man ofta en modell, där kulor under givna förutsättningar fördelas i lådor. Beroende på egenskaperna hos kulorna och lådorna, om de är särskiljbara eller inte särskiljbara, så varierar antalet fördelningsmöjligheter.

I nedanstående tabell kallar vi antalet kulor för n, antalet lådor för m och Stirlingtalet av andra slaget för S(n, m).

Kulorna är särskiljbara	Lådorna är särskiljbara	Lådor får vara tomma	Antal möjligheter
Ja	Ja	Ja	mⁿ
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	$n+m-1 \choose n$
Nej	Ja	Nej	$n-1 \choose m-1$

Centrala begrepp inom kombinatoriken är kombination, permutation och Dirichlets lådprincip.

Kombinatorikens verktyg är av stor betydelse inom datavetenskap, sannolikhetslära och statistik. Med kombinatorikens hjälp kan man, utifrån givna fakta, uttala sig med säkerhet. Till exempel: Det finns helt säkert minst tio svenskar som är lika långa på mikrometern när (se exempel i Dirichlets lådprincip). För en systematisk och mer fullständig beskrivning av de grundläggande kombinatoriska metoderna, se artikeln, "Tolvfaldiga vägen".

Delområden

Partitionsteori

Partitionsteori undersöker problem relaterade till heltalspartitioner, och är nära relaterat till q-serier, speciella funktioner och ortogonala polynom. Ursprungligen var partitionsteori ett delområde av talteori och analys, men betraktas numera som en del av kombinatorik eller ett helt eget område. Den använder bijektiva bevis och flera verktyg från analys och analytisk talteori, och har även samband med statistisk mekanik.

Källor

Den här artikeln ingår 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.

Navigation

Navigering

Temaportaler