****************************************************************
* Multiple-Choice-Test Diskrete Strukturen Sommersemester 2018 *
*                   (Gedächtnisprotokoll)                      *
*--------------------------------------------------------------*
* Aufgabenstellungen sind paraphrasiert. Richtige Antworten    *
* sind angekreuzt.                                             *
****************************************************************

Aufgabe 1:

Eine Fußballmannschaft besteht aus 10 ununterscheidbaren Fußballspielerinnen und einer Torhüterin. Aus 
einer Schulklasse mit 26 Schülerinnen soll eine Fußballmannschaft aufgestellt werden. Wieviele mögliche
Besetzungen gibt es?


( )  26**11

          /26\
(X)  11 * \11/

     /26\
( )  \11/

          /25\
(X)  26 * \10/


Aufgabe 2:

Es bezeichne a_n die Anzahl der n-langen Wörter über dem Alphabet {a,b}, die die Zeichenkette "bbb" 
nicht enthalten. a_1 = 2, a_2 = 4 und a_3 = 7. Welche der folgenden rekursiven Ausdrücke sind korrekt?
                                
( )  a_n = a_(n-1) + a_(n-2) + 2**(n-1) - a_(n-3)
( )  a_n = a_(n-1) + a_(n-2) + 2**n     - a_(n-3)
( )  a_n = a_(n-1) + 4 * a_(n-3)
(X)  a_n = a_(n-1) + a_(n-2) + a_(n-3)


Aufgabe 3:

Gegeben seien folgende Permutationen:

      / 1 2 3 4 5 \         / 1 2 3 4 5 \
π_1 = \ 5 3 1 4 2 /   π_2 = \ 3 5 1 2 3 /

Welche der folgenden Zykelschreibweisen beschreiben die Permutation, die entsteht, wenn man π_1 und π_2 
nach einander anwendet?

( )  (421)(53)
(X)  (5)(214)(3)
( )  (53)(124)
( )  (5)(124)(3)


Aufgabe 4:

Sei P(n,k) Anzahl ungeordneter k-Partitionen der Zahl n. Sei S(n,k) die Anzahl möglicher k-Partitionen 
einer n-elementigen Menge.
Elf Frauen und sieben Männer sollen vier Gruppen bilden, sodass in jeder Gruppe mindestens eine Frau und 
ein Mann vorhanden ist. Wieviele Gruppenbelegungen sind möglich?

( )  P(7,4) + P(11,4)
(X)  S(7,4) + S(11,4)
( )  4! (S(7,4) + S(11,4))
( )  S(7+11,4)


Aufgabe 5:

Ihre Schallplattensammlung beinhaltet 11 unterscheidbare Jazz-Platten und 11 unterscheidbare 
Klassik-Platten. Ihr Regal bietet Platz für 15 nebeneinanderliegende Platten. Wieviele vollständige 
Belegungen des Regals sind möglich, wenn alle Platten des selben Genres zu einander benachbart sein 
sollen.

                       ----
                       \                   /11\
( )                    /                   \ i/
                       ----
          i,j in {1,2,3,...,11} und i+j=15

                       ----
                       \                   /11\ /11\
( )                    /                   \ i/ \ j/
                       ----
          i,j in {1,2,3,...,11} und i+j=15

                       ----
                       \                   /11\ /11\
( )                    /                   \ i/ \ j/ i! j!
                       ----
          i,j in {1,2,3,...,11} und i+j=15

                       ----
                       \                   /11\ /11\
(X)  2!                /                   \ i/ \ j/ i! j!
                       ----
          i,j in {1,2,3,...,11} und i+j=15


Aufgabe 6:

Sei P(n,k) Anzahl ungeordneter k-Partitionen der Zahl n. Sei S(n,k) die Anzahl möglicher k-Partitionen
einer n-elementigen Menge.
Auf eine in vier unterscheidbare Segmente aufgeteilte Dartscheibe werden zwölf nicht unterscheidbare 
Pfeile geworfen. Jeder Pfeil trifft ein Segment und jedes Segment wird von mindestens einem Pfeil 
getroffen. Wieviele Verteilungen der Pfeile auf die Segmente sind möglich.


( )  P(12,4)


(X)  S(12,4)


( )  4! S(12,4)

     /11\
( )  \ 3/