Combinatorics and Mathematical Induction: Introduction

Introduction

Combinatorics is the branch of mathematics which is related to counting. It deals with arrangements of objects as well as enumeration, that is, counting of objects with specific properties. The roots of the subject can be traced as far back as 2800 BCE when it was used to study magic squares and patterns within them.

English physicist and mathematician Sir Isaac Newton, most famous for his law of gravitation, was instrumental in the scientific revolution of the 17th century. Newton’s belief in the “Persistance of patterns” led to his first significant mathematical discovery, the generalization of the expansion of binomial expressions.

Newton discovered Binomial Theorem which he claimed the easiest way to solve the quadratures of curves. This discovery is essential in understanding probability. The generalized version of the Binomial Theorem, the Multinomial Theorem, applies to multiple variables. It is widely used in Combinatorics and Statistics.

He was the first to use fractional indices and to employ coordinate  geometry  to  derive  solutions  to  Diophantine  equations.  He approximated partial sums of the harmonic series by logarithms (a precursor  to  Euler’s  summation  formula)  and  was  the  first  to  use power series with confidence and to revert power series. Newton’s Newton (1643−1727) work on infinite series was inspired by Simon Stevin’s decimals.

In 1705, he was knighted by Queen Anne of England, making him Sir Isaac Newton. Newton made discoveries in optics and theory of motions. Along with mathematician Leibnitz, Newton is credited for developing essential theories of calculus.

Combinatorics has many real life applications where counting of objects are involved. For example, we may be interested to know if there are enough mobile numbers to meet the demand or the number of allowable passwords in a computer system. It also deals with counting techniques and with optimisation methods, that is, methods related to finding the best possible solution among several possibilities in a real problem. In this chapter we shall study counting problems in terms of ordered or unordered arrangements of objects. These arrangements are referred to as permutations and combinations. Combinatorics are largely used in the counting problems of Network communications, Cryptography, Network Security and Probability theory. We shall explore their properties and apply them to counting problems.

Consider another situation: We all know that our electricity consumer card number is of the form B : C, where A denotes the electrical substation /larger capacity transformer number, B denotes the smaller capacity electricity transformer number and C denotes the consumer number. There may be conditions that to each substation certain maximal number of transformer can only be linked and with a particular transformer certain maximal number of consumer connection can only be linked. Now the question of deciding, whether a new Transformer/Substation needs to be erected, can be made by the count of the number of consumer connections linked with a substation transformer. How to get that count? This count can be easily arrived by the use of counting principles.