TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 159

Aus VoWi
< TU Wien:Algebra und Diskrete Mathematik UE (diverse)‎ | Übungen SS19
Version vom 7. März 2019, 16:54 Uhr von Gittenborg (Diskussion | Beiträge) (Gittenborg verschob die Seite TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen WS18/Beispiel 159 nach TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 159 und überschrieb dabei eine Weiterleitung: versch…)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen

Wieviele Möglichkeiten gibt es, aus einem 32-bändigen Lexikon genau 7 Bücher auszuwählen, wobei zwischen zwei ausgewählten Bänden immer mindestens einer im Regal stehen bleiben soll?

Lösung nach der Übung:[Bearbeiten]

Unser Übungsgruppenleiter hat es mit folgender Formel gerechnet:

\begin{pmatrix} n-(k-1)*a\\ k \end{pmatrix}

wobei a die anzahl der Bücher ist die zwischen 2 ausgewählten stehenbleiben muss.

wobei ich persöhnlich dieser Lösung auch eher Skeptisch gegenüberstehe

mfg -- DeepB

Lösung von Aeroflare[Bearbeiten]

Zum zeigen wie ich auf die Lösung gekommen bin stell ich die Lösung in einem Miniuniversum mit einem 6-bändigen Lexikon dar.

Angenommen man muss nur einen Band rausnehmen: 123456 123456 123456 123456 123456 123456

Hier sieht man, dass es 6 Möglichkeiten gibt also \begin{pmatrix} 6 \\ 1 \end{pmatrix} allgemein: \begin{pmatrix} n \\ k \end{pmatrix}

Das Selbe mit 2 Bändern: 123456 123456 123456 123456 123456 123456 123456 123456 123456 123456 => 10 Möglichkeiten \begin{pmatrix} 6-1 \\ 2 \end{pmatrix} allgemein: \begin{pmatrix} n-1 \\ k \end{pmatrix}

Mit 3 Bändern: 123456 123456 123456 123456 => 4 Möglichkeiten \begin{pmatrix} 6-2 \\ 3 \end{pmatrix} allgemein: \begin{pmatrix} n-2 \\ k \end{pmatrix}

Mit 4 Bändern: geht nix \begin{pmatrix} 6-3 \\ 4 \end{pmatrix} allgemein: \begin{pmatrix} n-3 \\ k \end{pmatrix}

So kann man die Formel auf 7 weiterführen und erhält: \begin{pmatrix} n-k+1 \\ k \end{pmatrix}

Was folgendes ergibt: \begin{pmatrix} 32-6 \\ 7 \end{pmatrix} = 657800

Lösung von D4ni31[Bearbeiten]

Ich habe mir das so gedacht: Die Anzahl der Möglichkeiten ist immer \begin{pmatrix} Anzahl Der Elemente Aus Denen Ausgewaehlt Werden Kann \\ ausgewaehlte Elemente \end{pmatrix}

Insgesamt gibt es 32 Bücher aus denen 7 ausgewählt werden. Da zwischen 2 ausgewählten Bänden immer mindestens einer im Regal bleiben muss haben wir 6 Bücher die nicht ausgewählt werden können. Es gibt also 32-6 Auswahlmöglichkeiten.

Daher: \begin{pmatrix} 32-6 \\ 7 \end{pmatrix}

Lösung von Karotte[Bearbeiten]

(überarbeitet von --MatheFreak 00:08, 11. Dez. 2010 (CET))

Meiner Meinung nach war die verwendete Formel im ersten Lösungsversuch ganz oben vom Übungsleiter korrekt, jedoch nicht der Lösungsweg ersichtlich. Letztendlich lässt sich diese Problemstellung auf ein Auswahl aus einer Teilmultimenge, die sich mit \begin{pmatrix} n + k - 1\\ k \end{pmatrix} berechnen lässt. Man muss sich nur klar werden, welche Werte die n und k annehmen. (Siehe Buch Seite 50/51, Auswählen einer Teilmultimenge)

