77 Líkindafræði

7.3 Samantektir

Einstaklingur heldur á fimm spilum. Hönd annars leikmanns sést við hlið stafla af spilapeningum. — **Mynd 7.8.** Samantektir hjálpa okkur að telja til dæmis mögulegar spilshendur þegar röð spilanna sem voru dregin skiptir ekki máli. (mynd: „IMG_3177“ eftir Zanaca/Flickr, CC BY 2.0)

Námsmarkmið

Eftir þennan hluta áttu að geta:

greint á milli þess hvenær nota á umraðanir og samantektir.
reiknað samantektir.
beitt samantektum við lausn hagnýtra verkefna.

Í hlutanum Umraðanir lærðum við að telja raðaðar runur af gefinni lengd úr safni hluta. Röðin skiptir máli: lokaröð kapphlaups og skipun í embætti félags eru dæmi um það. Í öðrum aðstæðum skiptir röðin ekki máli. Í flestum spilaleikjum er til dæmis sama í hvaða röð spilin á hendi bárust og leikmenn endurraða þeim oft til hægðarauka.

Samantektir: þegar röðin skiptir ekki máli

Þegar röð lista af hlutum skiptir ekki máli er listinn ekki umröðun heldur samantekt.

Dæmi 7.8

Aðgreining umröðunar og samantektar

Ákvarðaðu í hverju eftirfarandi tilviki hvort valið hlutmengi er umröðun eða samantekt.

Félag velur þrjá félaga í nefnd og allir bera jafna ábyrgð.
Þú þarft að endurstilla lykilorð tölvupósts og velur tíu tákna lykilorð án endurtekninga.
Dómari á hundasýningu velur fyrsta, annað og þriðja sæti úr sextán hundum.
Tilboð dagsins á veitingastað fylgir vali á þremur meðlætum af sex.

Lausn

Enginn munur er á ábyrgð nefndarmannanna þriggja og röðin skiptir því ekki máli. Þetta er samantekt.
Röð tákna í lykilorði skiptir máli og þetta er því umröðun.
Lokaröðin á hundasýningunni skiptir máli og þetta er því umröðun.
Diskur með kartöflumús, baunum og spergilkáli er í reynd sá sami og diskur með baunum, spergilkáli og kartöflumús. Þetta er því samantekt.

Samantektir taldar

Umraðanir og samantektir tengjast því að í báðum tilvikum er hlutmengi valið úr stærra safni. Skoðum tengslin svo nýta megi þekkingu á umröðunum við talningu samantekta. Á hve marga vegu má velja þrjá bókstafi úr A, B, C, D og E? Ef röðin skiptir máli er fjöldinn $_{5} P_{3} = 60$ . Talan er nógu lág til að skrá alla möguleikana í töfluna.

$A B C$	$A B D$	$A B E$	$A C B$	$A C D$	$A C E$
$A D B$	$A D C$	$A D E$	$A E B$	$A E C$	$A E D$
$B A C$	$B A D$	$B A E$	$B C A$	$B C D$	$B C E$
$B D A$	$B D C$	$B D E$	$B E A$	$B E C$	$B E D$
$C A B$	$C A D$	$C A E$	$C B A$	$C B D$	$C B E$
$C D A$	$C D B$	CDE	$C E A$	$C E B$	CED
$D C A$	$D A C$	$D A E$	$D B A$	$D B C$	$D B E$
$D C A$	$D C B$	DCE	$D E A$	$D E B$	DEC
$E A B$	$E A C$	$E A D$	$E B A$	$E B C$	$E B D$
$E C A$	$E C B$	ECD	$E D A$	$E D B$	EDC

Litamerkjum nú listann þannig að raðanir sömu þriggja bókstafanna fái sama lit, eins og á mynd 7.9.

