Step by Step solution about How to resolve the algorithm Catalan numbers/Pascal's triangle step by step in the Kotlin programming language

Kotlin Code for Computing Catalan Numbers

Overview

This Kotlin code calculates Catalan numbers for various values of n using a recursive Pascal's triangle approach. Catalan numbers have applications in counting, probability, and combinatorics.

Code Explanation

1. Global Constants

• ONE: A constant representing the value 1, initialized as a BigInteger.

2. pascal Function

• Parameters:
  • n: The row index of Pascal's triangle.
  • k: The column index of Pascal's triangle.
• Computes the value of Pascal's triangle at the given row and column using a recursive formula.
• If either n or k is 0, it returns 1.
• Otherwise, it multiplies all the integers from k + 1 to n and divides the result by the product of all the integers from 2 to n - k.
• Returns the computed value as a BigInteger.

3. catalanFromPascal Function

• Parameter:
  • n: The number of Catalan numbers to compute.
• Loop over odd values of i from 1 to n (step size of 2).
• For each i, calculate the corresponding row index in Pascal's triangle: mi = i / 2 + 1.
• Compute the Catalan number using the formula: catalan = pascal(i, mi) - pascal(i, mi - 2).
• Print the computed Catalan number and its index.

4. main Function

• Sets the value of n to 15.
• Calls the catalanFromPascal function with the argument n * 2 to compute and print Catalan numbers up to the given value.

Output

For n = 15, the output will be:

1 : 1
2 : 2
3 : 5
4 : 14
5 : 42
6 : 132
7 : 429
8 : 1430
9 : 4862
10 : 16796
11 : 58786
12 : 208012
13 : 742900
14 : 2674440
15 : 9694845

// version 1.1.2

import java.math.BigInteger

val ONE = BigInteger.ONE

fun pascal(n: Int, k: Int): BigInteger {
    if (n == 0 || k == 0) return ONE
    val num = (k + 1..n).fold(ONE) { acc, i -> acc * BigInteger.valueOf(i.toLong()) }
    val den = (2..n - k).fold(ONE) { acc, i -> acc * BigInteger.valueOf(i.toLong()) }
    return num / den
}

fun catalanFromPascal(n: Int) {
    for (i in 1 until n step 2) {
        val mi = i / 2 + 1
        val catalan = pascal(i, mi) - pascal(i, mi - 2) 
        println("${"%2d".format(mi)} : $catalan")
    }
}
 
fun main(args: Array<String>) {
    val n = 15
    catalanFromPascal(n * 2)
}