LEKTION 03-17

Idåg går vi genom de så kallade icke ordnade urval Vi börjar med lite terminologi:

Definition 0.1. En kombination av k objekt utvald från n olika objekt är ett urval, utan hänsyn till ordning och utan uprrepning, av k objekt från n olika objekt.

Notera att när man ska välja 2 element bland A, B, C finns det två alternativ: • med hänsyn till ordning, i.e val (A, B) är inte samma val som (B, A).

• med ingen hänsyn till ordning, i.e val (A, B) och (B, A) tänkas som samma val. Symbolen K(n, k) betecknar antalet kombination av k objekt utvald från n olika objekt. Det är klart att man skulle tro att K(n, r) < P (n, r). Till exempel:

P (3, 2) = |{AB, BA, AC, CA, BC, CB}| = 6
K(3, 2) = |{AB, AC, BC}| = 3

Notera att om vi multiplicera med antalet sätt att ordna upp två element får vi:

3 · 2! = 6

Så vi ska multiplicera varje kombination av k element bland n element med antal permutationer av k element för att få P (n, k):

K(n, k) · k! = P (n, k) = \frac{n!}{(n − k)!}

Vi ser att:

K(n, k) = \frac{n!}{k! · (n − k)!}

K(n, k) kallas binomial koefficienten och beteknas med \binom{n}{k}

Exempel • Antalet kombinationer av 0 element ur n element är:

\binom{n}{0} = 1

• Antalet kombinationer av 1 element ur n element är:

\binom{n}{1} = n

• Antalet kombinationer av n element ur n element är:

\binom{n}{n} = 1

• Antalet kombinationer av n − 1 element ur n element är:

\binom{n}{n − 1} = n

Exempel.

• En student skall basvara 7 av 10 givna frågor , vid en tantamen. På hur många

sätt kan hun välja ut dessa?

Vi ser att studenten kan välja utan ordning och säkert utan upprepning. Så svaret är:

\binom{10}{7} = \frac{10!}{3! · 7!} = 120

• Antag att frågorna är uppdelade i två grupper av fem. Exakt tre fågor från den

första gruppen skall besvaras, och därmed fyra från den andra.

Studenten ska välja först tre från första gruppen och sedan fyra från andra. Så enligt multiplications principen det finns

\binom{5}{3} · \binom{5}{4} = 50

många sätt man kan välja ut.

• Antag nu att minst tre frågor från den första gruppen skall besvaras.

Man kan välja exakt 3 frågor från den första gruppen och därmed 4 från andra, eller exakt 4 frågor från den första gruppen och därmed 3 från andra eller exakt 5 frågor från den första gruppen och därmed 2 från andra.

Enligt additions principen det finns

\binom{5}{3} · \binom{5}{4} + \binom{5}{4} · \binom{5}{3} + \binom{5}{5} · \binom{5}{2} = 50 + 50 + 10 = 110

många sätt man kan välja ut.

Exempel. Bestäm antalet delmängder med k element till en mängd med n element.

För att bilda en delmängd med k element ska man välja k element av n, utan upprepning och utan ordning. Faktisk har vi att:

{a_{1}, a_{2}, ..., a_{k}} = {a_{3}, a_{2}, a_{1}, ..., a_{k}}

Så det finns \binom{n}{k} delmängder med k element till en mängd med n element.

Notera att när k = 0 formulan säger att det finns \binom{n}{0=1} delmängd med 0 element, den tomma delmängden.

Vi ska nu bevisa två mycket viktiga identiteter:

(1) \binom{n}{k} = \binom{n}{n−k}.

(2) \binom{n+1}{k} = \binom{n}{k} + \binom{n}{k−1}

Bevis.

(1) Heltal \binom{n}{k} ger hur många delmängder med k element finns till en mängd med n element. Men varje gången vi väljer ut en delmängd med k element definerar vi också en delmängd med n − k element, nämlingen de som vi lämnar kvar. Det betyder att det finns lika många delmängder med k element som med n−k element.

(2) Heltal \binom{n+1}{k} ger hur många delmängder med k element finns till en mängd med n + 1 element. Låt A vara en mängd med n + 1 element och x ∈ A. Vi kan tänka på antal delmängder med k element som:

(Antal delmängder som innehåller x) + ( Antal delmängder som inte innehåller x)

En delmängd som innehåller x kan bildas genom att välja k − 1 element av n element, så på \binom{n}{k−1} många sätt. En delmängd som inte innehåller x kan bildas genom att välja k element av n element, så på \binom{n}{k} många sätt.

Som ett följd av (2) kan man “gruppera” binomial koeficienter i den så kallade Pascal triangle. Se sidan 120 i boken.

Example. Visa att:

\binom{n}{0} + \binom{n}{1} + ... + \binom{n}{n} = 2^{n}

Heltal 2^{n} beräknar antal delmängder till en mängd men n ellemnt. Heltal \binom{n}{i} beräknar avtal delmängder med i element till en mängd men n ellemnt. Formulan är alltså klar!

