Kombinatorik: Anzahl von Klammerungen in einem Produkt

21.10.2015, 12:10	leuchtturmwaerter	Auf diesen Beitrag antworten »
Kombinatorik: Anzahl von Klammerungen in einem Produkt Meine Frage: Guten Tag, im Rahmen meiner Bachelorarbeit (Ingenieurwissenschaften) suche ich einen Lösungsansatz für folgendes Problem: Ein Produkt mit m Faktoren soll mit n Klammerpaaren geklammer werden. Wie viele Möglichkeiten/Kombinationen gibt es hierzu. Bsp. für m=3 und n=2: ((a))bc ((a)b)c ((a)bc) etc. Auch unsinnige Klammerungen (Doppelklammern um einen Faktor) sind erlaubt. Dieses mathematische Problem repräsentiert ein Problem aus der Physik. Meine Ideen: Für ein Klammerpaar und m Faktoren gibt es $\begin{eqnarray} 1+2+3+...+m = \frac{m(m+1)}{2} \end{eqnarray}$ Möglichkeiten, die Klammer zu setzen. Für n Klammerpaare gibt es dementsprechend $\begin{eqnarray} \left (\frac{m(m+1)}{2} \right )^n \end{eqnarray}$ Kombinationsmöglichkeiten. Dabei gibt es aber natürlich Dopplungen, da ja die Klammern voneinander nicht unterscheidbar sind. Aber wieviele Dopplungen gibt es? Hier hänge ich gerade.
22.10.2015, 15:09	Hubert1965	Auf diesen Beitrag antworten »
Ich kann leider keine explizite Formel liefern, sondern nur eine rekursive (aus der man eigentlich leicht eine explizite machen könnte). Die rekursive Formel wiederum habe ich aus berechneten Zahlen abgeleitet, weswegen ich auch nicht erklären kann, wie sich einzelne Bestandteile des gefundenen Ausdrucks aus der Angabe ableiten lassen. Hier ist mein Beitrag zur Lösungsfindung: m = Anzahl der Faktoren n = Anzahl der Klammerpaare U = Anzahl der möglichen Klammersetzungen wenn die Klammern unterscheidbar sind, also (), [], {} usw. je einmal verwendet werden G = Anzahl der möglichen Klammersetzungen wenn die Klammern gleich sind, wenn also nur () verwendet wird, dies aber n-mal Es ist leicht einzusehen, dass gilt: $\begin{eqnarray} G(m,n) = \frac{U(m,n)}{n!} \end{eqnarray}$ Zur Herleitung von $\begin{eqnarray} U(m,n) \end{eqnarray}$ habe ich ein Programm geschrieben, dass in vielen Durchläufen per Zufall alle möglichen Klammersetzungen erzeugt, und dann die Kombinationen zählt. Dabei erzeugt das Progamm für jede neue Kombination eine neue Schublade, und steckt gleiche Kombinationen in gleiche Laden. Es hört erst auf, wenn pro existierender Lade eine bestimmte Mindestmenge an Treffern gelandet ist und zählt dann, am Ende, die Laden. Dabei wurden diese Zahlen ermittelt: U(1,1) = 1 U(2,1) = 3 U(3,1) = 6 U(4,1) = 10 U(5,1) = 15 U(6,1) = 21 U(7,1) = 28 U(8,1) = 36 U(9,1) = 45 U(10,1) = 55 U(11,1) = 66 U(12,1) = 78 U(13,1) = 91 U(14,1) = 105 U(15,1) = 120 U(16,1) = 136 U(17,1) = 153 U(18,1) = 171 U(19,1) = 190 U(20,1) = 210 U(1,2) = 2 U(2,2) = 12 U(3,2) = 40 U(4,2) = 100 U(5,2) = 210 U(6,2) = 392 U(7,2) = 672 U(8,2) = 1080 U(9,2) = 1650 U(10,2) = 2420 U(11,2) = 3432 U(12,2) = 4732 U(13,2) = 6370 U(14,2) = 8400 U(15,2) = 10880 U(1,3) = 6 U(2,3) = 60 U(3,3) = 300 U(4,3) = 1050 U(5,3) = 2940 U(6,3) = 7056 U(7,3) = 15120 U(8,3) = 29700 U(9,3) = 54450 U(10,3) = 94380 U(1,4) = 24 U(2,4) = 360 U(3,4) = 2520 U(4,4) = 11760 U(5,4) = 42336 U(6,4) = 127008 U(1,5) = 120 U(2,5) = 2520 U(3,5) = 23520 U(1,6) = 720 U(2,6) = 20160 U(1,7) = 5040 Die gefundenen Zahlen erscheinen dadurch plausibel, dass sie alle durch $\begin{eqnarray} n! \end{eqnarray}$ teilbar sind, und darüber hinaus folgenden Beziehungen genügen: $\begin{eqnarray} U(m,1)=\frac{m^2+m}{2} \end{eqnarray}$ Diese Beziehung lässt sich auch leicht aus theoretischen Überlegungen aus der Aufgabenstellung ableiten Die gefundenen Zahlen genügen im Fall von $\begin{eqnarray} n>1 \end{eqnarray}$ auch dieser Beziehung: $\begin{eqnarray} U(m,n)=U(m,n-1) \cdot \frac{(m+n) \cdot (m+n-1)}{n+1} \end{eqnarray}$ Leider stehe ich auf dem Schlauch wenn es darum geht, diese rekursive Formel in eine explizite umzuwandeln. Vielleicht hilft, dass man $\begin{eqnarray} U(m,1) \end{eqnarray}$ auch so schreiben kann: $\begin{eqnarray} U(m,n=1)=1 \cdot \frac{(m+n) \cdot (m+n-1)}{n+1} \end{eqnarray}$ Außerdem gilt auch $\begin{eqnarray} U(1,n)=n! \end{eqnarray}$ was mit theoretischen Überlegungen übereinstimmt und somit die Plausibilität der berechneten Zahlen stützt, aber wie ich das verwenden kann, um daraus eine explizite Formel zu machen, weil ich leider nicht. Also leider nicht die ganze Lösung, aber wenigstens ein Schritt in die richtige Richtung.
22.10.2015, 19:09	HAL 9000	Auf diesen Beitrag antworten »
Die Rekursion (ob richtig oder nicht, vermag ich noch nicht zu beurteilen) mündet in eine mögliche explizite Formel $\begin{align} G(m,n) = \frac{1}{n+1}\cdot \binom{m+n-1}{n}\cdot \binom{m+n}{n} \end{align}$ . Bzw. eine Darstellung, an der man die Ganzzahligkeit dieses $\begin{align} G(m,n) \end{align}$ sehen kann: $\begin{align} G(m,n) = \binom{m+n-1}{n}\binom{m+n}{n} - \binom{m+n-1}{n-1}\binom{m+n}{n+1} \end{align}$ .
22.10.2015, 21:54	Hubert1965	Auf diesen Beitrag antworten »
Der Wert, der sich aus HALs Formel für $\begin{eqnarray} G(m,n) \end{eqnarray}$ ergibt, unterscheidet sich bei einer Überprüfung mit rund 200 Wertepaaren für $\begin{eqnarray} m,n \end{eqnarray}$ von den Werten aus meiner Formel für $\begin{eqnarray} U(m,n) \end{eqnarray}$ genau um den Faktor $\begin{eqnarray} n! \end{eqnarray}$ , was ein Indiz dafür ist, dass beide Formeln äquivalent sind (also dieselben Werte ergeben). Der Beweis für die Äquivalenz wäre eine Herleitung der einen Formel aus der anderen, das sollte machbar sein. Da die Werte aus den Formeln mit den Werten aus meiner Auszählung in allen Fällen übereinstimmen, halte ich die Formeln für richtig, aber das ist natürlich noch lange kein Beweis. Hierzu wäre es notwendig, irgendwie aus der Angabe eine der beiden Formeln herzuleiten. Derzeit haben wir also eine vermutlich richtige Formel, wissen aber nicht, warum sie richtig ist.
22.10.2015, 22:14	HAL 9000	Auf diesen Beitrag antworten »
Du hast mich missverstanden: Ich habe deine rekursive Darstellung von U sowie die Verbindung zu G herangezogen, um diese explizite Darstellung zu gewinnen. Das ist also kein Beweis für die Richtigkeit als Anzahlformel bezogen auf das ursprüngliche Problem.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »