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, på 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
på en plade, hvor ingen af de ni søjler må være tomme. Lad os for en forelagt
bankoplade bruge henholdsvis a, b og c som b e tegnelse for antallet af sø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 må 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 på tale, skal have 1, 2 eller 3 numre i
hver søjle. Indføres betegnelserne h
0
= 9, h
1
= h
2
= . . . = h
7
= 10 og h
8
= 11, kan
man i søjlen s
m
vælge 1, 2 og 3 numre på 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 på
den måde. Ved at tage søjlerne i betragtning efter tur og generalisere problemet til
et varierende antal numre kan man nå 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