Topic : General rules of combinatorial mathematics

The field of mathematics that study problems of how many different combinations (subject to certain restrictions) can be made out of a specific number of objects is called combinatorial mathematics (combinatorics or counting).

Specialists in a broad range of fields have to deal with problems that involve combinations made up of letters, numbers or any other objects. For example: the department head in a factory has to allocate production assignments to machine – tool operators, the school principal draws up schedules of lessons and so on. For a software engineer combinatorics is important because its methods are used for analysis of algorithms efficiency and also for solving problems of combinatorial nature.

A finite set M that contains n elements will be called a n – set and we shall write |M| = n. A subset A M, which consists of k elements will be called a k-subset.

Let me remind you that a Cartesian product A×B of sets A and B is a set of all possible ordered pairs of (a, b). A×B = {(a, b)| a∈A, b∈B};

n - set is called ordered if it is mapped in a one–to–one manner onto the set {1,2,…,n}. (If each element of this n – set is assigned to a single i ∈ {1,2,….,n}).

The rule of sum.

If a certain object A can be chosen in m ways and another objects B can be chosen in n ways then the choice of “either A or B” can be accomplished in m + n ways.

A general statement of the rule of sum:

If an object a₁ can be chosen in m₁ ways,
an object a₂ can be chosen in m₂ ways,

----------------------------------------------------

an object a_k can be chosen in m_k ways,

then the choice of either a₁or a₂ or …. or a_k can be accomplished in m₁ + m₂ +....+ m_k ways. I remind that the possibility of a choice of a second element is excluded.

Example: In Kharkov university of radio - electronics students are trained at the computer science faculty in 3 specialities, at the system design faculty in 2 specialitics, at the faculty of electronics in 2 specialities, at the faculty of computer hardware design in 2 specialities, at the radio equipment faculty – in 2 specialities. In total a future full time student can choose a speciality in 3 + 2 + 2 + 2 + 2 = 11 ways.

The rule of product.

If an object A can be chosen in m ways and if, after any such a choice, an object B can be chosen in n ways then the choice of a pair (A, B) in that order can be accomplished in m*n ways.