Funktionen abzählen

09.05.2015, 09:29

daLoisl

Funktionen abzählen

Guten Tag,

ich soll die Anzahl aller monoton wachsenden Funktionen $\begin{eqnarray*} f: \{1, ..., n\} \to \{1, ..., n\} \end{eqnarray*}$ mit $\begin{eqnarray*} \forall i \in \{1, ..., n\}: f(i) \le i \end{eqnarray*}$ bestimmen.

Für die ersten paar n habe ich die Funktionen abgezählt und komme zu der Vermutung, das es sich jeweils um die n-te Catalan-Zahl handelt.
Allerdings weiß ich jetzt nicht, wie ich das beweisen kann, denn ich finde weder Rekursionsvorschrift noch eine Bijektion zu einer Menge deren Mächtigkeit ich kenne (zB Dyck-Pfade, Triangulierungen konvexer n-Ecke).

Ich würde mich sehr über Ratschläge dazu freuen smile

daLoisl

09.05.2015, 12:33

Math1986

Auf diesen Beitrag antworten »

RE: Funktionen abzählen
Du kommst hier vermutlich per Rekursion weiter:
Sei dazu $\begin{eqnarray*} F_n \end{eqnarray*}$ die Anzahl aller monoton wachsenden Funktionen $\begin{eqnarray*} f\colon \{1, ..., n\} \to \{1, ..., n\} \end{eqnarray*}$ mit $\begin{eqnarray*} \forall i \in \{1, \ldots, n\}: f(i) \le i \end{eqnarray*}$ und $\begin{eqnarray*} F_{n,k} \end{eqnarray*}$ die Anzahl solcher Funktionen $\begin{eqnarray*} f \end{eqnarray*}$ mit $\begin{eqnarray*} f(n)=k \end{eqnarray*}$ , $\begin{eqnarray*} 1\leq k\leq n \end{eqnarray*}$ .
Dann ist offenbar
$\begin{eqnarray*} F_n=\sum_{k=1}^nF_{n,k} \end{eqnarray*}$

$\begin{eqnarray*} F_{n,k} \end{eqnarray*}$ ist dabei jeweils die Anzahl aller monoton wachsenden Funktionen $\begin{eqnarray*} f\colon \{1, \ldots, n-1\} \to \{1,\ldots, k\} \end{eqnarray*}$ mit $\begin{eqnarray*} \forall i \in \{1,\ldots,n-1\}\colon f(i) \le i \end{eqnarray*}$ .
Ist $\begin{eqnarray*} f(n-1)=k \end{eqnarray*}$ so gibt es $\begin{eqnarray*} F_{n-1,k} \end{eqnarray*}$ solcher Funktionen, sonst gibt es $\begin{eqnarray*} F_{n-1,k-1} \end{eqnarray*}$ solcher Funktionen, also $\begin{eqnarray*} F_{n,k}=F_{n-1,k}+F_{n-1,k-1} \end{eqnarray*}$
Vermutlich kannst du diese Rekursion dann irgendwie auf die Catalan-Zahlen zurückführen.

09.05.2015, 16:15

daLoisl

Auf diesen Beitrag antworten »

Danke für die Antwort!

Zitat:

Ist $\begin{eqnarray*} f(n-1)=k \end{eqnarray*}$ so gibt es $\begin{eqnarray*} F_{n-1,k} \end{eqnarray*}$ solcher Funktionen, sonst gibt es $\begin{eqnarray*} F_{n-1,k-1} \end{eqnarray*}$ solcher Funktionen, also $\begin{eqnarray*} F_{n,k}=F_{n-1,k}+F_{n-1,k-1} \end{eqnarray*}$

Müsste es nicht $\begin{eqnarray*} F_{n,k}=F_{n-1,k}+F_{n,k-1} \end{eqnarray*}$ sein?

Weil für k > n $\begin{eqnarray*} F_{n,k}=0 \end{eqnarray*}$ gilt, komme ich damit auf:
$\begin{eqnarray*} F_{n,k} = \sum\limits_{i_1=1}^{min(k,n-1)} \sum\limits_{i_2=1}^{min(i_1,n-2)} \sum\limits_{i_3=1}^{min(i_2,n-3)} ... \sum\limits_{i_{n-1}=1}^{min(i_{n-2},1)} F_{1,i_{n-1}} \end{eqnarray*}$

Wegen $\begin{eqnarray*} F_{1,1} = 1 \end{eqnarray*}$ folgt:
$\begin{eqnarray*} F_n = \sum\limits_{k=1}^{n} \sum\limits_{i_1=1}^{min(k,n-1)} \sum\limits_{i_2=1}^{min(i_1,n-2)} \sum\limits_{i_3=1}^{min(i_2,n-3)} ... \sum\limits_{i_{n-2}=1}^{min(i_{n-3},2)} 1 \end{eqnarray*}$

Stimmt das bisher und kann man das irgendwie ausrechnen?

09.05.2015, 20:03

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von daLoisl
Danke für die Antwort!

Zitat:

