Combinatorics-II

Catalan Numbers

Introduction

There are a number of concepts that could be solved using Catalan numbers.

Catalan numbers are a succession of positive numbers that show up in many

counting problems in combinatorics. They count particular sorts of grid ways,

permutations, binary trees, and numerous other combinatorial items. They fulfill a

principal recurrence relation.

Catalan numbers are a set of positive integers that appear in many combinatorial

counting problems like the hand-shake problem, total number of paths from [0,0]

to [n,n] where you can’t move on diagonal elements etc. They keep track of lattice

pathways, permutations, binary trees, and a wide range of other combinatorial

objects. They have a closed-form formula in terms of binomial coefficients and

satisfy a fundamental recurrence relation.

Sample Problems:

1. Find the total number of ways from point (0, 0) to reach (n, n). You can’t

cross the diagonal and you cannot use the diagonal path.

2. Triangulation problem: You are given a polygon with n + 2 vertices. How

many triangles can you draw inside the given polygon using its diagonals?

The diagonals must not cut each other.

1
 3. How many different binary trees can be drawn with n nodes?

Now, with the following process, we have found out, For a given ‘n’ number of

nodes, how many ways it can be represented as a binary tree.

1. Define an array of size n and put arr[0] = 1.

2. For n = 1, there is one possible representation of a binary tree. Hence,

update the arr[1] = 1.

3. For n = 2, there are two configurations of binary trees possible. Hence,

4. For n = 3, there are five possible configurations of binary trees. Hence,

arr[3] = 5.

2
5. Hence, we can standardize the number of possible configurations of left

and right nodes as products of their respective array values, as shown in

the diagram.

6. Similarly, for n = 4, the possible number of nodes are

3
Code:

#include <iostream>
using namespace std;
unsigned long int catalan(unsigned int n)
{
if (n <= 1)
return 1;
// catalan(n) is sum of catalan(i)*catalan(n-i-1)
unsigned long int res = 0;
for (int i = 0; i < n; i++)
res += catalan(i)
* catalan(n - i - 1);
return res;
}
int main()
{
for (int i = 0; i < 10; i++)
cout << catalan(i) << " ";
return 0;
}

Time Complexity:

O (N2), where N is the number of nodes in the tree.

Inclusion Exclusion
Introduction:

It is a very easy technique, which could be used to solve many complicated

problems like the Hat-Check Problem i.e. to determine the number of

derangements (or permutations) of n objects such that no object is in its original

position. The inclusion-exclusion can help you evaluate the UNION of N sets by

their intersection.

Example:

4
 ● Suppose, we have to find the total number of elements between 1 to 10
either divisible by 2 or 5 .
A = [2, 4, 6, 8, 10]
B = [5, 10]

|A ∪ B| = |A| + |B| + |A ∩ B|
= 5 + 2 -1
=6

● Hence, for the total number of elements divisible by a,b and c

Live Problem - NGM2 - Another Game with Numbers

Problem Statement:

Little Chikoo likes to play with numbers. Often he plays the following game:

1. He chooses a number N and a set of positive integers.

2. He writes down all the numbers from 1 to N.

5
 3. He chooses the first number (say x) from the set and cancels out all the

multiples of x from 1 to N, including x.

He repeats step 3 for all the numbers from the set.

One day Little Chikoo was in the mood to play pranks. So his brother asked him to

play the game with a certain challenge. He made the game a little harder and

asked him to find out the number of integers that aren't cancelled after he

completes step 4. If he does that then Little Chikoo gets to play on his brother's

Nintendo for one full day. Now Little Chikoo is in a hurry and wants to finish the

job as soon as possible. He has asked for your help.

Approach:

If we think carefully, then we can understand that in the question we have to

find the number of integers that are not divisible by any integer given in the set.

To achieve that we can follow the following steps.

● First of all, we can convert the question a little bit. Instead of finding the

number of integers that are not divisible by any integer given in the set,

we can simply find the number which is divisible by at least one number

and subtract it from N. (i.e N - {number divisible by at least one

integer}).

● N is already given to us therefore, we just need to find the second part of

the equation described above.

6
 ● It is easy to find out that the number of integers (x) which are divisible by

a given integer in the range (1 to N) is simply [N/x] (rounded down). But

if we do it for all the integers given in the set it will give us a wrong

answer because of double counting (Because there can be an integer

that is divisible by more than one given integer but we have to count it

only once).

● To resolve the above-mentioned problem we use the principle of