Wir wählen 7 Bücher aus, zwischen je 2 ausgewählten muss mindestens eins im Regal stehenbleiben, macht folgende fixe Reihenfolge:

|Ao|Ao|Ao|Ao|Ao|Ao|A|

die 7 A's sind unsere ausgewählten Bücher, die o's stehen für die Bücher, die unbedingt dazwischen stehen bleiben müssen. In den Zwischenräumen steht der Platzhalter | für beliebig viele andere Bände (die stehen bleiben oder auch nicht; je nach Auwahl unserer 7 Bücher).

In der Kombinatorik wird immer aus einer Menge gezogen; in unserem Fall einer Multimenge, weil ein Element dieser Menge einem Buch entspricht, dass an einem bestimmten Platz stehen kann. Aber nachdem an jedem Platzhalter mehrere Bücher stehen können, muss jedes Element in der Menge öfters (theoretisch unendlich oft) vorkommen muss. Diese Multimenge definieren wir uns also wie folgt:
 M = \{a_{1}, a_{2}, a_{3}, \ldots a_{8} \} wobei a_{i} für ein Buch steht, dass beim i-ten Platzhalter eingefügt wird.
Daraus ergibt sich unser  n = \left| M \right| = 8
Jetzt haben wir unsere Menge aus der unsere Elemente der Reihe nach gezogen werden, aber wie oft muss gezogen werden? Von unseren 32 Plätzen sind bereits 13=6\cdot2+1 (einfach durch das abzählen aller 'A' und 'o' nachprüfbar) fix belegt. Es bleiben also noch 19 freie Plätze, die durch die Bücher belegt werden können, die wir aus unserer Menge ziehen \Rightarrow k = 19

D.h. aus einer theoretischen Ziehung von 6 Elementen von \{a_{1}, a_{1}, a_{5}, a_{6}, a_{6}, a_{8} \} würde bedeuten, dass

  • 2 Bücher vor dem 1. von uns gewählten Buch stehen
  • 1 Buch vor dem 5. von uns gewählten Buch steht (wenn man das 'o' mit zählt eigentlich 2, aber das 'o' haben wir schon in dem n berücksichtigt)
  • 2 Bücher vor dem 6. von uns gewählten Buch stehen
  • 1 Buch nach dem 7. (und letzten) von uns gewählten Buch steht

Mit der Formel können wir nun alle Möglichkeiten ausrechnen, die übriggebliebenen Bücher auf diese 8 Stellen zu verteilen, daher müsste die Lösung wie folgt lauten: { n + k - 1\choose k } = { 19 + 8 - 1 \choose 19 } also 8 Stellen (Unsere Elemente in der Menge, also die Anzahl der unterschiedlichen Kugeln die wir haben, bei dieser Formel sind von jeder der Kugel unendlich viele vorhanden) + Eine Auswahl von 19 Elementen aus der Menge, jede gezogene a1 Kugel entspricht einem Buch an der Stelle 1, jede a2 Kugel einem Buch an der Stelle 2 usw.

Somit haben wir alle Möglichkeiten durch :)

- So long, Karotte

Kontrolle von Irfy[Bearbeiten]

Dieses kurze Java Programm bestätigt die Zahlen von Aeroflare und Karotte.

  public class Main {
    public static void main(String[] args) {
      System.out.println(select(6, 1, 1));
      System.out.println(select(6, 2, 1));
      System.out.println(select(6, 3, 1));
      System.out.println(select(6, 4, 1));
      System.out.println(select(32, 7, 1));
    }
  
    private static int select(int n, int k, int d) {
      if (k == 1) {
        return n;
      }
      int sum = 0;
      for (int i = 1; i <= n - (k - 1) * (d + 1); ++i) {
        sum += select(n - i - d, k - 1, d);
      }
      return sum;
    }
  }

Parameter d mit dem Wert 1 entspricht der Bedingung dass zwischen zwei ausgewählten Bänden immer mindestens einer im Regal stehen bleiben soll. Output:

6
10
4
0
657800