Normat 51:1, 1001–1010 (2003) 1001
Hvor mange bankoplader er der?
Nils Andersen
Datalogisk Institut
Københavns U niversitet
Universitetsparken 1
DK–2100 København Ø
nils@diku.dk
Indledning
Banko er et umådelig populært spil i Danmark. Beregning af, hvor mange forskellige
bankoplader der kan konstrueres
1
, er en interessant anledning til at komme ind
en række grundlæggende kombinatoriske principper.
Nærmere beskrevet er spillet et lotteri, hvor deltagerne køb e r spilleplader med
fortrykte numre. Lederen af spillet udtrækker i tilfældig rækkefølge numrene, som
råbes op, og spillerne markerer de udtrukne numre deres plader. Den første,
som får en vandret række eller alle en plades numre markeret, har gevinst og råber
»banko!«.
Specifikation
I en meget udbredt version af spillet gælder om spillepladerne:
1. Der benyttes numrene fra og med 1 til og med 90.
2. En spilleplade er rektangulær, med 3 (vandrette) rækker og 9 (lodrette) jler,
og hver spilleplade rummer 15 forskellige numre. Hver plade har derfor ud over
numrene 12 blanke felter.
1
Spørgsmålet blev stillet i et brev til en af eksperterne bag den elektroniske brevkasse »Spørg
Naturvidenskaben« http://www.formidling.dk/sn/.
andersen.tex,v 1.5
1002 Nils Andersen Normat 1/2003
3. Numrene er sådan fordelt pladen, at der mindst er et tal i hver jle og
netop 5 tal i hver række.
4. Idet jlerne benævnes s
0
, s
1
, s
2
, . . . , s
7
, s
8
, skal et encifret nummer stå i s
0
og
et tocifret nummer i jlen s varende til nummerets forreste ciffer (tier-cifferet);
også nummer 90 placeres i s
8
. De tal, hver jle kan rumme, er med andre ord
s
0
: 1 til 9, s
1
: 10 til 19, s
2
: 20 til 29 og f remdele s op til s
7
: 70 til 79 og s
8
:
80 til 90.
5. I den enkelte jle placeres numrene i stigende orden læst ovenfra og ned.
Eksempel en banko-plade:
(1)
2
7
10
14
21
30
32
42
53
61
65
70
86
87
90
Opgaven er nu at bestemm e, hvor mange forskellige plader der kan konstrueres,
som opfylder kravene 1.–5. Spørgeren har en formodning om, at antallet er stort,
at hvert men nes ke jorden kunne adskillige plader at spille på, uden at der
blev brug for dubletter.
Analyse
Det er vigtigt at bemærke, at numrenes placering pladen har betydning. Ne-
denstående plade (med en anden placering af 42 og 53) er således forskellig fra
(1):
(2)
2
7
10
14
21
30
32
42
53 61
65
70
86
87
90
Grunden er naturligvis, at de to plader kan give forskellig gevinst, når der spilles
rækker, men forholdet betyder, at selv om hver plade angiver en delmængde
15 elementer fra mængden {1, 2, 3, . . . , 89, 90}, er korrespondancen mellem
delmængder og plader meget mangelfuld: den ene side betyder krav 4, at ikke alle
delmængder svarer til en bankoplade (for der skal være mindst et tal med hvert
tierciffer og jst tre tal med samme tierciffer), den anden side kan samme
delmængde svare til flere plader (som for eksempel (1) og (2), der har de samme
15 numre).
Som det ofte er tilfældet med problemer hentet fra den virkelige verden, er der
ikke nogen af kombinatorikkens skabeloner, som lige passer i det aktuelle tilfælde,
men vi kan nærme os et svar spørgsmålet ved at begynde med grove forenklinger
og gradvis inddrage flere og flere af kravene 1–5.
andersen.tex,v 1.5
Normat 1/2003 Nils Andersen 1003
Femten udvalgt blandt halvfemsindstyve
Selvom vi lige har indset, det ikke fører til det rigtige svar, kunne det måske alligevel
være interessant at overveje, hvor mange måder man kan vælge 15 forskellige
af tallene 1–90. I det mindste kan kombinatorikken her levere en færdig formel, for
det er jo den velkendte binomialkoefficient
90
15
, der kan beregnes som
90!
15! · 75!
=
90 · 89 · 88 · 87 · 86 · 85 · 84 · 83 · 82 · 81 · 80 · 79 · 78 · 77 · 76
15 · 14 · 13 · 12 · 11 · 10 · 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1
og har værdien 45795 673964 460816, altså m ere en d 45 b illiarder.
Signatur
Lad os et øjeblik se bort fra kravet om, at der netop skal være fem numre i hver
række, og blot overveje, hvilke begrænsninger der ligger i at placere femten numre
en plade, hvor ingen af de ni jler være tomme. Lad os for en forelagt
bankoplade bruge henholdsvis a, b og c som b e tegnelse for antallet af jler med
netop 1 talplads (2 blanke felter), 2 talpladser (1 blankt felt) og 3 talpladser (ingen
blanke felter), og lad os kalde triplet (a, b, c) for pladens signatur.
Signaturen for (1) er for eksempel (4, 4, 1).
Det oprindelige krav 2 betyder, at signaturer opfylde
a + 2b + 3c = 15,
a + b + c = 9.
Ved subtraktion fås b + 2c = 6, og da antallene skal være ikke-negative heltal,
bliver der kun fire muligheder: c = 0, 1, 2 eller 3. Ved indsættelse findes fire mulige
signaturer (a, b, c) = (3, 6, 0), (4, 4, 1), (5, 2, 2) eller (6, 0, 3). Det er let at se, at der
faktisk også findes bankoplader med hver af de fire signaturer.
Mulige nummermængder
De delmængder af 15 numre, som kan komme tale, skal have 1, 2 eller 3 numre i
hver jle. Indføres betegnelserne h
0
= 9, h
1
= h
2
= . . . = h
7
= 10 og h
8
= 11, kan
man i jlen s
m
vælge 1, 2 og 3 numre henholdsvis
h
m
1
,
h
m
2
og
h
m
3
måder.
Det kunne være interessant at vide, hvor mange delmængder der fremkommer
den måde. Ved at tage jlerne i betragtning efter tur og generalisere problemet til
et varierende antal numre kan man frem til en rekursionsformel for antallet af
delmængder.
Lad d
m;n
betegne antallet af delmængder med n numre, som har mellem 1 og 3
numre med fra hvert af de m første af de intervaller, der er beskrevet i krav 4 i den
indledende specifikation.
andersen.tex,v 1.5
1004 Nils Andersen Normat 1/2003
Da gælder
(3) d
m;n
=
0 med mindre m n 3m,
1 hvis m = n = 0,
h
m1
1
d
m1;n1
+
h
m1
2
d
m1;n2
+
h
m1
3
d
m1;n3
for 1 m 9.
Antallet d
9;15
af mulige nummermængder en bankoplade beregnes heraf til
6080 082602 343750, det er kun cirka 13% af alle delmængder med 15 numre,
som faktisk kan forekomme en plade.
Dynamisk programmering
Rekursionsligningerne (3) har en form, de direkte lader sig indtaste i et compu-
terprogram, men gør man bare det uden videre, vil programmet be regne de samme
værdier flere gange. Grunden hertil er illustreret i figur 1, der viser de indbyrdes
afhængigheder af de 46 værdier d
m;n
6= 0, som skal bruges und er beregning af d
9;15
i henhold til (3).
d
7;10
ville for eksem pel blive beregnet to gange, da den både skal bruges i ud-
trykket for d
6;12
og for d
6;13
, og i almindelighed ville d
m;n
blive beregnet lige
mange gange som antallet af stier, der i grafen figur 1 forbinder knuden d
m;n
med roden d
9;15
; specielt ville d
0;0
blive beregnet 1554 gange.
For at undgå dette ressourcespild kan man sideløbende med beregningerne ajour-
føre en tabel over tidligere beregnede par af argument og funktionsværdi. En me-
tode, som den måde ud over de rent funktionelle sammenhænge også benytter
en løbende tilstand, siges at bruge dynamisk programmering et nyttigt princip,
der ofte anvendes i operationsanalyse.
2
Frembringerfunktion
Mange kombinatoriske problemer er knyttet til en talfølge (a
n
)
n=0,1,...
; vi kan her
specielt forstå »problem« som »udvalgte kombinationer af elementer«, og a
n
er da
antallet af den slags kombinationer med netop n elementer.
Hvis A og B er to sådanne problemer, knyttet til henholdsvis (a
n
)
n=0,1,...
og
(b
n
)
n=0,1,...
, og man forbinder A og B til et nyt problem C ved, at en C-kombination
skal være foreningen af en A- og en B-kombination, knyttes det nye problem til en
talfølge (c
n
)
n=0,1,...
, hvor
(4) c
n
=
n
X
i=0
a
i
b
ni
.
2
Tak til den anonyme referent for forslaget om at inddrage rekursionsligninger og dynamisk
programmering.
andersen.tex,v 1.5
Normat 1/2003 Nils Andersen 1005
d
0;0
d
1;1
d
1;2
d
1;3
d
2;2
d
2;3
d
2;4
d
2;5
d
2;6
d
3;3
d
3;4
d
3;5
d
3;6
d
3;7
d
3;8
d
3;9
d
4;4
d
4;5
d
4;6
d
4;7
d
4;8
d
4;9
d
4;10
d
5;5
d
5;6
d
5;7
d
5;8
d
5;9
d
5;10
d
5;11
d
6;6
d
6;7
d
6;8
d
6;9
d
6;10
d
6;11
d
6;12
d
7;9
d
7;10
d
7;11
d
7;12
d
7;13
d
8;12
d
8;13
d
8;14
d
9;15
6
6 6 6
6 6 6 6 6
6 6 6 6 6 6 6
6 6 6 6 6 6 6
6 6 6 6 6 6 6
6 6 6 6 6
6 6 6
6
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
:
Figur 1 : Sammenhænge ved beregning af d
9;15
i henhold til (3).
Udtrykket for c
n
er netop koefficienten til x
n
i potensrækkeproduktet
P
i=0
a
i
x
i
·
P
j=0
b
j
x
j
. Hvis man derfor til et kombinatorisk problem A med tilknyttet talfølge
(a
0
, a
1
, a
2
, a
3
, . . .) danner
3
dets såkaldte frembringerfunktion, som er den formelle
potensrække a
0
+ a
1
x + a
2
x
2
+ a
3
x
3
+ · · · , vil multiplikation af frembringerfunk-
tionerne svare til den beskrevne forbindelse af de tilsvarende problemer.
Rekursionsligningen (3) har netop formen (4). Frembringerfunktionen for valg
af nu mre fra jle s
g
er
h
g
1
x+
h
g
2
x
2
+
h
g
3
x
3
, og for numre i de første m jler
3
Med x forstået som talfølgen (0, 1, 0, 0, . . .) og passende definition af addition og multiplikation
af talfølger kan potensrækken identificeres med talfølgen.
andersen.tex,v 1.5
1006 Nils Andersen Normat 1/2003
bliver
3m
X
n=m
d
m;n
x
n
=
m1
Y
g =0
h
g
1
x +
h
g
2
x
2
+
h
g
3
x
3
.
Vi søger d
9;15
i hele pladens frembringerfunktion
27
X
n=9
d
9;n
x
n
=
9
1
x +
9
2
x
2
+
9
3
x
3
·
·
10
1
x +
10
2
x
2
+
10
3
x
3
7
·
11
1
x +
11
2
x
2
+
11
3
x
3
Til computere findes færdige programsystemer, som kan regne formelt med po-
lynomier. Med lidt omhu er det dog ikke umuligt at foretage beregningerne uden
computer. Udtrykket har værdien (9x + 36x
2
+ 84x
3
)(10x + 45x
2
+ 120x
3
)
7
(11x +
55x
2
+ 165x
3
) = 3x · (5x)
7
·
11
x(3 + 12x + 28x
2
)(2 + 9x + 24x
2
)
7
(1 + 5x + 15x
2
), og
koefficienten til x
15
er beregnet i tabel 1, hvor f
n
er koefficienterne defineret ved
(3+12x+28 x
2
)(1+5x+15 x
2
) =
P
4
n=0
f
n
x
n
. Her benyttes også multinomialformlen
(x
1
+ x
2
+ . . . + x
k
)
n
=
X
n
1
+n
2
+...+n
k
=n
n
n
1
n
2
. . . n
k
x
n
1
1
x
n
2
2
· · · x
n
k
k
.
Værdien af multinomialkoefficienterne udregnes af
n
n
1
n
2
. . . n
k
=
n!
n
1
!n
2
! · · · n
k
!
.
Vi genfinder værdien beregnet ved dynamisk programmering.
koefficient f
n
p q r f
n
· 2
p
9
q
24
r
7
p q r
f
0
= 3 · 1 1 6 0 22 320522
2 4 1 198 404640
3 2 2 235 146240
4 0 3 23 224320
f
1
= 12 · 1 + 3 · 5 2 5 0 133 923132
3 3 1 529 079040
4 1 2 235 146240
f
2
= 28 · 1 + 12 · 5 + 3 · 15 3 4 0 244 331640
4 2 1 434 367360
5 0 2 51 480576
f
3
= 28 · 5 + 12 · 15 4 3 0 130 636800
5 1 1 92 897280
f
4
= 28 · 15 5 2 0 22 861440
6 0 1 4 515840
2358 335070
· 3 · 5
7
· 11 = 6080 082602 343750
Tabel 1 : Antallet af delmængder m ed 15 numre, der er mulige en bankoplade.
andersen.tex,v 1.5
Normat 1/2003 Nils Andersen 1007
Belægninger
En bankoplade kan ikke entydigt fastlægges ud fra sine 15 numre, me n det er klart,
at hvis man tillige b estemm er, hvor de blanke felter skal være, be tyder krav 5,
at numrene kun kan fyldes i én måde. Det kunne derfor være nyttigt at se
fordelingen af de blanke felter og udfyldningen med numre hver for sig.
Lad os kalde en plade, hvor det er besluttet, hvor der skal være numre, og
hvor der skal være blanke felter, men hvor der endnu ikke er fyldt numre i, for en
belægning. Her er for eksempel belægningen svarende til (1):
(5)
Selv om dette heller ikke besvarer vores hovedopgave, kunne man spørge, hvor
mange forskellige belægninger der egentlig findes?
Også her kan man skaffe sig en rekursionsformel ved at tage jlerne i betragtning
efter tur, men da vi skal frem til netop fem numre i hver række, er de t nødvendigt
at holde styr rækkerne hver for sig.
Lad b
m;i,j,k
betegne antallet af belægninger af en (3 × m)-matrix, hvor der er
henholdsvis i, j og k nummerfelter i hver af d e tre rækker og mindst et nummerfelt
i hver jle. Da gælder
b
m;i,j,k
=
0 med mindre 0 i, j, k m i + j + k,
1 hvis m = i = j = k = 0,
b
m1;i1,j,k
+ b
m1;i,j1,k
+ b
m1;i,j,k1
+ b
m1;i1,j1,k
+ b
m1;i1,j,k1
+ b
m1;i,j1,k1
+ b
m1;i1,j1,k1
for 1 m.
Den søgte værdi b
9;5,5,5
kan nu let beregnes ved dynamisk programmering, men
frembringerfunktioner (som nu generaliseres til flere variable) er et elegant alter-
nativ. Et enkelt felt pladen kan enten lades blankt eller vælges som nummerfelt
og har frembringerfunktionen 1 + x; de tre felter i en jle ville h ave frembrin-
gerfunktionen (1+x)
3
, hvis man kunne vælge frit, men da jlen ikke lades helt
blank, skal vi her bruge (1+x)
3
1. Da vi tillige ønsker at holde styr de tre ræk-
ker hver for sig, kan vi bruge henholdsvis x, y og z og lade frembringerfunktionen
for en jle være
(1 + x)(1 + y )(1 + z) 1 = x + y + z + xy + xz + yz + xyz.
Leddene s varer oplagt måde til de syv muligheder for en jle: y betyder kun et
nummer i midterste række, xz to numre, hvor det ene står i øverste og det andet i
nederste række, og videre.
Frembringerfunktionen for en plade med m jler bliver
X
i,j,k=0,...,m
b
m;i,j,k
x
i
y
j
z
k
=
(1 + x)(1 + y )(1 + z) 1
m
.
andersen.tex,v 1.5
1008 Nils Andersen Normat 1/2003
Koefficienten b
9;5,5,5
er det efterspurgte antal lovlige belægninger. Ved at bruge
binomialformlen et par gange finder man denne koefficient til
4
X
i=0
(1)
i
9
i

