Catalantall

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

  
    
      
        
          C
          
            n
          
        
        =
        
          
            1
            
              n
              +
              1
            
          
        
        
          
            
              (
            
            
              
                2
                n
              
              n
            
            
              )
            
          
        
        .
      
    
    {\displaystyle C_{n}={\frac {1}{n+1}}{2n \choose n}.}
  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.


== Egenskaper ==
Catalantallene vokser asymptotisk som

  
    
      
        
          C
          
            n
          
        
        ∼
        
          
            
              4
              
                n
              
            
            
              
                n
                
                  3
                  
                    /
                  
                  2
                
              
              
                
                  π
                
              
            
          
        
        .
      
    
    {\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}.}
  Tallene tilfredsstiller den rekursive formelen

  
    
      
        
          C
          
            n
            +
            1
          
        
        =
        
          ∑
          
            k
            =
            0
          
          
            n
          
        
        
          C
          
            n
          
        
        
          C
          
            n
            −
            k
          
        
        ,
      
    
    {\displaystyle C_{n+1}=\sum _{k=0}^{n}C_{n}C_{n-k},}
  som forklarer hvorfor Cn så ofte dukker opp som svaret på kombinatoriske telleproblemer.
Den genererende funksjonen er

  
    
      
        C
        (
        z
        )
        =
        
          ∑
          
            n
            =
            0
          
          
            ∞
          
        
        
          C
          
            n
          
        
        
          z
          
            n
          
        
        =
        
          
            
              1
              −
              
                
                  1
                  −
                  4
                  z
                
              
            
            
              2
              z
            
          
        
        .
      
    
    {\displaystyle C(z)=\sum _{n=0}^{\infty }C_{n}z^{n}={\frac {1-{\sqrt {1-4z}}}{2z}}.}
  


== Anvendelser i kombinatorikk ==
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:
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.


== Referanser ==


== Eksterne lenker ==
Catalantallene: følge A000108 i OEIS
(en) Eric W. Weisstein, Catalan Number i MathWorld.