Tafla mögulegra samantekta með tíu röðum og sex dálkum. Fyrsta röð: ABC, ABD, ABE, ACB, ACD, ACE. Önnur: ADB, ADC, ADE, AEB, AEC, AED. Þriðja: BAC, BAD, BAE, BCA, BCD, BCE. Fjórða: BDA, BDC, BDE, BEA, BEC, BED. Fimmta: CAB, CAD, CAE, CBA, CBD, CBE. Sjötta: CDA, CDB, CDE, CEA, CEB, CED. Sjöunda: DAB, DAC, DAE, DBA, DBC, DBE. Áttunda: DCA, DCB, DCE, DEA, DEB, DEC. Níunda: EAB, EAC, EAD, EBA, EBC, EBD. Tíunda: ECA, ECB, ECD, EDA, EDB, EDC. Sex umraðanir hvers sama þriggja bókstafa hóps hafa sama lit.

Eftir litamerkinguna sjást 60 reitir sem tíu sex reita hópar. Það er engin tilviljun. Við þekkjum formúluna fyrir fjölda umraðana en teljum samantektirnar nú á annan hátt með margföldunarlögmálinu í tveimur skrefum:

Skref 1: Veldu þrjá bókstafi án tillits til röðar.

Skref 2: Raðaðu bókstöfunum.

Fjöldi leiða til að velja þrjá bókstafi úr A, B, C, D og E er samantektafjöldinn sem við leitum að. Táknum hann $_{5} C_{3}$ , lesið „fjöldi samantekta fimm hluta þegar þrír eru teknir í senn“. Taflan sýnir að hann er tíu, fjöldi litanna. Almennt er fjöldi umröðunarleiða $n$ hluta þegar $r$ hlutir eru teknir í senn $_{n} P_{r} = \frac{n!}{(n - r)!}$ . Hann jafngildir einnig $_{n} C_{r} \times r!$ , svo $\frac{n!}{(n - r)!} =_{n} C_{r} \times r!$ . Deiling beggja hliða með $r!$ gefur formúluna hér fyrir neðan.

Dæmi 7.9

Beiting samantektaformúlunnar

Reiknaðu eftirfarandi:

8⁢𝐶3 $_{8} C_{3}$
12⁢𝐶5 $_{12} C_{5}$
15⁢𝐶9 $_{15} C_{9}$

Lausn

8⁢𝐶3=8!3!(8−3)!=8 $\times ⁠$ 7 $\times ⁠$ 𝟔 $\times ⁠$ 𝟓!𝟑 $\times ⁠$ 𝟐 $\times ⁠$ 𝟏 $\times ⁠$ 𝟓!=8 $\times ⁠$ 7=56 $_{8} C_{3} = \frac{8!}{3! (8 - 3)!} = \frac{8 \times 7 \times 6 \times 5!}{3 \times 2 \times 1 \times 5!} = 8 \times 7 = 56$
12⁢𝐶5=12!5!(12−5)!=𝟏𝟐 $\times ⁠$ 11 $\times ⁠$ 𝟏𝟎 $\times ⁠$ 9 $\times ⁠$ 8 $\times ⁠$ 𝟕!𝟓 $\times ⁠$ 𝟒 $\times ⁠$ 𝟑 $\times ⁠$ 𝟐 $\times ⁠$ 𝟏 $\times ⁠$ 𝟕!=11 $\times ⁠$ 9 $\times ⁠$ 8=792 $_{12} C_{5} = \frac{12!}{5! (12 - 5)!} = \frac{12 \times 11 \times 10 \times 9 \times 8 \times 7!}{5 \times 4 \times 3 \times 2 \times 1 \times 7!} = 11 \times 9 \times 8 = 792$
15⁢𝐶9=15!9!(15−9)!=𝟏𝟓 $\times ⁠$ 14 $\times ⁠$ 13 $\times ⁠$ 𝟏𝟐 $\times ⁠$ 11 $\times ⁠$ 10 $\times ⁠$ 𝟗!𝟗! $\times ⁠$ 𝟔 $\times ⁠$ 𝟓 $\times ⁠$ 4 $\times ⁠$ 𝟑 $\times ⁠$ 𝟐 $\times ⁠$ 1=14 $\times ⁠$ 13 $\times ⁠$ 11 $\times ⁠$ 104=5,005 $_{15} C_{9} = \frac{15!}{9! (15 - 9)!} = \frac{15 \times 14 \times 13 \times 12 \times 11 \times 10 \times 9!}{9! \times 6 \times 5 \times 4 \times 3 \times 2 \times 1} = \frac{14 \times 13 \times 11 \times 10}{4} = 5,005$

