LEKTION 03-19

Vi börjar med några exempler:

Exempel. Hur många arrangemang av bokstäverna i ANTANANARIVE finns det?

Vi har 12 bokstäver. Hade de varit olika skulle det funnit 12! stycken arrangemang, men nu finns det 4 stycken A och 3 stycken E. Så svaret är:

\frac{12!}{3! · 4!}

Hur många arrengemang finns det om vi ville ha alla A står till varandra?

Vi ska behandla alla A som ett element: AAAA = □. Så vi har nu 9 stycken element med 3 likadana N. Svaret är \frac{9!}{3!}.

Exempel. På hur många sätt kan bokstäverna i UNDERBAR arrangeras med exakt två konsekutiva vokaler?

Man kan konstruera ett arrangemang på följande sätt:

först ska man välja två vokaler och sätta den lika med ett elemnt, □. Sedan ska man beräkna antal arrangemang av element □, N, D, R, B,R. Och sedan ska man placera den annan vokal mellan två element ≠ □ Vi ser att man kan välja två vokaler ur tre (här vi ska välja MED ordning och utan upprepning) på \frac{3!}{1!} = 6 sätt. Dessutom finns det \frac{6!}{2!} antal arrangemang av element □, N, D, R, B,R. Också man kan placera den annan vokal mellan två element ≠ □ på 5 ulika sätt. Enligt multiplikationsprincipen svaret är

6 · \frac{6!}{2!} · 5 = 10800

Vi ska nu införa En generalisering av binomialkoefficienterna.

Antag att n_{1}, .., n_{k} är icke-negativa heltal och att n_{1} + ... + n_{k} = n. Då defineras den multinomialkoefficient som talet:

\binom{n}{n_{1}, n_{2}, ..., n_{k}} = \frac{n!}{n_{1}! · n_{2}! · ... · n_{k}!}

Vi observerade tidigare att:

Antalet arrangemang av n_{1} stycken identiska objekt, n_{2} stycken identiska objekt,...,n_{k} stycken identiska objekt, där n_{1} + n_{2} + ... + n_{k} = n är

\binom{n}{n_{1}, n_{2}, ..., n_{k}} = \frac{n!}{n_{1}! · n_{2}! · ... · n_{k}!}

Om man ska ligga n + 1 brev i n postfack måste något postfack få minst två brev. Denna kallas den Postfacksprincipen. Den generaliseras lätt som Om kn + 1 eller fler brev skall läggas i n postfack så måste något postfack innehålla

minst n + 1 brev.

Exempler.

• Av 13 personer så måste det finnas två som har födelsedag samma månad.

• I en liksidig triangel med sidan 1 väljes 5 punkter. Visa att det finns två punkter

vars avstånd är högst \frac{1}{2}.

Delar triangel i fyra delar. Enligt postfacksprincipen måste minst två punkter tillhöra samma deltriangel. Så dessa punkter har ett inböedes avstånd som är mindre eller lika med \frac{1}{2}.

• Finns det något sätt att placera på ett middasbjudning, tre par kring ett runt

bord så att alla bordsgrannar är av olika kön och ingen sitter brevid sin partner?

Det finns 3 kvinnor K_{1}, K_{2}, K_{3} och deras partner M_{1}, M_{2}, M_{3}. Om vi börjar med K_{1} ser vi att placering:

K_{1}M_{2}K_{3}M_{1}K_{2}M_{3}

går bra. Eftersom vi kan börja med en bland 6 personer och efter första placering har vi bara två möjlihet att placera andra pesonen, är svatret:

6 · 2 = 12

Definition 0.1. En partition av en mängd A är en uppdelning i djunkta delmägder • A = A_{1} ∪ A_{2} ∪ ... ∪ A_{k}.

• A_{i} ∩ A_{j} = ∅ för i ≠ j

Antalet aprtitioner av en mängd med n element i k delar betecknas med

S(n, k)

Stirlingtalet.

Exempel.

• S(n, 0) = 1

• S(n, 1) = 1

• S(n, n) = 1 Sterligtal kan beräknas enligt en rekursiv formula:

S(n, k) = S(n − 1, k − 1) + kS(n − 1, k)

Låt A vara en mängd med n element och x ∈ A. Mängden A \ {x} har n − 1 element och varje partition av A \ {x} i k − 1 delar ger en partition av A i k delar genom att sätta {a} = A_{k}. Dessutom varje partition av A \ {x} i k delar ger k olika partitioner av A i k delar genom att placera x i en av den k delar.

På hur många sätt kan vi dela en mängt med n element i k delar så att delarnas storlekar är n_{i}?

Vi vill beräkna partitioner på formen:

• A = A_{1} ∪ A_{2} ∪ A_{3} ∪ ... ∪ A_{k}

• A_{i} ∩ A_{j} = ∅ för varje i ≠ j.

• |A_{i}| = n_{i}

Svaret är \binom{n}{n_{1},n_{2},...,n_{k}}.

Grafteori

Euler var den förste som använde grafteori när han löste problemet med Königsbergs broar.( Se sidan 149 i boken).

I köningsberg fanns 7 broar som band samman de olika stadsdelarna. Eulers frågan var:

Kan man gå en promenad så att man går över varje bro precis en gång? Euler införde en graf där:

• ett hörn eller nod, • motsvarar en stadsdel och

• en kant — motsvarar en bro.

[figure]

Euler observerade att varje gången ett hörn passeras på en promenad används två kanter, utom vid första och sista. Dessutom vi ska använda varje kant precis en gång. Det betyder att det bara finnas två hörn med udda antal kanter.

Men Grafen har alla odda hörn. Så det är omjligt att gå en promenad så att man går över varje bro precis en gång.

Den här graf kallas Eulers graf. Eulers graf är en multi-graf efetersom den har parallela kanter.

En multi-graf kan också ha öglor. En graf utan parallela kanter eller öglar kallas en Enkel Graf. Vi ska betrakta bara enkla grafer!

Definition 0.2. En enkel graf är ett par (V, E) av mängder där: • V = {x_{1}, ..., x_{k}} är en icke-tom och ändlig. Den kallas mängden av hörn.

• E = {e_{1}, ..., e_{n}} där varje element e_{i} består av ett par av hörn, e_{i} = x_{j}x_{k}, i ≠ k. Den kallas mängden av kantor.

Varje enkel graf kan representeras geometriskt med punkter och linjer.

Exempel.

• Betrakta grafen W_{n} = (V, E), där – V = {0, 1, 2, ..., n} och

– E = {01, 02, ..., 0n, 12, 23, 34, ..., (n − 1)n, n1} W_{1} : [figure]

W_{2} : [figure] W_{4} : [figure]

• Vi definerar nu den kompletta grafen K_{n} = (V, E):

– V = {1, 2, 3, ..., n} och

– E = {ij|i ≠ j}. alla par av noder är fr̈bunda.

K_{4} : [figure] K_{5} : [figure]

Hur många kanter finns i K_{n}? Eftersom alla noder är förbunddamåste kardilateten av E vara \binom{n}{2}.