0 Daumen
1,4k Aufrufe

Ich habe n Kugeln, davon sind m schwarz und der Rest weiß. Aus den m schwarzen Kugel werden k Paare und m-2k einzelne Kugeln gebildet. Wie viele Möglichkeiten gibt es die Paare und einzelnen Kugeln in einem Kreis anzuordnen, dass die Paare und einzelnen Kugeln paarweise nicht benachbart sind?

Also z.B. 10 Kugeln, 5 schwarz S, 5 weiß W, zwei Paare und eine einzelne Kugel. Gültig wäre dann z.B.

SWSSWSSWWW

Wie viele solcher Möglichkeiten gibt es dann?

Avatar von

meinst du " in einem Kreis"  oder "auf einer Kreislinie" ?

ich meine eher auf einer Kreislinie. das ist aber auch egal. wichtig ist, dass die erste und letzte Stelle des beispiel z.B. "verbunden" zu denken sind (wie bei einem kreis oder tisch).,

Egal ist das ganz sicher nicht!  Aber es ist ziemlich sicher nicht das Innere des Kreises gemeint.

wieso? es ist doch egal, ob die auf einer kreislinie oder einer dreieckslinie oder einem quadrat liegen. wichtig ist doch nur, wer neben wem liegt?

Woher stammt die Frage denn?

Sobald "auf ... -linie" dasteht, ist es tatsächlich egal.

sie entstammt meiner fantasie. ich brauche das als zwischenergebnis für was anderes.

an wolfgang

dann war ich hier nicht sauber genug. ja, linie ist richtig.

ich kanns auch noch vereinfachen:

also, stellen wir uns vor S = 0, W = 1 und 00 = 2. Ich habe  s mal 0, w mal 1 und t mal 2. Es ist Die werden alle auf einer Kreislinie angeordnet. Zwischen den 2ern und den 0ern muss immer mindestens eine 1 liegen. Klarere so?

Hi Wolfgang. Lies dir seine letzten Fragen und die Kommentare durch. Vielleicht wird es dann klarer.

Heute ist es schon spät und mein Kopf ist auch schon müde. Daher an dieser Stelle nur eine Idee zur vorgehensweise.

Betrachte immer die schwarzen Kugeln mit genau einer weißen Kugel zusammen.

SW SSW SSW W W

Und dann betrachtest du deren Anzahl an Anordnungen

5! / (2! * 2!) = 30

Dann ist noch die Frage ob die Plätze im Kreis auf den die Kugeln Platz finden unterscheid bar sind oder nicht. Also ob eine Verschiebung jeder einzelnen Kugel um einen Platz nach rechts etwas ausmacht oder nicht. 

Ich überlege mir solche Dinge zunächst für wenige Kugeln und schaue dann ob mein Mathematisches Modell richtig ist. Man kann auch einen PC nehmen und damit mögliche Anordnungen auch auszählen lassen. 

Ich hoffe das bringt dich schon etwas weiter.

Nix da aufzählen. Ich btauche eine kombinatorische lösung.

Das ist doch nur zum Testen ob die Formel die richtige Lösung bietet.

achso. ja das hat sich mittlerweile gerichtet ... danke für deine hilfe!

2 Antworten

+1 Daumen
 
Beste Antwort

Hallo MathFox,

gegeben seien \(n\) Kugeln, davon sind \(m\) schwarz und aus den \(m\) schwarzen werden \(k\) Paare gebildet. Wenn das die Ausgangslage ist, folgt für die Anzahl der möglichen Kombinationen nach Deinen definierten Regeln:

$$\dfrac{1}{n-m}\cdot \binom{n-m}{k}\cdot\binom{n-m-k}{m-2k}$$

Für die Anzahl aller möglichen Kombinationen nach diesem Schema (also nur einzelne Kugeln und Paare) für \(m\) vorgegebene schwarze Kugeln gilt:

$$\sum_{k=0}^{\lfloor\frac{m}{2}\rfloor}{\dfrac{1}{n-m}\cdot \binom{n-m}{k}\cdot\binom{n-m-k}{m-2k}}$$

Soll zusätzlich die Anzahl der schwarzen Kugeln variabel sein, gilt:

$$\sum_{m=0}^{n}{\sum_{k=0}^{\lfloor\frac{m}{2}\rfloor}{\dfrac{1}{n-m}\cdot \binom{n-m}{k}\cdot\binom{n-m-k}{m-2k}}}$$

Ist es das, was Du berechnet hast? Bei Bedarf nachfragen.

Grüße

André

Avatar von
0 Daumen

ich gebe mal einen Ansatz zur Diskussion:

