Normat 52:1, 21–38 (2004) 21
Diskret matematikk finnes ikke
D. Laksov
Matematiska Institutionen, KTH
SE–100 44 Stockholm
laksov@math.kth.se
Matematikk og anvendelser
Det skrives mye om diskret matematikk som et nytt område av matematikken med
interes sante anvendelser, fra brevutbæring til livets opprinnelse. På NV-program-
met i gymnasene i Sverige har emnet matematik diskret blitt obligatorisk på «ma-
tematik/datalogi» grenen. Det oppsiktsvekke nde med dette er at det ikke fi nn es
noe matematisk område som heter Diskret matematikk og at det er både unaturlig
og uinteressant å dele inn matematikken i diskret matematikk og annen matema-
tikk. Spesielt forvirrende er det at anvendelsene som denne diskrete matematikken
skulle gi opph av til ofte viser seg å være banale omformuleringer av matematiske
begrep e r med ord hentet fra hverdagslivet og uten praktisk betydning. Et typisk
eksempel er når man omformulerer et kjent problem av en av tidenes mest fremstå-
ende matematikere W. R. Hamilton (1805–1865) om stier i en graf, som et problem
som postmenn møter når de skal dele ut post, eller som handelsreisende må løse for
å besøke kunder mest effektivt. Ikke bare er anvendelsene urealistiske, men man
har heller ikke bidratt noe til løsningen av problemet ved å kle det i ny språkdrakt.
Vi har illustrert dette med et utførlig eksempel nedenfor.
Slike pseudoanvendelser trekker oppmerksomheten bort fra matematikken som
et aktivt og sentralt vitenskapelig emne, med fundamentale naturvitenskapelige og
tekniske anvendelser. Det er knapt noe område av et høyteknologisk samfunn som
skulle fun gere uten bruk av matematisk teori og matem atiske formler.
Hysteriet med å fremstille deler av matematikken som «diskret» oppsto i for-
bindelse med datamaskinene. Intuitivt er disse «diskrete av naturen» ettersom de
inneholder en endelig mengde informasjon, og alle op e rasjone ne kan beskrives med
0-er og 1-ere. Ettersom bruken av datamaskinene fikk så stor oppmerksomhet og
ble spådd en stor økonomisk betydning var det fristende å fremstille sin egen lille
laksov.tex,v 1.12
22 D. Laksov Normat 1/2004
spesialitet i matematikken som spesielt passende for datamaskiner, og for kom-
mu nikasjon på nettet. Dermed kunne de være med å «dele på kaken». Det er også
riktig at datamaskinene skulle bli langsomme og klumpete, ja nesten ubrukelige, og
at kommunikasjonen på nettet umulig, uten omfattende bruk av matematikk. For
eksempel er komprimering av lyd og bilder, og lyd- og bildegjenkjennelse, som spil-
ler en stor rolle for lagring av informasjon i datamaskiner og for kommunikasjon en
av datamengder mellom d em, basert på resu ltater om trigonometriske funksjoner
funnet av J. Fourier (1768–1830), eller på wavelets som ble initiert av den svenske
matematikeren J. O. Strömberg for 20–30 år siden. Kryptering av informasjon på
nettet, som er avg j ørende for all handel på nettet, og som vi bruker hver gang
vi stikker et ban kkort i en automat, er basert på resultater i tallteori funnet av
P. Fermat (1601–1665). Hele teorien for informasjonsoverføring, og spesielt for det
mye omtalte bredbånd, ble utviklet av C. E. Shannon (1916–2002), og er basert på
statistisk mekanikk, termodynamikk og klassisk pot ensialteori fra fysikken. Dette
er bare noen e ksempler som viser hvilken fundamental rolle matematikken spiller
i dagens samfunn. Eksemplene viser også at det ikke er noen spesiell del av ma-
tematikken som passer bra for anvendelser på datamaskiner. Spennvidden mellom
Fourierrekker, Fermats lille sats og informasjonsteori er enorm. Det er heller in-
gen av disse områdene som utmerker seg som spesielt diskret. At vi har en følelse
av at datamaskinene virker på en «diskret måte» i noen mening, betyr selvsagt
ikke at den matematikken som beskriver operasjonene i datamaskinene har noen
spesiell «diskret karakter». Bredden av den matematikken som brukes i teknikk og
vitenskap er imponerende. De fleste anvendelsene av matematikken er basert på
en solid forståelse av matematikk, god innsikt i det praktiske problemet og ofte på
geniale idéer om hvordan matematikken og anvendelsene kan kombineres. De mest
overraskende matematiske resultater kommer til nytte, ofte slike som er funnet for
hundretalls år siden, selvsagt uten tanke på anvendelser.
Takk til referent og redaktør. Jeg vil benytte anledningen til å takke referenten
for velmotivert og konstruktiv kritikk av den første versjonen av denne artikkelen.
Utformningen og innholdet i versjonen ned enf or skyldes til en stor del redaktør
Marius Overholts optimistiske tolkning av referentrapporten og hans inspirerende
og oppmuntrende synspunkter.
Matematikkens omfang
At det er så mange ulike deler av matematikken som har naturvitenskapelige og
tekniske anvendelser reflekterer at matematikken er et gigantisk forskningsområde.
Bredden av matematikken er langt større enn hva de fleste er klare over. Vi deler
inn matematikken i 63 hovedområder. Hver av disse er oppdelt i underområder, som
ig j en er oppdelt i mindre deler. I Appendiks A har vi listet hovedklassifikasjonen
av matematikken. Denne kaller vi AMS-klassifikasjonen fordi den blir utgitt av
American Mathematical Society. Hele klassifikasjonen med alle underavdelingene
omfatter 56 tettskrevne A4-sider. For å illustrere mangfoldet har vi i Appendiks
B også gitt grovklassifikasjonen for ett av hovedområdene i matematikken, nemlig
algebraisk geometri (AMS-klassifikasjon 14), og i Appendiks C har vi også alle
underklassene av en av disse (AMS-klassifikasjon 14H–xx Curves). Spennvidden av
laksov.tex,v 1.12
Normat 1/2004 D. Laksov 23
matematikken er så stor at en matematiker som arbeider på et hovedområde har
like store vanskeligheter med å forstå hva en matematiker på et annet område gjør,
som en ekspert på atomfysikk har for å forstå en ekspert på vulkaner.
Ingen av de 63 områdene, eller deres underområder heter diskret matematikk,
og det tjener hverken noen hensikt, eller er sp es ielt påtrengende å påstå at noen
delområder er mer diskrete enn andre. Intuitivt har vi en presis følelse av hva dis-
kret betyr. For eksempel vil minuttviseren på en klokke bevege seg fra 0 til 60 i en
eneste kontinuerlig bevegelse, og alle tall mellom 0 og 60 blir passert. Sekundvise-
ren derimot hopper mellom sekundene og tar bare 60 ulike verdier. Vi oppfatter
derfor bevegelsen til sekundviseren som diskret, mens minuttviseren beveger seg
kontinuerlig eller i realtid. Prøver man å overføre denne intuisjonen til en konkret
beskrivelse av hva som burde være diskret i matematikken får man store problemer.
Oppfatter vi kontinuerlig som det omvendte av diskret hjelper det ikke mye. Be-
grepet kontinuitet finnes i alle deler av matematikken, selv når vi bare skal studere
et endelig antall objekter. En av hensiktene med denne artikkelen er å presentere
et par typiske eksempler på at begrepene avstand og kontinuitet kommer inn i de
meste uventede situasjoner som vi normalt oppfatter som diskrete. Prøver vi isteden
å holde fast på at minuttviseren passerer alle reelle tall mellom 0 og 60 så hjelpe r
det like lite for å beskrive hva som bør være kontinuerlig matematikk, ettersom de
reelle tallene spiller e n fundamental rolle i nesten alle deler av matematikken.
Om vi istedenfor, litt naivt, antar at «Skolverket» i Sverige har løst probleme t
med å presisere diskret matematikk og definerer diskret ut fra kurset Matematik
diskret på NV-programmet i svenske gymnaser så finner vi at diskret matematikk
består av en liten brøkdel av de enkleste de lene av områdene Matematisk logikk
(AMS-klassifikasjon 03), Kombinatorikk (AMS-klassifikasjon 05), Tallteori (AMS-
klassifikasjon 11), og Datalogi (AMS-klassifikasjon 68). Det kan være interessant å
merke at den brøkdelen av Kombinatorikk som er med i Matematik Diskret egentlig
hører hjemme i Sannsynlighetsteorien (AMS-klassifikasjon 60).
Resonnementer som gir seg ut for å være diskrete er ofte enkle og basert på
allmenne betraktninger som man ikke behøver noen matematisk utdannelse for å
utføre. Problemene har ofte karakteren av spill eller underholdningsmatematikk,
og virker tilgjorte. Anvendelse er naive, på grensen til det latterlige, og er ofte rene
omskrivninger av matematiske begreper i dagligspråk. De krever hverken innsikt
i anvendelsene eller i matematikken. Dette kan virke lokkende på unge uerfarne
personer som tror de kan drive matematikk uten en solid teoretisk bakgrunn, og
som håper på å oppnå sensasjonelle anvendelser uten å ha kjennskap til området de
skal bruke matematikken på. Dermed gjør de en tragisk feil fordi matematikkens
skjønnhet og karakter ligger i kunnskapene om matematiske teorier og resultater
og det fascinerende samspillet mellom disse. Det er også de dypere matematis-
ke resultatene sammen med solide innsikter i praktiske problemer som leder til
de epokegjørende tekniske og naturvitenskapelige anvendelsene av matematikken.
Uten omfattende kunnskaper og innsikter i matematikken kan man hverken ha
glede av matematikken eller anvende den til noe fornuftig.
laksov.tex,v 1.12
24 D. Laksov Normat 1/2004
Er endelige mengder «diskrete» eller «kontinerlige»?
Som nevnt er det vanlig å define re «diskret matematikk» som de delene av matema-
tikken som ikke er «kontinuerlige». Begrepet kontinuerlig er velkjent fra analysen og
bygger på at vi kan snakke om avstander, og derfor kan avgjøre når pu nkter ligger
nære eller langt fra hverandre. Det finnes imidlertid naturlige avstandsbegreper,
med store anvendelsesområder, selv på endelige mengder. Vi kan derfor resonnere
geometrisk og snakke om kontinuitet på endelige me ngde r. Derfor er det verdiløst
å forsøke å skille diskret fra kontinuerlig på denne måten.
Før vi gir et eksempel på avstandsmål på endelige mengder skal vi presisere
hva vi mener med avstand. Vi vet at hvert reelt tall a har en absoluttverdi |a|.
Avstanden mellom to tall a og b er absoluttverdien |a b| av differansen mellom
tallene. Hele den reelle analysen med kontinuitet, deriverbarhet og integrerbarhet er
bygget på denne absoluttverdien og tilsvarende avstandsmål i høyere dimensjoner.
Selvsagt holder følgende tre egenskaper:
1. (Ikkedegenererthet) |a| =0hvis og bare hvis a =0.
2. (Multiplikativitet) |ab| = |a||b|.
3. (Trekantulikheten) |a + b||a| + |b|.
Egenskap e r (1) og (3) tilfredsstilles av absoluttverdien |(a, b)| =
a
2
+ b
2
i pla-
net, og den tilsvarende absoluttverdien |(a
1
,a
2
,...,a
n
)| =
a
2
1
+ a
2
2
+ ···+ a
2
n
i
høyere-dimen sj onale rom. Vi velger disse egenskap e ne som en modell for avstand
på vilkårlige mengder. Vilkår (2) må vi, som i de høyere-dimensjonale tilfellene, ta
bort ettersom vi ikke har noen naturlig multiplikasjon.
Definisjon. La S være en vilkårlig mengde. En avstand, eller som vi sier metrikk,
på S assosierer et ikkenegativt tall d(x, y) til hvert par av elementer x, y i S slik at
for alle tripler av elementer x, y, z i S så vil følgende egenskaper være tilfredsstilt:
1. (Ikkedegenererthet) d(x, y)=0hvis og bare hvis x = y.
2. (Symmetri) d(x, y)=d(y, x).
3. (Trekantulikheten) d(x, z) d(x, y)+d(y, z).
En mengde S med en metrikk d kaller vi et metrisk rom. Spesielt blir de reelle
tallene R, eller det n-dimensjonale rommet metriske rom med metrikken
d(x, y)=|x y|.
Koder. Eksemplet vi skal gi på en endelig mengde med en avstand, det vil si
en metrikk, kommer fra kodeteorien. Som alle vet kan all informasjon overføres til
digital kode, det vil si, til strenger av 0-er og 1-ere. Det vanlige er at all informasjon
som skal lagres e ller sendes skrives som strenger av 0-er og 1-ere av en fast lengde
n. Vi skal bruke en mer fantasieggende terminologi og si at informasjon er overført
til ord av lengde n med bokstaver fra alfabetet 0, 1. For eksemp el er byte en vanlig
enhet for informasjon, og betyr den informasjonen som rommes i de 2
8
= 256
ordene av lengde 8 fra alfabetet 0, 1.
laksov.tex,v 1.12
Normat 1/2004 D. Laksov 25
Avstanden mellom to ord definerer vi som antallet posisjoner der ordene er ulike.
For eksempe l er avstanden d(x, y) mellom ordene x = 01100111 og y = 10101100 lik
5 fordi de skiller seg i første, andre, f emte, syvende og åttende posisjon. Avstanden
mellom x = 11110000 og y = 00001111 er 8 ettersom x og y skiller seg i alle de 8
posisjonene. Det er en instruktiv og underholdende oppgave å vise at ordene i en
byte med dette avstandsbegrepet danner et metrisk rom. Denne metrikken kalles
Hammingmetrikken etter Richard Hamming (1915–98).
At Hammingmetrikken er både naturlig og viktig ser vi når vi bruker den på
feilrettende koder. Anta at vi vil sende informasjon i form av ord av len gde 8 med
bokstaver fra alfabetet 0, 1 over en kanal der det forekommer støy slik at det ordet
som blir mottatt kan skille s eg fra det ordet vi sendte. Hva skal vi gjøre for å
oppdage, eller til og med rette, feil? Den vanligste måten å oppdage feil på er
ved å foreta en paritetssjekk, det vil si, vi lar selve meddelelsen være de første 7
bokstavene og lar den åttende bokstaven være 0 om det forekommer et like antall
1-ere blant de syv første bokstavene, og lar den være 1 om det forekommer et odde
antall 1-ere. Vi kaller den åttende bokstaven for et kontrollsiffer. For eksempel har
ordene 01100110 og 10101111 rett paritet. Sender vi ordet 01100110 og det oppstår
en feil slik at vi mottar 01101110 eller 01100111 så har ordet vi mottar feil paritet
og vi vet at en feil har oppstått. Derimot kan vi ikke oppdage to feil ettersom ordet
00000110 har rett paritet og forekommer fra 01100110 om vi gjør en feil i andre og
tredje posisjonen. Vi kan heller ikke rette en feil fordi ordet 01101110 som har feil
paritet kan fremkomme fra 01100110 og 01101100, begge med rett paritet, om vi
gjør en feil.
Prisen for å oppdage en feil er at vi bare kan s en de 2
7
= 128 meddelelser,
ettersom den åttende bokstaven er bestemt av de 7 første. Vil vi dessuten rette en
feil er prisen mye høyere. For å se dette bruker vi Hammingmetrikken for å få et
geometrisk bilde av situasjonen. Om vi skal rette en feil må avstanden mellom to
kodeord være minst 3. Dette er fordi, om vi sender et kodeord x og mottar ordet
x
med 1 feil, vil d(x, x
)=1.Omy er et annet kodeord og d(x, y) 3 får vi av
trekantulikheten at
3 d(x, y) d(x, x
)+d(x
,y)=1+d(x
,y),
det vil si, vi har d(x
,y) 2. Med andre ord må det har forekommet minst 2 feil
om vi sendte y og mottok x
. Derfor må vi ha sendt x om det bare har forekommet
en feil. Vi kan formulere kravet at avstanden mellom to kodeord skal være minst
3 geometrisk ved å si at for å rette en feil må hver sfære med radius 1 omkring et
kodeord, ikke inneholde noe annet kodeord.
Vi kan håpe at det rekker å bruke to kontrollsifre for å rette en feil. Faktum er
at det ikke engang rekker med tre kontrollsifre. Dette er fordi en sfære med radius
1 omkring et ord x inneholder nøyaktig 9 ord, nemlig x og de 8 ordene vi får av x
ved å endre på en bokstav. Om vi skal rette en feil så vi at sfærene av radius 1 om
kodeordene må være disjunkte. Bruker vi 3 kontrollsifre kan vi velge de fem første
sifrene fritt så vi har 2
5
kodeord og de 2
5
sfærene om disse med radius 1 må være
disjunkte. Dette gir 2
5
(2
3
+1) = 2
8
+2
5
kodeord, som er mer enn det totale antallet
2
8
kodeord av lengde 8 med bokstaver fra alfabetet 0, 1. Dette er umulig, så vi har
vist at vi må bruke minst 4 kontrollsifre for å rette en feil. I sannhet en høy pris.
laksov.tex,v 1.12
26 D. Laksov Normat 1/2004
Dette forklarer hvorfor det er så viktig å finne gode koder med få kontrollsifre i
forhold til antallet kodeord.
Mer generelt består en blokk-kode av lengde n fra et alfabet A av en undermengde
C av mengden B av alle ord av lengde n med bokstaver fra alfabetet A. Elementene
i C kalles kodeord. Hammingavstanden d(x, y) er antallet posisjoner der ordene x
og y er forskjellige. Som ovenfor er det en underholdende oppgave å verifisere at
dette gir en metrikk på B. Hammingdistansen d
C
for en kode C er den minste
avstand en mellom to kodeord, det vil si
d
C
= min{d(x, y): for alle distinkte punkter x og y i C}.
En kode med Hammingdistanse d
C
kan rette (d
C
1)/2 feil. Dette sees som
ovenfor. Om ordet x i C er et kodeord og x
et ord vi får fra x om vi gjør høyst
(d
C
1)/2 feil så gir trekantulikheten at f or hvert kodeord y så vil
d
C
d(x, y) d(x, x
)+d(x
,y) (d
C
1)/2 + d(x
,y) <d
C
/2+d(x
,y).
Det vil si at (d
C
1)/2 <d
C
/2 <d(x
,y) så x er det eneste kodeordet som kan gi
opphav til x
om vi gjør høyst (d
C
1)/2 feil.
Det er lett å forstå at det er vanskelig å konstruere koder med mange kodeord i
forhold til kontrollsifre. Kodene skal også være lette å bruke, så det må finnes enkle
regler for koding og dekoding. Noen av de beste kodene fåes ved å bruke strukturen
på elliptiske kurver, det vil si (i alle fall om karakteristikken er forskjellig fra 2 og
3) løsninger til ligningen
y
2
=4x
3
g
2
x g
3
med =g
3
2
27g
2
3
=0.
Det vil gå for langt å beskrive den omfattende teorien for elliptiske kurver. Studiet
av elliptiske kurver tilhører området algebraisk geometri (se 14H52 i Appendiks
C). Her blandes algebraiske, analytiske, tallteoretiske og geometriske metoder på
en måte som gjør at alt snakk om diskret og kontinuerlig er totalt meningsløst.
Som en kuriositet vil vi nevne at elliptiske kurver spilte en hovedrolle da Fermats
store sats, eller som den mer korrekt ble kalt Fermats formodning, det vil si at
ligning x
n
+ y
n
= z
n
ikke har noen heltallsløsninger slik at xyz =0når n>2,
ble løst på slutten av nittenhundretallet. Det var Gerhard Frey som bemerket at
det var en forbindelse mellom Fermats formodning og elliptiske kurver. Dette ledet
til en enorm aktivitet blant verdens fremste eksperter på området, og til Andrew
Wiles’ og Richard Taylors bevis for formodningen, samt til bevis for noen av de
viktigste formodningene om elliptiske kurver (se [3]). Beviset er en av de fremste
matematiske innsatsene på slutten av nittenhundretallet og løste det kanskje mest
kjente av alle matematiske problemer som hadde stått åpent i omtrent 350 år.
Er de hele tallene «diskrete»?
Om vi vil bruke vår intuisjon for å beskrive hva som bør være diskret matema-
tikk ligger det nær å ta d e hele tallene som et eksempel. Igjen blir vi bedratt av
laksov.tex,v 1.12
Normat 1/2004 D. Laksov 27
intu isjone n. Det finnes uendelig mange avstandsbegrep på de hele tallene, ett for
hvert primtall, som alle gir viktig informasjon om de hele tallene og som har store
anvendelsesområder i og u tenf or matematikken.
For å beskrive disse avstandsmålene fikserer vi et primtall p. Fra d e innledende
unive rsitetskursene vet vi at hvert helt tall n =0kan skrive entydig på formen
n = p
k
m der k er et ikkenegativt heltall, og m er heltall som ikke er delbart med
p. Vi innfører et avstandsmål på de hele tallene Z, eller e n p-adisk valuasjon som
det kalles mer teknisk, ved
|n|
p
=1/p
k
.
For eksempel, om p =3får vi |18|
3
=1/3
2
ettersom 18 = 3
2
·2, vi har |30|
3
=1/3
ettersom 30 = 3 · 10, og |20|
3
=1siden 20 = 3
0
· 20. Tallet 0 er spesielt ettersom
det deles av alle potenser av p, så vi setter |0|
p
=0. Det er en grei og illustrativ
oppgave å vise at følgende tre egenskaper holder:
1. (Ikkedegenerthet) |n|
p
=0hvis og bare hvis n =0.
2. (Multiplikativitet) |mn|
p
= |m|
p
|n|
p
.
3. (Ikke-arkimedisk trekantulikhet) |m + n|
p
max(|m|
p
, |n|
p
).
Vi merker at trekantulikheten er sterkere enn den vi brukte tidligere ettersom vi
normalt har max(|m|
p
, |n|
p
) < |m|
p
+ |n|
p
. Det er klart at vi får en metrikk d
p
på
Z ved å sette
d
p
(m, n)=|m n|
p
for alle hele tall m og n.
I analysen har vi sett hvordan vi fra de rasjonale tallene med den vanlige normen
kan konstruere de reelle tallene. Prosessen kalles komplettering og kan baseres på
Cauchyfølger. Denne konstruksjonen er tatt med i mange lærebøker. Vi minner
om at en Cauchyfølge i et metrisk rom er en følge av elementer x
1
,x
2
,... fra X
slik at for alle tall >0 finnes et heltall N slik at d(x
i
,x
j
) <når i, j N.
Grunnen til at vi oppfatter d e hele tallene som «diskrete» er at det ikke finnes
andre Cauchyfølger n
1
,n
2
,... av hele tall med den vanlige absoluttverdien enn de
der n
N
= n
N+1
= ··· for en N .
Situasjonen er helt annerledes for de hele tallene med en p-adisk valuasjon. For
eksempel vil følgen
a
1
=1,a
2
=1+p, a
3
=1+p + p
2
,a
n
=1+p + ···+ p
n
, ···
være en Cauchyfølge for den p-adiske valuasjonen. Dette er fordi når m<nvil
|a
n
a
m
|
p
= |p
m+1
+ p
m+2
+ ···+ p
n
|
p
=1/p
m+1
som raskt går mot 0 når m
vokser.
Samme konstruksjon som gir de reelle tallene R fra de rasjonale Q med abso-
luttverdien kan brukes på Z med den p-adiske valuasjonen og gir et tallområde Z
p
med en p-adisk valuasjon der alle Cauchyfølger konvergerer. Om leseren vil ha en
fullstendig analogi med konstruksjonen av R fra Q, så kan man b egynne med den p-
adiske valuasjonen på Q definert ved |m/n|
p
= |m|
p
/|n|
p
for alle heltall m og n =0,
og komplettere Q i denne valuasjonen. Vi får da en tallkropp Q
p
med en p-adisk
laksov.tex,v 1.12
28 D. Laksov Normat 1/2004
valuasjon der alle Cauchyfølger konvergerer. Vi kaller elementene i Q
p
de p-adiske
tallene. Kurt Hensel (1861–1941) utviklet i begynnelsen av nittenhundretallet en
teori for p-adiske tall og satt disse inn i en meget bred matematisk sammenheng
med f orbindelse r til analyse, algebra og geometri.
Hvert eleme nt i Z
p
kan konkret beskrives som kanoniske p-adiske uttrykk på
formen
n =(a
0
,a
1
,...)
p
=
j=0
a
j
p
j
med 0 a
j
<psom er helt analoge med desimalutviklingen av de reelle tallene.
Det er like lett å regne med p-adiske utviklinger som med desimalutviklinger, for
algoritmene for addisjon, subtraksjon, multiplikasjon og divisjon for desimalutvik-
linger kan overføres direkte til p-adiske utviklinger med ubetydelige endringer.
For å illustrere nytten av p-adiske tall skal vi vise hvordan de brukes til å løse
ligninger på formen
f(x) 0 (mod m)
for alle tall m og heltallspolynomer f(x). Slike ligninger forekommer overalt i ma-
tematikken og dens anvendelser. Vi påminner om at vi bruker Gauss’ (1777–1853)
geniale notasjon n l (mod m) for å uttrykke at m deler n l, og at e n løsning
av ligningen f (x) 0 (mod m) er et heltall n slik at f(n) er delbar med m. For
eksempel er tallene 1, 2, 3, 4, 5, 6 alle løsninger til ligningen
x
6
1 0 (mod 7).
Dette er et spesialtilfelle av Fermats lille sats som sier at for alle primtall p er
1, 2,...,p 1 løsninger til ligningen
x
p1
1 (mod p).
Av den kines iske restsatsen følger det at for å løse ligningen f(x) 0 (mod m) så
rekker det å løse ligningen
f(x) 0 (mod p
k
)
for alle primtall p og alle positive heltall k. La oss se på ligningen
x
2
2 (mod 7
k
).
Det finne s et 7-adisk tall
=(3.12612124 ···)
7
=3+7+2· 7
2
+6· 7
3
+ ···
slik at
2
=2i Z
7
. Tallet er altså en kvadratrot til 2 i Z
7
. Vi ser lett at de endelige
7-adiske utviklingene vi får ved å bryte av den uendelige 7-adiske utviklingen til
gir løsninger som kommer stadig nærmere tallet 2. Det vil si
3
2
2 (mod 7), (3 + 7)
2
2 (mod 7
2
), (3 + 7 + 2 · 7
2
)
2
2 (mod 7
3
),
(3 + 7 + 2 · 7
2
+6· 7
3
)
2
2 (mod 7
4
)
laksov.tex,v 1.12
Normat 1/2004 D. Laksov 29
og så videre. M ed andre ord, vi har
|3
2
2|
7
1/7, |(3 + 7)
2
2|
7
1/7
2
, |(3 + 7 + 2 · 7
2
)
2
2|
7
1/7
3
,
|(3 + 7 + 2 · 7
2
+6· 7
3
)
2
2|
7
1/7
4
,....
Hvis vi kjente hele den 7-adiske utviklingen til ville vi dermed ha løst alle kongru-
ensene x
2
2 (mod 7
k
), men vi kan like lite kjenne hele den 7-adiske utviklingen
til i Z
7
som vi kan kjenne hele desimalutviklingen til
2 i R.
Hensels lemm a. Det finnes et enkelt og hendig kriterium, kalt Hensels lemma, som
garanterer at ligningen e f(x) 0 (m od p
k
) har en løsning for alle k:
Anta at vi har et heltall a
0
slik at f (a
0
) 0 (mod p) og f
(a
0
) 0 (mod p). Da
finnes et entydig p-adisk tall = a
0
+a
1
p+···med 0 a
i
<pi Z
p
slik at f ()=0
i Z
p
. Ekvivalent, vil
f(a
0
+ a
1
p + ···+ a
m
p
m
) 0 (mod p
m+1
) for m =0, 1,....
Bevis. Vi bruker induksjon etter m.Form =0er lemmaet forutsetningen f(a
0
) 0
(mod p). Anta at vi har vist at den siste ligningen i lemmaet holder for m 1, det
vil si, vi har f(a
0
+ a
1
p + ···+ a
m1
p
m1
)=cp
m
og velg et vilkårlig tall a
m
som vi vil bestemme. Taylors formel, som er triviell for polynomer, sier at for alle
polynomer g(t) med heltallskoeffisienter vil
g(a + h)=g(a)+hg
(a)+h
2
e(h)
der e(t) er et polynom med heltallskoeffisienter. Bruker vi først Taylors formel på
f
(t) med a = a
0
og h = a
1
p + a
2
p
2
+ ···+ a
m
p
m
får vi
f
(a
0
+ a
1
p + ···+ a
m
p
m
) f
(a
0
) (mo d p),
og bruker vi den på f(t) med a = a
0
+ a
1
p + ···+ a
m1
p
m1
og h = a
m
p
m
får vi
f(a + a
m
p
m
) f(a)+a
m
p
m
f
(a) p
m
c + a
m
f
(a
0
)
(mod p
m+1
).
Ettersom f
(a
0
) 0 (mod p) ved antagelsen finnes det et entydig tall a
m
slik at
0 a
m
<pog c + a
m
f
(a
0
) 0 (mod p). For dette tallet vil
f(a
0
+ a
1
p + ···+ a
m
p
m
) f(a + a
m
p
m
) 0 (mod p
m+1
),
og vi har vist lemmaet.
Merk. Betingelsen f
(a
0
) 0 (mod p) må være oppfylt for at vi skal være sikre på
at Hensels lemma holder. For eksempel vil ligningen x
2
2 (mod 2
k
) ha løsningen
x =0for k =1, men ingen løsning for k =2fordi 0
2
2 2 (mod 4), 1
2
2 3
(mod 4), 2
2
=2 2 (mod 4) og 3
2
2 3 (mod 4). I dette tilfellet er den deriverte
av polynomet x
2
2 lik 2x som er identisk med null modulo 2.
Newtons metode. For å finne en løsning til kongruensene f (x) 0 (mod p
k
) for
store k er det nok å finne tilstrekkelig gode rasjonale tilnærminger a til i Q
7
.
laksov.tex,v 1.12
30 D. Laksov Normat 1/2004
Grunnen til dette er at |a|
7
er liten hvis og bare hvis differensen a er delelig
med en høy potens av 7. Vi trenger altså en effektiv metode for å finne rasjonale
tilnærminger til en løsning til likningen f(x)=x
2
2=0i Q
7
. Newtons metode
egner seg utmerket til formålet. Vi setter opp iterasjonen
a
n+1
= a
n
f(a
n
)
f
(a
n
)
=
1
2
a
n
+
2
a
n
og starter den m ed et rasjonalt tall a
1
som ligger nær i Q
7
. Vi kan for eksem-
pel velge a
1
=3, for dette viser seg å være nær nok til at Newton-iterasjonen
konvergerer til . I så fall får vi tilnærmingene
a
2
=11/6 = (3.11111111...)
7
som har to korrekte 7-adiske siffer, og
a
3
= 193/132 = (3.12603325...)
7
som har fire korrekte siffer. Akkurat som når vi bruker Newtons metode i R, kan vi
regne med en dobling av antall korrekte siffer i hvert steg hvis startpunktet er nær
nok til roten. Så dette er en svært effektiv algoritme for å løse f(x) 0 (mod p
k
)
for store k.
Det er interessant å observere at d en samme følgen a
1
=3, a
2
= 11/6, a
3
=
193/132,... av rasjonale tall konvergerer til to forskjellige kvadratrøtter til 2, den
ene i R og den and re i Q
7
. Men de to konvergensbegrepene er svært forskjellige.
Dette sees for eksempel ved at følgen divergerer i Q
5
, for kongruensen x
2
2
(mod 5) har ingen løsning, og dermed kan ikke 2 ha noen kvadratrot i Q
5
.
En «naiv» anvendelse av matematikken
Vi skal i denne seksjonen illustrere hva vi mener med banale anvendelser av ma-
tematikken. Det vil si anvendelser som bare er omformuleringer av matematiske
begrep e r i et dagligdags språk. Eksemplet er basert på e t resultat av matematike-
ren P. Hall (1904–1982) som er vakkert nok, og anvendelsen er elegant. Tolkningen
av setningen er imidlertid hårreisende, og anvendelsen har mer karakteren av lek
eller spill enn som en påtrengende praktisk oppgave. For å markere sambandet med
spill ber vi leseren tenke litt over følgende kortproblem:
Et kortproblem. Del opp en kortstokk i 13 bunter med 4 kort i hver. Vis at man
kan plukke ut 13 kort av ulike valører 1, 2, ..., 10, knekt, dronning, konge, ett fra
hver bunt.
Bemerkning. Merk først at løsningen ikke er så enkel som man først kan tro. Man
kan ikke bare trekke et ess fra en bunke som har et ess i seg, deretter en toer fra
en bunke som har en toer, og så videre. Om for eksempel den først bunken besto
av valørene 1, 3, 3, 3 og den andre av valørene 2, 3, 4, 5, og vi trekker et ess fra den
første bunken og en toer fra den andre er det klart at det er umulig å trekke en
laksov.tex,v 1.12
Normat 1/2004 D. Laksov 31
treer fra noen annen bunke ettersom alle treerne befant seg i den første og andre
bunken.
Ettersom kortproblemet er så enkelt kan vi ikke vente at det skal gi opphav til
interes sant matematikk, og det finnes selvsagt mange løsninger. Vi skal presentere
en elegant løsning som følger av følgend e vakre resultat:
Halls setning. La A
1
,A
2
,...,A
n
være mengder. Anta at unionen av hvert utvalg
av r av disse mengdene inneholder minst r elementer for alle r n. Da kan vi
finne n ulike elementer, en fra hver av de n mengdene.
Løsning av kortproblemet. For å se hvordan Halls setning løser kortproblemet til-
ordner vi til hver av de 13 buntene mengden av de 1, 2, 3 eller 4 ulike valører
som forekommer for kortene i bunten. Vi får da 13 undermengder A
1
,A
2
,...,A
13
av valørene 1, 2,...,10, knekt, dame, konge, der hver av mengdene A
1
,A
2
,...,A
13
består av 1, 2, 3 eller 4 elementer. For eksempel om buntene ser ut som
bunt 1 bunt 2 ··· bunt 12 bunt 13
51··· 45
64··· 45
7 knekt ··· 4 dame
10 knekt ··· 7 dame
så vil
A
1
= {5, 6, 7, 10},A
2
= {1, 4, knekt},A
12
= {4, 7},A
13
= {5, dame}.
I hvert utvalg A
i
1
,A
i
2
,...,A
i
k
av k mengder blant A
1
,A
2
,...,A
13
forekommer det
minst k ulike valører ettersom kortbuntene nummer i
1
,i
2
,...,i
k
tilsammen inne -
holder 4k kort. Ved Halls resultat finnes det derfor et utvalg av 13 ulike elementer,
en fra hver av mengdene A
1
, A
2
,...,A
13
. Med andre ord har vi funnet 13 ulike
valører, en fra hver av de 13 buntene.
Bemerkning. For å illustrere hvor useriøse anvendelser av matematikk kan være vil
vi nevne at Halls setning ofte kalles Halls ekteskapssetning. Dette er fordi vi kan
tolke setningen som at vi har n kvinner med hver sin liste A
1
,A
2
,...,A
n
over menn
som de kan tenke seg å gifte seg med. Om vi antar at listene til hvert utvalg av r
kvinner inneholder minst r ulike menn for r n, hvilket selvsagt er et nødvendig
krav for at det skal være mulig å finne en mann til alle, så er det mulig å gifte hver
av kvinnene med en mann på sin liste. Man skal lete lenge etter en så urealistisk
og politisk ukorrekt situasjon, og det er plagsomt at det finnes akademikere som
tar slike «anvendelser» alvorlig.
To bevis for Halls setning. For å illustrere hvor lite forkunnskaper som er nødven-
dig for å bedrive denne formen av matematikk gir vi to bevis f or Halls setning. Det
første beviset er ikke konstruktivt, det vil si, det sier at det finn es n elementer, men
ikke hvordan de kan finnes. Det andre beviset viser hvordan vi kan finne elemente-
ne. Den eneste matematikken som inngår i bevisene er induksjonsresonnementer.
Matematisk induksjon er egentlig et aksiom for de hele tallene, men vi bruker oftest
induksjon som om den er et resultat av sunn fornuft.
laksov.tex,v 1.12
32 D. Laksov Normat 1/2004
Første bevis for Halls setning. Vi viser setningen ved induksjon etter n. Setningen
holder klart for n =1. Anta nu at setningen gjelder for n =1, 2,...,k1. Vi skal
vise at den da gjelder for n = k. Beviset er delt i to tilfeller.
Tilfelle 1. Anta at for hver r<kvil unionene av hvert utvalg A
i
1
,A
i
2
,...,A
i
r
av r
mengder blant A
1
,A
2
,...,A
k
inneholder minst r+1 elementer. Da vil A
1
inneholde
minst to elementer. Velg en av disse elementene a
1
. For r<kvil da unionen av hvert
utvalg av r mengder blant A
1
,A
2
,...,A
k
inneholde minst r elementer forskjellige
fra a
1
. Det følger av induksjonsantagelsen at vi kan velge k 1 ulike elementer
forskjellige fra a
1
, en fra hver av mengdene A
2
,A
3
,...,A
k
. Disse k 1 elementene
sammen med a
1
gir k ulike elementer fra mengdene A
1
,A
2
,...,A
k
, og vi har vist
Halls setning i tilfelle 1.
Tilfelle 2. Anta at det finnes et s<kslik at det finnes et utvalg A
i
1
,A
i
2
,...,A
i
s
blant mengdene A
1
,A
2
,...,A
k
hvis union har nøyaktig s elementer. Ettersom s<k
kan vi ved induksjonsantagelsen finne s ulike elementer a
i
1
,a
i
2
,...,a
i
s
, en fra hver
av mengdene A
i
1
, A
i
2
,...,A
i
s
.
La j
1
,j
2
,...,j
ks
være de tallene blant 1, 2,...,k som er forskjellige fra tallene
i
1
,i
2
,...,i
s
. Da vil unionen av hvert utvalg av r av mengdene A
j
1
, A
j
2
,...,A
j
ks
inneholde minst r elementer forskjellige fra a
i
1
,a
i
2
,...,a
i
s
når r k s. Dette er
fordi, om det fantes et utvalg av r mengder blant A
j
1
,A
j
2
,...,A
j
k2
hvis union
inneholdt færre enn r elementer, så ville dette utvalget av r mengder sammen med
de s mengdene A
i
1
,A
i
2
,...,A
i
s
inneholde færre enn r + s elementer, hvilket er
mot forutsetningen i setningen. Av induksjonshypotesen anvendt på A
j
1
, A
j
2
,...,
A
j
ks
kan vi derfor finne k s ulike elementer forskjellige fra a
i
1
,a
i
2
,...,a
i
s
, en
fra hver av mengdene A
j
1
,A
j
2
,...,A
j
ks
. Sammen med a
i
1
,a
i
2
,...,a
i
s
gir disse
k s elementene k ulike elementer fra mengdene A
1
,A
2
,...,A
k
og vi har vist Halls
setning i tilfelle 2.
Andre bevis for Halls setning. Vi skal gi en me tode som gjør følgende operasjon på
elementer:
Om vi har funnet k ulike elementer a
i
1
,a
i
2
,...,a
i
k
, en fra hver av mengdene
A
i
1
,A
i
2
,...,A
i
k
, så kan vi fin ne en indeks i
k+1
forskjellig fra i
1
,i
2
,...,i
k
, og et
element a
i
k+1
forskjellig fra a
i
1
,a
i
2
,...,a
i
k
slik at etter en eventuell omordning
j
1
,j
2
,...,j
k+1
av i
1
,i
2
,...,i
k+1
så vil a
j
l
A
i
l
for l =1, 2,...,k+1.
Bruker vi dette for k =1, 2,...,n1 så følger Halls setning.
Ved å omnummerere mengden e A
1
,A
2
,...,A
n
kan vi selvsagt oppnå at i
1
=1,
i
2
=2,...,i
k
= k. Om det finnes et i>kog et element a
i
i A
i
forskjellig fra
a
1
,a
2
,...,a
k
, vil de k elementene a
1
,a
2
,...,a
k
,a
i
ha de egenskapene vi søker. Vi
kan derfor anta at A
i
er inneholdt i mengden B = {a
1
,a
2
,...,a
k
} for i = k +1,
k +2, ..., n. Sett (0) = k +1. Metoden består av å velge elementer a
(1)
,a
(2)
,...
etter følgende regel:
Av antagelsen i setningen finnes det minst ett element i mengden A
(0)
= A
k+1
,
og hvert element må være i B. Velg et slikt element a
(1)
. Av antagelsen finnes
det minst ett element i A
(0)
A
(1)
forskjellig fra a
(1)
. Om det er mulig, så
velg et av disse a
(2)
som ikke er i B og slutt prosessen. Om alle er i B så velg
et vilkårlig a
(2)
av disse og fortsett. Av antagelsen finnes det minst ett element
i A
(0)
A
(1)
A
(2)
som er forskjellig fra a
(1)
og a
(2)
. Om det er mulig, så
velg et av disse a
(3)
som ikke er i B og avslutt. Om ikke så velg et slikt element
a
(3)
i B og fortsett. Ettersom B er endelig og forskjellig fra A
1
A
2
···A
n
så
laksov.tex,v 1.12
Normat 1/2004 D. Laksov 33
slutter prosessen med et element a
(r)
som er inneholdt i A
(0)
A
(1)
A
(r1)
og som ikke er i B. Vi har nå ulike elementer a
(0)
,a
(1)
,...,a
(r)
der de r første
elementene er i B, der a
(r)
ikke er i B, og der a
(i)
er i A
(0)
A
(1)
···A
(i1)
for i =1, 2,...,r.
Nå endrer vi nummereringen til elementene som følger:
Velg r
1
<r
0
= r slik at a
(r)
= a
(r
0
)
er i A
(r
1
)
, deretter velger vi r
2
<r
1
slik
at a
(r
1
)
er i A
(r
2
)
, og fortsetter til vi har en 0 <r
s
slik at a
(r
s
)
er i A
(0)
=
A
k+1
. Elementene a
1
,a
2
,...,a
k
som er forskjellige fra a
(r
1
)
,a
(r
2
)
,...,a
(r)
end-
rer vi ikke numrene på. Vi har nå funnet k +1 ulike elementer, som ligger i
A
1
,A
2
,...,A
k
,A
k+1
.
Som vi har s ett følger Halls setning.
Latinske kvadrater. En noe mindre triviell anvendelse av Halls setning enn den vi
gjorde på kortproblemet er forbundet med latinske kvadrater. Et latinsk kvadrat
er et n n -ruten ett der tallene 1, 2,...,n forekommer i hver rekke og i hver søyle.
Når n =4har vi for eksempel
3 4 1 2
4 1 2 3
2 3 4 1
1 2 3 4
Det er rimelig å betrakte to latinske kvadrater som es sen sielt like om vi kan få det
ene fra det andre ved å omordne tallene 1, 2,...,n. Vi sier da at de er ekvivalente.
Blant alle ekvivalente kvadrater finnes det opplagt nøyaktig ett hvis siste rad er
1, 2,...,n.
Leonhard Euler (1707–83) initierte studiet av latinske kvadrater, og de har siden
den gang fascinert matematikere på grunn av sine spennende, og iblant mystiske
egenskap e r. Det fi nne s fremdeles mange uløste problemer om latinske kvadrater.
En snedig anvendelse av Halls setning viser at det for hvert n finnes en mengde
ikke ekvivalente latinske kvadrater. For å finne ikke ekvivalente latinske kvadrater
rekker det å begynne med tallene 1, 2,...,n på siste rad, og fortsette i nest siste
rad med en omordning av disse tallene som ikke holder noe tall fast. Det siste er
nødvendig for å kunne få et latinsk kvadrat. Vi må vise at de resterende n2 radene
kan fylles med de resterende tallene slik at vi får et latinsk kvadrat. Ettersom vi
skal vise nedenfor at antallet omordninger av tallene 1, 2,...,nsom ikke holder noe
tall fast vokser med n!/e, følger det da at det finnes en mengde ikke ekvivalente
latinske kvadrater for store n.
Vi skal vise mer enn at vi kan komplettere kvadratet til et latinsk kvadrat når
de to siste radene er gitt.
Setning. Hvis hver rad i et rutenett med m rader og n søyler der m<ninneholder
tallene 1, 2,...,n, og ingen søyle inneholder noe tall mer enn en gang, så kan
rutenettet utvides til et latinsk kvadrat av orden n.
Bevis. Det er nok å vise at vi kan utvide rutenettet med en enkelt rad. Anta at vi
har fylt m rader. La A
j
være de nm tallene som ikke forekommer i den j’te søylen.
Om vi kan finne et u tvalg a
1
,a
2
,...,a
n
av n ulike tall blant 1, 2,...,n med a
j
i A
j
laksov.tex,v 1.12
34 D. Laksov Normat 1/2004
kan vi komplettere rutene ttet med raden a
1
,a
2
,...,a
n
og dermed utvide rutenettet,
som vi ville. La A
j
1
,A
j
2
,...,A
j
r
være et utvalg av mengdene A
1
,A
2
,...,A
n
. Hvert
av tallene 1, 2,...,n fremkommer nøyaktig en gang i hver av de m radene. Derfor
forekommer hvert tall i nøyaktig n m av mengdene A
1
,A
2
,...,A
n
. Det følger
at hvert tall forekommer i høyst n m av mengdene A
j
1
,A
j
2
,...,A
j
r
. Derfor må
mengdene A
j
1
,A
j
2
,...,A
j
r
tilsammen inneholde minst r(n m)/(n m)=r tall.
Det følger derfor av Halls setning at det finnes n ulike tall a
1
,a
2
,...,a
n
, en fra
hver av mengd ene A
1
,A
2
,...,A
n
, presis som vi ønsket.
Vi skal gi to bevis for at antallet omordninger av tallene 1, 2,...,n som ikke holder
noen av disse tallene fast vokser som n!/e. Det ene bruker et viktig resultat som
kalles inklusjon/eksklusjon og det andre en snedig teknikk som kalles genereren-
de funksjoner. Begge metodene er meget brukt i mange deler av matematikken.
Metoden med genererende funksjoner gir dessuten en tiltrekkende algoritme for å
beregne antallet eksakt.
Inklusjon/eksklusjon. For hver mengde A betegner vi med |A| antallet elementer
i mengden. Videre lar vi n være et tall og betegner med J
k
de
n
k
= n!/k!(n k)!
delmengdene {j
1
,j
2
,...,j
k
} av {1, 2,...,n} med k elementer. Da vil
|A
1
A
2
···A
n
| =
n
k=1
(1)
k+1
{j
1
,j
2
,...,j
k
}J
k
|A
j
1
A
j
2
···A
j
k
|.
Bevis. For å vise formelen fikserer vi et element a som ligger i A
1
A
2
···A
n
. Dette
elementet gir et bidrag på 1 til venstre side av formelen. For å vise at det bidrar med
1 også til høyre side antar vi at a er inneholdt i mengdene A
i
1
,A
i
2
,...,A
i
l
, men
ikke i noen av de andre mengdene A
i
. Da vil a være i like mange av snittene A
j
1
A
j
2
···A
j
k
som vi kan velge ulike mengder {j
1
,j
2
,...,j
k
} blant {i
1
,i
2
,...,i
l
},
det vil si, på
l
k
måter. Derfor gir a et b idrag på
l
k=1
(1)
k+1
l
k
=
l
1
+
l
2
+ ···+(1)
l
l
l
=
(1 1)
l
1
=1
til summen til høyre. Vi har vist inklusjon/eksklusjonsformelen.
Vi bruker inklusjon/eksklusjonsformelen i tilfellet da A
i
er de omordningene av
tallene 1, 2,...,n som fikserer tallet i. Da består A
j
1
A
j
2
···A
j
k
av de (nk)!
omordningene som holder tallene j
1
,j
2
,...,j
k
fast, det vil si |A
j
1
A
j
2
···A
j
k
| =
(n k)!. Derfor vil
{j
1
,j
2
,...,j
k
}J
k
|A
j
1
A
j
2
···A
j
k
| =(n k)!
{j
1
,j
2
,...,j
k
}J
k
1=(n k)!
n
k
=
n!
k!
.
Ved inklusjon/eksklusjonsformelen får vi derfor
|A
1
A
2
···A
n
| =
n
k=1
(1)
k+1
n!
k!
= n!
1
1!
1
2!
+ ···+
(1)
n+1
n!
.
laksov.tex,v 1.12
Normat 1/2004 D. Laksov 35
Men fra analysen vet vi at e
x
=1+x/1! + x
2
/2! + ···. Setter vi x = 1 i denne
formelen for e
x
ser vi at summen 1/1! 1/2! + ···+(1)
n+1
1/n! ligger veldig nære
1 e
1
når n er stor. Derfor ligger tallet |A
1
A
2
···A
n
| nær n!(1 e
1
).
Vi er interessert i antallet omordninger av tallene 1, 2,...,n som ikke holder
noen av disse tallene fast, det vil si, vi vil vite hvor mange omordninger som ikke
er i mengden A
1
A
2
···A
n
. Det er derfor omtrent n! n!(1 e
1
)=n!/e
slike omordninger, hvilket vi ville vise.
Genererende funksjoner. Vi betegner med c
r
antallet omordninger av r elementer
som ikke holder noen av disse r elementene fast. Hver permu tasjon av de n elemen-
tene 0, 1,...,n holder nøyaktig n r elementer fast, der r kan være 0, 1,...,n. For
å finne alle omordninger av 1, 2,...,n merker vi at det finnes
n
n r
mu ligheter
for å velge de n r elementene som holdes fast. For hvert slikt valg må vi omord-
ne de r resterende elementene slik at de ikke holder noe element fast, det vil si,
de resterende elementene kan omordnes på c
r
måter. Tilsammen får vi at antallet
omordninger av 1, 2,...,n kan uttrykkes som
n!=
n
r=0
n
n r
c
r
,
eller ekvivalent
1=
n
r=0
c
r
(n r)!r!
.
Vi define rer nå en genererende funksjon
f(z)=
r=0
c
r
z
r
r!
.
Da vil
e
z
f(z)=
q=0
z
q
q!
r=0
c
r
z
r
r!
=
n=0
n
r=0
c
r
(n r)!r!
z
n
=
n=0
z
n
=
1
1 z
.
For å bestemme koeffisientene c
n
rekker det derfor å regne ut koeffisientene til z
n
på høyresiden i uttrykket
f(z)=
e
z
1 z
.
Selvsagt finne r man også lett den tilnærmede formelen for c
n
som er gitt ovenfor.
Hatteproblemet. For enda en gang å vise hvor naive forkledningene av matema-
tiske resultater i såkalt praktiske termer kan være vil vi nevne at problemet med å
finne antallet c
n
iblandt kalles hatteproblemet. Dette fordi, om n personer leverer
inn sine hatter i en garderobe og personene glemmer nummerlappene, så er c
n
/n!
sannsynligheten for at ingen får tilbake riktig hatt. Jeg tror dette viser hvor se-
riøs og nyttig den så kalte «diskrete matematikken» er. Desverre er lærebøkene på
skoler og universiteter fulle av slik svindel.
laksov.tex,v 1.12
36 D. Laksov Normat 1/2004
Appendiks A. AMS-klassifikasjonen
00 General
01 History and biography
03 Mathematical logic
05 Combinatorics
06 Order, lattices, ordered algebraic structures
08 General algebraic systems
12 Field theory and polynomials
13 Commutative rings and algebras
14 Algebraic geometry
15 Linear and multilinear algebra; matrix theory
16 Asso ciative rings and algebras
17 Nonasso ciative rings and algebras
18 Category theory, homological algebra
19 K-theory
20 Group theory and generalizations
22 Topological groups, Lie groups
26 Real functions
28 Measure and integration
30 Functions of a complex variable
31 Potential theory
32 Several complex variables and analytic spaces
33 Sp ec ial functions
34 Ordinary differential equations
35 Partial differential equations
37 Dynamical systems and ergodic theory
39 Finite differences and functional equations
40 Sequences, series, summability
41 Approximations and e xpansions
42 Fourier analysis
43 Abstract harmonic analysis
44 Integral transforms, operational calculus
45 Integral equations
46 Functional analysis
47 Ope rator theory
49 Calculus of variations and optimal control
51 Geometry
52 Convex and discrete geometry
53 Differential geometry
54 General topology
55 Algebraic topology
57 Manifolds and cell complexes
58 Global analysis, analysis on manifolds
60 Probability theory and stochastic processes
62 Statistics
65 Numerical analysis
68 Computer science
laksov.tex,v 1.12
Normat 1/2004 D. Laksov 37
70 Mechanics of particles and systems
73 Mechanics of deformable solids
76 Fluid mechanics
78 Optics, electromagnetic theory
80 Classical thermodynamics, heat transfer
81 Quantum Theory
82 Statistical mechanics, structure of matter
83 Relativity and gravitational theory
85 Astronomy and astrophysics
86 Geophysics
90 Economics, operations research , programming
91 Game theory, economics, social and behavioral sciences
92 Biology and other natural sciences
93 Systems theory; control
94 Information and communication, circuits
97 Mathematics education
Appendiks B. AMS-klassifikasjo nen av Algebraisk geometri
14–XX Algebraic geometry
14Axx Foundations
14Bxx Lo cal theory
14Cxx Cycles and subschemes
14Dxx Families, fib rations
14Exx Birational Geometry
14Fxx (Co)homology theory [See also 13Dxx]
14Gxx Arithmetic problems. Diophantine geometry [See also 11Dxx, 11Gxx]
14Hxx Curves
14Jxx Surfaces and higher-dimensional varieties
[For analytic theory, see 32Jxx]
14Kxx Abelian varieties and schemes
14Lxx Algebraic Groups [For linear algebraic groups, see 20Gxx;
for Lie algebras, se e 17B45]
14Mxx Sp ecial varieties
14Nxx Projective and enumerative geometry
14Pxx Real algebraic and real analytic geometry
14Qxx Computational aspe cts in algebraic geometry
[See also 12Y05, 13Pxx, 68W30]
14Rxx Affine Geometry
laksov.tex,v 1.12
38 D. Laksov Normat 1/2004
Appendiks C. AMS-klassifikasjonen av 14Hxx, kurver
14Hxx C urves
14H05 Algebraic functions; function fields [See also 11R58]
14H10 Families, moduli (algebraic)
14H15 Families, moduli (analytic) [See also 30F10, 32Gxx]
14H20 Singularities, local rings [See also 13Hxx, 14B05]
14H25 Arithmetic ground fields [See also 11Dxx, 11G05, 14Gxx]
14H30 Coverings, fundamental group [See also 14E20, 14F35]
14H37 Automorphisms
14H40 Jacobians, Prym varieties [See also 32G20]
14H42 Theta functions; Schottky problem [See also 14K25, 32G20]
14H45 Sp ecial curves and curves of low genus
14H50 Plane and space curves
14H51 Sp ecial divisors (gonality, Brill–Noether theory)
14H52 Elliptic curves [See also 11G05, 11G07, 14Kxx]
14H55 Riemann surfaces; Weierstrass points; gap sequences [See also 30Fxx]
14H60 Vector bundles on curves and their moduli [See also 14D20, 14F05]
14H70 Relationships with integrable systems
14H81 Relationships with physics
14H99 None of the above, but in this section
Bibliografi
[1] Ian Andersson, A first course in Combinatorial Mathematics. (Second
edition.) Clarendon Press, Oxford 2000.
[2] AMS subject classification 2000. American Mathematical Society, Providence,
RI, 2000.
[3] Simon Singh, Fermats gåta. Norstedts, Stockholm 1998.
[4] James Tanton, Solve This. The Mathematical Association of America,
Washington, DC, 2001. ISBN 0-88385-717-0.
laksov.tex,v 1.12
