Combinatorics (BASICS)

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!