Coursera - Computer Science: Programming With A Purpose

Write a program TrinomialBrute.java that takes two integer command-line arguments n and k and computes the corresponding trinomial coefficient. The trinomial coefficient T(n, k) is the coefficient of x^n+k in the expansion of (1 + x + x²)ⁿ. For example,

    (1 + x + x²)³ = 1 + 3x + 6x² + 7x³ + 6x⁴ + 3x⁵ + x⁶

Thus, T(3, 3) = 1, T(3, 2) = 3, T(3, 1) = 6, and T(3, 0) = 7.

Implement a recursive function trinomial() to compute T(n, k) by using the following recurrence relation:

                   1                                                            if n = 0 and k = 0
    T(n, k) = 0                                                            if k < -n or k > n
                   T(n-1, k-1) + T(n-1, k) + T(n-1, k+1)   otherwise

To do so, organize your program according to the following public API:

public class TrinomialBrute {

    // Returns the trinomial coefficient T(n, k).
    public static long trinomial(int n, int k)

    // Takes two integer command-line arguments n and k and prints T(n, k).
    public static void main(String[] args)
}

As you will see, this approach is hopeless slow for moderately large values of n and k.

~/Desktop/recursion> java TrinomialBrute 3 3
1

~/Desktop/recursion> java TrinomialBrute 3 2
3

~/Desktop/recursion> java TrinomialBrute 3 1
6

~/Desktop/recursion> java TrinomialBrute 3 0
7

~/Desktop/recursion> java TrinomialBrute 24 12
287134346

~/Desktop/recursion> java TrinomialBrute 30 0
[takes too long]

Note: you may assume that n is a non-negative integer.

Trinomial coefficients arise in combinatorics. For example, T(n, k) is the number of permutations of n symbols, each of which is −1, 0, or +1, which sum to exactly k and T(n, k−n) is the number of different ways of randomly drawing k cards from two identical decks of n playing cards.

Note: the above description is copied from Coursera and converted to markdown for convenience

Solution:

public class TrinomialBrute {

    // Returns the trinomial coefficient T(n, k).
    public static long trinomial(int n, int k) {
        if ((n == 0) && (k == 0)) {
            return 1;
        } else if ((k < -n) || (k > n)) {
            return 0;
        }
        return trinomial(n - 1, k - 1) + trinomial(n - 1, k) + trinomial(n - 1, k + 1);
    }

    // Takes two integer command-line arguments n and k and prints T(n, k).
    public static void main(String[] args) {
        final int n = Integer.parseInt(args[0]);
        final int k = Integer.parseInt(args[1]);
        StdOut.println(trinomial(n, k));
    }
}

Link To: Java Source Code