Wir haben n Kugeln, davon m schwarze Kugeln und k Kugelpaare. Also w:=m-n weiße Kugeln. Wir betrachten einen Kreis aus w weißen Kugeln:

~draw~ kreis(0|0 1);kreis(2|0.5 1);kreis(3.8|1.5 1);kreis(-2|0.5 1);kreis(-3.8|1.5 1);;vektor(2|-3 -0.5|2 "");vektor(-2|-3 0.5|2 "");vektor(-4.5|-2 1|2 "");vektor(4.5|-2 -1|2 "");zoom(10) ~draw~

An den Pfeilen können wir dann jeweils genau ein Objekt einfügen, insgesamt somit w-1 Stück, s.d. sich diese später nicht berühren. Da wir k Paare und m-2k einzelne Kugeln haben, ergibt das insgesamt m-k einzufügende Objekte. Es muss somit eine Grundvoraussetzung erfüllt sein:

$$ w - 1 = n - m - 1 \geq m - k \quad\Rightarrow\quad n \geq 2m-k + 1$$

Ich bezeichne im Folgenden nun weiße Kugeln mit 0, schwarze mit 1 und zwei schwarze Kugeln mit 2. Lücken mit _

Nun besorgen wir uns w-1 Behälter, stellen sie in eine Reihe und verteilen die 1er und 2er darauf.
Es gibt k 2er und m-2k 1er. (w-1)-(k)-(m-2k)=(n-m-1)-(k)-(m-2k)=n-2m+k-1 Behälter werde leer bleiben, erhalten somit ein _

Die Anzahl der unterschiedlichen Verteilungen auf die Behälter (Permutation mit Wiederholung) ist:

$$\frac{ \left( w-1 \right)! }{ k! * (m-2k)! * (n-2m+k-1)!} = \frac{(n-m-1)! }{ k! * (m-2k)! * (n-2m+k-1)!} $$Nun sucht man sich eine feste(!) Einfügeposition im weißen Kreis, fügt jeweils den Inhalt des ersten Behälters ein, geht eine Stelle nach rechts, den Inhalt des zweiten Behälters, etc. (Falls leer einfach zum nächsten gehen)

Es bleibt das Problem, dass z.B. die Behälterkombi 1 1 _ _ _ 2 _ _ das gleiche Bild wie _ 1 1 _ _ _ 2 _ hervorrufen wird (eben nur um eine Stelle verdreht). Wir erhalten jedes Bild w-1=n-m-1 mal, somit müsste die Gesamtzahl aller Kombinationen mit

$$ A(m,n,k) := \frac{1}{n-m-1} * \frac{(n-m-1)! }{ k! * (m-2k)! * (n-2m+k-1)!} $$ anzugeben sein. Aber ob das stimmt? Ich weiß es nicht.

Gruß

Avatar von 6,0 k

Deine Formel ist Quatsch, siehe A(3,10,0)

Ob sie jetzt Quatsch ist, nur weil sie deine Frage nicht beantwortet? ...

$$ \frac{(n-m)! }{ k! * (m-2k)! * (n-2m+k)!} $$

Ist die korrigierte Formel für die möglichen Permutationen, da man w Objekte und nicht nur w-1 Objekte in den Kreis einbauen kann. Das muss jetzt nur noch mit dem richtigen Vorfaktor versehen werden, der oben ist leider falsch.

Meine Antwort bitte in ein Kommentar umwandeln.

Auch das ist Quatsch. (Wie) hast Du das Problem verstanden?

Hast du meinen Kommentar gelesen? Ich sagte doch, es fehle noch ein Faktor für das Endresultat?

Ich verstehe das Problem so:

Du möchtest aus w weißen und s schwarze Kugeln einen Kreis erzeugen, in dem maximal 2 schwarze Kugeln nebeneinander liegen können. Gleichzeitig möchtest du, dass genau k-mal zwei schwarze Kugeln nebeneinander liegen. Und nun suchst du die Gesamtanzahl aller Anordnungen, die dieser Anforderung entsprechen.

---

Die Formel im Kommentar sagt dir nur, wie viele Möglichkeiten es gibt, diese Kugeln in einer Geraden mit den obigen Anforderungen anzuordnen. Verbiegt man diese zu einem Kreis, schränkt das die Möglichkeiten natürlich ein.

Ist auch egal. OIch habe die richtige Lösung jetzt. oben die ist es aber nicht.

Danke für den Hinweis, das ist mir allerdings auch schon aufgefallen. Du könntest uns ja am Ergebnis teilhaben lassen.

könnte ich. ja

Aber? .........

Aber was habe ich davon?

Okay, verstanden.

Kein Interesse? Tip: du brauchst zwei Binomiale Koeffizienten.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community