Menu Close

Números de Catalan

Los números de Catalan forman la sucesión cuyo término general es
Numeros_de_Catalan_1

Los primeros números de Catalan son

   1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786

Los números de Catalan satisfacen la siguiente relación de recurrencia:
Numeros_de_Catalan_2

Asintóticamente, los números de Catalan crecen como:
Numeros_de_Catalan_3
considerando que el cociente entre el n-ésimo número de Catalan y la expresión de la derecha tiende hacia 1 cuando n tiende a infinito.

Definir las funciones

   catalan :: [Integer]
   grafica :: Int -> Int -> IO ()

tales que

  • catalan es la lista de términos de la sucesión de Catalan. Por ejemplo,
     λ> take 12 catalan
     [1,1,2,5,14,42,132,429,1430,4862,16796,58786]
     λ> length (show (catalan !! 50000))
     30096
  • (grafica a b) dibuja los n-ésimos términos de la sucesión de Catalan, para n entre a y b, junto con los de la expresión de la derecha de
    Numeros_de_Catalan_3
    Por ejemplo, (grafica 5 10) dibuja
    Numeros_de_Catalan_4
    y (grafica 55 60) dibuja
    Numeros_de_Catalan_5

Soluciones

import Graphics.Gnuplot.Simple
 
catalan :: [Integer]
catalan = scanl (\c n -> c*2*(2*n-1) `div` (n+1)) 1 [1..]
 
grafica :: Int -> Int -> IO ()
grafica a b = 
  plotLists [Key Nothing]
            [[(fromIntegral n, fromIntegral (catalan !! n)) | n <- [a..b]]
            ,[(n,4**n/(n**(3/2)*(sqrt pi))) | n <- [c..d]]]
  where c, d :: Double
        c = fromIntegral a
        d = fromIntegral b

