Diskret matematik · 2025-05-07

Uppgift 5

Per Alexandersson Kombinatorik Beräkning

Uppgift 5

De 9 damerna Agda, Berit, Cecilia, Dorotea, Ester, Frideborg, Gerd, Hilda och Ingalill ska organisera syföreningens årsmöte. Agda, Berit och Cecilia kan bara laga huvudrätter. Gerd, Hilda och Ingalill kan bara laga efterrätter. De tre övriga kan laga både huvudrätter och efterrätter.

(a)

Mötet behöver exakt fyra personer som kan laga huvudrätter. På hur många sätt kan dessa utses bland de sex som kan laga huvudrätt?

(b)

Om man nu vill välja en grupp damer där exakt fyra av dem kan laga huvudrätt, och exakt fyra av dem kan laga efterrätt, på hur många sätt kan detta göras? Som exempel: $ \{\mathtt{Berit},\, \mathtt{Dorotea},\, \mathtt{Ester},\, \mathtt{Frideborg},\, \mathtt{Gerd} \} $ utgör ett godkänt urval, då exakt fyra av dessa kan laga huvudrätt och exakt fyra av dem kan laga efterrätt.

(c)

Berit och Gerd vill inte laga mat med Ester; de är rädda för Esters matlagning¹. På hur många sätt kan man nu göra urvalet i (b) där vi undviker att Ester blir vald samtidigt som Berit eller Gerd?

Inget av svaren på (a), (b), (c) överstiger $100$.

Se föregående tenta---Ester har en historik med att råka flambera sina husdjur. ↩

Visa lösningDölj lösning

Det finns sex personer som kan laga huvudrätt, att välja 4 av dem kan göras på $\binom{6}{4} = 15$ sätt.
Damernas expertisområden illustreras nedan:

Vi gör en falluppdelning beroende på hur många som ingår bland $B = \{\mathtt{Ester},\mathtt{Dorotea},\mathtt{Frideborg} \}$. Vi väljer först från $B$, och lägger därefter till damer från $H$ och $E$: \[\begin{aligned} \textbf{En dam från $B$:} &\quad \binom{3}{1} \cdot \binom{3}{3} \cdot \binom{3}{3} = 3, \\ \textbf{Två damer från $B$:}&\quad \binom{3}{2} \cdot \binom{3}{2} \cdot \binom{3}{2} = 27,\\ \textbf{Tre damer från $B$:}&\quad \binom{3}{3} \cdot \binom{3}{1} \cdot \binom{3}{1} = 9. \end{aligned}\] Detta ger totalt $39$ olika val.
Vi gör inklusion--exklusion. Vi räknar först när Ester och Gerd båda ingår. Detta val måste kompletteras med damer från $B$, $H$ och $E$: \[\begin{aligned} \textbf{Ingen dam till från $B$:} &\quad \binom{2}{0} \cdot \binom{3}{3} \cdot \binom{2}{2} = 1, \\ \textbf{En dam till från $B$:} &\quad \binom{2}{1} \cdot \binom{3}{2} \cdot \binom{2}{1} = 12, \\ \textbf{Två damer till från $B$:} &\quad \binom{2}{2} \cdot \binom{3}{1} \cdot \binom{2}{0} = 3. \end{aligned}\] Totalt: $16$ val. På samma sätt så finns det 16 val där både Ester och Agda ingår.

Vi dubbelräknar dock de fall där alla tre (Ester, Agda och Gerd) ingår. Det saknas då två till personer för huvudrätt, och två till för efterrätt (som kan vara samma).

\[\begin{aligned} \textbf{Ingen dam till från $B$:}&\quad \binom{2}{0} \cdot \binom{2}{2} \cdot \binom{2}{2} = 1, \\ \textbf{En dam till från $B$:} &\quad \binom{2}{1} \cdot \binom{2}{1} \cdot \binom{2}{1} = 8, \\ \textbf{Två damer till från $B$:}&\quad\binom{2}{2} \cdot \binom{2}{0} \cdot \binom{2}{0} = 1. \end{aligned}\] Detta ger oss $10$ val där både Ester, Agda och Gerd ingår.

Så med inklusion--exklusion finns det då totalt $ 39 - 2\cdot 16 + 10 = 17 $ olika val där Ester (om hon är med) inte är tillsammans med Agda eller Gerd.
```
(* Med Mathematica, Agda=1, Berit=2, etc *)
Select[
  Subsets[Range[9]],
  Length[Intersection[Range[1, 6], #]] == 4 &&
    Length[Intersection[Range[4, 9], #]] == 4 &&
    Implies[MemberQ[#, 5], ! MemberQ[#, 2] && ! MemberQ[#, 7]] &
  ] // Column
```