Ovning. Bestäm antal ord av lengd n i alfabetet {0, 1} med exakt r nollor.

Vi använda ord binomial koefficienter på grund av följande stas: SATS. Det gäller att för n ≥ 1,

(x + y)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{n−k}y^{k}

Bevis. Det är klart att (x+y)^{n} består av antal termer på formen x^{n−k}y^{k}, med k varierande från 0 till n. Vi ska visa att för ett fixt k det finns precis \binom{n}{k} termer på formen x^{n−k}y^{k}. Vi får ett term på formen x^{n−k}y^{k} när vi tar y exakt k gånger (av n). Antal sätt att välja k gånger y är \binom{n}{k}.

Exempel. Bestäm den kostanta termen i

(2t^{4} + \frac{1}{t})^{10}

Enligt binomialsatsen är:

(2t^{4} + \frac{1}{t})^{10} = ∑_{k=0}^{10} \binom{10}{k}(2t^{4})^{10−k} · \frac{1}{t^{k}} = ∑_{k=0}^{10} \binom{10}{k}2^{10−k}t^{40−5k}

Vi får termen innehållande t^{0} då 40 − 5k = 0, dvs då k = 8.

Det följer att kostanta termen är \binom{10}{8}2^{2} = 45 · 4 = 180.

Nu ska vi handla om problemet att välja ut k objekt från n objekt, UTAN hensyn till ordning och MED upprepning tillåtet. Det här är det svåraste av de fyra fallen.

Låt, för varje i = 1, 2, ..., n, talet x_{i} beteckna antalet gånger objekt num. i väljes. Då det måste vara:

x_{1} + x_{2} + ... + x_{n} = k där x_{i} ≥ 0, i = 1, ..., n

Så vi ska bestämma antalet icke-negativa heltalösning till ekvationen.

Svaret är :

\binom{n + k − 1}{k}

Bevis. Antag att vi har r stycken identiska objekt och vill placera den i n olika lådor. På hur många sätt kan man göra det? Om talet x_{i} betecknar antalet objekt som läggs i låda nummer i svaret är igen antalet icke-negativa heltalösning till ekvationen:

x_{1} + x_{2} + ... + x_{n} = k.

En placering av r stycken identiska objekt o i n olika lådor kan beskrivas som:

• • ...• | • • ...• | ...
låda 1  låda 2  ...

Så vi ska beräkna antal permutationer av (n − 1 + k) objekt ((n − 1) stycken | och k stycker •). Men antal permutaioner mellam r stycken • och antal permutationer mella (n − 1) stycken | ger samma placeringen.

Så totalt har vi

\frac{(n − 1 + k)!}{(n − 1)!k!} = \binom{n − 1 + k}{k}

.

Vi har också bevisat att: Antalet sätt att placera r stycken identiska objekt i n olika lådor är:

\frac{(n − 1 + k)!}{(n − 1)!k!} = \binom{n − 1 + k}{k}

.

Exempel Bestäm antalet heltalslösningar till:

x_{1} + x_{2} + x_{3} + x_{4} = 32

sådan att x_{1}, x_{1} ≥ 5 och x_{3}, x_{4} ≥ 7.

Låt y_{1} = x_{1} − 5, y_{2} = x_{2} − 5, y_{3} = x_{1} − 7, y_{4} = x_{4} − 7. Vi ser att

y_{1} + y_{2} + y_{3} + y_{4} = x_{1} + x_{2} + x_{3} + x_{4} − (10 + 14) = 8

Vi ska hitta alla icke-negativa heltalslösningar till

y_{1} + y_{2} + y_{3} + y_{4} = 8

Svaret är \binom{8+4−1}{8} = 165.

Exempel. Hur många tal kan man bilda av siffrorna 1, 2, ..., 9 on varje siffra bara får användas en gång och siffrorna skall komma i stotleksording? Exempel på tillåtna tal är 7, 235, 45789.

Betrakta mängden {1, 2, ..., 9}. Varje icke-tomma delmängd definerar ett tal där varje siffra bara användas en gång och siffrorna skall komma i stotleksording. Till exempel: delmängden {1, 4, 6} definerar 146.

Så svaret är 2^{9} − 1.

Exempel. Visa att \frac{(2n)!}{2^{n}} är ett heltal.

Heltal (2n)! beräknar antalet permutationer av 2n element. Betrakta den 2n objekt

a_{1}a_{1}a_{2}a_{2}...a_{n}a_{n}

Eftersom vi har två stycken a_{i} för varje i = 1, ..., n, beräknar \frac{(2n)!}{2^{n}} antal arrangemang av denna element. Så den är svaren till “hur många arrangemang finns det av elementen a_{1}, a_{1}, a_{2}, a_{2}, ..., a_{n}, a_{n}”. Det följer att \frac{(2n)!}{2^{n}} måste vara ett heltal.