Lösningar till tentamensskrivning i kombinatorik fdk 2002-05-28

Fullständig version; men ännu ej helt korrekturläst.

1. Se avsnitt 1.4 i läroboken. (Antalen är \binom{x+n−1}{n} totalt, \binom{x}{n} injektiva, \binom{n−1}{n−x} surjektiva funktioner.)

2. Vi börjar med b)-uppgiften. Under förutsättningarna är (för 1 ≤ i ≤ r och n ≥ 1) a_{i}(n + 1) =

∑_{j=1}^{r} c_{ij}a_{j}(n), där c_{ij} = \{ \begin{matrix}0, & om ∃ k : r_{k} = x_{i}x_{j} \\ 1 & annars \end{matrix} . Låt C = ( \begin{matrix}c_{11} & … & c_{1r} \\ ⋮ & & ⋮ \\ c_{r1} & … & c_{rr} \end{matrix} ), A(n) =( a_{1}(n) ; ⋮ ; a_{r}(n) ),

B = ( 1 … 1 ) och a(n) = BA(n) = a_{1}(n) + … + a_{r}(n) för n ≥ 1 (med användande av konventionen att identifiera en 1 × 1-matris med dess enda post). De rekursiva sambanden kan

då sammanfattas A(n + 1) = CA(n) (n ≥ 1). Låt p(x) = det(xE − C) = ∑_{i=0}^{r} λ_{i}x^{r−i} vara det

karakteristiska polynomet för C; då är enligt Cayley-Hamiltons sats

∑_{i=0}^{r} λ_{i}a(n − i) = ∑_{i=0}^{r} λ_{i}BA(n − i) = B ∑_{i=0}^{r} λ_{i}C^{r−i}A(n − r) = Bp(C)A(n − r) = 0

för n ≥ r + 1. Alltså uppfyller den genererande funktionen f(x) = 1 + ∑_{n≥1} a(n)x^{n} för antalen

ord att f(x) · x^{r}p(x^{−1}) = q(x), där q är ett polynom av grad högst r (och där x^{r}p(x^{−1}) = ∑_{i} λ_{i}x^{r−i} också är ett polynom). f är således (serieutvecklingen i origo av) polynomkvoten q(x)/(x^{r}p(x^{−1})), vilket skulle visas.

Vi kan nu tillämpa denna allmänna metod direkt i a)-fallet. Matrisen C blir ( \begin{matrix}0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \end{matrix} ),

så p(x) = | \begin{matrix}x & −1 & −1 \\ −1 & x − 1 & 0 \\ −1 & −1 & x − 1 \end{matrix} | = x^{3} − 2x^{2} − x + 1; och direkt räkning visar att a(1) = 3,

a(2) = 7 och a(3) = 16; så q(x) ≡ (1 + 3x + 7x^{2} + 16x^{3})(1 − 2x − x^{2} + x^{3}) (mod x^{4}), vilket ger q(x) = 1 + x. Således är h(x) = (1 + x)/(1 − 2x − x^{2} + x^{3}). Självklart kan h(x) också beräknas mer direkt. Det är däremot inte särskilt lätt att först bestämma |H_{n}| som funktion av n. (Som man kan se av svaret, är nämnaren ett tredjegradspolynom utan rationella nollställen; så dess nollställen är rejält krångliga att skriva som algebraiska uttryck.)

3. Vi tillämpar först den första distributiva lagen på (x ∨ y, x, z), sedan absorptionslagarna samt kommutativa lagen för ∧, sedan den första distributiva lagen för (z, x, y), sedan associativa lagen för ∨ samt kommutativa lagen för ∧, och till sist absorptionslagarna. Detta ger (x ∨ y) ∧ (x ∨ z) = ((x ∨ y) ∧ x) ∨ ((x ∨ y) ∧ z) = x ∨ (z ∧ (x ∨ y)) = x ∨ ((z ∧ x) ∨ (z ∧ y)) = (x ∨ (x ∧ y)) ∨ (y ∧ z) = x ∨ (y ∧ z), vilket skulle bevisas.

4. Observera först att två isomorfa pomängder har samma kardinalitet (d. v. s. innehåller lika många element). Vidare har en äkta delpomängd alltid lägre kardinalitet.

(V.G.V.)

(lösn. t. tent.skrivn. i kombinatorik fdk 2002-05-28, sid. 2.)