Dæmi 7.10

Samantektaformúlunni beitt í verkefnum

Í Texas Hold’em, afbrigði af póker, fá leikmenn tvö spil úr venjulegum stokki. Hve margar ólíkar hendur eru mögulegar?
Borðspilið Clue notar 21 spil. Ef þrír spila fær hver sex spil á hönd. Hve margar ólíkar Clue-hendur með sex spilum eru mögulegar?
Palmetto Cash 5 er leikur á vegum happdrættis menntamála í Suður-Karólínu. Leikmenn velja fimm heilar tölur frá 1 til og með 38 og vinna 100.000 dollara aðalvinning ef slembibúnaðurinn velur þær í hvaða röð sem er. Hve mörg ólík mengi vinningsnúmera eru möguleg?

Lausn

Venjulegur stokkur hefur 52 spil og höndin tvö. Röðin skiptir ekki máli og því notum við samantektaformúluna:
$_{52} C_{2} = \frac{52!}{2! (52 - 2)!} = \frac{52 \times 51 \times 50!}{2 \times 1 \times 50!} = \frac{52 \times 51}{2} = 1,326 .$
Röðin skiptir aftur ekki máli og fjöldi samantekta er:
$_{21} C_{6} = \frac{21!}{6! (21 - 6)!} = \frac{21 \times 20 \times 19 \times 18 \times 17 \times 16 \times 15!}{6 \times 5 \times 4 \times 3 \times 2 \times 1 \times 15!} = \frac{21 \times 19 \times 17 \times 16}{2} = 54,264 .$
Velja þarf fimm af 38 tölum. Röðin skiptir ekki máli og fjöldi samantekta er:
$_{38} C_{5} = \frac{38!}{5! (38 - 5)!} = \frac{38 \times 37 \times 36 \times 35 \times 34 \times 33!}{5 \times 4 \times 3 \times 2 \times 1 \times 33!} = 501,492 .$

Stærðfræðingar

Stærðfræðingar Austurlanda til forna

Samantektir voru lítið rannsakaðar í Evrópu fyrr en um 13. öld, en stærðfræðingar í Mið- og Austurlöndum fjær höfðu þá unnið með þær í margar aldir. Indverski stærðfræðingurinn Pingala lýsti þeim eigi síðar en á 2. öld f.Kr.; Varāhamihira á 6. öld og Halayudha á 10. öld þróuðu verk hans áfram. Á 9. öld setti jainíski stærðfræðingurinn Mahāvīra fram samantektaformúluna sem við notum enn.

Á 10. öld þekkti Al-Karaji í Bagdad einnig formúlur fyrir samantektir. Verk hans er glatað en persneski stærðfræðingurinn Omar Khayyam þekkti það og endurtók niðurstöðurnar í varðveittum skrifum. Khayyam er líklega þekktastur sem skáld fyrir Rubaiyat-ljóðin.

Á 11. öld vann Jia Xian í Kína einnig með samantektir og síðar Yang Hui á 13. öld.

Ekki er vitað hvort uppgötvanir þessara manna bárust milli svæða eða hvort indverskir, persneskir og kínverskir stærðfræðingar komust sjálfstætt að þeim. Stærðfræðiþekking og jafnvel textar bárust þó eftir verslunarleiðum og því er ekki hægt að útiloka miðlun.

Dæmi 7.11

Samantektum beitt með margföldunarlögmálinu

Í stúdentaráði háskóla eru tíu nemendur á fjórða ári, átta á þriðja, sex á öðru og fjórir á fyrsta.

Á hve marga vegu má velja átta manna nefnd úr hópnum?
Á hve marga vegu má velja átta manna nefnd ef tveir þurfa að koma úr hverjum árgangi?

Lausn

Velja þarf átta af 28 og fjöldi nefnda er því $_{28} C_{8} = 3,108,105$ .
Skiptu valinu í fjögur skref: veldu fyrst úr fjórða ári, síðan úr þriðja, úr öðru og loks úr fyrsta, eins og taflan sýnir. Árgangur

