The Nth term in the Wedderburn–Etherington number sequence (starting with the number 0 for n = 0) counts the number of unordered rooted trees with n leaves in which all nodes including the root have either zero or exactly two children.
For a given N. The task is to find first N terms of the sequence.
Sequence:
0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, ….
Trees with 0 or 2 childs:
Examples:
Input : N = 10
Output : 0, 1, 1, 1, 2, 3, 6, 11, 23, 46,
Input : N = 20
Output : 0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, 127912
Approach:
The Recurrence relation to find Nth number is:
- a(2x-1) = a(1) * a(2x-2) + a(2) * a(2x-3) + … + a(x-1) * a(x)
- a(2x) = a(1) * a(2x-1) + a(2) * a(2x-2) + … + a(x-1) * a(x+1) + a(x) * (a(x)+1)/2
Using the above relation we can find the ith term of the series. We will start from the 0th term and then store the answer in a map and then use the values in the map to find the i+1 th term of the series. we will also use base cases for the 0th, 1st and 2nd element which are 0, 1, 1 respectively.
Below is the implementation of the above approach :
C++
// CPP program to find N terms of the sequence #include <bits/stdc++.h>using namespace std;// Stores the Wedderburn Etherington numbersmap<int, int> store;// Function to return the nth// Wedderburn Etherington numbersint Wedderburn(int n){ // Base case if (n <= 2) return store[n]; // If n is even n = 2x else if (n % 2 == 0) { // get x int x = n / 2, ans = 0; // a(2x) = a(1)a(2x-1) + a(2)a(2x-2) + ... + // a(x-1)a(x+1) for (int i = 1; i < x; i++) { ans += store[i] * store[n - i]; } // a(x)(a(x)+1)/2 ans += (store[x] * (store[x] + 1)) / 2; // Store the ans store[n] = ans; // Return the required answer return ans; } else { // If n is odd int x = (n + 1) / 2, ans = 0; // a(2x-1) = a(1)a(2x-2) + a(2)a(2x-3) + ... + // a(x-1)a(x), for (int i = 1; i < x; i++) { ans += store[i] * store[n - i]; } // Store the ans store[n] = ans; // Return the required answer return ans; }}// Function to print first N // Wedderburn Etherington numbersvoid Wedderburn_Etherington(int n){ // Store first 3 numbers store[0] = 0; store[1] = 1; store[2] = 1; // Print N terms for (int i = 0; i < n; i++) { cout << Wedderburn(i); if(i!=n-1) cout << ", "; }}// Driver codeint main(){ int n = 10; // function call Wedderburn_Etherington(n); return 0;} |
Java
// Java program to find N terms of the sequence import java.util.*;class GFG {// Stores the Wedderburn Etherington numbersstatic HashMap<Integer, Integer> store = new HashMap<Integer, Integer>();// Function to return the nth// Wedderburn Etherington numbersstatic int Wedderburn(int n){ // Base case if (n <= 2) return store.get(n); // If n is even n = 2x else if (n % 2 == 0) { // get x int x = n / 2, ans = 0; // a(2x) = a(1)a(2x-1) + a(2)a(2x-2) + ... + // a(x-1)a(x+1) for (int i = 1; i < x; i++) { ans += store.get(i) * store.get(n - i); } // a(x)(a(x)+1)/2 ans += (store.get(x) * (store.get(x) + 1)) / 2; // Store the ans store. put(n, ans); // Return the required answer return ans; } else { // If n is odd int x = (n + 1) / 2, ans = 0; // a(2x-1) = a(1)a(2x-2) + a(2)a(2x-3) + ... + // a(x-1)a(x), for (int i = 1; i < x; i++) { ans += store.get(i) * store.get(n - i); } // Store the ans store. put(n, ans); // Return the required answer return ans; }}// Function to print first N // Wedderburn Etherington numbersstatic void Wedderburn_Etherington(int n){ // Store first 3 numbers store. put(0, 0); store. put(1, 1); store. put(2, 1); // Print N terms for (int i = 0; i < n; i++) { System.out.print(Wedderburn(i)); if(i != n - 1) System.out.print(" "); }}// Driver codepublic static void main(String[] args) { int n = 10; // function call Wedderburn_Etherington(n); }}// This code is contributed by Princi Singh |
Python3
# Python3 program to find N terms # of the sequence# Stores the Wedderburn Etherington numbersstore = dict()# Function to return the nth# Wedderburn Etherington numbersdef Wedderburn(n): # Base case if (n <= 2): return store[n] # If n is even n = 2x elif (n % 2 == 0): # get x x = n // 2 ans = 0 # a(2x) = a(1)a(2x-1) + a(2)a(2x-2) + ... + # a(x-1)a(x+1) for i in range(1, x): ans += store[i] * store[n - i] # a(x)(a(x)+1)/2 ans += (store[x] * (store[x] + 1)) // 2 # Store the ans store[n] = ans # Return the required answer return ans else: # If n is odd x = (n + 1) // 2 ans = 0 # a(2x-1) = a(1)a(2x-2) + a(2)a(2x-3) + ... + # a(x-1)a(x), for i in range(1, x): ans += store[i] * store[n - i] # Store the ans store[n] = ans # Return the required answer return ans# Function to print first N# Wedderburn Etherington numbersdef Wedderburn_Etherington(n): # Store first 3 numbers store[0] = 0 store[1] = 1 store[2] = 1 # Print N terms for i in range(n): print(Wedderburn(i), end = "") if(i != n - 1): print(end = ", ")# Driver coden = 10# function callWedderburn_Etherington(n)# This code is contributed by Mohit Kumar |
C#
// C# program to find N terms of the sequence using System;using System.Collections.Generic; class GFG {// Stores the Wedderburn Etherington numbersstatic Dictionary<int, int> store = new Dictionary<int, int>();// Function to return the nth// Wedderburn Etherington numbersstatic int Wedderburn(int n){ // Base case if (n <= 2) return store[n]; // If n is even n = 2x else if (n % 2 == 0) { // get x int x = n / 2, ans = 0; // a(2x) = a(1)a(2x-1) + a(2)a(2x-2) + ... + // a(x-1)a(x+1) for (int i = 1; i < x; i++) { ans += store[i] * store[n - i]; } // a(x)(a(x)+1)/2 ans += (store[x] * (store[x] + 1)) / 2; // Store the ans if(store.ContainsKey(n)) { store.Remove(n); store.Add(n, ans); } else store.Add(n, ans); // Return the required answer return ans; } else { // If n is odd int x = (n + 1) / 2, ans = 0; // a(2x-1) = a(1)a(2x-2) + a(2)a(2x-3) + ... + // a(x-1)a(x), for (int i = 1; i < x; i++) { ans += store[i] * store[n - i]; } // Store the ans if(store.ContainsKey(n)) { store.Remove(n); store.Add(n, ans); } else store.Add(n, ans); // Return the required answer return ans; }}// Function to print first N // Wedderburn Etherington numbersstatic void Wedderburn_Etherington(int n){ // Store first 3 numbers store.Add(0, 0); store.Add(1, 1); store.Add(2, 1); // Print N terms for (int i = 0; i < n; i++) { Console.Write(Wedderburn(i)); if(i != n - 1) Console.Write(" "); }}// Driver codepublic static void Main(String[] args) { int n = 10; // function call Wedderburn_Etherington(n); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript program to find N terms of the sequence // Stores the Wedderburn Etherington numbersvar store = new Map();// Function to return the nth// Wedderburn Etherington numbersfunction Wedderburn(n){ // Base case if (n <= 2) return store[n]; // If n is even n = 2x else if (n % 2 == 0) { // get x var x = parseInt(n / 2), ans = 0; // a(2x) = a(1)a(2x-1) + a(2)a(2x-2) + ... + // a(x-1)a(x+1) for (var i = 1; i < x; i++) { ans += store[i] * store[n - i]; } // a(x)(a(x)+1)/2 ans += (store[x] * (store[x] + 1)) / 2; // Store the ans store[n] = ans; // Return the required answer return ans; } else { // If n is odd var x = (n + 1) / 2, ans = 0; // a(2x-1) = a(1)a(2x-2) + a(2)a(2x-3) + ... + // a(x-1)a(x), for (var i = 1; i < x; i++) { ans += store[i] * store[n - i]; } // Store the ans store[n] = ans; // Return the required answer return ans; }}// Function to print first N // Wedderburn Etherington numbersfunction Wedderburn_Etherington(n){ // Store first 3 numbers store[0] = 0; store[1] = 1; store[2] = 1; // Print N terms for (var i = 0; i < n; i++) { document.write( Wedderburn(i)); if(i != n - 1) document.write( ", "); }}// Driver codevar n = 10;// function callWedderburn_Etherington(n);// This code is contributed by rrrtnx.</script> |
Output:
0, 1, 1, 1, 2, 3, 6, 11, 23, 46
Time Complexity: O(n2logn)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
