Kombinatorik: Klammer setzen

Daniel (root) Gast #1284258
Lesenswert?
• ▲
▼ 
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
Beitrag melden Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Markierten Text zitieren Antwort Antwort mit Zitat
Johann L. Persönliche Seite #1284437
Lesenswert?
• ▲
▼ 
...und wenn solche mathematischen Spitzfindigkeiten nicht gewollt sind, 
findet man leicht die Rekursionsformel


wie man von da aus zu einer expliziten Formel wie
kommt, ist dann Hausaufgabe :-)

Viel Spaß damit!

Johann
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Johann L. Persönliche Seite #1284463
Lesenswert?
• ▲
▼ 
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:


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

Johann
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Daniel (root) Gast #1284756
Lesenswert?
• ▲
▼ 
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

1
>>> def k(n):

2
...     if n in [0,1]:

3
...             return 1

4
...     s = 0

5
...     for i in range(1,n):

6
...             s+=k(i)*k(n-i)

7
...     return s

8
...

9
>>>

10
>>> [k(i) for i in range(0,10)]

11
[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 :-)
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Johann L. Persönliche Seite #1284779
Lesenswert?
• ▲
▼ 
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
Beitrag melden Bearbeiten Löschen Markierten Text zitieren Antwort Antwort mit Zitat
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren