Combinatorics Decoded

By A K Pandey

Combinatorics is one of most logical and live field of mathematics. Concepts of combinatorics are widely applicable in probability and computations. Learning combinatorics requires little different approach. It requires building fundamental rules of execution. Every new problem demands a new rule. This book focuses on experiential learning of the subject.
It takes reader into the all new world of the combinatorics while developing intuitive map of working algorithms.

This book is suitable as a class text or for individual study. This trusted book covers the Concepts of Combinatorics including the counting techniques, Permutations and Combinations, Arrangements of objects in circular manner, Derangement, generating functions and recurrence relations. This wonder book is also suitable for any one interested in learning combinatorics from SCRATCH and having no basic knowledge.

Concepts are presented in very lucid manner, students will definitely find it very easy to read. A wide range of solved examples, about 300 combinatoric problems taken from various mathematical competitions and exercises are also included.

Contents:
-Permutations and Combinations

-Generating Functions

-Recurrence Relations

-partitions of Integers

-counting sequences and generating functions

-Derangement

-Application of Prime Factorization Theorem in combinatorics

-Binomial Coefficients and Multinational Coefficients

-Lots of Problems

• Language: English
• Publisher: IIT PAL
• Release date: Sep 30, 2020
• ISBN: 9781393006749

Book preview

Before we begin

The Beginning of Scientific Counting

C

OMBINATORICS IS ALL about counting. So be it counting of heads or counting of different outcomes, in this book we will discover many exciting examples of things you can count. Undoubtedly this book is all about counting uncountable in some sense.

History of combinatorics is very interesting, combinatorial problems have been studied by ancient Indian, Arabian and Greek mathematicians. Major work on the subject were carried during the 19th and 20th century.

Combinatorics has many applications in other areas of mathematics, including, coding and cryptography, and computations.

C:\Users\Ojas\Desktop\images.png Barcodes

You must have observed this type of barcodes on almost everything you buy now days!

Have you ever observed how these barcodes are helping manufacturer and industries all over the world? To be more mathematical, if a manufacturer uses above formats of barcode, can you think of maximum number of products that the company can produce.

Or, how could a barcode be designed, so that there can be at least 100000 different products?

Passwords

How much time would it require (worst case) to guess (or hack) a password or a secret code, which is 9 character long and can contain alphabets, numbers and some special characters like @#$%&*?

Well, one thing it will surely depend upon is – How many such different codes would be possible?

Problems such as these require a systematic and a logical way of counting to be answered correctly, and, in a reasonable amount of time. This topic is all about that – to count without counting!

We’ll begin with the basic principles of counting, and as we proceed, we’ll develop some advanced techniques which can help us answer a lot of complex counting related problems and ultimately count the uncountable!

Do not worry we will find it out in this chapter. We will also establish the fundamentals behind counting and develop smarter way of counting.

We will also look for answers to the questions like In how many ways is it possible to do?  or what is the possible number of ways?

Let us start working into it!

Chapter-1

NOW WHEN WE HAVE SEEN that counting one by one is not going to work in most of the case, we need to establish few basic rules to overcome this. We call these basic rules that ease out counting burden, Fundamental Principle of Counting. If we want to do counting smartly, we have to work upon these fundamental rules fist. To do so, let’s start with a very interesting counting problem.

To introduce the principles, let us take an example of a car brand that sells the following three categories of cars,

And six different models of each say LXi, VXi, ZXi and LDi, VDi, ZDi. Now can you count, how many different types of cars does the car brand sells?

Before moving ahead, think about it for a moment and try to find out the answer yourself.

Well, let us create a list of all the possible cases one by one and count all these cases.

There are 6 different Hatchback cars by brand viz hatchback of LXi,  VXi, ZXi and LDi, VDi, ZDi.

AND,

Finally, if we count, a total of 6+6+6 = 18 types of cars are available with the brand. All right!

Here is how we can reach that number by a simple calculation.

Since there are 3 car categories (hatchback , sedan & SUV), and each of these comes in 6 different models, the total number of types of cars can be obtained multiplying the number of categories (3) with the number of models available for each category (6),

Which is 3 x 6 = 18

Now I am going to make this counting little more complicated. Suppose each of the above models were available in 4 different colours.

Black  Blue  orange  White 

How many different cars do you think are available now?

Let us do the counting again. Previously we had 18 different cars, now each car is available in four colour options.

Since each of the car is available in 4 colours, and there are 18 different types of cars (as we calculated above), we have 18 black cars +18 blue cars +18 orange cars +18 white cars = 18 x 4 = 72 different cars.

And this number can be obtained by multiplying together, the number of categories of cars (3), number of models for each category (4) and the number of colours available for each model (5) i.e. 3x 4x 5= 60

Now let’s see one more example to have more insights of the process.

Suppose there are 3 different flights and 5 different trains connecting two cities New York and Chicago. In how many different ways can you reach from NY to Chicago (using only these flights or trains)?

To reach from Ney York to Chicago we have two choice, choice 1 is to go by flight and second choice is to go via train.

Because you can either choose one of the flights (3 choices) or choose one of the trains (2 choices). Therefore the total numbers of choices are 3 + 2 = 5 (Flight 1 or Flight 2 or Flight 3 or Train 1 or Train 2).

Now when we have seen these examples and done the calculation involved in them, let us now summarise the calculations more formally.

If a task T can be divided into subtasks T1 and T2, which can completed in m ways and n ways respectively, and T will be completed by completing either T1 or T2, then the number of ways of completing T will be m + n. We call this Addition Principle.

If a task T can be divided into subtasks T1 and T2, which can completed in m ways and n ways respectively, and T will be completed by completing both T1 and T2, then the number of ways of completing T will be m.n. We call this Multiplication Principle.

We can extend this multiplication principle as, If a task T can be divided into n subtasks T1,T2,T3,....Tn, which can completed in m1, m2, m3... mn ways respectively and T will be completed by completing each of these subtasks, then the number of ways of completing T will be m1.m2 .m3....mn.

Let us now apply these principles in few real problems. I suggest you to apply above principles and try to solve following problems yourself before seeing the solution.

Solution: Let E1 be the event of travelling from A to B & E2 be the event of travelling from B to C by the person.

8 Flights    10 Flights 

Travel Tokyo to Barcilona can happen in 8 ways and travel cBarcilona to Toronto can happen in 10 ways.

Since both the events (travel 1 and travel 2) are to be happened in order, simultaneously. Hence, the number of ways = 8 × 10 = 80.

Example-1.2

A college offers 7 courses in the morning and 5 in the evening. Find the possible number of choices with the student if he wants to study one course in the morning and one in the evening.

Solution: The student has seven choices from the morning courses out of which he can select one course in 7 ways.

For the evening course, he has 5 choices out of which he can select one in 5 ways.

Hence the total number of ways in which he can make the choice of one course in the morning and one in the evening = 7 × 5 = 35.

Example-1.3

Mr. Rik wants to go from his home in Paris to office in Toronto via New York and come back home. There are 8 different flights Paris to New York and 6 different flights from New York to Toronto. In