Catalantall
Utseende
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 n trekanter ved hjelp av diagonaler som ikke krysser hverandre. For eksempel for n = 3 kan en slik triangulering av femkanten foregå på 5 forskjellige måter:
![Eksempler på catalantall i polygoner](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/3/36/Catalan_number_polygons_example.png)
- 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.
((())) (()()) (())() ()(()) ()()()
- Cn er antall binære trær med n+1 blader.
![Eksempler på catalantall som binære trær](http://178.128.105.246/cars-http-upload.wikimedia.org/wikipedia/commons/0/01/Catalan_number_binary_tree_example.png)
Referanser
[rediger | rediger kilde]- ^ «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]- Catalantallene: følge A000108 i OEIS
- (en) Eric W. Weisstein, Catalan Number i MathWorld.