Kombinatorik - ein Parkplatz-Problem

14.05.2014, 16:01	LeneK	Auf diesen Beitrag antworten »
Kombinatorik - ein Parkplatz-Problem Man stelle sich Parkplätze entlang einer Straße vor mit der Länge 1 und der Anzahl L. Autos haben die Länge k, dass heißt wenn sie parken nehmen sie k Parkplätze hintereinander ein. Autos suchen sich völlig zufällig einen Parkposition aus. Dabei müssen zwischen zwei Autos keine Lücken bleiben. Bei einer Parkplatzanzahl von k+1 hat das erste Auto zwei Möglichkeiten zu parken. Wie viele möchliche Parkpositionen hat das zweite Auto im Durchschnitt (Erwartungswert) in Abhängigkeit von k und L? Wie viele hat das dritte? Meine Ideen: Für das erste Auto ist die anzahl der Möglichkeiten L-k+1 (bei L=k gibt es eine Möglichkeit). Für das zweite Auto habe ich mir überlegt, dass die maximale Anzahl an möglichen Situationen auf das das zweite Auto stoßen kann die Anzahl an Möglichkeiten ist, die das erste Auto hat, also L-k+1. Die Anzahl an Möglichkeiten, die das Auto dann hat überhaupt einen Parkplatz zu finden, wo es rein passt hängt von L ab. Ist L=2k gibt es nur zwei Möglichkeiten bei denen das zweite Auto überhaupt einen Platz findet. Der Erwartungswert wäre also 2/(L-k+1) = 2/(k+1). Verallgemeinert habe ich das auf: (L-2k+1)*2/(L-k+1). Für das dritte Auto fehlt mir leider der Ansatz, da die Möglichkeiten nicht mehr überschaubar sind. Bei L=3k gibt es 3 Möglichkeiten, bei der das dritte Auto einen Parkplatz findet (je mit einer Möglichkeit). Meint ihr mein Ansatz für das zweite Auto ist richtig? Kann mir jemand mit dem dritten weiterhelfen?
14.05.2014, 16:27	HAL 9000	Auf diesen Beitrag antworten »
Wenn ich richtig verstehe, interessierst du dich für die Gesamtanzahl der Parkmöglichkeiten von $\begin{eqnarray} n \end{eqnarray}$ Autos der Länge $\begin{eqnarray} k \end{eqnarray}$ bei Gesamtlänge $\begin{eqnarray} L \end{eqnarray}$ des Parkraums? Das kann man durch (gedankliche ) "Verkürzung" der Autos auf Länge 1 lösen, in dem man im gleichen Atemzug die Gesamtlänge um $\begin{eqnarray} n(k-1) \end{eqnarray}$ verkürzt. In dem Sinne sind dann noch $\begin{eqnarray} n \end{eqnarray}$ Autos auf $\begin{eqnarray} L-n(k-1) \end{eqnarray}$ Positionen unterzubringen. Dafür gibt es genau $\begin{eqnarray} \binom{L-n(k-1)}{n} \end{eqnarray}$ Möglichkeiten bei ununterscheidbaren Autos. Willst du sie als unterscheidbar betrachten (also 1.Auto, 2.Auto usw.), dann muss da noch Faktor $\begin{eqnarray} n! \end{eqnarray}$ dranmultipliziert werden.
14.05.2014, 17:03	LeneK	Auf diesen Beitrag antworten »
Vielen Dank für die schnelle Antwort. Die Sache ist, dass ich nicht nach der Anzahl an Möglichkeiten drei Auto auf dem gesamten Platz zu verteilen suche, sondern die durchschnittliche Anzahl an Möglichkeiten, die das dritte Auto hat, wenn die anderen beiden schon zufällig positioniert sind. Es kann dabei sein, dass es Situationen gibt, in denen gar kein Platz für das dritte Auto ist oder aber das dritte Auto sich zwischen mehreren Möglichkeiten entscheiden kann. Dazu müsste ich nun wissen wie viele Möglichkeiten das dritte Auto bei jeder möglichen Parksituation der anderen beiden Autos hat (dabei sind Auto eins und zwei nicht unterscheidbar) und dies dann durch die Anzahl aller Möglichkeiten die ersten beiden Autos zu parken teilen. Leider habe ich keine Ahnung wie ich diesen Erwartungswert berechne.
14.05.2014, 17:24	HAL 9000	Auf diesen Beitrag antworten »
Ja, vom ersten zum zweiten Wagen wäre das einfach noch der Quotient der beiden von mir genannten Anzahlen, also $\begin{eqnarray} \frac{\displaystyle 2!\binom{L-2(k-1)}{2}}{\displaystyle 1!\binom{L-(k-1)}{1}} = \frac{(L-2k+2)(L-2k+1)}{L-k+1} \end{eqnarray}$ . Leider klappt das bei den Folgepositionen nicht mehr, da dein Platzierungsverfahren für $\begin{eqnarray} n\geq 2 \end{eqnarray}$ nicht die Laplace-Eigenschaft hat, d.h., dass alle möglichen Parkkonstellationen von $\begin{eqnarray} n \end{eqnarray}$ Autos gleichwahrscheinlich sind.
14.05.2014, 17:32	LeneK	Auf diesen Beitrag antworten »
Ja, das sollte für das zweite gehen. Aber ist es für das dritte dann nicht ähnlich? Die Anzahl an Möglichkeiten, die es gibt das zweite Auto unterzubringen ist die Anzahl an Situationen auf die das dirtte Auto treffen kann. Also wenn die Gesamtmöglichkeiten drei Autos unterzubringen dadurch teilt, passt das dann nicht auch, oder wird da was vernachlässigt?
14.05.2014, 17:41	LeneK	Auf diesen Beitrag antworten »
achso das problem ist, dass die ersten beiden Autos nicht unterscheidbar sind, sondern nur das dritte?
Anzeige

14.05.2014, 17:45	HAL 9000	Auf diesen Beitrag antworten »
Nein, es ist nicht dasselbe: Die Parkmöglichkeiten des ersten Autos haben alle dieselbe Wahrscheinlichkeit $\begin{eqnarray} \frac{1}{L-k+1} \end{eqnarray}$ , alles schön Laplacesch, prima. Nun zum zweiten Auto: Wenn beispielsweise das erste Auto in einer Randposition steht, dann gibt es für das zweite Auto $\begin{eqnarray} (L-2k+1) \end{eqnarray}$ Parkmöglichkeiten, aus denen es gleichverteilt auswählt. Insgesamt ist also für jede dieser Konstellationen die Wahrscheinlichkeit $\begin{eqnarray} \frac{1}{(L-k+1)(L-2k+1)} \end{eqnarray}$ . Steht das erste Auto aber eine Position weiter vorn (wir nehmen mal k>1 an), dann hat das zweite Auto nur noch $\begin{eqnarray} (L-2k+1) \end{eqnarray}$ Möglichkeiten, was die Konstellationwahrscheinlichkeit dann auf $\begin{eqnarray} \frac{1}{(L-k+1)(L-2k)} \end{eqnarray}$ erhöht, usw. Das erste Auto irgendwo in der "Mitte geparkt - d.h. bei hinreichend großem L - ergibt dann entsprechend $\begin{eqnarray} \frac{1}{(L-k+1)(L-3k)} \end{eqnarray}$ . Laplacesche Gleichverteilung würde hingegen für jede Konstellation dieselbe Wahrscheinlichkeit $\begin{eqnarray} \frac{1}{(L-2k+2)(L-2k+1)} \end{eqnarray}$ bedeuten - das liegt auf alle Fälle zwischen den beiden Extremen oben, d.h. $\begin{eqnarray} \frac{1}{(L-k+1)(L-2k+1)} < \frac{1}{(L-2k+2)(L-2k+1)} < \frac{1}{(L-k+1)(L-3k)} \end{eqnarray}$ .
14.05.2014, 17:55	LeneK	Auf diesen Beitrag antworten »
Ok, verstanden.... Dann werde ich wohl erstmal vereinfachend annehmen müssen, dass alle Situationen auf die das dritte Auto stoßen kann gleich warhscheinlich sind und schauen ob es mir das Ergebnis ruiniert. Aber falls du eine Idee hast, wie ich es doch genau bestimmen kann wäre ich dir dankebar. Vielen Dank auf jeden Fall für diese Hilfe.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »