Anzahl an Folgen mit genau k runs

13.12.2018, 07:16	Studentu	Auf diesen Beitrag antworten »
Anzahl an Folgen mit genau k runs Hallo allerseits, ich habe mal wieder ein kombinatorisches Problem: Die Anzahl an "runs" einer Folge $\begin{eqnarray} a_1, ..., a_n \end{eqnarray}$ sei definiert durch: die Folge hat k runs <--> es gibt genau k-1 Indizes $\begin{eqnarray} 1 \leq j < n \end{eqnarray}$ mit $\begin{eqnarray} a_j > a_{j+1} \end{eqnarray}$ . Ich versuche nun nachzuvollziehen, dass es unter allen Folgen $\begin{eqnarray} a_1, ..., a_n \in \{0,1\}^n \end{eqnarray}$ genau $\begin{eqnarray} \binom{n+1}{2k-1} \end{eqnarray}$ Folgen mit genau k runs gibt. Mir ist klar, dass man sich eine Folge von 0-er und 1-er Blöcken anschauen muss und daher habe ich versucht, mir zu überlegen, wieviele Möglichkeiten man bei einer Folge hat, einen Anfangsindex für einen 0er-Block auszuwählen, sodass es genau k runs gibt, aber dann muss man ja auch noch die Endindizes der Blöcke betrachten und das Ganze wird viel komplizierter. Vielleicht bin ich damit auch total auf dem Holzweg... Schafft es jemand von euch, nachzuvollziehen, wie man auf diese Anzahl kommt?
13.12.2018, 10:55	HAL 9000	Auf diesen Beitrag antworten »
In einem ersten Schritt hängen wir künstlich vorn $\begin{eqnarray} a_0=0 \end{eqnarray}$ und hinten $\begin{eqnarray} a_{n+1}=1 \end{eqnarray}$ an die Sequenz, wir betrachten also alle Sequenzen der Länge $\begin{eqnarray} (n+2) \end{eqnarray}$ , die mit 0 beginnen und auf 1 enden. Jetzt schauen wir uns in dieser Sequenz die Positionen aller Wechsel 01 bzw. 10 an. Die finden auf jeden Fall immer im Wechsel statt, und sowohl der erste als auch der letzte solcher Wechsel ist vom Typ 01. Wenn es also wie bei den $\begin{eqnarray} k \end{eqnarray}$ -Runs gefordert genau $\begin{eqnarray} (k-1) \end{eqnarray}$ Wechsel 10 geben soll, dann liegen zwischen denen sowie außen umrahmt genau $\begin{eqnarray} k \end{eqnarray}$ Wechsel 01. Die Positionen dieser insgesamt $\begin{eqnarray} (2k-1) \end{eqnarray}$ Wechsel sind frei wählbar aus den Positionen $\begin{eqnarray} 0,\ldots,n \end{eqnarray}$ der künstlich erweiterten Sequenz, das ergibt $\begin{eqnarray} \binom{n+1}{2k-1} \end{eqnarray}$ Auswahlmöglichkeiten. P.S.: Man kann auf diese Vorüberlegung mit der künstlichen Erweiterung der Sequenz verzichten, hat dann aber das Problem, dass man die vier Fälle 0...0, 0...1, 1...0 und 1...1 von Sequenzen der Länge $\begin{eqnarray} n \end{eqnarray}$ getrennt diskutieren muss. Mit der Erweiterung umschifft man diese Fallunterscheidung in eleganter Weise.
14.12.2018, 04:13	Studentu	Auf diesen Beitrag antworten »
Toll erklärt, danke Hal! Bekommt man diese kombinatorischen Sachen auch mit der Zeit einfach ins Gefühl oder hat man einfach das Glück, dass sie einem klar sind oder das Pech, dass dies eben nicht der Fall ist?
14.12.2018, 09:01	HAL 9000	Auf diesen Beitrag antworten »
Ich hab das glaube ich schon öfter hier geschrieben: Diesen "man" kenne ich nicht. Bei solchen Problemstellungen kommt es ja darauf an, die Situation so zu abstrahieren, dass ein vorhandenes kombinatorisches Modell anwendbar ist. Hier bei dieser Aufgabe klappt das sogar (mehr oder weniger) direkt, in vielen Situationen muss man das Problem aber auch noch geeignet zerlegen, ggfs. mit Fallunterscheidungen, bis die Teilprobleme klein genug sind, um auf sie solche Abstraktionen anwenden zu können. Das ist oft ziemlich mühsam, der Weg ist nicht immer sofort klar, d.h., man muss auch mal eine Idee probieren und oft dann auch wieder verwerfen. Dabei lauern diverse Fallstricke, etwa dass man bei solchen Zählproblemen Fälle vergisst oder mehrfach zählt. Manch einer mag sich noch so eine Mühe geben, diese Art Problemanalyse kriegt er einfach nicht hin. Anderen liegt es eher, aber auch die benötigen Übung und viele Beispiele, bis sie ein gutes Gespür dafür entwickeln, zu letzteren würde ich mich in aller Bescheidenheit zählen. D.h., ich glaube nicht dass man es erzwingen kann, aber man kann zumindest versuchen, sich da zu verbessern.
17.12.2018, 05:54	Studentu	Auf diesen Beitrag antworten »
Du hast Recht, "man" sollte nicht vergeneralisieren. Verstehe... Dann gehöre ich jetzt zur dritten Gruppe, die noch fleißig übt und ausprobiert, um hoffentlich eines Tages festzustellen, dass sie wie du zur zweiten Gruppe gehört.

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »