1.
Introduction
2.
Principles of Combinatorics
3.
Problems
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

# Combinatorics (BASICS)

Malay Gain
1 upvote

## Introduction

Combinatorics means the number of ways we can arrange some objects or we can choose some objects from a collection. It is one of the fundamental concepts that we need to know to solve programming problems. Here we will be discussing some basic formats of combinatorics problems and how to solve them. We will also implement the solutions of combinatorics problems in terms of pseudocode.

## Principles of Combinatorics

Sum rule:

``If there are n1 number of ways to reach the destination B from A and n2 number of ways to reach destination C  from B, then there are total n1+n2 number of ways to reach destination B or C.``

Example

You need to travel in between city A and B. You can either fly, take a train, or a bus. There are 12 different flights in between A and B, 5 different trains and 10 buses. How many options do you have to get from A to B?

Ans.

According to the sum rule, there are total (12+5+10)=27 options to get from A to B.

Product rule:

``If there are n1 number of ways to reach the destination B from A and n2 number of ways to reach destination C  from B, then there are total n1*n2 number of ways to reach from A to destination  C.``

Example

A new company with just two employees, Dhruv and Souhard, rents a floor of a building with 12 offices. How many ways are there to assign different offices to these two employees?

Ans.  Dhruv can be assigned with an office in 12 ways, and Souhard can be assigned with any one of the remaining 11 offices after assigning Dhruv with one. So, by product rule, there are 12*11=132 ways to assign different offices to these two employees.

The Subtraction Rule (Inclusion-Exclusion Principle)

``It uses a sum rule and then corrects for the overlapping part i.e., If a task can be done in either n1 ways or n2 ways, then the number of ways to do the task is n1 + n2 minus the number of ways to do the task that are common to the two different ways.``

Example

How many bit strings of length 5 start either with a bit 1 or end with 0?

Ans.

(no. of bit strings starts with 1 + no. of bit strings ends with 0) – no. of bit strings starts with 1 and ends with 0)

=

Pigeonhole Principle

``If k + 1 or more objects are placed into k boxes, there is at least one box containing two or more of the objects where k is a positive integer.``

There are 13 pigeons sitting in 12 holes. So, there is at least one hole where 2 or more pigeons are sitting in every possible arrangement.

Example

In any group of 27 English words, there must be at least two that begin with the same letter because there are 26 letters in the English alphabet.

Note: Please try to solve the problems first and then see the below solution approaches.

## Problems

Problem type 1

There are n distinct objects. How many ways k objects can be arranged from n objects.

Solution approach

For the 1st position, there are n possibilities.

For the 2nd position, there are (n-1) possibilities.

For the 3rd position, there are (n-2) possibilities.

.

.

.

.

For, the kth position there are (n-k+1) possibilities.

So, by product rule total no of ways P(n,k) =n*(n-1)*(n-2)..........(n-k+1) =

Problem type 2

Find the number of ways k objects can be chosen from n distinct objects?

Solution approach

Basically, we need to find the combination of k objects from n distinct objects = C(n,k) =

Problem type 3

Find the number of k-permutations of a set of n objects when repetition allowed?

Solution approach

As there will be n possibilities for each of k positions, the number of k-permutations= n*n*n…..k times =

Problem type 4

How many ways n objects can be arranged where n1 indistinguishable objects of type 1 and  n2 indistinguishable objects of type 2…… nk indistinguishable objects of type k

Solution approach

n objects can be arranged in n! Ways. But n1 objects are of similar type, their occurrences are indistinguishable. Similarly for other types of objects, it is true.

So, the number of unique arrangements =

Problem type 5

How many way k elements can be chosen from the set with n elements when repetition is allowed?

Solution approach

In this case number of different combinations = C(n+k-1,k)=

Problem type 6

Find how many solution does this equation have, x1+x2+x3+.......+xn = k, where xi is a non-negative integer?

Solution approach

If there are k elements, we need to put (n-1) separators to distribute k elements in n parts. Similarly, we can add (n-1) extra elements with k elements and choose k elements from (n+k-1) elements randomly. In that case remaining (n-1) elements will be considered as separators.

So, numbe of ways we can choose k elements from (n+k-1) elements = number of solutions the equation having = C(n+k-1,k)=

Also see, Euclid GCD Algorithm

## FAQs

Q1.Find the maximum number of different Boolean functions involving n Boolean variables?

(A)2^n  ( B)2^(n/2)  (C) 2n  (D) None of these

For every variable there are 2 possible values i.e. 0 or 1. So, total number of different boolean function = 2*2*2*......n times =

Q2.Find the number of different n × n symmetric matrices with each element being either 0 or 1 is?

As the matrix is symmetric, we need to only consider the upper or lower triangle of the matrix diagonal. So, total 1+2+....+n=n(n+1)/2 elements of the matrix will change, others will be fixed. Hence, the total number of different symmetric matrices possible

= 2*2*2*.......n(n+1)/2 times

## Key Takeaways

This article covered the basics of combinatorics, few problems, and their solution.

Check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here.

Happy learning!

Live masterclass