Generating Function

A generating function compactly represents a sequence by treating its elements as coefficients of a polynomial. Useful for combinatorics and recurrence relations.

For a sequence a0, a1, a2…, the generating function is:

G(x) = a0 + a1x + a2x^2 + …

Java example for Fibonacci numbers:

1
2
3
4
5
6
7
8
// F(n) = F(n-1) + F(n-2)
// G(x) = xF(x) + F(x)
// Solving gives closed form solution

int fibonacci(int n) {
  return (int) ((Math.pow(1+sqrt(5), n) - Math.pow(1-sqrt(5), n)) / 
                (Math.pow(2,n) * sqrt(5)));
}

C++ example for Catalan numbers:

1
2
3
4
5
6
7
// C(n) = sum(C(i)*C(n-i-1), i = 0 to n-1) 
// G(x) = 1 + xG(x)^2
// Solving gives closed form

int catalanNumber(int n) {
  return (int)((2*n)! / ((n+1)! * n!));
}

Python example for Pascal’s triangle:

1
2
3
4
5
6
7
# P(n, k) = P(n-1, k) + P(n-1, k-1) 
# G(x) = 1 + xG(x) + x^2G(x)^2 + ...
# Binomial theorem gives closed form

def pascals(n, k):
  coeff = math.factorial(n) // (math.factorial(k) * math.factorial(n - k))
  return coeff

Generating functions transform sequences into algebraic forms amenable to analysis.

A generating function is a way to represent a sequence of numbers in the form of a function. Specifically, it is often a power series whose coefficients represent the elements of the sequence. It’s a useful concept in combinatorics, probability, and algorithm design.

Mathematically, the generating function ( G(x) ) for the sequence ( a_0, a_1, a_2, … ) is defined as:

[ G(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots ]

Generating functions can be manipulated algebraically to solve for properties of the sequence, such as finding a closed-form expression for the ( n )-th element or counting the number of ways to achieve a certain sum in a set of numbers.

Java

Here’s how you could implement a basic generating function for the Fibonacci sequence in Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public class GeneratingFunction {
    public static double fibonacciGenFunc(int n, double x) {
        double a = 1, b = x;
        for (int i = 2; i <= n; i++) {
            double temp = a + b * x;
            a = b;
            b = temp;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(fibonacciGenFunc(5, 0.5));
    }
}

C++

In C++, it would look like this:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;

double fibonacciGenFunc(int n, double x) {
    double a = 1, b = x;
    for (int i = 2; i <= n; i++) {
        double temp = a + b * x;
        a = b;
        b = temp;
    }
    return a;
}

int main() {
    cout << fibonacciGenFunc(5, 0.5) << endl;
    return 0;
}

Python

And in Python:

1
2
3
4
5
6
7
def fibonacciGenFunc(n, x):
    a, b = 1, x
    for i in range(2, n + 1):
        a, b = b, a + b * x
    return a

print(fibonacciGenFunc(5, 0.5))

All three code snippets calculate the value of the generating function for the Fibonacci sequence up to the ( n )-th term at ( x = 0.5 ).