Diskrete Strukturen Übung 26.4.2001

Matthias Hensler 26. April 2001

Aufgabe P1

S = \{\underbrace{\{1, 9\}}_{U}, \{2, 8\}, \{3, 7\}, \{4, 6\}, \{5\}\}

|M| = 6

Pot ({1, …, 9}) → S
f : x ↦ U ∈ S
M → S

Aufgabe P2

( \begin{matrix}1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{matrix} ) ⇝ (1, 3, 2, 4)

( \begin{matrix}1 & 2 & 3 & 4 \\ 3 & 4 & 1 & 1 \end{matrix} ) ⇝ (1, 3)(2, 4)

P2.a

σ = (1, 3, 4, 6)(2, 3, 10, 5, 8, 7)

P2.b

σ(x) im Beispiel: σ(3) = 10

σ_{1}, σ_{2} : (σ_{1} ∘ σ_{2})(x) = σ_{1}(σ_{2}(x))

σ_{1} = (i_{1}, …, i_{r}), σ_{2} = (j_{1}, …, j_{r}) i_{k} ≠ j_{l} ∀k, l

σ_{1}σ_{2}(x) = \{ \begin{matrix}σ_{1}(x) & x ∈ \{i_{1}, …, i_{r}\} \\ σ_{2}(x) & x ∈ \{j_{1}, …, j_{r}\} \\ id(x) & sonst \end{matrix} \} = σ_{2} ∘ σ_{1}(x)

σ_{1} = (1, 2, 3)(4)

P2.c

σ^{4} := σ ∘ σ ∘ σ ∘ σ
( \begin{matrix}1 & 2 & 3 & 4 \\ 3 & 4 & 2 & 1 \end{matrix} )^{−1} = ( \begin{matrix}1 & 2 & 3 & 4 \\ 4 & 3 & 1 & 2 \end{matrix} )
∥  ∥
(1, 3, 2, 4)^{−1} = (1, 4, 2, 3)
σ^{−1} = (6, 4, 9, 1)(7, 8, 5, 10, 3, 2)

σ^{4} = (1)(9)(4)(6)(2, 8, 10)(3, 7, 5) = (2, 8, 10)(3, 7, 5)

σ^{12} = id

σ^{123} = σ^{3} ∘ σ^{120} = σ^{3} ∘ (σ^{12})^{10} = σ^{3} = (1, 6, 4, 9)(2, 5)(3, 8)(10, 7)

Aufgabe P3

( \begin{matrix}1 & 2 & 3 & 4 \\ x_{1} & x_{2} & x_{3} & x_{4} \end{matrix} )
x_{1} x_{2} x_{3} x_{4}
1 2 3 4 id
1 2 4 3 (3,4)
1 3 2 4 (2,3)
1 3 4 2 (2,3,4)=(2,3)(3,4)(4,3)(4,2)
1 4 2 3  ⋯
1 4 3 2
2 1 3 4 ⋮
2 1 4 3
⋮ ⋮ ⋮ ⋮  ...

(1, 2, 3, 4, …, n) = (1, 2)(2, 3)(3, 4) … (n − 1, n)

\begin{aligned}S_{4} = & \{id, (12), (13), (14), (23), (24), (34), (123), (132), (124), (142), (134), (143), (234), (243), \\ & (1234), (1432), (1324), (1423), (1342), (1243), (12)(34), (13)(24), (14)(23)\} \end{aligned}

Aufgabe P4

P4.a

∑_{k=0}^{n} \binom{n}{k}^{2} = ∑_{k=0}^{n} \binom{n}{k}\binom{n}{k} = ∑_{k=0}^{n} \binom{n}{k}\binom{n}{n − k} = \binom{n + n}{n} = \binom{2n}{n}

Kombinatorisch: aus n Frauen und n Männern eine n-Gruppe auswählen.

P4.b

∑_{k=1}^{n} k\binom{n}{k}^{2} = ∑_{k=1}^{n} k\binom{n}{k}\binom{n}{n − k} = n\binom{2n − 1}{n − 1}

Kombinatorisch: aus n Frauen und n Männern eine n-Gruppe auswählen und eine (weibliche/männliche) Person als Lehrer bestimmen.