9 i
5
3
=
9
0
·
9
5
3
9
1
·
8
5
3
+
9
2
·
7
5
3
9
3
·
6
5
3
+
9
4
·
5
5
3
= 735210.
Samme formel kunne man i øvrigt være nået frem til ved at benytte princippet
med »at medregne og udelukke«, som kan findes beskrevet i enhver lærebog i
kombinatorik.
Bankoplader
For en given belægning er det let at beregne antallet af måder, hvorpå den kan
udfyldes til en bankoplade. Antallet af plader med belægningen (5) er for eksempel
9
2

10
1
4
10
2
3
10
3
0
11
3
= 36 · 10
4
· 45
3
· 120
0
· 165 = 5 412825 000000
og (1) er altså en af disse mange muligheder.
På samme måde kunne man i princippet de øvrige 735209 belægninger igen-
nem og finde antallet af plader for hver af dem men i praksis er det naturligvis
uoverkommeligt.
Man kunne godt komme igennem ved at gruppere belægningerne i ækvivalens-
klasser med samme antal udfyldninger. Man kunne for eksempel regne to belægnin-
ger for ækvivalente, hvis den ene kunne føres over i den anden ved en permutation
af rækkerne og af de midterste jler s
1
til s
7
, men der ville blive 146 forskellige
klasser, og beregningerne ville blive lidt omstændelige.
Det er smartere endnu en gang at benytte frembringerfunktioner eller rekur-
sionsligninger. Lad a
m;i,j,k
være antallet af (3 × m)-matricer, hvis jler er udfyldt
i overensstemmelse med krav 4 i den indledende specifikation, og hvor der er hen-
holdsvis i, j og k numre i hver af de tre rækker.
Frembringerfunktionen for sådanne (3 × 9)-matricer bliver
X
i,j,k=0,...,9
a
9;i,j,k
x
i
y
j
z
k
=
9
1
(x + y + z ) +
9
2
(xy + xz + yz) +
9
3
xyz
·
10
1
(x + y + z ) +
10
2
(xy + xz + yz) +
10
3
xyz
7
·
11
1
(x + y + z ) +
11
2
(xy + xz + yz) +
11
3
xyz
,
og det søgte antal lovlige bankoplader er koefficienten a
9;5,5,5
i dette udtryk.
andersen.tex,v 1.5
Normat 1/2003 Nils Andersen 1009
signatur
a, b, c
koefficient
til x
5
y
5
z
5
i u
a
v
b
w
c
faktor
f p q r f · 2
p
9
q
24
r
7
p q r
(3, 6, 0) 1710 12 · 5 3 4 0 110 224800
12 · 1 + 3 · 5 2 5 0 133 923132
3 · 1 1 6 0 22 320522
266 468454
· 1710 = 455661 056340
(4, 4, 1) 639 28 · 5 + 12 · 15 4 3 0 130 636800
28 · 1 + 3 · 15 3 4 0 134 106840
12 · 5 4 2 1 195 955200
12 · 1 + 3 · 5 3 3 1 529 079040
3 · 1 2 4 1 198 404640
1188 182520
· 639 = 759248 630280
(5, 2, 2) 240 28 · 15 5 2 0 22 861440
28 · 5 + 12 · 15 5 1 1 92 897280
28 · 1 + 3 · 15 4 2 1 238 412160
12 · 5 5 0 2 23 224320
12 · 1 + 3 · 5 4 1 2 235 146240
3 · 1 3 2 2 235 146240
847 687680
· 240 = 203445 043200
(6, 0, 3) 90 28 · 15 6 0 1 4 515840
28 · 1 + 3 · 15 5 0 2 28 256256
3 · 1 4 0 3 23 224320
55 996416
· 90 = 5039 677440
1 423394 407260
· 3 · 5
7
· 11 = 3 669688 706217 187500
Tabel 2 : Antallet af lovlige bankoplader.
Med et programsystem til symbolsk regning aflæses denne koefficient til tallet
3 669688 706217 187500; tabel 2 viser, hvordan man med lidt tålmodighed også kan
finde værdien uden brug af EDB. Lad os indføre betegnelserne u, v og w for
4
u = x + y + z, v = xy + xz + yz og w = xyz. En fuldstændig beregning af
3 · 5
7
· 11(3u + 12v + 28w)(2u + 9v + 24w)
7
(u + 5v + 15w) er ikke nødvendig, for kun
produkter af formen u
a
v
b
w
c
, hvor (a, b, c) er en af de re signaturer, kan indeholde
led af formen x
5
y
5
z
5
.
4
Disse udtryk kaldes de tre første elementarsymmetriske polynomier
andersen.tex,v 1.5
1010 Nils Andersen Normat 1/2003
Rekursionsformel
De tilsvarende rekursionsligninger er
a
m;i,j,k
=
0 med mindre 0 i, j, k m i + j + k,
1 hvis m = i = j = k = 0,
h
m1
1
(a
m1;i1,j,k
+ a
m1;i,j1,k
+ a
m1;i,j,k1
)
+
h
m1
2
(a
m1;i1,j1,k
+ a
m1;i1,j,k1
+ a
m1;i,j1,k1
)
+
h
m1
3
a
m1;i1,j1,k1
for 1 m 9.
Beregnes a
9;5,5,5
efter disse ligninger, fører det undervejs til 372 forskellige argu-
mentsæt (m; i, j, k), hvor a
m;i,j,k
6= 0. Ved udnyttelse af symmetrien i problemet
kan dette tal nedbringes væsentligt: Hvis (i
0
, j
0
, k
0
) er en permutation af (i, j, k),
a
m;i
0
,j
0
,k
0
= a
m;i,j,k
; det er derfor tilstrækkeligt at bes temme a
m;i,j,k
for i j k.
Bemærk, at selv om i j k, behøver der ikke at gælde i j k 1,
rekursionen omformuleres.
Lad {i, j, k} betegne multimængden bestående af disse tre elementer, det vil sige:
Rækkefølge er uden betydning, men forekomster regnes me d multiplicitet. For i = 1
og j = k = 2 har vi for eksempel {i, j, k 1} = {1, 2, 2 1} = {1, 2, 1} = {1, 1, 2},
hvilket ikke er samme multimængde som {i, j, k} = {1, 2, 2}.
For de nye størrelser a
0
m;{i,j,k}
er rekursionsformlen
a
0
m;{i,j,k}
=
0 med mindre 0 i, j, k m i + j + k
1 hvis m = i = j = k = 0
h
m1
1
(a
0
m1;{i1,j,k}
+ a
0
m1;{i,j1,k}
+ a
0
m1;{i,j,k1}
)
+
h
m1
2
(a
0
m1;{i1,j1,k}
+ a
0
m1;{i1,j,k1}
+ a
0
m1;{i,j1,k1}
)
+
h
m1
3
a
0
m1;{i1,j1,k1}
for 1 m 9
Her fører udregning af a
0
9;{5,5,5}
kun igennem i alt 108 forskellige a
0
m;{i,j,k}
6= 0.
Beregning (efter princippet for dynamisk programmering) lader sig eventuelt gen-
nemføre med papir og blyant. Man genfinder resultatet
a
0
9;{5,5,5}
= 3 669688 706217 187500
At f ærre end hve r syvende delmængde med 15 elementer kunne bruges, opvejes
altså langt af, at hver af de delmængder, som kan forekomme, i gennemsnit kan
udformes til en bankoplade mere end 600 måder. Med mellem 6 og 7 milliarder
mennesker p å jorden kan der blive flere end 500 millioner plader til hver, selv om
de alle skal være forskellige.
andersen.tex,v 1.5