TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 164

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?

Dieses Beispiel ist als verified_by_tutor markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)

Lösung nach der Übung:

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

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

Ich habe mir das so gedacht: Die Anzahl der Möglichkeiten ist immer ${\begin{pmatrix}AnzahlDerElementeAusDenenAusgewaehltWerdenKann\\ausgewaehlteElemente\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

(ü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\cdot 2+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

Anmerkung: Wieso ziehst du 6 Elemente? Es werden ja 7 Bücher gezogen...??? bzw. 19 stehen gelassen... wie kommst du zur Zahl 6?

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

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