Entringer Number in C++
Introduction:
Definition:
An Entringer number, denoted by E(n, k), represents the number of valid permutations of the set {1, 2, 3, ..., n+1} that satisfy the following conditions:
- The permutation starts with the element k + 1.
- The subsequent elements alternate between decreasing and increasing in value.
- The permutation wraps around, meaning n + 1 follows 1 and n precedes n + 1.
Syntax:
int EntringerNumber(int n, int k);
Parameters:
- n: An integer representing the size of the set {1, 2, 3, ..., n+1}.
- k: An integer representing the permutation's starting element (k + 1).
Base Cases:
- E(0, 0) = 1 (Only one valid permutation for an empty set starting with 1).
- E(n, 0) = 0 (No valid permutation exists for n > 0 starting with 1 as the sequence would only decrease).
Recursive Formula:
The Entringer number can be calculated using the following recurrence relation:
- E(n, k) = E(n, k-1) + E(n-1, n-k)
- E(n, k-1) represents the number of permutations where the previous element decreasing (k is one less than the current element).
- E(n-1, n-k) represents the number of permutations starting with n (which becomes n - k after decreasing by k elements).
C++ Implementation (Top-Down Recursive Approach):
#include <iostream>
int EntringerNumber(int n, int k) {
if (n == 0 && k == 0) {
return 1;
} else if (n == 0 || k == 0) {
return 0;
} else {
return EntringerNumber(n, k - 1) + EntringerNumber(n - 1, n - k);
}
}
int main() {
int n, k;
std::cout << "Enter the value of n: ";
std::cin >> n;
std::cout << "Enter the value of k: ";
std::cin >> k;
int entringerNumber = EntringerNumber(n, k);
std::cout << "The Entringer number E(" << n << ", " << k << ") is: " << entringerNumber << std::endl;
return 0;
}
Output:
![Entringer Number in C++](https://static.tutorialandexample.com/cpp/entringer-number-in-cpp1.png)
Explanation:
- The EntringerNumber function takes n and k as arguments.
- It checks for the base cases:
- If n and k are both 0, it returns 1 (one valid permutation).
- If either n or k is 0, it returns 0 (no valid permutations).
- For other cases, it applies the recursive formula:
- E(n, k-1) calculates the number of permutations where the previous element decreased.
- E(n-1, n-k) calculates the number of permutations starting with n (which becomes n-k after decreasing).
- The function returns the sum of these two values.
Example:
- Let's find E(4, 2):
- Start with 3 (k + 1).
- Decrease to 2.
- Increase to 4.
- Decrease to 1.
- This permutation (3, 2, 4, 1) satisfies the Entringer number condition.
- EntringerNumber(4, 2) will return 4 using the provided code, indicating four valid permutations for this case.
Applications:
Entringer numbers have limited practical applications outside of combinatorial mathematics. They are primarily used for theoretical research in permutations, pattern avoidance, and generating functions.