Müsste es nicht $\begin{eqnarray*} F_{n,k}=F_{n-1,k}+F_{n,k-1} \end{eqnarray*}$ sein?

Nein, warum? verwirrt

09.05.2015, 20:47

daLoisl

Auf diesen Beitrag antworten »

Zitat:

Nein, warum? verwirrt

$\begin{eqnarray*} F_{n,k}= |\{f: \{1, ...,n-1\} \to \{1, ..., k\} | \forall i, j \in \{1, ..., n-1\}: i < j \Rightarrow f(j) \le f(j) \wedge f(i) \le i\} | = |\{f: \{1, ...,n-1\} \to \{1, ..., k\} | (\forall i, j \in \{1, ..., n-1\}: i < j \Rightarrow f(j) \le f(j) \wedge f(i) \le i) \wedge f(n-1)=k\} \cup \{f: \{1, ...,n-1\} \to \{1, ..., k\} | (\forall i, j \in \{1, ..., n-1\}: i < j \Rightarrow f(j) \le f(j) \wedge f(i) \le i) \wedge f(n-1) \ne k\} | = |\{f: \{1, ...,n-2\} \to \{1, ..., k\} | (\forall i, j \in \{1, ..., n-2\}: i < j \Rightarrow f(j) \le f(j) \wedge f(i) \le i)\} | + |\{f: \{1, ...,n-1\} \to \{1, ..., k-1\} | (\forall i, j \in \{1, ..., n-1\}: i < j \Rightarrow f(j) \le f(j) \wedge f(i) \le i)\}| = F_{n-1,k} + F_{n,k-1} \end{eqnarray*}$

Es kann gut sein, dass ich da den einen oder anderen Fehler eingebaut habe.
Das Ganze ist aber nicht besonders tragisch, da ich mittlerweile schon eine Bijektion von unserer Menge auf die der Dyck-Pfade der Länge 2n gefunden habe und von denen kenne ich bereits die Mächtigkeit.

10.05.2015, 09:59

Math1986

Auf diesen Beitrag antworten »

Zitat:

Original von daLoisl

Zitat:

Nein, warum? verwirrt

Ja, das stimmt wohl.

Zitat:

Original von daLoisl
Das Ganze ist aber nicht besonders tragisch, da ich mittlerweile schon eine Bijektion von unserer Menge auf die der Dyck-Pfade der Länge 2n gefunden habe und von denen kenne ich bereits die Mächtigkeit.

Und wie sieht die aus?

10.05.2015, 12:34

daLoisl

Auf diesen Beitrag antworten »

Zitat:

Und wie sieht die aus?

Einen Dyck-Pfad kann man als 0/1-Vektor der Länge 2n mit jeweils genau n 0en (Pfeil nach oben) und n 1en (Pfeil nach unten) schreiben, wobei in jedem Anfangsstück des Vektors nicht mehr 1en als 0en vorkommen dürfen. Wenn ich die Funktion $\begin{eqnarray*} f \end{eqnarray*}$ auf den Dyckpfad $\begin{eqnarray*} (0, \underbrace{1, ..., 1,}_{\substack{f(2)-f(1) mal}} 0, \underbrace{1, ..., 1,}_{\substack{f(3)-f(2) mal}} 0, ..., 0, \underbrace{1, ..., 1,}_{\substack{f(n)-f(n-1) mal}} 0, \underbrace{1, ..., 1}_{\substack{n-f(n)+1 mal}}) \end{eqnarray*}$ abbilde, kann man unter Berücksichtigung von $\begin{eqnarray*} 1 \le f(i) \le i \end{eqnarray*}$ zeigen, dass es sich um eine bijektive Abbildung handelt.

10.05.2015, 14:33

RavenOnJ

Auf diesen Beitrag antworten »

Du meinst wahrscheinlich
$\begin{eqnarray*} (0, \underbrace{1, ..., 1,}_{\substack{f(2)-f(1) mal}} 0, \underbrace{1, ..., 1,}_{\substack{f(3)-f(2) mal}} 0, ..., 0, \underbrace{1, ..., 1,}_{\substack{f(n)-f(n-1) mal}} 0, \underbrace{1, ..., 1}_{\substack{n-f(n)+{\color{red}f(1)} mal}}) \end{eqnarray*}$

10.05.2015, 16:27

daLoisl

Auf diesen Beitrag antworten »

Ja, aber es gilt $\begin{eqnarray*} f(1)=1 \end{eqnarray*}$ , weil $\begin{eqnarray*} 1\le f(i) \le i \end{eqnarray*}$

10.05.2015, 17:16

RavenOnJ

Auf diesen Beitrag antworten »

Zitat:

Original von daLoisl
Ja, aber es gilt $\begin{eqnarray*} f(1)=1 \end{eqnarray*}$ , weil $\begin{eqnarray*} 1\le f(i) \le i \end{eqnarray*}$

Klar, hatte das $\begin{align*} f(i) \le i \end{align*}$ nicht beachtet. Die Bijektivität mit den Dyck-Pfaden wäre dann ja auch nicht gegeben.

Neue Frage »

Antworten »

Funktionen abzählen

Verwandte Themen