Anordnung < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:30 Mi 02.11.2011 | | Autor: | clemenum |
| Aufgabe | Auf wieviele Arten können wir die Zahlen $1, 2, . . . , n$ anordnen, sodaß
abgesehen vom ersten Element — die Zahl $k$ nur dann placiert werden kann, falls $k-1$ oder $k + 1$ bereits placiert wurden (also links von k stehen)? |
Vorgangsweise:
Ich erwähne ein paar Einzelfälle und versuche dann allgemeine Argumentation (ich bevorzuge also die induktive Vorgangsweise):
$n=2: 1,2; 2,1 $
$n= 3: 1,2,3; 2,1,3; 2,3,1; 3,2,1$
$n=4:1,2,3,4; 2,1,3,4; 2,3,1,4; 2,3,4,1; 3.2,4,1; 3,4,2,1; 3,2,1,4; 4,3,2,1;$
Ein Zusammenhang mit den 2-er Potenzen lässt sich also (ziemlich stark) vermuten.
Wäre eine Fortführung dieses Beweises im Sinne eines Induktionsbeweises am sinnvollsten oder soll z.B. eine Bijektion auf die Potenzmenge der Menge [mm] $\{1,2,3,\ldots,n-1\} [/mm] gefunden werden. Im Falle der Induktion wüßte ich jedoch nicht wie ich den Indutionsschritt durchführen sollte?
Meine Vermtung: Die Zahlen [mm] $1,2\ldots,n$ [/mm] lassen sich auf genau [mm] $2^{n-1}$ [/mm] verschiedene Weisen nach der obigen Bedingung anordnen.
|
|
| |
|
Hallo clemenum,
hübsche Aufgabe. 
> Auf wieviele Arten können wir die Zahlen [mm]1, 2, . . . , n[/mm]
> anordnen, sodaß
> abgesehen vom ersten Element — die Zahl [mm]k[/mm] nur dann
> placiert werden kann, falls [mm]k-1[/mm] oder [mm]k + 1[/mm] bereits placiert
> wurden (also links von k stehen)?
>
> Vorgangsweise:
> Ich erwähne ein paar Einzelfälle und versuche dann
> allgemeine Argumentation (ich bevorzuge also die induktive
> Vorgangsweise):
>
> [mm]n=2: 1,2; 2,1[/mm]
> [mm]n= 3: 1,2,3; 2,1,3; 2,3,1; 3,2,1[/mm]
> [mm]n=4:1,2,3,4; 2,1,3,4; 2,3,1,4; 2,3,4,1; 3.2,4,1; 3,4,2,1; 3,2,1,4; 4,3,2,1;[/mm]
> Ein Zusammenhang mit den 2-er Potenzen lässt sich also
> (ziemlich stark) vermuten.
>
> Wäre eine Fortführung dieses Beweises im Sinne eines
> Induktionsbeweises am sinnvollsten oder soll z.B. eine
> Bijektion auf die Potenzmenge der Menge
> [mm]$\{1,2,3,\ldots,n-1\}[/mm] gefunden werden. Im Falle der
> Induktion wüßte ich jedoch nicht wie ich den
> Indutionsschritt durchführen sollte?
Und ich wüsste gerade nicht, wie die Bijektion aussehen sollte.
> Meine Vermtung: Die Zahlen [mm]1,2\ldots,n[/mm] lassen sich auf
> genau [mm]2^{n-1}[/mm] verschiedene Weisen nach der obigen Bedingung
> anordnen.
Ja, das ist richtig.
Wenn Du den Fall n=5 angehen wolltest, dann ist doch die Frage, wie Du Deine Ergebnisse für n=4 dabei nutzen kannst.
Die 5 kann erst platziert werden, wenn die 4 schon platziert ist. Also schauen wir uns mal an, was das heißt:
Es gab 4 Anordnungen, bei denen die 4 an vierter Stelle stand. Danach kann nun die 5 nur auf eine Weise platziert werden.
Es gab 2 Anordnungen, bei denen die 4 an dritter Stelle stand. Danach kann die 5 nun auf zwei Weisen platziert werden.
Dann 1 Anordnung mit der 4 an zweiter Stelle; drei Möglichkeiten für die 5, und schließlich
1 Anordnung mit der 4 am Anfang; vier Möglichkeiten für die 5.
Dazu kommt noch 1 Anordnung, die mit der 5 anfängt: 5,4,3,2,1.
Insgesamt also 4*1+2*2+1*3+1*4+1=16
Versuch das mal zu verallgemeinern.
Für 6 Zahlen also 8*1+4*2+2*3+1*4+1*5+1=32
Grüße
reverend
|
|
|
|