Fjöldi leiða til að velja fulltrúa fjórða

ár $_{10} C_{2} = 45$

þriðja ár $_{8} C_{2} = 28$

annað ár $_{6} C_{2} = 15$

fyrsta ár $_{4} C_{2} = 6$

. Margföldunarlögmálið gefur heildarfjöldann með margfeldi þessara fjögurra undirverkefna: $45 \times 28 \times 15 \times 6 = 113,400$ nefndir sem uppfylla skilyrðin.

Fjöldi	leiða til að velja fulltrúa fjórða
ár	$_{10} C_{2} = 45$
þriðja ár	$_{8} C_{2} = 28$
annað ár	$_{6} C_{2} = 15$
fyrsta ár	$_{4} C_{2} = 6$

Prófaðu skilning þinn

Þú vilt telja hve margar leiðir eru til að raða forritum á heimaskjá símans. Á að nota umraðanir eða samantektir?

Yngri bróðir þinn pakkar fyrir fjölskyldufrí en hefur aðeins pláss fyrir þrjú leikföng. Ef finna á fjölda mögulegra leikfangahópa, á að nota umraðanir eða samantektir?

Reiknaðu

_{12}{C_{10}}

Reiknaðu

_{16}{C_3}

Þú skipuleggur bílferð með vinum. Sex vinir koma til greina en aðeins er pláss fyrir þrjá aðra í bílnum. Hve margir ólíkir ferðahópar eru mögulegir?

Þú pakkar þremur skyrtum og þremur pilsum fyrir ferð. Ef átta skyrtur og fimm pils koma til greina, á hve marga vegu má pakka?

Æfingar úr hluta 7.3

Ákvarðaðu í eftirfarandi æfingum hvort aðstæðurnar lýsi umröðun eða samantekt.

Þú pakkar fyrir frí og þarft að velja fimm skyrtur.

Þú og vinir þínir ætlið að spila leik og þurfið að ákveða hver á að gera fyrstur, hver annar og svo framvegis.

Þú horfir á uppáhaldsraunveruleikaþáttinn og vilt finna fjölda mögulegra raða þriggja efstu.

Þú vinnur í fjögurra manna hópi með bekkjarfélögum og vilt finna hve margar samsetningar hópsins eru mögulegar.

Gefðu svör við eftirfarandi æfingum sem heilar tölur.

5⁢𝐶3

_5{C_3}

8⁢𝐶2

_8{C_2}

8⁢𝐶6

_8{C_6}

12⁢𝐶3

_{12}{C_3}

12⁢𝐶5

_{12}{C_5}

10.

14⁢𝐶3

_{14}{C_3}

11.

14⁢𝐶10

_{14}{C_{10}}

12.

15⁢𝐶5

_{15}{C_5}

13.

15⁢𝐶13

_{15}{C_{13}}

14.

18⁢𝐶3

_{18}{C_3}

15.

18⁢𝐶6

_{18}{C_6}

16.

20⁢𝐶4

_{20}{C_4}

17.

Í flestum afbrigðum pókers hefur hönd fimm spil og röðin skiptir ekki máli. Hve margar ólíkar pókerhendur eru til?

18.

Kennari byrjar hverja kennslustund á að velja þrjá nemendur til að kynna lausnir heimaverkefna. Ef nemendur eru 41, á hve marga vegu má velja þá?

19.

Sjö eru í framboði til þriggja sæta í skólastjórn sem allir kjósendur umdæmisins kjósa um. Á hve marga vegu má skipa sætin þrjú?

20.

Tuttugu keppendur eru í raunveruleikaþætti og tíu falla úr keppni eftir fyrsta þátt. Hve margir ólíkir hópar brottfallinna keppenda eru mögulegir?

21.

Í kappreið má leggja svonefnt exacta box-veðmál með tveimur hestum. Veðmálið vinnur ef þeir verða fyrstir og aðrir í hvorri röðinni sem er. Hve mörg slík veðmál eru möguleg í tólf hesta hlaupi?

