# Entringer Number in Java

Combinatorial numbers that count specific kinds of permutations are known as the Entringer numbers. They specifically stand for the quantity of permutations of the set {1, 2,..., n + 1} that begin with k + 1.

There is a zigzag pattern to these permutations; they fall at first, then rise and fall again.

Example 1:

Input: n = 4, k = 2

Output : E(n,k) = 4

Explanation: The number of {1, 2, 3, 4, 5} permutations that begin with 3 is what we are looking for.

The following combinations are allowed: {[3 1 4 2 5],[ 3 2 4 1 5], [3 2 5 1 4], [3 1 5 2 4]}

As a result, E(4, 2) = 4.

Example 2:

Input: n =4 , k = 3

Output: E(n,k) = 5

Explanation: The number of {1, 2, 3, 4, 5} permutations that begin with 4 is what we are looking for.

The following combinations are allowed: {[4 5 2 3 1],[ 4 5 1 3 2], [4 3 5 1 2], [4 2 1 5 3], [4 1 5 2 3]}

As a result, E(4, 3) = 5.

## Approach: Using Dynamic Programming

The code uses a dynamic programming approach to calculate the Entringer number E(n, k), a combinatorial number that counts the number of permutations of [n] where no integer appears in its natural position. It initializes an array `dp` of size `n+1`, iterates from `i = 1` to `n`, and updates the `dp` array to the values in `currentArray`. The final result is the Entringer number for the specified values of `n` and `k`. This bottom-up dynamic programming approach efficiently computes the desired result.

Here’s the implementation of finding the entringer number using the approach :

FileName: EntringerNumber.java

`import java.util.Arrays;public class EntringerNumber {    // Return Entringer Number E(n, k)    public static int calculateZigzagNumber(int n, int k) {        // array to store values        int[] dp = new int[n + 1];        Arrays.fill(dp, 0);        // Base cases        dp[0] = 1;        // iterate to get the current value from the previous value        for (int i = 1; i <= n; i++) {            int[] currentArray = new int[n + 1];            Arrays.fill(currentArray, 0);            for (int j = 1; j <= i; j++) {                currentArray[j] = currentArray[j - 1] + dp[i - j];            }            // assigning values to iterate further            dp = currentArray;        }        return dp[k];    }    public static void main(String[] args) {        int n = 4, k = 2;        System.out.println(calculateZigzagNumber(n, k));    }}`

Output:

`4`

Complexity analysis: The code has a time complexity of O(n^2) due to constant-time operations in the inner loop and a space complexity of O(n) due to the `dp` and `currentArray` arrays. It uses dynamic programming to calculate Entringer numbers, but the time complexity is quadratic due to nested loops.

## Approach: Using Recursion

The code uses a recursive method to calculate the Entringer number E(n, k). It starts with base cases to handle special situations. Then, it uses a recursive step to consider two cases: the last element in its natural position (E(n, k-1)) and the last element not in its natural position (E(n-1, n-k). The function calls itself and continues until reaching the base cases. The main function serves as a driver program to test the function with specific values.

FileName:EntringerNumber1.java

`import java.util.*;public class EntringerNumber1 {    // Function to calculate Entringer Number E(n, k)    static int calculateEntringerNumber(int n, int k) {        // Base Case: E(0, 0) = 1        if (n == 0 && k == 0)            return 1;        // Base Case: E(n, 0) = 0 for n > 0        if (k == 0)            return 0;        // Recursive step: E(n, k) = E(n, k-1) + E(n-1, n-k)        return calculateEntringerNumber(n, k - 1) +                calculateEntringerNumber(n - 1, n - k);    }    /* Driver program to test the Entringer Number function */    public static void main(String[] args) {        int n = 4, k = 2;        int result = calculateEntringerNumber(n, k);        System.out.println( result);    }}`

Output:

`4`

Complexity analysis: The code calculates Entringer numbers using a recursive algorithm, resulting in an exponential time complexity of O(2^n) due to the recursive nature of the algorithm. The space complexity is determined by the depth of the recursion stack, with the worst-case height reaching O(n). Memoization or dynamic programming can optimize the solution, reducing redundant calculations and bringing the time complexity closer to O(n^2).