mikrocontroller.net

Forum: Offtopic Kombinatorik: Klammer setzen


Autor: Daniel (root) (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Daniel (root) (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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
>>> 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 :-)

Autor: Johann L. (gjlayde) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Yahoo-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.