Kombinatorik mit 3 Variablen < Kombinatorik < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hey Leute...
Leztens hatte ich das Problem,die Anzahl der Möglichkeiten zu bestimmen, k Latten eines offenen Zaunes(also mit 2 Enden) mit insgesamt m Latten,so auszutauschen,dass zwischen zwei erneuerten Latten mindestens n alte Latten stehenbleiben! Dieses Problem wandelte man dann in 0-1 Folgen der Länge m mit k Einsen,sodass zwischen je 2 Einsen mindestens n Nullen stehen
Also gibt es m-(k-1)*n Möglichkeiten,glaub ich...
Meine Frage ist nun: Was verändert sich an diesem Schema,wenn der Zaun in Form eines Kreises aufgestellt wäre,sprich also keine Enden hätte?
Meiner Meinung nach hatt sich ja am Grundproblem nichts geändert oder?Naja seh ich es richtig ,dass durch den Zusammenschluss die k-1 Lücken zu k Lücken werden und ich die Erste Eins meiner Folge einfach zusätlich um m Stellen verschieben könnte? Also es für dieses Problem m*(m-k*n) Möglichkeiten gibt?
Über eine Hilfe und ein wenig Verständnisaufbereitung wär ich sehr dankbar!!!
Lg Basti
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 04:56 Fr 24.04.2009 | | Autor: | felixf |
Hallo!
> Leztens hatte ich das Problem,die Anzahl der Möglichkeiten
> zu bestimmen, k Latten eines offenen Zaunes(also mit 2
> Enden) mit insgesamt m Latten,so auszutauschen,dass
> zwischen zwei erneuerten Latten mindestens n alte Latten
> stehenbleiben! Dieses Problem wandelte man dann in 0-1
> Folgen der Länge m mit k Einsen,sodass zwischen je 2 Einsen
> mindestens n Nullen stehen
> Also gibt es m-(k-1)*n Möglichkeiten,glaub ich...
Sagen wir mal $k = 3$.
Dann muss die erste 1 irgendwo an den Stellen $1, [mm] \dots, [/mm] m - 2 k - 3$ stehen. Sagen wir mal sie hat Stelle $i$. Die zweite $1$ muss dann irgendwo an Stelle $i + n + 1, [mm] \dots, [/mm] m - k - 2$ stehen, sagen wir mal an Stelle $j$. Und die letzte 1 muss irgendwo an Stelle $j + n + 1, [mm] \dots, [/mm] m$ stehen. Es gibt also [mm] $\sum_{i=1}^{m - 2k - 3} \sum_{j = i + n + 1}^{m - k - 2} [/mm] (m - (j + n + 1) + 1)$ Moeglichkeiten.
Wenn man das ausrechnet bzw. ausrechnen laesst, sieht man dass ein ziemlich komplizierter Term herauskommt, in dem z.B. [mm] $m^3$, $k^3$, [/mm] etc. auftauchen. Insofern kann deine Formel nicht stimmen.
> Meine Frage ist nun: Was verändert sich an diesem
> Schema,wenn der Zaun in Form eines Kreises aufgestellt
> wäre,sprich also keine Enden hätte?
> Meiner Meinung nach hatt sich ja am Grundproblem nichts
> geändert oder?
Doch, es ist naemlich eine Bedingung hinzugekommen: die Anzahl der Nullen hinter der letzten Eins plus die vor der ersten Eins muessen auch mindestens $n$ sein.
> Naja seh ich es richtig ,dass durch den
> Zusammenschluss die k-1 Lücken zu k Lücken werden und ich
> die Erste Eins meiner Folge einfach zusätlich um m Stellen
> verschieben könnte? Also es für dieses Problem m*(m-k*n)
> Möglichkeiten gibt?
So einfach geht das nicht.
Ich bezweifle, dass man fuer dieses Problem eine einfache Formel herausbekommt. Erzaehl doch mal lieber wo du das Problem her hast bzw. wie du darauf gekommen bist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:45 Sa 25.04.2009 | | Autor: | Bossebaby |
Hey Felix...
Danke erstmal für die Antwort!
ich hab das über k vergessen beim offenen zaun denn es gibt natürlich
[mm] \vektor{m-(k-1)*n\\ k} [/mm] Möglichkeiten denn du hast ja (k-1) Lücken der Länge n!
Jetzt beim geschlossenen Zaun dachte ich der einzige Unterschied ist das es eine Lücke mehr gibt und man die erste 1 um m-1 Stellen verschieben kann also [mm] m*\vektor{m-k*n\\ k} [/mm] Möglichkeiten der neuen Situation!!?
Deine Doppelsumme kann ich nicht ganz nachvollziehen, abba die hast du ja auch aus meiner falschen Formel gezogen...
Das ist übriegens ein Problem aus ner Übung der diskreten Mathematik,die wir vor 2 Wochen mal in den Übungen hatten! Und als ich meinen Prof gefragt habe ,meinte er nur ich müsste bei der geschlossenen Variante eine Fallunterscheidung machen!? Ich wüsste nur überhaupt nicht was ich da unterscheiden sollte? gerade und ungerade Anzahl m??? Scheint mir für ne allgemeine Formel hier nicht so sinnvoll!
Wär schön wenn du dir dasnochmal überlegen könntest ,denn anscheinend versteh ich da iwas an der Logik nicht!
LG Basti
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:02 Sa 25.04.2009 | | Autor: | felixf |
Hallo Basti!
> Danke erstmal für die Antwort!
> ich hab das über k vergessen beim offenen zaun denn es
> gibt natürlich
> [mm]\vektor{m-(k-1)*n\\ k}[/mm] Möglichkeiten denn du hast ja (k-1)
> Lücken der Länge n!
Aah, das macht mehr Sinn. Und das stimmt sogar wuerd ich sagen 
> Jetzt beim geschlossenen Zaun dachte ich der einzige
> Unterschied ist das es eine Lücke mehr gibt und man die
> erste 1 um m-1 Stellen verschieben kann also
> [mm]m*\vektor{m-k*n\\ k}[/mm] Möglichkeiten der neuen Situation!!?
Ganz so einfach geht das nicht, da du jetzt einige Sachen doppelt zaehlst.
Eventuell koenntest du eine Summe ueber den Index der ersten Latte machen, und die restlichen dann mit einem Binomialkoeffizienten abhandeln. Wenn der Index der ersten Latte zu weit vorne ist muss der Index der letzten Latte vom Ende wegbegrenzt werden, ansonsten kann er auch am Ende stehen. Insofern teilst du die Summe in zwei Summen auf; koennte auch sein dass dein Prof das mit Fallunterscheidung meinte.
Oder es gibt noch ne andere Loesung die mir grad nicht auffaellt...
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:19 So 26.04.2009 | | Autor: | Bossebaby |
Ja genau das mit den Sequenzen ,die sich widerholen hab ich mir auch überlegt,abba dann hatten wir letztens das Lemma von Raney,falls dir das ein Begriff ist und ich war mir nicht sicher ob das nur für Summen oder auch für Folgen gilt..Es ist zwar iwie logisch das sich 0-1 Folgen wiederholen wenn du sie um m Stellen verschiebst,abba einen Lösungsweg hab ich nich gefunden,denn ich konnte keine Vorschrift für die Abzählung finden und ich hab mir echt den Kopf zerbrochen!Naja,ich werd Dienstag meinen Prof nochmal fragen und poste dir dann die Antwort,abba erstma vielen Dank das du dich überhaupt damit auseinandergesetzt hast!! Schönes WE dir noch und auf bald
LG Basti
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 05:17 So 26.04.2009 | | Autor: | felixf |
Moin Basti!
> Ja genau das mit den Sequenzen ,die sich widerholen hab ich
> mir auch überlegt,abba dann hatten wir letztens das Lemma
> von Raney,falls dir das ein Begriff ist
War's mir nicht, hab's aber mal nachgeschaut. Allerdings weiss ich nicht ob ihr nicht vielleicht eine recht andere Formulierung hattet, bei dieser zumindest hab ich keine Idee wie/ob man das hier anwenden koennte.
> Naja,ich werd Dienstag meinen Prof
> nochmal fragen und poste dir dann die Antwort,
Darauf bin ich gespannt! :)
Ich hab mittlerweile den Weg ueber die Summe weiter verfolgt, und hab als Ergebnis folgende Formel herausbekommen: $(n - 1) [mm] \binom{m - k n - 1}{k - 1} [/mm] + [mm] \binom{m - k n + 1}{k}$.
[/mm]
Ich hoffe ich hab nicht nirgendwo verzaehlt... Der erste Term kommt von den Faellen, wo die erste Latte an den Stellen $1, [mm] \dots, [/mm] n-1$ steht und somit hinten eine gewisse Menge Platz gelassen werden muss. Der hintere Term beschreibt die restlichen Moeglichkeiten, wobei ich hier erst eine Indextransformation gemacht hab (um ueber Binomialkoeffizienten zu summieren wo oben nur die Laufvariable drinnen steht, und dann die Formel [mm] $\sum_{i=A}^B \binom{i}{A} [/mm] = [mm] \binom{B + 1}{A + 1}$ [/mm] zu benutzen um alles zu einem Binomialkoeffizient zusammenzufassen.)
Dir auch noch ein schoenes Wochenende!
LG Felix
|
|
|
|
