Kombinatorik mit Nebenbedingungen? Das Dominostein-Problem

06.09.2019, 12:45	JohnMalt1	Auf diesen Beitrag antworten »
Kombinatorik mit Nebenbedingungen? Das Dominostein-Problem Hallo zusammen, ich grübele schon länger an einem Problem, welches ich hier mal ausführen möchte, da ich noch keine zufriedenstellende Lösung gefunden habe. Das Problem lässt sich zumindest als eine "typische Kombinatorik"-Aufgabe formulieren, ob es aber wirklich in die Kategorie passt, kann ich nicht sicher sagen. Üblicherweise geht es ja häufig um $\begin{eqnarray} N \end{eqnarray}$ unterscheidbare Kugeln, bspw. durch Beschriftung mit $\begin{eqnarray} 1,\ldots,N \end{eqnarray}$ , die aus einer Urne gezogen werden. Gesucht wird dann die Anzahl an Kombinationen, $\begin{eqnarray} k \end{eqnarray}$ Kugeln zu ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge. Diese Aufgabenstellung möchte ich etwas erweitern. Wir behalten die Urne bei und tauschen die Kugeln durch Dominosteine. Jeder Dominostein ist eindeutig unterscheidbar durch die Beschriftung zweier unterschiedlicher Zahlen (ohne Reihenfolge) von $\begin{eqnarray} 1,\ldots,n \end{eqnarray}$ , also $\begin{align} (i; j), i=1,\ldots,n-1,\quad j=i+1,\ldots,n. \end{align}$ Damit haben wir insgesamt $\begin{align} N_n=\sum_{a=0}^{n-1} a = \frac{n(n-1)}{2} \end{align}$ mögliche Dominosteine, nämlich $\begin{align} (1;2), (1;3), \ldots, (1;n), (2;3), \ldots, (2;n), \ldots, (n-1;n) \end{align}$ Soweit zu den Grundvoraussetzungen. Würde ich einfach nur wieder $\begin{eqnarray} k \end{eqnarray}$ Dominosteine ziehen ohne Zurücklegen und ohne Beachtung der Reihenfolge der gezogenen Dominosteine, würde ich keine andere Fragestellung erreichen. Daher nun die neue Frage: Wie viele Kombinationen gibt es, $\begin{eqnarray} k \end{eqnarray}$ Dominosteine zu ziehen, ohne eine Zahl doppelt zu haben? Wenn ich also den Dominostein $\begin{eqnarray} (3;4) \end{eqnarray}$ ziehe, dürfen keine anderen Dominosteine mit einer $\begin{eqnarray} 3 \end{eqnarray}$ oder einer $\begin{eqnarray} 4 \end{eqnarray}$ gezogen werden. Diese Aufgabenstellung habe ich auch bereits gelöst und ist nicht weiter schwer. Dafür muss man sich Überlegen, dass jede Zahl auf genau $\begin{eqnarray} n-1 \end{eqnarray}$ Dominosteinen vorhanden ist. Für $\begin{eqnarray} k=1 \end{eqnarray}$ gibt es natürlich einfach $\begin{eqnarray} N_n= \frac{n(n-1)}{2} \end{eqnarray}$ "Kombinationen". Für $\begin{eqnarray} k=2 \end{eqnarray}$ bedeutet es, dass der erste Dominostein "frei" gewählt werden kann, für den zweiten Dominostein muss man aber nicht nur den gezogenen Dominostein entfernen, sondern man muss die je $\begin{eqnarray} n-2 \end{eqnarray}$ Dominosteine mit der ersten und der zweiten Zahl entfernen. Es verbleiben also für den zweiten Dominostein $\begin{align} N_n-1-2(n-2) = \frac{n(n-1)}{2} -1-2(n-2) = \frac{(n-2)(n-3)}{2} = N_{n-2} \end{align}$ Das ist widerum klar, man kann ja auch einfach überlegen, dass man einfach als ersten Dominostein den mit der $\begin{eqnarray} (n-1;n) \end{eqnarray}$ auswählt und dann fallen alle Dominosteine mit den höchsten beiden Zahlen weg, also verbleiben genau die Dominosteine, als würde man nur bis $\begin{eqnarray} n-2 \end{eqnarray}$ zählen, anstatt bis $\begin{eqnarray} n \end{eqnarray}$ . Für die Anzahl der Kombinationen muss man natürlich das Produkt noch durch $\begin{eqnarray} 2! \end{eqnarray}$ teilen, wenn die Reihenfolge nicht berücksichtigt werden soll. Es gibt also $\begin{align} \frac{N_n\cdot N_{n-2}}{2} \end{align}$ Damit sieht man schnell, dass für die Anzahl an Kombinationen für allgemeines $\begin{eqnarray} k \end{eqnarray}$ gilt: $\begin{align} \frac{N_n\cdot N_{n-2}\cdot N_{n-4}\cdot\ldots\cdot N_{n-2(k-1)}}{k!} \end{align}$ Jetzt komme ich zur eigentlichen Problematik, bei welcher ich nicht weiterkomme: Was ist, wenn man eine beliebige, aber feste Menge von Dominosteinen vorweg aus der Urne nimmt. Wie lassen sich nun die Anzahl der Kombinationen "vernünftig" berechnen. Mir würden da auch einige "wenn, dann" ausreichen oder sonstige Hilfen. Ich habe diese Problemstellung in einem Programm, wo $\begin{eqnarray} n=45 \end{eqnarray}$ und $\begin{eqnarray} k\in[1,9] \end{eqnarray}$ gilt. Wenn ich dann aber aus den verfügbaren $\begin{eqnarray} 990 \end{eqnarray}$ Dominosteinen eine "zufällige" (bei mir ist es nicht zufällig, aber gehen wir einfach mal von einer Zufallsmenge aus, da ich keine konkreten Angaben dazu machen kann) Menge von etwa $\begin{eqnarray} 400 \end{eqnarray}$ Dominosteinen herausnehme, habe ich keine bessere Lösungsidee bisher, einfach schleifenweise einen Dominostein nach dem anderen von den $\begin{eqnarray} 590 \end{eqnarray}$ Verfügbaren zu ziehen und jedes Mal die Menge der übrigen verfügbaren Dominosteine zu ermitteln und wieder über diese iterieren. Da aber am Ende eine sehr große Anzahl an Kombinationen entsteht, ist es spätestens ab $\begin{eqnarray} k>4 \end{eqnarray}$ zeitlich unmöglich, es auf diese Weise zu berechnen. Für $\begin{eqnarray} k=9 \end{eqnarray}$ würde die Rechenzeit mit meinem Rechner sicherlich mehrere Wochen oder Jahre betragen. Ich bin für jede Hilfe dankbar oder auch über jegliche Literaturhinweise, wo solche oder ähnliche Probleme behandelt werden. Kann mir jemand helfen?

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »