Given a number N. The task is to find the number of permutations of 1 to N such that no three terms of the permutation form an increasing subsequence.
Examples:
Input : N = 3 Output : 5 Valid permutations : 132, 213, 231, 312 and 321 and not 123 Input : N = 4 Output : 14
The above problem is an application of Catalan numbers. So, the task is to only find the nth Catalan Number. First few Catalan numbers are 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, … (considered from 0th number)
Below is the program to find Nth Catalan Number:
C++
// C++ program to find the// nth catalan number#include <bits/stdc++.h>using namespace std;// Returns value of Binomial Coefficient C(n, k)unsigned long int binomialCoeff(unsigned int n, unsigned int k){ unsigned long int res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1] for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res;}// A Binomial coefficient based function// to find nth catalan// number in O(n) timeunsigned long int catalan(unsigned int n){ // Calculate value of 2nCn unsigned long int c = binomialCoeff(2 * n, n); // return 2nCn/(n+1) return c / (n + 1);}// Driver codeint main(){ int n = 3; cout << catalan(n) << endl; return 0;} |
Java
// Java program to find the// nth catalan numberimport java.io.*;class GFG{// Returns value of Binomial// Coefficient C(n, k)static long binomialCoeff(long n, long k){ long res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n*(n-1)*---*(n-k+1)] / // [k*(k-1)*---*1] for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res;}// A Binomial coefficient based // function to find nth catalan// number in O(n) timestatic long catalan(long n){ // Calculate value of 2nCn long c = binomialCoeff(2 * n, n); // return 2nCn/(n+1) return c / (n + 1);}// Driver codepublic static void main (String[] args) { int n = 3; System.out.println(catalan(n));}}// This code has been contributed// by inder_verma. |
Python3
# Python program to find the # nth catalan number # Returns value of Binomial # Coefficient C(n, k) def binomialCoeff(n, k): res = 1 # Since C(n, k) = C(n, n-k) if k > n - k: k=n-k # Calculate value of # [n*(n-1)*---*(n-k+1)] // # [k*(k-1)*---*1] for i in range(k): res = res * (n - i) res = res // (i + 1) return res # A Binomial coefficient based # function to find nth catalan # number in O(n) time def catalan(n): # Calculate value of 2nCn c = binomialCoeff(2 * n, n) # return 2nCn/(n+1) return c // (n + 1) # Driver code n = 3print(catalan(n))# This code is contributed # by sahil shelangia |
C#
// C# program to find the// nth catalan numberusing System;class GFG{// Returns value of Binomial// Coefficient C(n, k)static long binomialCoeff(long n, long k){ long res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n*(n-1)*---*(n-k+1)] / // [k*(k-1)*---*1] for (int i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res;}// A Binomial coefficient based // function to find nth catalan// number in O(n) timestatic long catalan(long n){ // Calculate value of 2nCn long c = binomialCoeff(2 * n, n); // return 2nCn/(n+1) return c / (n + 1);}// Driver codepublic static void Main (String[] args) { int n = 3; Console.WriteLine(catalan(n));}}// This code is contributed// by Kirti_Mangal |
PHP
<?php// PHP program to find the // nth catalan number // Returns value of Binomial // Coefficient C(n, k) function binomialCoeff($n, $k){ $res = 1; // Since C(n, k) = C(n, n-k) if($k >$n - $k) $k = $n - $k; // Calculate value of // [n*(n-1)*---*(n-k+1)] // // [k*(k-1)*---*1] for ($i = 0; $i < $k; $i++) { $res = $res * ($n - $i); $res = $res / ($i + 1); } return $res;}// A Binomial coefficient based // function to find nth catalan // number in O(n) time function catalan($n){ // Calculate value of 2nCn $c = binomialCoeff(2 * $n, $n); // return 2nCn/(n+1) return $c / ($n + 1);}// Driver code $n = 3;print(catalan($n));// This code is contributed // by mits?> |
Javascript
<script>// Javascript program to find the// nth catalan number// Returns value of Binomial Coefficient C(n, k)function binomialCoeff(n, k){ var res = 1; // Since C(n, k) = C(n, n-k) if (k > n - k) k = n - k; // Calculate value of // [n*(n-1)*---*(n-k+1)] / [k*(k-1)*---*1] for (var i = 0; i < k; ++i) { res *= (n - i); res /= (i + 1); } return res;}// A Binomial coefficient based function// to find nth catalan// number in O(n) timefunction catalan(n){ // Calculate value of 2nCn var c = binomialCoeff(2 * n, n); // return 2nCn/(n+1) return c / (n + 1);}// Driver codevar n = 3;document.write( catalan(n));</script> |
Output:
5
Time Complexity: O(n)
Auxiliary Space: O(1)
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!