Eftirfarandi æfingar fjalla um spilaleikinn euchre, sem notar 24 spil úr venjulegum stokki: aðeins gildin 9, 10, J, Q, K og A. Sum afbrigði nota einnig áttur eða sjöur og áttur, en hér er 24 spila útgáfan notuð.

22.

Euchre-hönd hefur fimm spil. Á hve marga vegu má fá fimm spila hönd þegar röð móttöku skiptir ekki máli, þannig að 9

\heartsuit

, J

\heartsuit

{\text{K}}\clubsuit

9\spadesuit

10\spadesuit

er sama hönd og

9\spadesuit

, J

\heartsuit

, 9

\heartsuit

{\text{K}}\clubsuit

10\spadesuit

23.

Þegar allir fjórir leikmennirnir hafa fengið spilin á hendi eru fjögur spil eftir á grúfu á miðju borðsins. Hve marga ólíka fjögurra spila hópa má mynda úr stokknum?

24.

Euchre er spilað í pörum. Á hve marga vegu geta tveir samherjar fengið fimm spila hendur þegar röðin skiptir ekki máli? Eftir að fyrri leikmaður fær spil eru 24 − 5 = 19 spil eftir. Frumvísbendingin notar ranglega

52 - 5 = 47

og miðast við fullan stokk.

Þú og fimm vinir þínir ætlið í rússíbana. Vagninn rúmar sex manns í þremur tveggja manna röðum og hópurinn fyllir því einn vagn.

25.

Á hve marga vegu má velja tvo í fremstu röð?

26.

Þegar fremsta röðin hefur verið valin, á hve marga vegu má velja tvo í miðröðina?

27.

Þegar tvær fremstu raðirnar hafa verið valdar, á hve marga vegu má velja tvo í öftustu röð?

28.

Notaðu margföldunarlögmálið og fyrri svör til að finna á hve marga vegu hópurinn getur skipt sér í raðir í rússíbanavagninum.

Talningarfræðifélag háskólans hefur átján félaga og fjórir þeirra verða valdir í nefnd.

29.

Hve margar ólíkar fjögurra manna nefndir eru mögulegar ef ábyrgð er jafnt skipt?

30.

Í stað þess að ábyrgðinni sé skipt jafnt verður einn nefndarmaður valinn formaður. Hve margar ólíkar nefndir eru mögulegar? Veldu fyrst formann, síðan hina þrjá úr þeim félögum sem eftir eru og notaðu margföldunarlögmálið. Sýndu útreikninga.

31.

Teljum nefndir með formanni á annan hátt. Veldu fyrst fjóra í nefndina eins og í fyrri spurningu og síðan einn þeirra sem formann. Sýndu útreikninga. Fæst sami fjöldi?

Powerball

er happdrætti margra fylkja sem kostar tvo dollara í hvert skipti. Leikmaður velur fimm tölur frá 1 til 69, hvítu kúlurnar, og eina tölu frá 1 til 26, Powerball-kúluna.

32.

Á hve marga vegu má velja hvítu kúlurnar? Sá sem velur allar fimm tölurnar rétt en ekki Powerball-kúluna vinnur eina milljón dollara.

33.

Á hve marga vegu má velja Powerball-kúluna? Sá sem velur hana rétt vinnur fjóra dollara.

34.

Hve margar leikleiðir eru alls? Sá sem velur allar fimm hvítu kúlurnar og Powerball-kúluna rétt vinnur eða deilir aðalvinningnum. Samkvæmt tölum frumkaflans byrjar aðalvinningurinn í 40 milljónum dollara og hækkar í næsta drætti ef enginn vinnur; hæsta gildi sem þar er nefnt er 1,586 milljarðar dollara. Á hve marga vegu má fylla út einn Powerball-miða?

35.

Þú sérð um dagskrá tónlistarhátíðar með aðalsviði, aukasviði og nokkrum minni sviðum. Fjörutíu hljómsveitir eru staðfestar; fimm þeirra leika á aðalsviðinu og átta á aukasviðinu. Á hve marga vegu má úthluta hljómsveitum á þessi tvö svið?