Kombinatorik: Klammer setzen

[Daniel (root) (Gast)]

Hallo,

ich möchte mit einer Aufgabe die Offtopic Rechenleistung
etwas beanspuchen^^

Diese Aufgabe ist kein "Homework". (um mal vorzubeugen)

Wenn man eine binäre Operation x hat, zum Beispiel in infix Notation
Binär bezieht sich auf Parameteranzahl. Auf wieviele Arten lässt sich
das Klammern?

a x b
    => 1

(a x b) x c
a x (b x c)
    => 2

((a x b) x c) x d
(a x b) x (c x d)
(a x (b x c)) x d
a x ((b x c) x d)
a x (b x (c x d))
    => 5

... to continue


Wichtig ist, dass man die Operanden an ihrer Stelle belässt.
Wenn eine Klammerung vorliegt, liessen sich die Operanden
immernoch auf n! Arten verstellen. Deswegen will ich die
nur Klammerungszahl haben.

Eine Überlegung von mir war es, Klammerplätze zu permutieren.
Das geht aber nicht, weil Klammerung gewisse Regel mitbringt.

Ich könnte mir denken, dass diese Aufgabe info-mathe Studium typisch
sind und vielleicht manchen hier bekannt ist.

MfG, Daniel

[Johann L. (gjlayde)]

Daniel (root) schrieb:
> Wenn man eine binäre Operation x hat, zum Beispiel in infix Notation
> Binär bezieht sich auf Parameteranzahl. Auf wieviele Arten lässt sich
> das Klammern?

Es gibt unendlich viele Möglichkeiten:

a
(a)
((a))
(((a)))
((((a))))
...

Johann

[Johann L. (gjlayde)]

...und wenn solche mathematischen Spitzfindigkeiten nicht gewollt sind, 
findet man leicht die Rekursionsformel

$$\begin{align} k_1 &= 1 \\ k_n &= \sum_{i=1}^{n-1} k_i k_{n-i} \quad \mathrm{f\ddot ur}\ n > 1 \end{align}$$

wie man von da aus zu einer expliziten Formel wie

$$k_{n+1} = \frac{(2n)!}{(n+1)!\,n!}$$

kommt, ist dann Hausaufgabe :-)

Viel Spaß damit!

Johann

[Johann L. (gjlayde)]

Und hab eben noch eine andere interessante Darstellung gefunden, die 
eine Brücke zur Analysis schlägt. Die Folge k_n lässt sich auch 
definieren über die Potenzreihe:

$$f(x) = \frac{1-\sqrt{1-4x}}{2x}=\sum_{n=0}^\infty k_{n+1}x^n$$

Weil f um 0 analytisch ist, werden damit die Koeffizienten k_n eindeutig 
definiert.

Johann

[Daniel (root) (Gast)]

Hallo Johaan,

ich backe kleinere Brötchen :-) Ich würde diese 3 Formel gegen
das Verständnis der ersten austauschen ...

Ehrlich gesagt erkenne ich keine Struktur in der rekuriven Folge
Hier mal Pythoncode

>>> def k(n):
...     if n in [0,1]:
...             return 1
...     s = 0
...     for i in range(1,n):
...             s+=k(i)*k(n-i)
...     return s
...
>>>
>>> [k(i) for i in range(0,10)]
[1, 1, 1, 2, 5, 14, 42, 132, 429, 1430]

Aber die ersten Werte scheinen übereinzustimmen.

k(4) = k(1)*k(3)+k(2)*k(2)+k(3)*k(1) =
2 * k(1)*{k(1)*k(2)+k(2)*k(1)}+{k(1)*k(1)*k(1)*k(1)} =
4 * k(1)^2 * k(2) + k(1)^4 = 4*1+1 = 5

vielleicht sehe ich im Traum die Struktur :-)

[Johann L. (gjlayde)]

Daniel (root) schrieb:
> Hallo Johaan,
>
> ich backe kleinere Brötchen :-) Ich würde diese 3 Formel gegen
> das Verständnis der ersten austauschen ...
>
> Ehrlich gesagt erkenne ich keine Struktur in der rekuriven Folge
> Hier mal Pythoncode

Die Struktur erkennt man nicht durch schnöde Zahlen -- auch dann nicht, 
wenn die 42 darunter ist ;-)

> vielleicht sehe ich im Traum die Struktur :-)

...und den Wald trotz der Bäume

N8

Johann