Combinatorics For Programmers and Coders

Hey! Computer Geeks! Here we will discuss two or more special numbers that made the way of coding easy,

Introduction to Catalan Numbers:

The Catalan numbers are a sequence of positive integers that appear in many counting problems in combinatorics. They count certain types of lattice paths, permutations, binary trees, and many other combinatorial objects. They satisfy a fundamental recurrence relation and have a closed-form formula in terms of binomial coefficients.

The Catalan number Cn describes, among other things:

• The number of binary trees with n nodes,
• The number of ways in which parentheses can be placed in a sequence of n+ 1 numbers to be multiplied two at a time,
• The number of well-formed reverse Polish expressions with n operands and n + 1 operators,
• The number of paths in a grid from (0, 0) to (n, n), increasing just one coordinate by one at each step, without crossing the main diagonal,
•  The number of n-bit sequences that the number of 1s never exceeds the number of 0s in each position from left to right,
• The number of ways you can draw non-crossing segments between 2n points on a circle in the plane,
• The number of ways a polygon with n + 2 sides can be cut into n triangles,
•  The number of frieze pattern with n + 1 rows,
• The number of mountain ranges you can draw using n upstrokes and n downstrokes,

BUILDING ALGORITHM FOR THE PROBLEM STATEMENT:

Implementation of pairs:

In the given problem statement if we consider that any number of stars and number of children per each parent node is 2 then we can construct the problem as follows: Full Binary Trees: A Binary Tree is full if every node has 0 or 2 children. Thus, a full binary tree with n stars or nodes has 𝑛−12 internal vertices, 2𝑛 edges, and 𝑛+1 leaves.

Now the question is How many Full Binary Trees Possible with 𝑛∗ internal vertices?

**N.B.: - This 𝒏 is not the total number of nodes or stars, this 𝒏 is the total number of internal vertices. In the given question we will be given a number of total stars, not internal vertices, but the calculation is on the basis of internal parent nodes.

In-Fact the number of Full Binary Trees with 𝑛 internal vertices is the Catalan Number, 𝐶𝑛.

Implementation on Triplets/Quadruplets or Generalized Form of Catalan Number:

If the children per each node are three or four, we can’t compute Catalan number to print the possible number of full k-array trees, So, we have to generalized the format so that it can work for any number of child node given,

As per we know,

So, for Generalized case, Catalan Number also called as Fuss-Catalan Number is given by:

So, for all the possible Generalized terms for initial k-Catalan number:

Some Problems on Catalan Number and Fuss-Catalan Number can be seen here:

1. https://www.hackerearth.com/problem/algorithm/catalan-numbers-1/
2. https://www.spoj.com/problems/SKYLINE/
3. https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=932
4. http://codeforces.com/problemset/problem/9/D
5. https://www.spoj.com/problems/FUNPROB/
6. http://lightoj.com/login_main.php?url=volume_showproblem.php?problem=1170
7. https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4752

References:

•  CR Categories and Descriptors. G.2.1 [Mathematics and Computing]: Discrete Mathematics – Combinatorics, Counting problems.
• Dershowitz, N., Zaks, S., Enumeration of ordered trees, Discrete Mathematics,31 (1980), • Weisstein, E. W., Catalan numbers, http://mathworld.wolfram.com/CatalanNumber.html
• Robert Dickau https://www.robertdickau.com/fusscatalan.html
• Multivariate Catalan Number https://arxiv.org/abs/0711.0906