Catalantall

Fra Wikipedia, den frie encyklopedi
Hopp til navigering Hopp til søk

Catalantallene er en følge av naturlige tall som ofte forekommer i telleproblemer i kombinatorikk. For n ≥ 0, betegnes det n´te catalantallet Cn, og er gitt ved formelen

De første catalantallene er

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452.

Catalantallene er oppkalt etter den belgiske matematikeren Eugène Charles Catalan. Begrepet «Catalantall» (Catalan numbers) ble første gang kjent brukt i 1938 av den skotske matematikeren Eric Temple Bell.[1]

Egenskaper[rediger | rediger kilde]

Catalantallene vokser asymptotisk som[trenger referanse]

Tallene tilfredsstiller den rekursive formelen[trenger referanse]

som forklarer hvorfor Cn så ofte dukker opp som svaret på kombinatoriske telleproblemer.

Den genererende funksjonen er[trenger referanse]

Anvendelser i kombinatorikk[rediger | rediger kilde]

  • Cn er antall måter et polygon med n+2 kanter kan deles opp i trekanter ved hjelp av n diagonaler.
Eksempler på catalantall i polygoner
  • Cn er antall måter n par av venstre- og høyreparenteser '(' og ')' kan skrives etter hverandre slik at hver høyreparentes lukker en venstreparentes.
((()))   (()())   (())()   ()(())   ()()()
Eksempler på catalantall som binære trær

Referanser[rediger | rediger kilde]

  1. ^ «Earliest Known Uses of Some of the Words of Mathematics (C)». Jeff Miller. 25. juni 2017. Besøkt 7. februar 2019. 

Eksterne lenker[rediger | rediger kilde]