12 soluciones de “Números de Catalan

  1. Juanjo Ortega (juaorture)
     
    import Graphics.Gnuplot.Simple
     
    catalan :: [Integer]
    catalan = aux 1 1
     
    aux :: Integer -> Integer -> [Integer]
    aux n x = x : aux m ((product [1..2*n])`div`(m*product [1..n] ^ 2))
        where m = n + 1
     
    grafica :: Int -> Int -> IO ()
    grafica a b = plotLists [Key Nothing] ([[(x, f (fI x)) | x <- [a..b]],[(x,g (fI x)) | x <- [a..b]]] :: [[(Int,Double)]])
            where f n = (product [1..2*n])/((n+1)*product [1..n] ^ 2)
                  g n = 4**n / ((n ** (3/2))*sqrt(pi))
                  fI = fromIntegral
  2. ignareeva
    catalan :: [Integer]
    catalan = 1: map (floor) [numerosCatalan n | n <- [0..]]
      where numerosCatalan 0 = 1
            numerosCatalan n = (2*((2*n)+1))/(n+2) * numerosCatalan (n-1)
  3. monlagare
     
    catalan :: [Integer]
    catalan = [div (product [1..2*n]) (product [1..n+1] * product [1..n]) | n <- [0..]]
  4. eliguivil
    import Graphics.Gnuplot.Simple
     
    catalan :: [Integer]
    catalan = [(fac (2*n))`div`(fac (n+1) * fac n) | n <- [0..]]
      where
        fac n = product [1..n]
     
    grafica :: Int -> Int -> IO ()
    grafica a b = do plotLists [] [xs,ys]
      where
        xs = zip [a'..b'] catalan'
        ys :: [(Double,Double)]
        ys = zip [a'..b'] asin
        asin :: [Double]
        asin = [(4**n)/(n**(3/2)*sqrt pi) | n <- [a'..b']]
        a' = fromIntegral a
        b' = fromIntegral b
        catalan' :: [Double]
        catalan' = [fromIntegral $ (fac (2*n))`div`(fac (n+1) * fac n) | n <- [a..b]]
          where
            fac n = product [1..n]
  5. eliguivil
    import Graphics.Gnuplot.Simple (plotLists)
     
    catalan :: [Integer]
    catalan = [(fac (2*n))`div`(fac (n+1) * fac n) | n <- [0..]]
      where
        fac n = product [1..n]
     
    grafica :: Int -> Int -> IO ()
    grafica a b = do plotLists [] [xs,ys]
      where
        xs = zip [a'..b'] catalan'
        ys :: [(Double,Double)]
        ys = zip [a'..b'] asin
        asin :: [Double]
        asin = [(4**n)/(n**(3/2)*sqrt pi) | n <- [a'..b']]
        a' = fromIntegral a
        b' = fromIntegral b
        catalan' :: [Double]
        catalan' = [fromIntegral $ (fac (2*n))`div`(fac (n+1) * fac n) | n <- [a..b]]
          where
            fac n = product [1..n]
  6. marmerzaf
    listaCatalan :: [Integer]
    listaCatalan  = [factorial (2*n) `div`( factorial (n+1) *  factorial n)| n <- [0..]]
    factorial n = product [1.. n]
     
     
    catalan n =factorial (2*n)/( factorial (n+1) *  factorial n)
    cn n = 4 ** n / (n**(3/2)* n**1/2)
     
    grafica3 :: Int -> Int -> IO ()
    grafica3 a b =  plotLists [] ([[(x1, catalan( fromIntegral x1)) | x1 <- [a..b]],[(y1, cn(fromIntegral y1))| y1 <- [a..b]]] :: [[(Int,Double)]])
  7. antmorper3
    catalan :: [Integer]
    catalan = [aux n | n <- [0..]]
     where aux 0 = 1
           aux n = div (2*aux (n-1)*(2*n-1)) (n+1)
     
    grafica :: Int -> Int -> IO ()
    grafica a b = do plotLists [Key Nothing] ([[(n,fromInteger(catalan!!n)) | n <- [a..b]]
                                               ,[(n,f (fromIntegral n)) | n <- [a..b]]] :: [[(Int,Double)]])
     where f n = 4**n / (n**(3/2)*sqrt (pi))
  8. enrnarbej
    catalan :: [Integer]
    catalan = map fst cata
            where
             cata = (1,0) : map ((c,n) -> (2*c*(2*n+1) `div` (n+2),n+1)) cata
     
    -- La gráfica la representaremos en Maxima
    -- catalan (n) := (2*n)! / ((n+1)!*n!)$
    -- catalanAprox (n) := float ((4^n) / (n^(3/2)*sqrt (%pi)))$
    -- grafica (a,b) := wxplot2d([catalan (x),catalanAprox (x)],[x,a,b])$
  9. albcercid
     
    catalan :: [Integer]
    catalan = aux 1 0
       where aux a b = a:aux (div (2*(2*b + 1)*a) (b + 2)) (b + 1)
     
    grafica :: Int -> Int -> IO ()
    grafica a b = plotFuncs [] [c..d] [graf2,catalan2]
           where c = fromIntegral a
                 d = fromIntegral b
     
    graf2 :: Double -> Double
    graf2 x = (4**x)/(((x**(1.5))*sqrt (pi)))
     
     
    catalan2 :: Double -> Double
    catalan2 n =(fc (2*n))/(((fc (n))^2)*(n+1))
            where   fc x = product [1..x]
  10. glovizcas
    catalan :: [Integer]
    catalan =  [(fact(2*n))`div`(fact(n+1)*fact n) | n <- [0..]]
     
    fact :: Integer -> Integer
    fact 0 = 1
    fact n = n*fact (n-1)
     
    grafica4 :: Int -> Int -> IO ()
    grafica4 a b = plotLists [Key Nothing]
        ([[(x, fromInteger( last(take x(catalan))) ) | x <- [a..b]], 
        [(x,(expresion (fromIntegral x)))| x <- [a..b]]] :: [[(Int,Double)]] )
     
    expresion x = (4.0**x)/(x**(1.5)*pi**(0.5))
  11. antdursan
    catalan :: [Integer]
    catalan = [div (fact (2*n)) (((fact (n+1))*(fact n))) | n <- [0..]]
                  where fact 0 = 1
                        fact n = n*(fact (n-1))
     
    catalanAprox :: [Double]
    catalanAprox = [(4.0**(fromIntegral x))/((fromIntegral x)**(1.5)*pi**(0.5)) | x <- [1..]]
     
    grafica :: Int -> Int -> IO ()
    grafica a b = plotLists [] [[(x,fromInteger (head (drop (x) catalan))) | x <- [a..b]], [(x, (head (drop (x-1) (catalanAprox)))) | x <- [a..b]]]
  12. cescarde
    catalan :: [Integer]
    catalan = [c n | n <- [0..]]
     
    c :: Integer -> Integer
    c 0 = 1
    c n = f (2*n) `div` ((f (n+1))*f n)
      where f x = product [1..x]
     
     
    grafica :: Int -> Int -> IO ()
    grafica a b = do plotLists [h] ([[(n,f (catalan!!n)) | n <- [a..b]],
                                     [(n,g (f1 n)) | n <- [a..b]]] :: [[(Int,Double)]])
      where g n = 4**n / (n**(3/2)*sqrt (pi))
            h = Key Nothing
            f = fromInteger
            f1 = fromIntegral

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.