Step by Step solution about How to resolve the algorithm Stirling numbers of the first kind step by step in the Go programming language

This Go program calculates and prints the unsigned Stirling numbers of the first kind, denoted as S1(n, k), for values of n and k up to a specified limit. Stirling numbers of the first kind count the number of permutations of n elements with k disjoint cycles.

Here's how the program works:

1. Input and Initialization:

   • limit: Sets the upper bound for n and k (default: 100).
   • last: Specifies the maximum value for n and k to be printed (default: 12).
   • unsigned: Controls whether to calculate unsigned or signed Stirling numbers (default: true for unsigned).
   • s1: 2D slice ([][]*big.Int) of arbitrary precision integers (big.Int) to store the Stirling numbers.

2. Generating Stirling Numbers:

   • The program uses a recursive approach to generate the unsigned Stirling numbers of the first kind. It fills the 2D slice s1 for all values of n and k up to the specified limit.
   • For each n and k, it calculates S1(n, k) using the recursive formula:
     1. If k is 0, S1(n, 0) = 1.
     2. Otherwise, S1(n, k) = (n-1) * S1(n-1, k) + (-1)^k * S1(n-1, k-1).

3. Printing the Stirling Numbers:

   • The program prints the calculated Stirling numbers in a table format.
   • The first row shows the values of k, while the first column shows the values of n.
   • The intersection of each row and column contains the corresponding S1(n, k) value.

4. Finding and Printing the Maximum Value:

   • The program finds the maximum value among the Stirling numbers in the last row of the table (corresponding to n = limit).
   • It prints the maximum value and its number of digits.

The program demonstrates the calculation and properties of unsigned Stirling numbers of the first kind for small values of n and k.

package main

import (
    "fmt"
    "math/big"
)

func main() {
    limit := 100
    last := 12
    unsigned := true
    s1 := make([][]*big.Int, limit+1)
    for n := 0; n <= limit; n++ {
        s1[n] = make([]*big.Int, limit+1)
        for k := 0; k <= limit; k++ {
            s1[n][k] = new(big.Int)
        }
    }
    s1[0][0].SetInt64(int64(1))
    var t big.Int
    for n := 1; n <= limit; n++ {
        for k := 1; k <= n; k++ {
            t.SetInt64(int64(n - 1))
            t.Mul(&t, s1[n-1][k])            
            if unsigned {
                s1[n][k].Add(s1[n-1][k-1], &t)
            } else {
                s1[n][k].Sub(s1[n-1][k-1], &t)
            }           
        }
    }
    fmt.Println("Unsigned Stirling numbers of the first kind: S1(n, k):")
    fmt.Printf("n/k")
    for i := 0; i <= last; i++ {
        fmt.Printf("%9d ", i)
    }
    fmt.Printf("\n--")
    for i := 0; i <= last; i++ {
        fmt.Printf("----------")
    }
    fmt.Println()
    for n := 0; n <= last; n++ {
        fmt.Printf("%2d ", n)
        for k := 0; k <= n; k++ {
            fmt.Printf("%9d ", s1[n][k])
        }
        fmt.Println()
    }
    fmt.Println("\nMaximum value from the S1(100, *) row:")
    max := new(big.Int).Set(s1[limit][0])
    for k := 1; k <= limit; k++ {
        if s1[limit][k].Cmp(max) > 0 {
            max.Set(s1[limit][k])
        }
    }
    fmt.Println(max)
    fmt.Printf("which has %d digits.\n", len(max.String()))
}