Kombinatorik-Problem

29.11.2007, 10:27	Sommerzeit	Auf diesen Beitrag antworten »
Kombinatorik-Problem Hallo, ich habe folgendes Problem: Ich will herausfinden, wieviele Möglichkeiten es gibt, N nicht voneinander unterscheidbare Objekte auf M Fächer zu verteilen, wobei in jedes Fach beliebig viele Objekte passen. Anscheinend ist die Zahl der Möglichkeiten durch den Binomialkoeffizienten N + M - 1 über M - 1 gegeben. Wenn ich konkrete Fälle einsetze, stimmt das immer, aber ich habe keinen allgemeinen Beweis und nicht mal die kleinste Idee für einen Ansatz. Es wäre nett, wenn mir jemand einen Tipp geben könnte. Vielen Dank, Sommerzeit
29.11.2007, 10:35	AD	Auf diesen Beitrag antworten »
Stelle die $\begin{eqnarray} N \end{eqnarray}$ Objekte in eine Reihe. Die Fächereinteilung wird jetzt dadurch erreicht, dass du $\begin{eqnarray} M-1 \end{eqnarray}$ Zwischenwände irgendwo in der Reihe platzierst. Auf diese Art und Weise hast du eine Reihe bestehend aus $\begin{eqnarray} N+M-1 \end{eqnarray}$ Elementen: $\begin{eqnarray} N \end{eqnarray}$ Objekte und $\begin{eqnarray} M-1 \end{eqnarray}$ Zwischenwände. Und nun gibt es genau $\begin{eqnarray} \binom{N+M-1}{M-1} \end{eqnarray}$ Möglichkeiten, die $\begin{eqnarray} M-1 \end{eqnarray}$ Zwischenwände aus den $\begin{eqnarray} N+M-1 \end{eqnarray}$ möglichen Positionen auszuwählen, fertig.
29.11.2007, 10:40	Philipp Imhof	Auf diesen Beitrag antworten »
RE: Kombinatorik-Problem Eine (IMHO) anschauliche Erklärung: Du ordnest deine N Objekte in einer Reihe an: ********** Dazu gibt es N! Möglichkeiten. Nun schiebst du die (M-1) Trennwände dazwischen: \|\|\|\|*** Leere Fächer sind nicht verboten, also hast du nun (N+M-1)! Möglichkeiten, diese Zeichenfolge anzuordnen. Davon fallen diejenigen Möglichkeiten weg, in denen du nur Trennwände vertauschst. Und auch diejenigen, in welchen du nur die Objekte vertauschst. Also: $\begin{eqnarray} \frac{(n+m-1)!}{(m-1)!n!} \end{eqnarray}$ Und wenn wir jetzt $\begin{eqnarray} n = n+m-1 - (m-1) \end{eqnarray}$ schreiben, entspricht dies der Definition $\begin{eqnarray} \binom{n+m-1}{m-1} \end{eqnarray}$
29.11.2007, 14:15	Sommerzeit	Auf diesen Beitrag antworten »
Die mögliche Anordnung von Trennwänden, um die Verteilung zu erreichen, ist sehr anschaulich. Ich habe da immer in eine andere Richtung gedacht. Danke für die schnelle Hilfe!

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »