Facit till rekommenderade uppgifter vecka 3

5.1.1

1, 127, 966, 1701, 1050, 266, 28, 1.

5.1.2

Det finns 2ⁿ funktioner från en mängd med n element till en mängd med två element. Av dessa är alla utom två surjektiva. Alltså finns det 2ⁿ-2 funktioner och eftersom detta antal också ges av 2!S_n,2 måste S_n,2=(2ⁿ-2)/2=2^n-1-1. Om vi skall dela in en mängd med n element i n-1 icke-tomma delar måste det bli n-2 delar som vardera innehåller ett element och en del som innehåller två element. Antalet sätt att göra en sådan indelning är lika med antalet sätt att plocka ut en tvådelmängd ur en mängd med n element.

5.2.1

Den första är reflexiv och transitiv men inte symmetrisk. Samma sak gäller den andra. Den tredje är reflexiv, symmetrisk och transitiv, så det är en ekvivalensrelation. Den fjärde är inte reflexiv och inte transitiv, men symmetrisk.

5.3.1

34 650.

5.3.3

Efter fyra drag har två pjäser av varje slag spelats ut. Ställningen beror inte på i vilken ordning de har placerats utan bara på vilka platser. Eftersom det finns nio rutor gäller det att lägga nio bollar i tre lådor så att det kommer två i den första (ena färgen), två i den andra (andra färgen) och fem i den tredje (tomma rutor).

5.4.1

[1⁷], [1⁵2], [1⁴3], [1³2²], [1³4], [1²23], [1²5], [12³], [124], [13²], [16], [2²3], [25], [34], [7].

5.4.2

Genom att i en partition av n i k delar minska varje del med ett får vi en partition av n-k i upp till k delar.

5.5.2

Exempelvis (1)(268974)(35). Observera att det finns flera som duger.

5.5.3

Konjugera st med t så får vi t(st)t^-1=ts. Eftersom konjugerade permutationer har samma typ har st och ts samma typ.

5.6.1

Tecknen är 1, -1 och 1.

5.6.4

(i) Möjlig. (Egentligen krävs en konstruktion för att visa att det faktiskt är möjligt.) (ii) Omöjlig.

5.7.1

908 107 200.

5.7.4

(12)(23)(45)(56)(78) och (13)(35)(57)(26). Tecknen är -1 respektive 1.

5.7.5

Visa exempelvis med induktion eller med sållprincipen.

5.7.6

Kontrollera reflexivitet, symmetri och transitivitet. Det finns elva ekvivalensklasser.

6.1.3

6, 5.

6.2.3

x=2, y=1 i Z₇. I Z₅ finns ingen lösning.

6.2.4

x=3 och x=5.

6.3.4

6, 13, 7, 8.

6.3.5

4.

6.6.1

(i) x=11k-2, där k är ett heltal. (ii) Det finns inga lösningar.

6.6.4

(i) x=5. (ii) x=4 och x=8.

6.6.5

7.

6.6.7

(i) 2. (ii) 3. (iii) 7. (iv) 5.