Catalan numbers#9643

Catalan numbers (Editorial)

Let's rewrite the recurrence relation as follows:

с_{0} = 1, с_{n} = c_{0} c_{n - 1} + c_{1} c_{n - 2} + c_{2} c_{n - 3} + ... + c_{n - 1} c_{0}, i f n > 0

с_0 = 1, \\ с_n = c_0c_{n-1} + c_1c_{n-2} + c_2c_{n-3} + ... + c_{n-1}c_0,~if~n > 0

For example,

$с_{0} = 1$ с_0 = 1
$с_{1} = c_{0} c_{0} = 1$ с_1 = c_0c_0 = 1,
$с_{2} = c_{0} c_{1} + c_{1} c_{0} = 1 + 1 = 2$ с_2 = c_0c_1 + c_1c_0 = 1 + 1 = 2,
$с_{3} = c_{0} c_{2} + c_{1} c_{1} + c_{2} c_{0} = 2 + 1 + 2 = 5$ с_3 = c_0c_2 + c_1c_1 + c_2c_0 = 2 + 1 + 2 = 5,
$с_{4} = c_{0} c_{3} + c_{1} c_{2} + c_{2} c_{1} + c_{3} c_{0} = 5 + 2 + 2 + 5 = 14$ с_4 = c_0c_3 + c_1c_2 + c_2c_1 + c_3c_0 = 5 + 2 + 2 + 5 = 14,
$с_{5} = c_{0} c_{4} + c_{1} c_{3} + c_{2} c_{2} + c_{3} c_{1} + c_{4} c_{0} = 14 + 5 + 4 + 5 + 14 = 42$ с_5 = c_0c_4 + c_1c_3 + c_2c_2 + c_3c_1 + c_4c_0 = 14 + 5 + 4 + 5 + 14 = 42

Since the value of $с_{n}$ с_n is computed based on all previous values $c_{0}, c_{1}, c_{2}, ..., c_{n - 1}$ c_0, c_1, c_2, ..., c_{n-1}, we will store the Catalan numbers in a linear array.

Algorithm implementation

Declare an array $c a t$ , where we'll store the Catalan numbers: $c a t [i] = c_{i}$ cat[i] = c_i.

long long cat[10001];

Read the input data.

scanf("%lld %lld", &n, &m);

Compute the Catalan numbers using the recurrence relation.

cat[0] = 1;
for (i = 1; i <= n; i++)
{
  for (j = 0; j < i; j++)
    cat[i] = (cat[i] + cat[j] * cat[i - j - 1]) % m;
}

Print the $n$ -th Catalan number.

printf("%lld\n", cat[n]);

Python implementation

Read the input data.

n, m = map(int, input().split())

Store the values of the Catalan numbers in the list $c a t$ , where $c a t [i] = c_{i}$ cat[i] = c_i.

cat = [0] * (n + 1)

Compute the Catalan numbers using the recurrence relation.

cat[0] = 1
for i in range(1, n + 1):
  for j in range(i):
    cat[i] = (cat[i] + cat[j] * cat[i - j - 1]) % m

Print the $n$ -th Catalan number.

print(cat[n])