Skip to content
The Chat Archive
qwen3-235b-a22b· Alibaba (Qwen) LMArena Human Preference 140K

Beispiele für Catalan-Zahlen und Stirling Zahlen 1 und 2

  1. User

    Beispiele für Catalan-Zahlen und Stirling Zahlen 1 und 2

  2. Assistant

    Catalan-Zahlen:

    Definition:
    Die Catalan-Zahlen CnC_n zählen verschiedene kombinatorische Strukturen und sind durch die Formel

    Cn=1n+1(2nn)C_n = \frac{1}{n+1} \binom{2n}{n}

    definiert.

    Beispiele für kleine nn:

    • C0=1C_0 = 1 (leere Struktur)
    • C1=1C_1 = 1 (z.B. eine Klammerpaar () oder ein Pfad mit einem Auf- und Abstieg)
    • C2=2C_2 = 2 (z.B. zwei Klammerungen: ()() und (()))
    • C3=5C_3 = 5 (z.B. fünf verschiedene Klammerungen wie ((())), (()()), etc.)
    • C4=14C_4 = 14

    Anwendungen:

    • Anzahl der Dyck-Pfade (Pfade von (0,0)(0,0) nach (2n,0)(2n,0) mit Schritten ↑\uparrow und ↓\downarrow, die nie unter die x-Achse sinken)
    • Anzahl der triangulierten (n+2)(n+2)-Ecke
    • Anzahl der vollständig geklammerten Ausdrücke mit nn Paaren

    Stirling-Zahlen erster Art (ungezeichnet):

    Definition:
    Die ungezeichneten Stirling-Zahlen erster Art s(n,k)s(n,k) zählen die Anzahl der Permutationen von nn Elementen mit genau kk Zyklen.

    Beispiele für kleine nn und kk:

    • s(3,1)=2s(3,1) = 2 (z.B. die Zyklen (1 2 3)(1\,2\,3) und (1 3 2)(1\,3\,2))
    • s(3,2)=3s(3,2) = 3 (z.B. die Permutationen mit zwei Zyklen: (1)(2 3)(1)(2\,3), (2)(1 3)(2)(1\,3), (3)(1 2)(3)(1\,2))
    • s(3,3)=1s(3,3) = 1 (die Identität mit drei Zyklen)
    • s(4,2)=11s(4,2) = 11 (Permutationen mit zwei Zyklen, z.B. (1 2 3)(4)(1\,2\,3)(4), (1 2)(3 4)(1\,2)(3\,4), etc.)

    Rekursion:

    s(n,k)=s(n−1,k−1)+(n−1)⋅s(n−1,k)s(n,k) = s(n-1,k-1) + (n-1) \cdot s(n-1,k)

    Stirling-Zahlen zweiter Art:

    Definition:
    Die Stirling-Zahlen zweiter Art S(n,k)S(n,k) zählen die Anzahl der Partitionen einer nn-elementigen Menge in kk nicht-leere Teilmengen.

    Beispiele für kleine nn und kk:

    • S(3,1)=1S(3,1) = 1 (eine Teilmenge: {a,b,c}\{a,b,c\})
    • S(3,2)=3S(3,2) = 3 (Partitionen: {{a},{b,c}}\{\{a\},\{b,c\}\}, {{b},{a,c}}\{\{b\},\{a,c\}\}, {{c},{a,b}}\{\{c\},\{a,b\}\})
    • S(3,3)=1S(3,3) = 1 (drei Teilmengen: {{a},{b},{c}}\{\{a\},\{b\},\{c\}\})
    • S(4,2)=7S(4,2) = 7 (sieben Partitionen einer 4-Menge in zwei Teilmengen)
    • S(4,3)=6S(4,3) = 6 (z.B. {{a,b},{c},{d}}\{\{a,b\},\{c\},\{d\}\}, etc.)

    Rekursion:

    S(n,k)=S(n−1,k−1)+k⋅S(n−1,k)S(n,k) = S(n-1,k-1) + k \cdot S(n-1,k)

    Zusammenhang zu Bell-Zahlen:
    Die Bell-Zahl BnB_n ist die Summe aller S(n,k)S(n,k) für k=1k=1 bis nn:

    Bn=∑k=1nS(n,k)B_n = \sum_{k=1}^n S(n,k)

    Beispiel: B3=S(3,1)+S(3,2)+S(3,3)=1+3+1=5B_3 = S(3,1) + S(3,2) + S(3,3) = 1 + 3 + 1 = 5.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.