Nr
Uppgift
Poäng
1
[Biggs 5.1.2] Bevisa att S(n,2)=2n-1-1.
3
Lösning: Vi kan lösa problemet kombinatoriskt dvs räkna antalet partitioner av en mängd med n element i två delar. Om vi först ser det som att lägga n bollar i 2 lådor får vi 2n sätt att göra detta. En partition består av icke-tomma delar och ordningen mellan delarna saknar betydelse. Det finns två sätt att lägga bollarna i två lådor så att en låda blir tom. När vi tagit bort dessa två fall får vi dela med två eftersom ordninen saknar betydelse.
Alltså är S(n,2)=(2n-2)/2=2n-1-1.
2
[Biggs 5.3.3] Visa att antalet olika möjliga ställningar efter fyra drag i tic-tac-toe är 756.
3
Lösning: Vi har nio rutor på spelplanen. Efter fyra drag står där två spelpjäser från den ena spelaren och två från den andra. Det finns också fem tomma rutor. Det går inte att avgöra i vilken ordning spelpjäserna ställts dit. Alltså får vi att antalet ställningar ges av antalet sätt att lägga nio bollar i tre lådor så att det kommer fem i den första, två i den andra och två i den tredje, dvs
3
[Biggs 5.7.1 Hur många ord med fjorton bokstäver kan man bilda av bokstäverna i ordet "klassifikation".
3
Lösning: Om vi ser de olika bokstäverna som ingår som lådor och positionerna i ordet som bollar gäller det att lägga fjorton bollar i nio lådor så att det kommer 3 i den första (I), 2 i den andra (K), 2 i den tredje (A), 2 i den fjärde (S) och en i var och en av de fem andra (L,F,T,O,N). Antalet sätt att göra detta ges av
4
[Biggs 5.7.4] Låt a och b vara de element i S8 som i cykelnotation skrivs a=(123)(456)(78) och b=(1357)(26)(4)(8) . Bestäm tecknet för a och tecknet för b och uttryck a och b som en produkt av så få transpositioner som möjligt.
3
Lösning: Vi kan räkna ut tecknet genom att se på längderna av cyklerna. Varje cykel av udda längd har tecken +1 och varje cykel av jämn längd har teecken -1. I det första fallet blir alltså tecket (+1)×(+1)×(-1)=-1. För den andra permutationen har vi två cykler av jämn längd och två av udda, vilket ger (-1)×(-1)×(+1)×(+1)=+1.Vi kan skriva permutationerna som produkter av transpositioner genom att skriva varje cykel för sig som en produkt av transpositioner. Vi får a=(12)(23)(45)(56)(78) och b=(13)(35)(57)(26).
Om det skulle gå att skriva a med färre transpositioner måste det vara med högst tre transpositioner. En produkt av högst tre transpositioner kan bara flytta på högst sex element men då skulle det finnas två fixpunkter för a, dvs element som går på sig själva, men det finns inga fixpunkter alls för a.
Om b skulle kunna skrivas med färre transpositioner måste det vara högst två stycken. Det medför att den bara kan flytta på högst fyra element. Det skulle då finnas minst fyra fixpunkter, vilket det inte gör.
5
[Biggs 5.7.5] Visa att S(n,3)=(3n-1+1)/2-2n-1.
3
Lösning: Vi kan visa detta med hjälp av induktion. Det första värde på n där uttrycket har någon mening är för n=3 då vi har S(3,3)=1 eftersom det bara finns ett sätt att dela in en mängd med tre element i tre delar. Högerledet för n=3 är (33-1+1)/2-23-1=(9+1)/2-4=5-4=1.
Vi kan nu anta att påståendet per induktion är sant för n=k, dvs att S(k,3)=(3k-1+1)/2-2k-1. Vi vill nu visa att det också är sant för n=k+1. Rekursionsformeln för Stirlingtal ger S(k+1,3)=S(k,2) + 3 S(k,3) = [enligt induktionsantagandet] = S(k,2) + 3((3k-1+1)/2-2k-1) = S(k,2) + (3k+1)/2 + 1-3×2k-1 = [enligt tidigare uppgift] =2k-1 + (3k+1)/2 + 1-(2+1)×2k-1 =(3k+1)/2 -2k, vilket är lika med högerledet för n=k+1.
Alltså följer av induktionsprincipen att S(n,3)=(3n-1+1)/2-2n-1 för alla n³3.
6
[Biggs 6.3.8] Bevisa genom att betrakta produkten av alla nollskilda element i Zp att (p-1)!+1 är delbart med p.
6
Lösning: Vi tar produkten av alla element i Zp som inte är lika med 0. Det är p-1 stycken. Vi får (p-1)!. Å andra sidan vet vi att alla element i Zp som inte är noll har en invers. De enda elementen som är sina egna inverser är 1 och -1, som är lösningarna till x2=1. Att de är de enda lösningarna ser vi genom att skriva x2-1=(x+1)(x-1). Eftersom alla element utom 0 är inverterbara i Zp kan vi inte ha en produkt som är noll utan att någon av faktorerna är noll. Alla andra element utom +1 och -1 är alltså olika sina inverser. När vi tar produkten av alla nollskilda element kan vi para dem med sina inverser och dessa produkter blir alltid 1. De enda element som blir kvar är +1 och -1, vars produkt är -1. Därmed är (p-1)! = -1 i Zp.
7
Visa att varje permutations i Sn kan skrivas som en produkt av transpositionerna (12), (23), ...,(n-1 n).
6
Lösning: Om a är en permutation som tar n till k kan vi multiplicera a med (n-1 n)(n-1 n-2)... (k k+1) till vänster så får vi en permutation som tar n till n. Per induktion kan vi anta att denna permutation kan skrivas som en produkt av transpositionerna (12), (23), ...,(n-2 n-1). Eftersom inversen av (n-1 n)(n-1 n-2)... (k k+1) kan skrivas som en produkt av transpositionerna (12), (23), ...,(n-1 n) kan a skrivas som en produkt av transpositionerna (12), (23), ...,(n-1 n). Bassteget i induktioen är att en permutation i S1kan skrivas som en produkt av transpositioner vilket är en trivialt, eftersom det inte behövs några transpositioner alls.