inclusion-exclusion. If we think carefully we want to calculate (F(a1) ∪

F(a2)....F(ak)).

● Where ai is the given divisor and F(ai) means numbers of integers

divisible by ai in the range 1 to N.

● As we discussed above that (F(a1) ∪ F(a2)....∪ F(ak)) = (F(a1) + F(a2)....+

F(ak)) - (F(a1) ∩ F(a2)....∩ F(ak))(all pair of intersection).

● It is simple to find (F(a1) + F(a2)....+ F(ak)) because F(ai) is nothing but

equal to N/ai. Now to find the intersection we can say that (F(ai) ∩

F(ai+1)) is equal to the N/LCM(ai,ai+1).

● In order to find the intersection of all the pairs of divisors, we can use bit

masking for more clarity. You can refer to the following implementation.

Code:
#include<bits/stdc++.h>
#define ll long long int
using namespace std;

ll calculateLCM(ll a , ll b){
if(a == 0) return b;

return (a * b) / __gcd(a , b);

7
 cin>>n>>k;
for(int i=0;i<k;i++) cin>>ar[i];

for(int mask=1;mask<(1 << k);mask++){

ll lcm = 0;
int count = 0;

for(int i=0;i<15;i++)
if(mask & (1 << i)){
lcm = calculateLCM(lcm , ar[i]);
count++;
}

if(count % 2) res += n / lcm;

cout<<n - res;
}

Pigeon Hole Principle

This principle simply states that there are N numbers of pigeons and we have to

put these into (N-1) holes. Each of them needs to go exactly one of the holes,

then at least one of the pigeons has to share the hole. The concept is very easy,

and it could be used to solve many different problem questions.

Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to roost.

Because there are 20 pigeons but only 19 pigeonholes, at least one of these 19

pigeonholes must have at least two pigeons in it. This illustrates a general

principle called the pigeonhole principle, which states that if there are more

pigeons than pigeonholes, then there must be at least one pigeonhole with at

least two pigeons in it.

8
Example :

Suppose, we have to prove that there exist two numbers between 20 and 30, such

that their difference is also divided by 9. The possible remainders when a number

is divided by 9 are - 0, 1, 2,3,4,5,6,7,8, that is, 9 numbers.

Hence, we can conclude that there are at least 2 numbers, having the same

remainder.

a1 = 9 * d1 + r1

a2 = 9 * d2 + r1

(a1 - a2) = (9d1 - 9d2)

= 9 (d1 - d2)
9 (𝑑1 − 𝑑2)
= 9

Live Problem: Hallow - Halloween Treats

9
Every year there is the same problem at Halloween: Each neighbour is only

willing to give a certain total number of sweets on that day, no matter how

many children call on him, so it may happen that a child will get nothing if it is

too late. To avoid conflicts, the children have decided they will put all sweets

together and then divide them evenly among themselves. From last year's

experience of Halloween, they know how many sweets they get from each

neighbor. Since they care more about justice than about the number of sweets

they get, they want to select a subset of the neighbors to visit, so that in sharing

every child receives the same number of sweets. They will not be satisfied if

they have any sweets left which cannot be divided. Your job is to help the

children and present a solution.

Approach:
● First, we are going to find the prefix sum, from the given elements. Because

we can see that sum of any range L to R can represent using prefix sum as

Sum(L,R) = (prefixSum(R) - prefixSum(L-1)), Also modulo is an associative

property under addition. Therefore, prefixSum will help us to find whether

the sum of the subarray is divisible by the number of children (c) or not.

● Now we compute prefixSum modulo c, which will be stored in another

array. Now, wherever we get zero or equal remainder, then there exists a

solution from [previous position + 1] till [last position]. Because if we get

a zero it means that the sum from the first position to that position is

divisible by c. Else if we find that the remainder at two different positions is

equal it means that the sum of the range between these two positions is

divisible by c.

● Now, if the remainder is zero it means we can distribute equal candies to all

the children

10
Code:

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5;

int main(){

int c , n, x;

while(true){
cin>>c>>n;

if(c+n == 0) break;

//rem[i] = position where prefix_sum % c = i

for(int i=1;i<=n;i++) {
cin>>x;
pre[i] = pre[i-1] + x;
}

for(int i=1;i<=n;i++){
int r = pre[i] % c;

if(rem[r] != -1){
for(int L = rem[r]+1;L<=i;L++) cout<<L<<" ";
cout<<endl;
break;
}
else{
rem[r] = i;
}
}
}

11