Catalan numbers

Let's consider the implementation of the algorithm for calculating Catalan numbers in the Julia language.

Introduction

In this example, we will study the implementation of an algorithm for calculating Catalan numbers, a sequence of natural numbers that are important in combinatorics and other areas of mathematics. We will look at how the Catalan number calculation function works, as well as how it applies to a range of values and to large numbers.

What are Catalan numbers?

Catalan numbers are a sequence of numbers that is often found in combinatorics problems. For example, they are used to count the number of correct bracket sequences, the number of paths on a lattice, the number of ways to split a polygon into triangles, and so on.

The formula for calculating the nth Catalan number looks like this:

where — the binomial coefficient.

This formula is used in the code.

# Определяем функцию для вычисления числа Каталана
# n::Integer означает, что аргумент должен быть целым числом
# binomial(2n, n) вычисляет биномиальный коэффициент
# ÷ обозначает целочисленное деление
catalannum(n::Integer) = binomial(2n, n) ÷ (n + 1)

catalannum (generic function with 1 method)

Calculating Catalan numbers for the range from 1 to 15

Function catalannum.(1:15) applies the function catalannum for each element in the range from 1 to 15. The dot after the function name means vectorization, which is the application of a function to each element of a collection.

The result will be an array of Catalan numbers from 1 to 15.

# Применяем функцию к диапазону от 1 до 15
catalannum.(1:15)

15-element Vector{Int64}:
       1
       2
       5
      14
      42
     132
     429
    1430
    4862
   16796
   58786
  208012
  742900
 2674440
 9694845

Calculating the 100th Catalan number

To calculate large Catalan numbers, the function is used big(100), which converts the number 100 to the type BigInt. This allows you to work with numbers larger than the standard size of integer types to avoid overflow.

The result will be the 100th Catalan number, represented as a large integer.

# Вычисляем 100-е число Каталана, используя BigInt
catalannum(big(100))

896519947090131496687170070074100632420837521538745909320

Conclusion

We have reviewed the implementation of the algorithm for calculating Catalan numbers in the Julia language. A function has been created catalannum, which uses binomial coefficients to calculate Catalan numbers. We applied it to the range from 1 to 15 and calculated the 100th Catalan number using BigInt. This allows you to work effectively with both small and large values of Catalan numbers. Such calculations are useful in combinatorics, algorithm analysis, and other areas of mathematics.

The example was developed using materials from Rosetta Code