MATHEMATISCHES INSTITUT DER UNIVERSITÄT MÜNCHEN Dr. W. Spann, G. Kleen SS 2023

Programmieren I für Studierende der Mathematik

Aufgabe 6

Sei n ∈ ℕ und k_{1}, …, k_{l} ∈ ℕ_{0} (l ≥ 2) mit k_{1} + … + k_{l} = n.

\binom{n}{k_{1}, …, k_{l}} := \frac{n!}{k_{1}!k_{2}! ⋯ k_{l}!}

wird als Multinomialkoeffizient bezeichnet. Er gibt an, wieviele n-Tupel aus l paarweise verschiedenen Elementen x_{1}, …, x_{l} gebildet werden können, wenn jedes x_{i} genau k_{i}-fach im n-Tupel vorkommen soll.

Die Berechnung von Multinomialkoeffizienten lässt sich über die Formel

\binom{n}{k_{1}, …, k_{l}} = \binom{n}{k_{1}}\binom{n − k_{1}}{k_{2}} ⋯ \binom{n − k_{1} − … − k_{l−2}}{k_{l−1}}

auf die Berechnung von Binomialkoeffizienten zurückführen.

Erstellen Sie eine Funktion mit Ergebnistyp double zur Berechnung des Multinomialkoeffizienten. Die Funktion soll 0 zurückgeben und den Fehler EDOM setzen, wenn unzulässige Argumente eingesetzt werden. Die Berechnung der Binomialkoeffizienten soll mit der in der Vorlesung besprochenen Methode durchgeführt werden. Benutzen Sie aus Effizienzgründen die Beziehung \binom{n}{k} = \binom{n}{n−k}, wenn n ≥ k > \frac{n}{2}, und behandeln Sie auch die Fälle k = n und k = 0 korrekt.

Testen Sie Ihr Programm an folgenden Beispielen:

(a)  \binom{8}{2, 3, 3},  \binom{50}{20, 20, 10},  \binom{100}{25, 11, 37, 27},  \binom{500}{200, 150, 20, 80, 50}.

(b)  ∑_{k_{1}=0}^{n} ∑_{k_{2}=0}^{n−k_{1}} \binom{n}{k_{1}, k_{2}, n − k_{1} − k_{2}}x^{k_{1}}y^{k_{2}}z^{n−k_{1}−k_{2}}

mit einzulesenden (und wieder auszugebenden) reellen x,y,z und n ∈ ℕ.

Bearbeitungszeitraum: bis Freitag, 16.6.2023, 12^{00}