Anordnen von Zahlen < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 00:04 Sa 10.11.2012 | | Autor: | Lu- |
| 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. |
Ich habe mir als ersten Bsp. angeschaut:
n=2 habe ich 1,2 und 2,1 -> 2 Arten
n =3 habe ich 1,2,3 und 2,1,3 und 2,3,1 und 3,2,1 -> 4 Arten
n= 4 habe ich 1,2,3,4 und 2,1,3,4 und 2,3,1,4 und 2,3,41und 3,2,4,1 und 3,2, 1, 4 und 3,4,2,1 und 4,3, 2, 1 -> 8 Arten
(Also vermutung zweier Potenzen)
So hab ich es verstanden aber nun ist das allgemeine mir wichtig:
Überlegungen:
Sei k die erste Zahl
Nun kann ich nach oben oder nach unten weiter anstückeln
-)nach oben weiter anstückeln kann ich insgesamt n-k mal
-)nach unten weiter antsückeln kann ich insgesamt k-1 mal
Angenommen ich weiß für n die Anzahl der Möglichkeiten, M(n).
Dann kann n+1 nur placiert werden wenn n schon plaziert wurde.
Wenn n an letzter Stelle stand kann n+1 nur danach placiert werden. Wenn n an vorletzter Stelle stand kann n+1 auf zwei verschiedene Stellen placiert werden....
Wenn n an der ersten Stelle steht, dann kann n+1 auf n-1 verschiedenen Stellen placiert werden.
Wenn n+1 an erster Stelle steht gibt es nur 1 Anordnung.
ich komme in meiner überlegung zu keiner aussage/resultat
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:33 Sa 10.11.2012 | | Autor: | Fulla |
Hallo Lu-,
kannst du die Aufgabenstellung vielleicht etwas präzieser/anders formulieren? Ich verstehe nicht, was genau gemeint ist...
Angenommen n=5 und k=2. Für die 1 wähle ich einen der 5 "Plätze":
_ _ 1 _ _
Warum sollte ich jetzt die 2 nicht platzieren können? Ich habe doch 4 Möglichkeiten....?
Lieben Gruß,
Fulla
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 00:45 Sa 10.11.2012 | | Autor: | Lu- |
Im Titeltext steht die Angaben wie am Übungszettel, diese wollte ich nicht natürlich nicht anders formulieren.
> Angenommen n=5 und k=2.
Ich fange nun immer bei dem element an der ersten Stelle an.
z.B 1 _ _ _ _
Dann darf ich an zweiter Stelle nur die 2 placieren, den sonst ist die Bedingung der Angabe nicht erfüllt.
1 2 _ _ _
z.B. Fange ich so an: 2 _ _ _ _
Dann darf ich an zweiter Stelle sowohl 1 als auch 3 wählen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:53 Sa 10.11.2012 | | Autor: | Fulla |
Hallo nochmal,
ach sooooo! Man wählt die erste Zahl k und darf dann für die Zweite nur k+1 oder k-1 einsetzen. Z.B. bei 3 2 _ _ _ wären als nächste Zahlen 1 oder 4 möglich.
Ich habe grade ein bisschen rumprobiert und stelle mal die Vermutung auf: Bei n Zahlen gibt es [mm]2^{n-1}[/mm] Möglichkeiten.
Mir ist aufgefallen, dass es auf eine Summe von Binomialkoeffizienten rauslaufen wird. Geht man die verschiedenen Startzahlen k durch, gibt es z.B. für n=5 immer [mm]\binom{4}{k-1}[/mm] Möglichkeiten. In der Summe heißt das dann [mm]\sum_{k=1}^{n-1}\binom{n-1}{k-1}=2^{n-1}[/mm]
Probier in der Richtung mal weiter. Ich hab jetzt grad keine Muse mehr, da einen Beweis/eine Begründung zu finden.
Lieben Gruß,
Fulla
|
|
|
| |
|
Hallo Lu-,
die Aufgabe ist völlig unzureichend formuliert.
> 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.
Fullas Lesart wäre in der Tat auch möglich. Nur wäre das Ergebnis dann n!, also das gleiche wie bei beliebiger Reihenfolge der Platzierung. Es steht nicht zu vermuten, dass das gemeint ist, aber ordentlich gesagt ist es nicht.
Übrigens ist die Schreibweise "placieren" so obsolet, dass sie heute als blasiert gelten darf. Sie war bis in die 1920er Jahre einigermaßen üblich und dann recht schnell durch die Schreibweise "plazieren" ersetzt. Erst die letzte Rechtschreibreform im letzten Jahrzent bestand darauf, dass das Wort nun "platzieren" zu schreiben sei, weil ja eine Verwandtschaft mit "Platz" bestünde. Das ist etymologischer Schwachsinn, aber eben heutige Regel.
Aber das tut hier nichts zur Sache. Zurück zur Aufgabe.
> Ich habe mir als ersten Bsp. angeschaut:
> n=2 habe ich 1,2 und 2,1 -> 2 Arten
> n =3 habe ich 1,2,3 und 2,1,3 und 2,3,1 und 3,2,1 -> 4
> Arten
> n= 4 habe ich 1,2,3,4 und 2,1,3,4 und 2,3,1,4 und
> 2,3,41und 3,2,4,1 und 3,2, 1, 4 und 3,4,2,1 und 4,3, 2, 1
> -> 8 Arten
> (Also vermutung zweier Potenzen)
Diese Vermutung ist richtig. Für die Anordnung der Zahlen 1 bis n gibt es [mm] 2^{n-1} [/mm] Möglichkeiten, wenn man Deiner Interpretation der Aufgabe folgt, die ich - wie gesagt - teile.
> So hab ich es verstanden aber nun ist das allgemeine mir
> wichtig:
> Überlegungen:
> Sei k die erste Zahl
> Nun kann ich nach oben oder nach unten weiter anstückeln
>  nach oben weiter anstückeln kann ich insgesamt n-k mal
> nach unten weiter antsückeln kann ich insgesamt k-1
> mal
>
> Angenommen ich weiß für n die Anzahl der Möglichkeiten,
> M(n).
> Dann kann n+1 nur placiert werden wenn n schon plaziert
> wurde.
> Wenn n an letzter Stelle stand kann n+1 nur danach
> placiert werden. Wenn n an vorletzter Stelle stand kann n+1
> auf zwei verschiedene Stellen placiert werden....
> Wenn n an der ersten Stelle steht, dann kann n+1 auf n-1
> verschiedenen Stellen placiert werden.
> Wenn n+1 an erster Stelle steht gibt es nur 1 Anordnung.
>
>
> ich komme in meiner überlegung zu keiner aussage/resultat
Das wird rekursiv gehen.
Schau Dir n=5 an:
Wenn die 1 vorne steht, gibt es nur 1 Möglichkeit für den Rest.
Wenn die 2 vorne steht, gibt es 4 Möglichkeiten für den Rest.
Wenn die 3 vorne steht, gibt es 6 Möglichkeiten für den Rest.
Wenn die 4 vorne steht, gibt es 4 Möglichkeiten für den Rest.
Wenn die 5 vorne steht, gibt es nur 1 Möglichkeit für den Rest.
Ich nehme an, Du erkennst die Binomialkoeffizienten [mm] \vektor{4\\i}.
[/mm]
Denk mal drüber nach, wie sich diese Möglichkeiten konstruieren lassen, wenn man die für n=4 kennt, oder allgemeiner, wie man die für n+1 konstruiert, wenn man die für n schon kennt. Stichwort: Pascalsches Dreieck.
Und schließlich bleibt noch diese Regel: [mm] \summe_{i=0}^{m}\vektor{m//i}=2^m
[/mm]
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:28 Sa 10.11.2012 | | Autor: | Lu- |
Danke für den Post#
Für n=5 ist mir das klar, aber ich muss es allgemein zeige und da habe ich leider noch immer keinen beweis zusammenbekommen.
Sei [mm] \phi [/mm] (n,j) die Anzahl der Möglichkeiten mit j al erste Zahl von [n]
[mm] \phi [/mm] (n,1)=1
-> zweite Ziffer nur 2 sein kann
nach oben weiter anstückeln kann ich insgesamt n-k =n-1mal
nach unten weiter antsückeln kann ich insgesamt k-1 =0 mal
[mm] \phi [/mm] (n,n)=1
-> zweite Ziffer nur n-1 sein
nach oben weiter anstückeln kann ich insgesamt n-k=0 mal
nach unten weiter antsückeln kann ich insgesamt k-1 =n-1 mal
[mm] \phi [/mm] (n,n-1)=?
Die zweite Ziffer kann n oder n-2 sein.
Die ditte Ziffer kann -> n-1 , n , _ , _ ,.. die Ziffer n-2 sein
-> n-1 , n-2 , _ , _ ,.. die Ziffer n oder n-3 sein.
Aber ich komme nicht aufs alllgemeine
> kennt, oder allgemeiner, wie man die für n+1 konstruiert, wenn man die für n schon kennt.
Das habe ich im ersten Post schon aufgeschrieben.
> Angenommen ich weiß für n die Anzahl der Möglichkeiten,
> M(n).
> Dann kann n+1 nur placiert werden wenn n schon plaziert
> wurde.
> Wenn n an letzter Stelle stand kann n+1 nur danach
> placiert werden. Wenn n an vorletzter Stelle stand kann n+1
> auf zwei verschiedene Stellen placiert werden....
> Wenn n an der ersten Stelle steht, dann kann n+1 auf n-1
> verschiedenen Stellen placiert werden.
> Wenn n+1 an erster Stelle steht gibt es nur 1 Anordnung.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:04 So 11.11.2012 | | Autor: | Lu- |
Kein Tipp mehr für mich übrig ;?
Konnte es leider noch nicht lösen.
LG
|
|
|
| |
|
Hallo Lu-,
> Danke für den Post#
> Für n=5 ist mir das klar, aber ich muss es allgemein
> zeige
Das ist mir klar.
> und da habe ich leider noch immer keinen beweis
> zusammenbekommen.
>
> Sei [mm]\phi[/mm] (n,j) die Anzahl der Möglichkeiten mit j al erste
> Zahl von [n]
>
> [mm]\phi[/mm] (n,1)=1
> -> zweite Ziffer nur 2 sein kann
> nach oben weiter anstückeln kann ich insgesamt n-k
> =n-1mal
> nach unten weiter antsückeln kann ich insgesamt k-1 =0
> mal
>
> [mm]\phi[/mm] (n,n)=1
> -> zweite Ziffer nur n-1 sein
> nach oben weiter anstückeln kann ich insgesamt n-k=0
> mal
> nach unten weiter antsückeln kann ich insgesamt k-1
> =n-1 mal
>
> [mm]\phi[/mm] (n,n-1)=?
> Die zweite Ziffer kann n oder n-2 sein.
> Die ditte Ziffer kann -> n-1 , n , _ , _ ,.. die Ziffer
> n-2 sein
> -> n-1 , n-2 , _ , _ ,.. die Ziffer n oder n-3 sein.
> Aber ich komme nicht aufs alllgemeine
Na, dann nehmen wir doch mal ganz allgemein [mm] \phi(n,k).
[/mm]
Hier ein nicht rekursiver Weg:
Nach der Bildungsregel können die Zahlen <k ja nur in absteigender Reihenfolge auftreten, die Zahlen >k nur in aufsteigender.
Es sind noch (n-1) Plätze zu besetzen. Die (k-1) Zahlen <k belegen davon bestimmte Plätze. Wenn die Plätze klar sind, sind also auch die Zahlen darauf klar. Es gibt also [mm] \vektor{n-1\\k-1} [/mm] Möglichkeiten dafür.
Insgesamt also [mm] \summe_{k=1}^{n}\vektor{n-1\\k-1}=\summe_{k=0}^{n-1}\vektor{n-1\\k}=2^{k-1} [/mm] Möglichkeiten.
Fertig.
> > kennt, oder allgemeiner, wie man die für n+1 konstruiert,
> wenn man die für n schon kennt.
> Das habe ich im ersten Post schon aufgeschrieben.
Ja, habe ich gelesen. Aber da bist Du doch auch schon nicht weiter gekommen.
> > Angenommen ich weiß für n die Anzahl der
> Möglichkeiten,
> > M(n).
> > Dann kann n+1 nur placiert werden wenn n schon
> plaziert
> > wurde.
> > Wenn n an letzter Stelle stand kann n+1 nur danach
> > placiert werden. Wenn n an vorletzter Stelle stand kann
> n+1
> > auf zwei verschiedene Stellen placiert werden....
> > Wenn n an der ersten Stelle steht, dann kann n+1 auf
> n-1
> > verschiedenen Stellen placiert werden.
> > Wenn n+1 an erster Stelle steht gibt es nur 1
> Anordnung.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:44 Mi 14.11.2012 | | Autor: | Lu- |
Danke für die Mühe.
Wir haben das Bsp schon in der Uni durchgnommen, aber was meintest du in deinen Post unter:
> Wenn die Plätze klar sind, sind also auch die Zahlen darauf klar.
Das habe ich leider noch immer nicht verstanden, was du mir damit sagen willst...
|
|
|
| |
|
Hallo nochmal,
> Wir haben das Bsp schon in der Uni durchgnommen,
Mit welchem Ergebnis?
> aber was
> meintest du in deinen Post unter:
> > Wenn die Plätze klar sind, sind also auch die Zahlen
> darauf klar.
> Das habe ich leider noch immer nicht verstanden, was du mir
> damit sagen willst...
Naja - nehmen wir mal an, wir hätten die Zahlen von 1 bis 19.283 anzuordnen und beginnen gerade zufällig mit der 6.
Wenn wir nun festlegen/wissen, auf welchen 5 Plätzen dahinter die Zahlen <6 stehen werden, dann ist doch auch klar, dass der 1. Platz von der "5", der 2. von der "4" ... und der 5. von der "1" belegt werden wird. Anders ist es ja gar nicht erlaubt.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:00 Mi 14.11.2012 | | Autor: | Lu- |
Wir haben es mit der rekursiven Methode gemacht, fast genauso wie in deinen anderen Post geschrieben. Deshalb wollte ich hier nochmals nachfragen, da mir die Methode nicht klar ist.
Ich verstehe noch immer nicht wie du dann auf die
> Es gibt also $ [mm] \vektor{n-1\\k-1} [/mm] $ Möglichkeiten dafür.
kommst.
Kurz zusammenfassend was ich bei der methode verstanden habe:
Zahlen < k nur in absteigender Reihenfolge plaziert
Zahlen >k nur in aufsteigender Reihenfolge plaziert
n-1 Plätze zu besetzten
-) nach oben anstückeln kann ich n-k mal
-) nach unten anstückeln kann ich k-1 mal
Ich finde keine allgemeine Argumentation um auf [mm] \vektor{n-1\\k-1} [/mm] zu kommen. Für was sind dies überhaupt die Möglichkeiten?
|
|
|
| |
|
Hallo,
> Wir haben es mit der rekursiven Methode gemacht, fast
> genauso wie in deinen anderen Post geschrieben. Deshalb
> wollte ich hier nochmals nachfragen, da mir die Methode
> nicht klar ist.
>
> Ich verstehe noch immer nicht wie du dann auf die
> > Es gibt also [mm]\vektor{n-1\\
k-1}[/mm] Möglichkeiten dafür.
> kommst.
>
> Kurz zusammenfassend was ich bei der methode verstanden
> habe:
> Zahlen < k nur in absteigender Reihenfolge plaziert
> Zahlen >k nur in aufsteigender Reihenfolge plaziert
> n-1 Plätze zu besetzten
> nach oben anstückeln kann ich n-k mal
> nach unten anstückeln kann ich k-1 mal
Ja, genau. Damit sind wir doch im Prinzip fertig.
> Ich finde keine allgemeine Argumentation um auf
> [mm]\vektor{n-1\\
k-1}[/mm] zu kommen. Für was sind dies überhaupt
> die Möglichkeiten?
Das sind die Möglichkeiten, (k-1) Plätze für das Anstückeln nach unten aus den (n-1) noch freien Plätzen auszuwählen.
lg
rev
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:13 Mi 14.11.2012 | | Autor: | Lu- |
> Das sind die Möglichkeiten, (k-1) Plätze für das Anstückeln nach unten aus den (n-1) noch freien Plätzen auszuwählen.
Aber das ist doch dann nicht in absteigender Reihenfolge?
|
|
|
| |
|
Hi,
> > Das sind die Möglichkeiten, (k-1) Plätze für das
> Anstückeln nach unten aus den (n-1) noch freien Plätzen
> auszuwählen.
> Aber das ist doch dann nicht in absteigender Reihenfolge?
Doch, natürlich. Das meine ich doch damit: Wenn Du weißt, auf welche Plätze Du die "kleineren" Zahlen legen darfst, dann gibt es nur noch eine einzige Möglichkeit - Du darfst sie ja nur in absteigender Reihenfolge platzieren.
Deswegen reicht die Platzauswahl eben schon aus.
lg
rev
|
|
|
| |
|
Hallo nochmal,
ah, da ist es wieder. Ich hatte diese Lösung gestern schonmal im Kopf, aber nicht mehr griffbereit.
Ich bleibe bei Deiner Benennung [mm] \phi(n,k).
[/mm]
Wenn k festgelegt ist, bleiben noch (n-1) Zahlen zu verteilen. Wir bilden alle, die >k sind, auf die nächstkleinere Zahl ab und tun so, als wären wir bei dem gleichen Problem für (n-1) Zahlen. Allerdings ist die erste Wahl nicht mehr so frei: die "erste" Zahl aus diesen (n-1) Zahlen kann ja nur (k+1) oder (k-1) sein, mit der Ausnahme von k=1 und k=n, wo es nur eine Fortsetzung gibt.
Das ist genau das Bildungsprinzip des Pascalschen Dreiecks, und insbesondere gilt:
[mm] \summe{k=1}^{n}\phi(n,k)=2*\summe_{k=1}^{n-1}\phi(n-1,k)
[/mm]
- womit die Verdopplung von n zu n+1 belegt ist.
Da für n=1 nur die Möglichkeit [mm] \phi(1,1)=1 [/mm] besteht, gibt es also für beliebiges n gerade [mm] 2^{n-1} [/mm] Möglichkeiten.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:01 Mi 14.11.2012 | | Autor: | Lu- |
Verspätet, aber vielen dank ;)
Liebe grüße
|
|
|
|
