Belegung n Feldern... < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich habe folgendes Problem:
Ich soll k Steine auf n Felder legen und zwar so, dass keine zwei Steine benachbart sind.
Wenn 1 ein belegtes Feld darstellt und 0 ein freies, so wäre also erlaubt 101000 und nicht erlaubt 0110000.
Ich habe mir überlegt, dass ich vielleicht anstatt 1er auf die Felder zu legen, immer Paare 01 auf die Felder lege. Dann bekomme ich automatisch, dass keine zwei 1er neben einander liegen. Dafür hätte ich [mm] \vektor{n \\ 2k} [/mm] Möglichkeiten. Dann muss ich mir überlegen, dass ja auch auf dem ersten Feld ein Stein liegen kann. Also lege ich auf das erste Feld einen Stein und verteile dann k-1 Paare. Dann habe ich [mm] \vektor{n-1 \\ 2(k-1)} [/mm] Möglichkeiten.
Das macht zusammen [mm] \vektor{n \\ 2k}+\vektor{n-1 \\ 2(k-1)} [/mm] Möglichkeiten (was ich so ohne weiteres glaub nicht zusammenfassen kann).
Stimmen diese Überlegungen?
Insgesamt soll angeblich [mm] \vektor{n-k+1 \\ k} [/mm] rauskommen. Aber davon bin ich irgendwie weit entfernt habe ich den Eindruck. Kann mir irgendjemand weiter helfen?
Danke! 
|
|
| |
|
moin,
Deine Überlegung ist glaube ich noch nicht ganz ausgereift.^^
Test das mal mit ein paar Werten:
Wenn k=1 ist dann wollen wir genau einen Stein verteilen, dafür gibt es n Möglichkeiten (denn er kann ja auf keinen Fall irgendwo neben gelegt werden^^).
Setzt du für k 1 ein so kommt bei dir aber irgendwas anderes raus, nicht n.
Ich glaube der Hauptgrund ist, dass du nur solche Reihen betrachtest:
0101010101010....
1010101010101...
Was wäre aber mit
10000100100100100001 ?
Außerdem erzähl doch mal, wieso du ${n [mm] \choose [/mm] 2k}$ Möglichkeiten hast die k "01"-Blöcke auf n Felder zu verteilen, das will sich mir nicht wirklich erschließen...
lg
Schadow
|
|
|
| |
|
> moin,
>
> Deine Überlegung ist glaube ich noch nicht ganz
> ausgereift.^^
> Test das mal mit ein paar Werten:
> Wenn k=1 ist dann wollen wir genau einen Stein verteilen,
> dafür gibt es n Möglichkeiten (denn er kann ja auf keinen
> Fall irgendwo neben gelegt werden^^).
> Setzt du für k 1 ein so kommt bei dir aber irgendwas
> anderes raus, nicht n.
>
> Ich glaube der Hauptgrund ist, dass du nur solche Reihen
> betrachtest:
> 0101010101010....
> 1010101010101...
>
> Was wäre aber mit
> 10000100100100100001 ?
ich lass mal die erste 1 außen vor. Das ist dann ja der zweite Binomialkoeffizient. Und 0000100100100100001 bekomme ich, indem ich 5 01-Blöcke lege:
000(01)0(01)0(01)0(01)000(01)
die restlichen freien Felder werden einfach "mit Nullen aufgefüllt". Ich setze also 2k Elemente (k einser, k nuller) auf n Felder - also [mm] \vektor{n \\ 2k} [/mm] Möglichkeiten.
Aber es ist wirklich irgendwie doof, dass die Formel für k=1 schon nicht mehr funktioniert. Aber sonst fehlt mir irgendwie die Idee... :-(
Hast du denn keine Idee für mich?
|
|
|
| |
|
Das Problem ist, dass du eben nicht 2k Felder wählst.
Da die Blöcke zusammenhängen setzt du jeweils nur einen Block pro "Zug", verlierst dabei aber 2 Felder, unter Umständen sogar mehr...
Versuch vielleicht mal mit einer Induktion zu beweisen, dass wirklich ${n-k+1 [mm] \choose [/mm] k}$ rauskommt.
Bedenke dabei: wenn n>k ist dann ist nach Definition ${n [mm] \choose [/mm] k} = 0$
Also Induktionsanfang:
n=1, da kannst du höchstens einen Stein setzen, also passt das.
n=2 kannst du auch nur einen Stein setzen, passt also auch mit der Formel.^^
n=3 kannst du entweder einen Stein oder zwei setzen, für beide passt die Formel...
Wie da ein Induktionsschritt aussehen würde bin ich mir grad auch nicht ganz sicher, vielleicht $n [mm] \to [/mm] n+1$ oder $n [mm] \to [/mm] n+2$, probier vielleicht mal ein wenig rum.
Viel Glück und Spaß. ;)
lg
Schadow
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:55 So 23.10.2011 | | Autor: | Balendilin |
> Das Problem ist, dass du eben nicht 2k Felder wählst.
> Da die Blöcke zusammenhängen setzt du jeweils nur einen
> Block pro "Zug", verlierst dabei aber 2 Felder, unter
> Umständen sogar mehr...
>
> Versuch vielleicht mal mit einer Induktion zu beweisen,
> dass wirklich [mm]{n-k+1 \choose k}[/mm] rauskommt.
> Bedenke dabei: wenn n>k ist dann ist nach Definition [mm]{n \choose k} = 0[/mm]
>
> Also Induktionsanfang:
> n=1, da kannst du höchstens einen Stein setzen, also
> passt das.
> n=2 kannst du auch nur einen Stein setzen, passt also auch
> mit der Formel.^^
> n=3 kannst du entweder einen Stein oder zwei setzen, für
> beide passt die Formel...
>
> Wie da ein Induktionsschritt aussehen würde bin ich mir
> grad auch nicht ganz sicher, vielleicht [mm]n \to n+1[/mm] oder [mm]n \to n+2[/mm],
> probier vielleicht mal ein wenig rum.
>
Danke! Ich habs per vollständiger Induktion beweisen können
> Viel Glück und Spaß. ;)
>
> lg
>
> Schadow
|
|
|
|
