MATEMATIK Dag : 040604 Tid : 8.45 - 13.45. Göteborgs Universitet Hjälpmedel : Inga Peter Hegarty Vakt : Håkan Samuelsson 0740-350646.

Tentamenskriving i Diskret Matematik (MAN 240)

≥ 13 poäng, inkl. poängen från inlämningsuppgifterna, ger godkännt. Denna gräns kan minskas efteråt.

1 (1.5p+1.5p) (i) Sverige har tagit ut en trupp till EM som består av 23 spelare : 3 målvakter, 8 försvarare, 8 mittfältare och 4 anfallare. Det är troligt att Lars-Tommy väljer att spela 4-4-2, dvs målvakt + 4 försvarare + 4 mittfältare + 2 anfallare.

Hur många möjliga laguppställningar finns det alltså, om vi antar (något orealistiskt !) att inbördesordningen i varje lagdel är oväsentligt ? (ii) Låt oss vara jätteoptimistisk och anta att Sverige gör 37 mål under turneringen. Hur många möjligheter finns det då för skytteligan ?

(T.ex. en möjlighet är : Zlatan 36 mål, H. Larsson 1 mål, alla de andra 21 spelarna 0 mål).

2 (4x1p+2p). Man hänvisas till grafen G i Fig. 13.17(b).

(i) Ange en Hamilton cykel i den ‘oriktade’ grafen G^{∗} eller förklara varför ingen sådan existerar.

(ii) Ange χ(G^{∗}) och en explicit optimal färgning av G^{∗}.

(iii) Ange ett spanning träd av minimal vikt i G^{∗}.

(iv) Genomför Dijkstra’s algoritm för att hitta en kortaste väg från a till z i G (skriv ner vilken kant du väljer i varje steg).

(v) Kör nu FF-algoitmen för att hitta ett maximalt flöde från a till z och en minimal cut-set (skriv ner vilken augmenting väg du väljer i varje steg).

3 (3p). Formulera och bevisa Philip Halls sats om matchningar i bipartite grafer.

4 (3p). Ange (i termer av fakultets funktioner) antalet permutationer

π : {1, 2, ..., 100} → {1, 2, ..., 100}

där inga två av π(1), π(2), π(3), π(4) är på varandra följande tal.

5 (1p+1p+1p) Formulera och bevisa recurrence relationer för (i) Stirling talen S(n, k), (ii) Catalan talen C_{n}, (iii) antalet derangements d_{n} av n st. föremål.

6 (3p). Lös fullständigt följande recurrence relation (dvs ange en sluten formel för u_{n}) :

2u_{n} = 7a_{n−1} − 3a_{n−2} + 3^{n} ∀ n ≥ 2,
u_{0} = 1, u_{1} = 1.

Obs! Tentan beräknas vara färdigrättad den 11 juni. Då kan den hämtas i mottagningsrummet mellan kl. 12:30-13:00. Tentamensresultat lämnas också ut per telefon 772 35 09 efter kl. 14:00.