Count ways to divide circle using N non-intersecting chords

Given a number N, find the number of ways you can draw N chords in a circle with 2*N points such that no 2 chords intersect.
Two ways are different if there exists a chord which is present in one way and not in other.

Examples:

Input : N = 2
Output : 2
Explanation: If points are numbered 1 to 4 in
clockwise direction, then different ways to
draw chords are:
{(1-2), (3-4)} and {(1-4), (2-3)}

Input : N = 1
Output : 1
Explanation: Draw a chord between points 1 and 2.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

If we draw a chord between any two points, can you observe the current set of points getting broken into two smaller sets S_1 and S_2. If we draw a chord from a point in S_1 to a point in S_2, it will surely intersect the chord we’ve just drawn.
So, we can arrive at a recurrence that Ways(n) = sum[i = 0 to n-1] { Ways(i)*Ways(n-i-1) }.
Here we iterate over i, assuming that size of one of the sets is i and size of another set automatically is (n-i-1) since we’ve already used a pair of points and i pair of points in one set.

C++

 // cpp code to count ways  // to divide circle using // N non-intersecting chords. #include using namespace std;    int chordCnt( int A){        // n = no of points required     int n = 2 * A;            // dp array containing the sum     int dpArray[n + 1]={ 0 };     dpArray = 1;     dpArray = 1;     for (int i=4;i<=n;i+=2){         for (int j=0;j

Java

 // Java code to count ways // to divide circle using // N non-intersecting chords. import java.io.*;    class GFG {     static int chordCnt(int A)     {            // n = no of points required         int n = 2 * A;            // dp array containing the sum         int[] dpArray = new int[n + 1];         dpArray = 1;         dpArray = 1;         for (int i = 4; i <= n; i += 2) {             for (int j = 0; j < i - 1; j += 2)              {                 dpArray[i] += (dpArray[j] *                                dpArray[i - 2 - j]);             }         }            // returning the required number         return dpArray[n];     }     public static void main(String[] args)     {         int N;         N = 2;         System.out.println(chordCnt(N));         N = 1;         System.out.println(chordCnt(N));         N = 4;         System.out.println(chordCnt(N));     } }    // This code is contributed by Gitanjali.

/div>

Python 3

 # python code to count ways to divide # circle using N non-intersecting chords. def chordCnt( A):        # n = no of points required     n = 2 * A        # dp array containing the sum     dpArray = *(n + 1)     dpArray = 1     dpArray = 1     for i in range(4, n + 1, 2):         for j in range(0, i-1, 2):             dpArray[i] += (dpArray[j]*dpArray[i-2-j])        # returning the required number     return int(dpArray[n])    # driver code N = 2 print(chordCnt( N)) N = 1 print(chordCnt( N)) N = 4 print(chordCnt( N))

C#

 // C# code to count ways to divide  // circle using N non-intersecting chords. using System;    class GFG {            static int chordCnt(int A)     {         // n = no of points required         int n = 2 * A;            // dp array containing the sum         int[] dpArray = new int[n + 1];         dpArray = 1;         dpArray = 1;                    for (int i = 4; i <= n; i += 2)          {             for (int j = 0; j < i - 1; j += 2)             {                 dpArray[i] += (dpArray[j] * dpArray[i - 2 - j]);             }         }            // returning the required number         return dpArray[n];     }            // Driver code     public static void Main()     {         int N;         N = 2;         Console.WriteLine(chordCnt(N));         N = 1;         Console.WriteLine(chordCnt(N));         N = 4;         Console.WriteLine(chordCnt(N));     } }    // This code is contributed by vt_m.



Output:

2
1
14