Kombinatorik

29.06.2005, 21:01

abi2006s

Kombinatorik

Ich soll folgende Textaufgabe lösen:

Ein Reisebüro bietet mehrere Touren an mit 6 unterschiedlichen Städten an.

a) Wieviele 4-Tages-Reisen sind möglich, wenn keine Stadt zwei Tage oder länger besucht wird?

b) Wieviele 8-Tages-Touren sind möglich, wenn jede Stadt besucht wird?

Ich habe mir als Lösung errechnet:

für a) 6!/2! = 360

für b) 6! * 6 * 6 = 25920

kann das richtig sein ??

30.06.2005, 00:02

JochenX

Auf diesen Beitrag antworten »

wie kommst du denn auf diese ergebnisse
ich bekomme andere werte.... also erklär sei doch mal genauer!

bei b) z.b. beachte, dass du nach anordnung der 6 städte du noch 2 von den 6 für einen 2-tagesaufenthalt planst
bzw. welche der 6 städte für einen 3tagesaufenthalt geplant wird

mfg jochen

PS: ich nehme übrigens mal ganz frei an, dass man eine stadt nur 1mal besuchen darf oder? also insbesondere auch nicht für a) 1 tag rom, dann 2 tage... dann ein tag rom?

30.06.2005, 17:40

abi2006s

Auf diesen Beitrag antworten »

Für Aufgabe a) gilt sicherlich, dass man in eine Stadt nicht zurückkehrt.

a) da keine Stadt zweimal besucht werden soll,
würde das also "4 aus 6" mit Berücksichtigung der Reihenfolge
bedeuten
6! / (6-4)! = 360
(oder anders 6*5*4*3= 360) ????

b) hier habe ich zunächst alle 6 aufgeteilt, damit ich die Bedingung "jede Stadt wird besucht" erfülle. Danach habe ich doch für jeden der restlichen zwei Tage wieder alle Städte zur Auswahl (?)
also: 720*6*6 oder ???

30.06.2005, 17:44

JochenX

Auf diesen Beitrag antworten »

zur a) da hatte ich mich verlesen, dachte jede stadt dürfte auch bis zu 2 tage besucht werden
wenn jede stadt nur einmal und nur genau einen tag besucht werden darf, dann ist das genehm, was du da stehen hast!

wie gesagt b) würde ich mit folgenden bedingungen auffassen:
jede stadt wird nur einmal besucht; dann aber immer eine anzahl voller tage (beliebig viele im prinzip)

also dein verständnis verstehe ich so nicht.....
das ist eine typisch missverständlich formulierte aufgabe

30.06.2005, 18:56

Auf diesen Beitrag antworten »

@abi2006s

Bei b) stimme ich ja Jochens Verständnis der Aufgabe zu, aber selbst wenn eine Stadt mehrfach (mit Unterbrechungen) besucht werden darf, ist deine Lösung falsch: Wer sagt dann, dass alle 6 Städte an den ersten 6 Tagen besucht werden müssen? Deine Anzahl ist somit für diese Interpretationsvariante zu niedrig. Für die Interpretationsvariante von Jochen (und mir) ist diese Anzahl allerdings zu hoch.

01.07.2005, 01:05

JochenX

Auf diesen Beitrag antworten »

hui ich wollte das mal durchrechnen
ohne zu viel verraten sage ich mal mein zahlenergebnis (nach einem glas selbstgemixtem sangria gebe ich da aber keinerlei garantie drauf): 15120 verschiedene touren

01.07.2005, 07:24

Auf diesen Beitrag antworten »

Soviel hast du nun auch nicht ge- Prost

-en, denn $\begin{eqnarray*} 6!\cdot{7 \choose 2} \end{eqnarray*}$ ist richtig.

01.07.2005, 14:29

abi2006s

Auf diesen Beitrag antworten »

hmm,

also b) soll so verstanden werden, dass man auch mehrmals in eine Stadt einreisen kann. Es ist sehr blöd formuliert, aber meine Aufgabe hat noch eine weitere Zusatzaufgabe c) mit den gleichen Bedingungen (6 Städte, 8Tages-Reisen) und dem expliziten Hinweis das " ... aber in keine bereits verlassene Stadt zurückgekehrt wird".

für c) habe ich übrigens 720 Touren als Lösung ?

01.07.2005, 14:39

JochenX

Auf diesen Beitrag antworten »

nein c) ist falsch; das ist dann ja meine (und arthurs) lösung oben
bedenke, dass eine tour mit 2 tagen rom und 1 tag madrid, eine andere ist als 1 tag rom und 2 tage madrid, auch wenn die reihenfolge erhalten bleibt

