Stack Overflow
Stack Overflow

Questions tagged [catalan]

Catalan numbers are mainly used in computer science with enumerating full binary trees or solving combinatorial problems. Do not use this tag with the spoken language Catalan or the geographic region known as Catalonia or Fuss-Catalan numbers.

References

Related sites

Related sequences

Catalan numbers are for full binary trees, e.g. all nodes have 0 or 2 branches, and count only leaves, while Motzkin numbers are for regular binary trees, e.g. all nodes have 0,1, or 2 branches, and count all nodes.

Notes

For Fuss-Catalan numbers use tag fuss-catalan-numbers

114 questions
87
votes
11 answers

With ' N ' no of nodes, how many different Binary and Binary Search Trees possible?

For Binary trees: There's no need to consider tree node values, I am only interested in different tree topologies with 'N' nodes. For Binary Search Tree: We have to consider tree node values.
siva
  • 1,693
  • 2
  • 21
  • 29
35
votes
30 answers

Finding all combinations of well-formed brackets

This came up while talking to a friend and I thought I'd ask here since it's an interesting problem and would like to see other people's solutions. The task is to write a function Brackets(int n) that prints all combinations of well-formed brackets…
aleemb
  • 31,265
  • 19
  • 98
  • 114
17
votes
2 answers

What is the fastest (known) algorithm to find the n-th Catalan number mod m?

The problem is to find the n-th Catalan number mod m, where m is NOT prime, m = (10^14 + 7). Here are the list of methods that I have tried: (max N = 10,000) Dynamic programming for table look-up, too slow Use Catalan formula ncr(2*n, n)/(n + 1),…
roxrook
  • 13,511
  • 40
  • 107
  • 156
14
votes
2 answers

Python calculating Catalan Numbers

I have code which is calculating catalan numbers with method of Binominal Coefficients. def BinominalCoefficient(n,k): res = 1; if (k > n - k): k = n - k for i in range(k): res *= (n - i) res /= (i + 1) …
Reodont
  • 329
  • 1
  • 14
11
votes
8 answers

puzzle: N persons sitting on round table. No of ways of handshakes without crossing any other handshakes

We have n persons sitting on a round table. Any person can do a handshake with any other person. In how many ways these n people can make handshakes so that no two handshakes crosses each other. I found this puzzle in a technical interview forum,…
user2328404
  • 423
  • 1
  • 4
  • 9
10
votes
1 answer

Time complexity for combination of parentheses

I tried to do the classical problem to implement an algorithm to print all valid combinations of n pairs of parentheses. I found this program (which works perfectly) : public static void addParen(ArrayList list, int leftRem, int rightRem,…
salamanka44
  • 904
  • 3
  • 17
  • 36
10
votes
3 answers

Given a sorted integer array, how may Binary Search trees can be formed from it?

Consider I have an array [3,18,15,25,26], how many possible binary search trees can be formed from it?
Rahul
  • 44,892
  • 25
  • 73
  • 103
9
votes
9 answers

How to print all possible balanced parentheses for an expression?

For example, with elements a,b,c,d, there are 5 possible ways to take neighboring elements and reduce them into a single element, where exactly two elements must be combined at a time (below represented by parentheses): (((ab)c)d), ((a(bc))d),…
Jexcy
  • 594
  • 4
  • 15
9
votes
2 answers

Algorithm for finding kth binary number with certain properties

Let's assume we will consider binary numbers which has length 2n and n might be about 1000. We are looking for kth number (k is limited by 10^9) which has following properties: Amount of 1's is equal to amount of 0's what can be described as…
abc
  • 2,371
  • 3
  • 25
  • 36
8
votes
3 answers

Generate permutation using a single stack

Can anyone please explain algorithm to generate the permutations possible when using only a single stack and push and pop are the only operations allowed. Have searched about it a lot, but no definite answer. Also the total number of such…
Rohit Jain
  • 831
  • 3
  • 12
  • 22
8
votes
1 answer

Number of ways of correctly arranging parenthesis

I've been thinking for a while about this problem: What's the number of ways of correctly* arranging 2*n parenthesis. *A correctly arranged sequence of parenthesis has an equal number of open and closed parenthesis at its end and a larger or…
Arvid Nyman
  • 113
  • 1
  • 7
8
votes
3 answers

Catalan Numbers, Recursive function time complexity

The following function produces the nth number in catalan numbers. What is the exact time complexity function of this function or how can I find it myself? int catalan(int n) { if (n==0 || n==1) return 1; int sum = 0; for(int…
Amen
  • 1,524
  • 5
  • 22
  • 41
6
votes
2 answers

Closure Number Method for Generate Parenthesis Problem

The standard Generate Parenthesis question on Leetcode is as follows Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given n = 3, a solution set is: [ "((()))", "(()())", …
Stuxen
  • 708
  • 7
  • 21
6
votes
2 answers

Algorithm to generate mountain ranges with upstrokes and down-strokes (java)

I tried to do the classical problem to implement an algorithm to print all valid combinations of n pairs of parentheses. And I found this program (which works perfectly) : public static void addParen(ArrayList list, int leftRem, int…
salamanka44
  • 904
  • 3
  • 17
  • 36
6
votes
1 answer

Enumerate all full (labeled) binary tree

I'm searching a practical algorithm for enumerating all full labeled binary tree. A full binary tree is a tree where all internal nodes has a degree 3, the leaves has degree 1 and the root has a degree 2. A labeled tree is a tree where all leaves…
Giggi
  • 681
  • 2
  • 9
  • 17
1
2 3 4 5 6 7 8