MATEMATISKA INSTITUTIONEN STOCKHOLMS UNIVERSITET

Avd. Matematik Examinator: Jörgen Backelin Tentamensskrivning i kombinatorik fdk, 2002-05-28

09^{00}–14^{00}

1. Utred den andra raden i ”den tolvfaldiga vägen”, d. v. s. antalet funktioner f : N → X (dels samtliga, dels injektiva, dels surjektiva), där N består av n likadana element, och X av x olika element. Du bör både ange antalen, förklara införda beteckningar, och visa att dina påståenden stämmer. 3 p

2. Ett ord (en sträng) s innehåller ett ord t som delord, om s på minst ett sätt kan skrivas som en sammansättning av tre ord, s = s_{1}ts_{2}, där t är det mittersta (och där vi tillåter att det ena eller båda av s_{1} och s_{2} är tomma ord; så s självt är alltid ett delord av s).

a)

Låt H_{n} vara mängden av ord s av längd n i alfabetet {x, y, z}, sådana att varken xx eller yz är delord av s. Beräkna den genererande funktionen h(x) för H_{n} (n ∈ ℕ). Visa speciellt att h(x) är en rationell funktion, d. v. s. kan uttryckas som (serieutvecklingen i origo av) kvoten av två polynom. 2 p

b)

En svepande generalisering: Visa att om Σ är ett alfabet med r element, r_{1}, …, r_{m} är m stycken ord av längd 2, och F_{n} är mängden av ord i Σ av längd n och saknande r_{1}, …, r_{m} som delord, så är den genererande funktionen f(x) för (F_{n})_{n=0}^{∞} rationell. 3 p Ledning: Detta kan göras på flera goda sätt. Bl. a. kan man införa r stycken delfunktioner a_{i}(n) := |{s ∈ F_{n} : s börjar på x_{i}}| (där Σ = {x_{1}, …, x_{r}}), och hitta ett matrissamband mellan dem. I så fall kan man ha nytta av att använda Cayley-Hamiltons sats: om p(x) = det(xE − A) är det karakteristiska polynomet för en kvadratisk matris A, så är p(A) = 0. (Cayley-Hamiltons sats får användas utan bevis.)

3. Låt L vara ett lattice, sådant att den första distributiva lagen uppfylls: För alla x, y, z ∈ L gäller x ∧ (y ∨ z) = (x ∧ y) ∨ (x ∧ z). Visa att då måste också den andra distributiva lagen vara uppfylld, d. v. s. att för alla x, y, z ∈ L gäller x ∨ (y ∧ z) = (x ∨ y) ∧ (x ∨ z). (Bara den första distributiva lagen, och sådana egenskaper som gäller för alla lattice (t. ex. att (x ∧ y) ∨ x = x), får användas utan bevis.) 3 p

4. För varje pomängd (”poset”) (P, <), så bildar alla de pomängder som är isomorfa med (P, <) en isomorfiklass. Låt A = {isomorfiklasser av ändliga pomängder}. Inför en relation <_{A} på mängden A, genom att låta p <_{A} q omm p innehåller någon pomängd P och q någon pomängd Q, sådana att P är en äkta inducerad delpomängd (”subposet”) av Q.

a) Visa att (A, <_{A}) själv är en pomängd, men inte en ändlig pomängd.  2 p
b) Visa att A har ett minsta element ˆ0, men inte ett största element.  2 p

c)

Avgör huruvida A har en rangfunktion (”is graded”), i meningen att för varje element p ∈ A alla maximala kedjor från ˆ0 till p har samma längd. 2 p

d) Avgör huruvida A är ett lattice.  2 p

(V.G.V.) e)

Rita upp intervallet [p, q], där p är ekvivalensklassen till [2], och q är ekvivalensklassen till (det booleska latticet) B_{2}. Beräkna med ledning av detta μ(p, q), där μ är Möbiusfunktionen. 2 p

5. a) Låt för n = 0, 1, … M_{n} vara de binära strängar s = b_{1}b_{2} ⋯ b_{2n} av längd 2n, som uppfyller att s innehåller n nollor och n ettor, samt att varje vänster delsträng b_{1} ⋯ b_{ℓ} innehåller minst lika många ettor som nollor. Visa att |M_{n}| = C_{n} = \frac{1}{n+1} \binom{2n}{n} för varje n, genom direkt räkning.  3 p (Det räcker alltså inte i denna deluppgift att bara ge en bijektion mellan M_{n} och någon annan välkänd mängd F_{n}, där familjen (F_{n})_{n=0}^{∞} också räknas av Catalantalen C_{n}. Du måste då också visa att |F_{n}| = C_{n}.)

Låt nu som vanligt S_{n} = {permutationer av [n]} = {bijektioner σ : [n] → [n]}. Betrakta mängderna S_{n}^{(123)} och S_{n}^{(321)} av permutationer av [n] som undviker mönstret (123) respektive mönstret (321). (Formella definitioner:

S_{n}^{(123)} = {σ ∈ S_{n} : ( ∄(i, j, k) med i < j < k och σ(i) < σ(j) < σ(k))};
S_{n}^{(321)} = {σ ∈ S_{n} : ( ∄(i, j, k) med i < j < k och σ(i) > σ(j) > σ(k))}.)

b)

Visa för varje n att |S_{n}^{(123)}| = |S_{n}^{(321)}|, genom att ange en explicit bijektion

ϕ_{n} : S_{n}^{(123)} → S_{n}^{(321)} .  2 p

c)

Visa för varje n att |S_{n}^{(123)}| = C_{n}, antingen genom direkt räkning, eller genom att etablera

bijektioner mellan S_{n}^{(123)} (eller S_{n}^{(321)}) och andra kända mängder med Catalantal många element (exempelvis M_{n} från första deluppgiften). 3 p

Jag påminner om att du bör ange din elpostadress på skrivningsomslaget, för att få personligt besked om ditt resultat, och i förekommande fall förslag på tid för muntlig tentamen.