Aantal verschillende bomen-formule?

Integraalrekening, afgeleiden, rijen, convergentie & divergentie van reeksen, meervoudige integratie.
anonieme gebruiker
Nieuw lid
Nieuw lid
Berichten: 1
Lid geworden op: 17 jun 2009, 16:41

Aantal verschillende bomen-formule?

Bericht door anonieme gebruiker » 17 jun 2009, 17:10

Ik zat een beetje te puzzelen met grafen en heb een aantal dingen/formules ontdekt, maar ik heb één probleem. Ik zou graag willen weten of er een formule is, om het aantal verschillende bomen uit te rekenen. Bijvoorbeeld, als je twee punten heb, heb je één mogelijke boom (O=punt):

O---O

En als je er 3 hebt, ook 1:

O---O---O

En als je er 4 hebt, zijn er 2 mogelijke bomen:

O---O---O---O

Afbeelding

Bij 5 zijn er 3, en bij 6 zijn er 6. Dit was gegeven in het boek. Nu kan ik zelf moeilijk een formule erbij bedenken, omdat ik het verband niet weet, en niet altijd zeker ben dat ik alle mogelijke bomen heb gehad. Daarom zou ik willen weten of hier een formule bij hoort, waarbij x het aantal punten is en y het aantal mogelijke bomen.
Op de Engelse Wikipedia staat een formule die er helaas toch niet bijhoort. Die is y=x^(x-2). Die werkt alleen als alle punten 'gelabeld' zijn, dus als je 3 punten hebt, die allemaal verschillend zijn. Noem ze bijvoorbeeld A, B en C, dan heb je volgens die formule 3 mogelijkheden:

A---B---C
B---A---C
B---C---A

Maar is er ook een formule voor het aantal mogelijke bomen als alle punten hetzelfde zijn (dus niet gelabeld)?

Bedankt. :)

Plaats reactie