@arthur: ist natürlich interessant, einen "blank" zur auswahl einzusetzen
ich hatte mit $\begin{eqnarray*} {6 \choose 2}+{6 \choose 1}(={7 \choose 2}) \end{eqnarray*}$ gerechnet...

edit: bei b) kommt dann eine übermäßig große zahl raus bei mir

01.07.2005, 17:32

Auf diesen Beitrag antworten »

Zitat:

Original von LOED
@arthur: ist natürlich interessant, einen "blank" zur auswahl einzusetzen

Nennt man mitunter auch "Kombinationen mit Wiederholung" (letzte Zeile in Jan's Tabelle zur Kombinatorik). Augenzwinkern

Zitat:

Original von LOED
edit: bei b) kommt dann eine übermäßig große zahl raus bei mir

191520

01.07.2005, 19:40

JochenX

Auf diesen Beitrag antworten »

jupp so in der größenordnung wars, finde meinen zettel nimmer und rechne das jetzt nicht noch mal nach smile

yuppieh

04.07.2005, 14:39

abi2006s

Auf diesen Beitrag antworten »

hmm,

also für c) gilt

6! $\begin{eqnarray*} \begin{pmatrix} 7 \\ 2 \end{pmatrix} \end{eqnarray*}$

und wie kommt Ihr für b) auf 191520 ?

alle Möglichkeiten wären : 262144, jedoch soll ja jede Stadt mind. einmal besucht werden.

04.07.2005, 15:15

Auf diesen Beitrag antworten »

Zitat:

Original von abi2006s
alle Möglichkeiten wären : 262144

Und wieder eine Verwechslung: Die Anzahl aller 8-Tages-Touren für 6 Städte (ohne dass jede Stadt besucht wird) ist nicht $\begin{eqnarray*} 8^6=262144 \end{eqnarray*}$ , sondern $\begin{eqnarray*} 6^8=1679616 \end{eqnarray*}$ .

Bei b) gibt es zwei Fälle zu unterscheiden:

i) Je zwei Städte werden an zwei Tagen besucht. Dann gibt es $\begin{eqnarray*} {6\choose 2} \end{eqnarray*}$ Möglichkeiten für die Auswahl dieser beiden Städte und dann jeweils $\begin{eqnarray*} \frac{8!}{2!2!} \end{eqnarray*}$ Anordnungsmöglichkeiten (Permutationen mit Mehrfachelementen).

ii) Genau eine Stadt wirden an drei Tagen besucht. Dann gibt es $\begin{eqnarray*} 6 \end{eqnarray*}$ Möglichkeiten für die Auswahl dieser Stadt und dann jeweils $\begin{eqnarray*} \frac{8!}{3!} \end{eqnarray*}$ Anordnungsmöglichkeiten (wieder Permutation mit Mehrfachelementen).

Als Gesamtanzahl ermittelt man folglich $\begin{eqnarray*} {6\choose 2}\cdot\frac{8!}{2!2!}+6\cdot \frac{8!}{3!}=191520 \end{eqnarray*}$ .

EDIT: Übrigens, da Leopold sich im Beitrag

http://www.matheboard.de/thread.php?postid=176145#post176145

so viel Mühe gegeben hat: Diese Aufgabe b) hier lässt sich in genau dasselbe Modell einordnen und die gesuchte Anzahl ist: $\begin{eqnarray*} \left|R_{(4,2,0,0,0,0,0,0)}\right|+\left|R_{(5,0,1,0,0,0,0,0)}\right| \end{eqnarray*}$

Dabei ist

$\begin{eqnarray*} \left| R_{\kappa} \right| \ = \ \frac{8!}{\left(1!\right)^{k_1} \left(2!\right)^{k_2} \left(3!\right)^{k_3} \left(4!\right)^{k_4} \left(5!\right)^{k_5} \left(6!\right)^{k_6}\left(7!\right)^{k_7}\left(8!\right)^{k_8}} \cdot \frac{(6)_k}{k_1! k_2! k_3! k_4! k_5! k_6! k_7! k_8!} \end{eqnarray*}$

mit $\begin{eqnarray*} \kappa = (k_1,k_2,k_3,k_4,k_5,k_6,k_7,k_8) \end{eqnarray*}$ und $\begin{eqnarray*} k = \sum_{i=1}^8~k_i \end{eqnarray*}$ sowie $\begin{eqnarray*} (6)_k = 6 \cdot 5 \cdots (6-k+1) \end{eqnarray*}$ .

Neue Frage »

Antworten »

Kombinatorik

Verwandte Themen