a)

Antag först att p <_{A} q <_{A} p. Då funnes P, P′ ∈ p och Q, Q′ ∈ q sådana att P vore en äkta delpomängd av Q, och Q′ en äkta delpomängd av P′. Men då vore |P | < |Q| = |Q′| < |P′| = |P |, d. v. s. |P | < |P |, vilket är absurt. Alltså är <_{A} antisymmetrisk. Antag nu att p <_{A} q <_{A} r. Då finns P ∈ p, Q, Q′ ∈ q och R ∈ r, sådana att P är en äkta delpomängd av Q och Q′ är en äkta delpomängd av R. Vidare är ju Q och Q′ isomorfa (eftersom de tillhör samma isomorfiklass), så det finns en isomorfi ϕ : Q ≃ Q′. Sätt P′ = ϕ(P). Då är P′ en äkta delpomängd av Q′ och alltså en äkta delpomängd av R. Vidare är restriktionen av ϕ till P en isomorfi mellan P och P′, så P′ ∈ p. Alltså gäller även p <_{A} r. Följdaktligen är <_{A} transitiv. Eftersom <_{A} är antisymmetrisk och transitiv, så är (A, <_{A}) verkligen en pomängd. Å andra sidan finns det ju pomängder av varje kardinalitet, så A är oändlig.

b)

Det minsta elementet är isomorfiklassen som bara består av det tomma latticet (den tomma mängden med den tomma relationen). (Eftersom den tomma mängden är en äkta delmängd av varje annan mängd, är verkligen denna klass mindre än varje annat element i A.) (Om du tillhör dem som bara vill ha icketomma underliggande mängder i lattices, så bör ditt svar vara: ”Det minsta elementet är isomorfiklassen som består av alla ettelementslattices (med triviala relationer).”) Inget element p ∈ A kan vara störst; ty om P ∈ p och q ∈ A har element av kardinalitet större än |P |, så är q varken mindre än eller lika med p.

c)

A har rangfunktionen ρ given av ”ρ(p) = |P |, om P ∈ p”. (Om du inte accepterar det tomma latticet, så blir ρ(p) = |P | − 1.) Om p och q är på varandra följande element i en maximal kedja i ett intervall i A, och P ∈ p och Q ∈ q med P ⊂ Q, så gäller nämligen att |Q| = |P | + 1. (Annars kunde man ju skjuta in en delmängd R, så att P ⊂ R ⊂ Q, och förse R med den inducerade latticestrukturen; och då låge isomorfiklassen för R mellan p och q, motsägande kedjans maximalitet.)

d)

A är inte ett lattice. T. ex. har de två olika elementen av rang två inget join, eftersom tre olika element av rang tre täcker båda.

e) Bilden utgår av TeXniska skäl. Intervallet är isomorft med latticet M_{5}, och μ(p, q) = 2.

5. a) Det finns flera goda sätt att göra detta på. (Se gärna någon lärobok i diskret matematik!) Ett sätt är följande: Låt för varje n ∈ ℕ och varje k ∈ \{0\}∪[n] M_{n,k} vara mängden av binära strängar s = b_{1} ⋯ b_{n} av längd n, sådana att varje vänster delsträng av s (inklusive s själv) innehåller minst lika många ettor som nollor, och att s innehåller (precis) k ettor. Sätt också tillfälligt \left[{n \atop k}\right] = |M_{n,k}|. Man ser då att \left[{n \atop k}\right] kan beräknas med hjälp av en ”trunkerad Pascals triangel”, med reglerna \left[{n \atop k}\right] = \{ \begin{matrix}0 & om k < \frac{n}{2}; \\ \left[{n−1 \atop k−1}\right] + \left[{n−1 \atop k}\right] & annars. \end{matrix} Man kan också se att trunkeringen motsvarar ”normala Pascalregler” i en situation där man i stället startat med \left[{0 \atop 0}\right] = 1 men \left[{0 \atop −1}\right] = −1 (och övriga \left[{0 \atop k}\right] = 0), eftersom man då får en ”negativ spegelbild” av den triangel vi egentligen vill undersöka. Härav (eller med något mindre intuitivt induktionsbevis) får vi \left[{n \atop k}\right] = \binom{n}{k} − \binom{n}{k + 1} = \frac{n!((k + 1) − (n − k))}{(k + 1)!(n − k)!} = \frac{n!(2k + 1 − n)}{(k + 1)!(n − k)!} , och eftersom M_{n} = M_{2n,n} alltså |M_{n}| = \left[{2n \atop n}\right] = C_{n}.

b) Definiera ϕ_{n}(σ) genom (ϕ_{n}(σ))(i) = σ(n + 1 − i) (σ ∈ S_{n}^{(123)}, i ∈ {1, …, n}).

(V.G.V.)

(lösn. t. tent.skrivn. i kombinatorik fdk 2002-05-28, sid. 3.)

c)

Jag skall etablera en bijektion ψ_{n} : M_{n} ≃ S_{n}^{(321)} för varje n. P. gr. a. resultaten i föregående deluppgifter kommer det då att följa att |S_{n}^{(123)}| = |S_{n}^{(321)}| = |M_{n}| = C_{n}.

Tolka element σ ∈ S_{n}^{(321)} som följder (σ(1), …, σ(n)). Tolka element s = b_{1} ⋯ b_{2n} ∈ M_{n} som personalförändringshistorier i enlighet med inverterad kompromissanställningsskyddslagstiftning: vid första uppsägning i en rad, sägs den sist anställde upp; men om däremot uppsägningen direkt föregåtts av en uppsägning, utan mellanliggande nyanställning, sägs den först anställde upp. b_{i} = 1 tolkas som ”nyanställning”; b_{i} = 0 som ”uppsägning”. Villkoret på vänster delsträngar av s får då den naturliga tolkningen ”Om företaget saknar anställda, så kan ingen anställd sägas upp”. Låt nu med dessa tolkningar ψ(s) vara den ordning i vilken 1 , …, n avskedas, om de anställts i denna ordning av ett företag med personalförändringshistoria s (från start till konkurs; där konkursen förmodligen berodde på dålig arbetsmoral på grund av den undermåliga personalpolitiken :–). Det är då klart att ψ(s) ∈ S_{n}^{(321)} (för s ∈ M_{n}), eftersom ifall i < j < k vi har att om ψ(s)(i) > ψ(s)(k) och ψ(s)(j) > ψ(s)(k), både i och j måste vara anställda vid tidpunkten för avskedandet av k; och alltså i, som anställts före j, också måste avskedas före j, d. v. s. det måste då gälla att ψ(s)(i) < ψ(s)(j). Alltså är ψ_{n} en funktion från M_{n} till S_{n}^{(321)}. För att visa att ψ_{n} är en bijektion, räcker det att visa att det finns en invers θ_{n} : S_{n}^{(321)} ⟶ M_{n} till ψ_{n}. Givet σ ∈ S_{n}^{(321)}, konstruerar vi en binär sträng s = b_{1}b_{2} ⋯ med följande algoritmiska förfarande:

— Starta med 0 bit utskriven, och med ”hittills högsta lästa tal” h := 0.

— ”Läs in” σ(1), …, σ(n) i tur och ordning.

— — Om det senast lästa talet σ(i) är större än (gamla) h, så skriv ut σ(i) − h ettor, och sätt därefter h := σ(i). Oavsett om du skrev några ettor eller ej, så skriv till sist en nolla.

(Således är t. ex. θ_{n}((3, 1, 5, 2, 4, 6)) = 111001100010.) s får verkligen (precis) n ettor, eftersom varje gång inläsningen av ett σ(i) avslutats, h ettor har skrivits, och eftersom slutvärdet av h är n. Vidare har en nolla skrivits för varje i ∈ {1, …, n}, så s innehåller n nollor. Vidare, om en vänster delsträng s′ avslutas på den i:te nollan, så innehåller s′ i nollor, men max(σ(1), …, σ(i)) ettor, och det största av i stycken olika positiva heltal måste verkligen vara ≥ i. (En vänster delsträng s′ som slutar på 1 innehåller en vänster delsträng som är tom eller slutar på 0, och som har lika många nollor men färre ettor än s′; så s′ har t. o. m. strikt fler ettor än nollor.) Således ligger verkligen θ_{n}(σ) i M_{n}, om σ ∈ S_{n}^{(321)}; d. v. s. θ_{n} : S_{n}^{(321)} ⟶ M_{n}. Det är nu ganska lätt att inse (men krångligt att i en text formellt bevisa) att verkligen ψ_{n} och θ_{n} är varandras inverser.