matematikk.net

La $a+b+c+d+e=19$.

a) Hvor mange positive heltallige løsninger fins?

b) Hvor mange ikkenegative heltallige løsninger fins?

c) Hvor mange ikkenegative heltallige løsninger fins dersom $a\leq 4$

b)
[tex]\binom{19+5-1}{5-1}=\binom{23}{4}=8855\,\,[/tex]

ulike løsninger

$B)$
Enig med janhaa her. En kjent måte å løse heltallslikninger som denne på er ved stars and bars-teknikken. Vi ser for oss at vi splitter opp $19$ i $19$ enere. La $*$ betegne $1$. Vi skriver $19$ som $\{*******************\}$. Vi har fem heltall $a,b,c,d,e$. Vi ønsker altså å splitte opp mengden av enere mellom disse. For å splitte opp mengden i fem forskjellige seksjoner, trenger vi fire "vegger". Vi lar $\mid$ betegne en slik vegg. Vi kan for eksempel skrive opp $19$ som $\{***\mid *******\mid ****\mid ***\mid **\}$. Vi ser at i dette tilfellet hadde vi hatt $a=3, b=7,c=4,d=3,e=2$, som hadde vært en gyldig løsning. Ved å tenke på løsningene som stjerner og skillevegger mellom disse ser vi at problemet kan oversettes til: på hvor mange måter kan vi plassere $19$ stjerner og $4$ skillevegger på $23$ forskjellige plasser. Dette er igjen det samme som å spørre om hvor mange forskjellige plasseringer de $4$ barene kan ha blant $23$ forskjellige plasser. Vi fyller inn da stjernene etterpå. Dette er akkurat det vi kan regner ut med binomialkoeffisienten; hvor mange måter kan vi velge $k$ elementer fra en mengde med $n$ elementer. Altså må det være $\binom{23}{4} = 8855$ antall muligheter.

$A)$
Vi bruker stars and bars her og. Siden $a,b,c,d,e \geq 1$, kan vi vel heller tenke at $a,b,c,d,e = 1$ fra før av og at vi kun adderer oppå dette. Eventuelt kan vi tenke at vi evaluerer likningen $a+b+c+d+e=14$. Vi har fortsatt $4$ vegger, men nå $14$ stjerner å velge mellom. Det gir $\binom{14+4}{4} = \binom{18}{4} = 3060$ antall muligheter.

$C)$
Her blir det også stars and bars gitt, men med en liten modifikasjon.
Vi vet fra før av at det finnes $8855$ ikke-negative heltallige løsninger, hvis vi ser bort ifra den øvre grensen på $a$. Vi kan skrive "ulovlige" løsninger av $a$ som $5 + x$ der $x \geq 0$. Da har vi følgende likning:
$(x+5)+b+c+d+e=19$
$x+5+b+c+d+e=19$
$x+b+c+d+e=14$
Antall mulige kombinasjoner på denne regnet vi ut i $A)$, det er jo $3060$ antall mulige løsninger. Alle disse er ulovlige da $a>4$ i alle disse løsningene da vi satte $a=5+x$. Antall lovlige kombinasjoner må da være $\binom{23}{4} - \binom{18}{4} = 8855 - 3060 = 5795$ antall mulige løsninger.

Flott, Stars-and-bars (også kjent som ball-and-urn) er en veldig kul og nyttig kombinatorisk teknikk!