Verteilung von Gruppen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 14:12 Di 15.02.2011 | | Autor: | kewlBandit |
| Aufgabe | | Wie viele Möglichkeiten gibt es, m verschiedenfarbige Gruppen von je a Kugeln auf c Urnen so aufzuteilen, dass exakt t Urnen belegt sind und sich in keiner Urne mehr als eine Kugel einer Farbe befindet? Für die Parameter gilt: c > t >= a, m > 1. |
Hallo, diese Aufgabe ist aus der Nachrichtentechnik, eigentlich geht es um Kanalbelegungen. Ich habe sie in obiges Urnenmodell übersetzt.
Mein Ansatz ist folgender:
N = T * V = Möglichkeiten, t aus c zu wählen * Möglichkeiten, Kugeln auf t Urnen zu verteilen .
Da exakt t Urnen belegt werden sollen, berechne ich erst einmal, wie viele Möglichkeiten es gibt, t aus c auszuwählen. Das sind:
T = [mm] \vektor{c \\ t}.
[/mm]
Der zweite Schritt besteht meiner Meinung nach darin, zu berechnen, wie viele Möglichkeiten es gibt, diese t Urnen gemäß den Randbedingungen mit Kugeln zu füllen. Die Randbedingungen waren:
- I. In jeder Urne mind. 1 Kugel
- II. In keiner Urne mehr als 1 Kugel einer Farbe
Hierin liegt genau mein Problem: Verteile ich die Kugeln der Farbe nach, so erfülle ich auf jeden Fall Bed. II. Die Anzahl an Möglichkeiten wäre
V = [mm] \vektor{t \\ a}^{m}. [/mm]
Allerdings zähle ich hierbei auch die Möglichkeiten, dass manche Urnen leer bleiben. Das verstößt gegen Bedingung I. Daher mein 2. Ansatz: Zunächst fülle ich jede Urne mit je einer Kugel, danach verteile ich die übrig gebliebenen der Farbe nach. Das führt auf
V = [mm] \vektor{t \\ a} [/mm] * [mm] \vektor{t - a \\ a} [/mm] * ... * [mm] \vektor{t-r*a \\ t-r*a} [/mm] * [mm] \vektor{r*a \\ a-(t-r*a)} [/mm] * [mm] \vektor{t \\ a}^{m-r-1}
[/mm]
Der Fall [mm] \vektor{r*a \\ a-(t-r*a)} [/mm] rührt daher, dass es noch weniger als a Urnen zu füllen gibt, diese aber gefüllt werden müssen, das legt [mm]t-r*a[/mm] Positionen für die aktuelle Farbe fest. Die restlichen Kugeln dieser Farbe (a-(t-r*a)) können beliebig auf die anderen Urnen verteilt werden. Allerdings glaube ich hier zu wenige Möglichkeiten zu zählen. Hat jemand eine Idee?
(Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.)
|
|
| |
|
> Wie viele Möglichkeiten gibt es, m verschiedenfarbige
> Gruppen von je a Kugeln auf c Urnen so aufzuteilen, dass
> exakt t Urnen belegt sind und sich in keiner Urne mehr als
> eine Kugel einer Farbe befindet? Für die Parameter gilt: c
> > t >= a, m > 1.
> Hallo, diese Aufgabe ist aus der Nachrichtentechnik,
> eigentlich geht es um Kanalbelegungen. Ich habe sie in
> obiges Urnenmodell übersetzt.
>
>
> Mein Ansatz ist folgender:
>
> N = T * V = Möglichkeiten, t aus c zu wählen *
> Möglichkeiten, Kugeln auf t Urnen zu verteilen .
>
>
> Da exakt t Urnen belegt werden sollen, berechne ich erst
> einmal, wie viele Möglichkeiten es gibt, t aus c
> auszuwählen. Das sind:
>
> T = [mm]\vektor{c \\ t}.[/mm]
>
> Der zweite Schritt besteht meiner Meinung nach darin, zu
> berechnen, wie viele Möglichkeiten es gibt, diese t Urnen
> gemäß den Randbedingungen mit Kugeln zu füllen. Die
> Randbedingungen waren:
> - I. In jeder Urne mind. 1 Kugel
> - II. In keiner Urne mehr als 1 Kugel einer Farbe
>
> Hierin liegt genau mein Problem: Verteile ich die Kugeln
> der Farbe nach, so erfülle ich auf jeden Fall Bed. II. Die
> Anzahl an Möglichkeiten wäre
>
> V = [mm]\vektor{t \\ a}^{m}.[/mm]
>
> Allerdings zähle ich hierbei auch die Möglichkeiten, dass
> manche Urnen leer bleiben. Das verstößt gegen Bedingung
> I. Daher mein 2. Ansatz: Zunächst fülle ich jede Urne mit
> je einer Kugel, danach verteile ich die übrig gebliebenen
> der Farbe nach. Das führt auf
>
> V = [mm]\vektor{t \\ a}[/mm] * [mm]\vektor{t - a \\ a}[/mm] * ... *
> [mm]\vektor{t-r*a \\ t-r*a}[/mm] * [mm]\vektor{r*a \\ a-(t-r*a)}[/mm] *
> [mm]\vektor{t \\ a}^{m-r-1}[/mm]
>
> Der Fall [mm]\vektor{r*a \\ a-(t-r*a)}[/mm] rührt daher, dass es
> noch weniger als a Urnen zu füllen gibt, diese aber
> gefüllt werden müssen, das legt [mm]t-r*a[/mm] Positionen für die
> aktuelle Farbe fest. Die restlichen Kugeln dieser Farbe
> (a-(t-r*a)) können beliebig auf die anderen Urnen verteilt
> werden. Allerdings glaube ich hier zu wenige Möglichkeiten
> zu zählen. Hat jemand eine Idee?
Wie bei komplexeren Kombinatorikaufgaben üblich, kommen
geeignete Ideen nicht so schnell. Mir ist es dann oft eine
Hilfe, zuerst ein konkretes Beispiel mit gewählten Parameter-
werten zu betrachten. Ich würde hier etwa vorschlagen:
$\ m=3$ (3 Farben Rot, Grün, Blau)
$\ a=4$
$\ m*a=3*4=12$ Kugeln: R R R R G G G G B B B B
$\ c=9$ (Anzahl Urnen insgesamt)
$\ t=7$ (Anzahl nicht leere Urnen)
Damit es wirklich t nicht leere Urnen geben kann, muss
natürlich noch die Bedingung [mm] t\le{m*a} [/mm] erfüllt sein.
Zwischen c und t würde die Voraussetzung [mm] c\ge{t} [/mm] (anstatt c>t)
eigentlich auch schon genügen.
Für die Lösung ist noch wichtig zu wissen, ob die verschiedenen
Urnen als unterscheidbar gelten sollen. Ich nehme einmal an, ja -
das heißt, dass wir im Beispiel 9 nummerierte Urnen [mm] U_1, U_2, [/mm] ... , [mm] U_9
[/mm]
haben und dass es dann wesentlich ist, welche Urne genau
welchen Inhalt hat (falls nicht, bitte korrigieren !) .
Gleichfarbige Kugeln sollen bestimmt als ununterscheidbar
gelten.
LG Al-Chw.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:10 Di 15.02.2011 | | Autor: | kewlBandit |
Erst einmal vielen Dank für deine Antwort.
Die Unterscheidbarkeit hast du richtig gedeutet. Die Urnen sind sehr wohl unterscheidbar, gleichfarbeige Kugeln allerdings nicht. Ich werde mal versuchen, dein Zahlenbeispiel durchzurechnen.
|
|
|
|
