MULTIPLICATIVE PRINCIPLE: COUNTING TECHNIQUES AND EXAMPLES - MATHS - 2024

The multiplicative principle is a technique used to solve counting problems to find the solution without having to list its elements. It is also known as the fundamental principle of combinatorial analysis; it is based on successive multiplication to determine how an event can occur.

This principle states that, if a decision (d ₁) can be made in n ways and another decision (d ₂) can be made in m ways, the total number of ways in which decisions d ₁ and d ₂ can be made will be equal to multiply from n _* m. According to the principle, each decision is made one after the other: number of ways = N _{1 *} N ₂ … _* N _x ways.

Examples

Example 1

Paula plans to go to the movies with her friends, and to choose the clothes she will wear, I separate 3 blouses and 2 skirts. How many ways can Paula dress?

Solution

In this case, Paula must make two decisions:

d ₁ = Choose between 3 blouses = n

d ₂ = Choose between 2 skirts = m

That way Paula has n _* m decisions to make or different ways of dressing.

n _* m = 3 _* 2 = 6 decisions.

The multiplicative principle stems from the tree diagram technique, which is a diagram that relates all the possible outcomes, so that each one can occur a finite number of times.

Example 2

Mario was very thirsty, so he went to the bakery to buy juice. Luis takes care of him and tells him that it comes in two sizes: large and small; and four flavors: apple, orange, lemon and grape. How many ways can Mario choose the juice?

Solution

In the diagram it can be seen that Mario has 8 different ways to choose the juice and that, as in the multiplicative principle, this result is obtained by multiplying n _* m. The only difference is that through this diagram you can see what the ways in which Mario chooses the juice are like.

On the other hand, when the number of possible outcomes is very large, it is more practical to use the multiplicative principle.

Counting techniques

Counting techniques are methods used to make a direct count, and thus know the number of possible arrangements that the elements of a given set can have. These techniques are based on several principles:

Addition principle

This principle states that, if two events m and n cannot occur at the same time, the number of ways in which the first or second event can occur will be the sum of m + n:

Number of shapes = m + n… + x different shapes.

Example

Antonio wants to take a trip but does not decide which destination; at the Southern Tourism Agency they offer you a promotion to travel to New York or Las Vegas, while the Eastern Tourism Agency recommends traveling to France, Italy or Spain. How many different travel alternatives does Antonio offer you?

Solution

With the Southern Tourism Agency Antonio has 2 alternatives (New York or Las Vegas), while with the Eastern Tourism Agency he has 3 options (France, Italy or Spain). The number of different alternatives is:

Number of alternatives = m + n = 2 + 3 = 5 alternatives.

Permutation principle

It is about specifically ordering all or some of the elements that make up a set, to facilitate the counting of all the possible arrangements that can be made with the elements.

The number of permutations of n different elements, taken all at once, is represented as:

_n P _n = n!

Example

Four friends want to take a picture and want to know how many different ways they can be arranged.

Solution

You want to know the set of all the possible ways in which the 4 people can be positioned to take the picture. Thus, you have to:

₄ P ₄ = 4! = 4 _* 3 _* 2 _* 1 = 24 different shapes.

If the number of permutations of n available elements is taken by parts of a set that is made up of r elements, it is represented as:

_n P _{r =} n! ÷ (n - r)!

Example

In a classroom there are 10 seats. If 4 students attend the class, in how many different ways can students fill the positions?

Solution

We have that the total number of the set of chairs is 10, and of these only 4 will be used. The given formula is applied to determine the number of permutations:

_n P _r = n! ÷ (n - r)!

₁₀ P ₄ = 10! ÷ (10 - 4)!

₁₀ P ₄ = 10! ÷ 6!

₁₀ P ₄ = 10 _* 9 _* 8 _* 7 _* 6 _* 5 _* 4 _* 3 _* 2 _* 1 ÷ 6 _* 5 _* 4 _* 3 _* 2 _* 1 = 5040 ways to fill the positions.

There are cases in which some of the available elements of a set are repeated (they are the same). To calculate the number of arrays taking all the elements at the same time, the following formula is used:

_n P _r = n! ÷ n ₁ ! _* n ₂ !… n _r !

Example

How many different four letter words can be formed from the word "wolf"?

Solution

In this case there are 4 elements (letters) of which two of them are exactly the same. Applying the given formula, it is known how many different words result:

_n P _r = n! ÷ n ₁ ! _* n ₂ !… n _r !

₄ P _{2, 1,1} = 4! ÷ 2! _* 1! _* 1!

₄ P _{2, 1, 1} = (4 _* 3 _* 2 _* 1) ÷ (2 _* 1) _* 1 _* 1

₄ P _{2, 1, 1} = 24 ÷ 2 = 12 different words.

Combination principle

It is about arranging all or some of the elements that make up a set without a specific order. For example, if you have an XYZ arrangement, it will be identical to the ZXY, YZX, ZYX arrangements, among others; this is because, despite not being in the same order, the elements of each arrangement are the same.

When some elements (r) are taken from the set (n), the principle of combination is given by the following formula:

_n C _{r =} n! ÷ (n - r)! R!

Example

In a store they sell 5 different types of chocolate. How many different ways can 4 chocolates be chosen?

Solution

In this case, 4 chocolates have to be chosen from the 5 types that they sell in the store. The order in which they are chosen does not matter and, in addition, a type of chocolate can be chosen more than twice. Applying the formula, you have to:

_n C _r = n! ÷ (n - r)! R!

₅ C ₄ = 5! ÷ (5 - 4)! 4!

₅ C ₄ = 5! ÷ (1)! 4!

₅ C ₄ = 5 _* 4 _* 3 _* 2 _* 1 ÷ 4 _* 3 _* 2 _* 1

₅ C ₄ = 120 ÷ 24 = 5 different ways to choose 4 chocolates.

When all elements (r) of the set (n) are taken, the combination principle is given by the following formula:

_n C _{n =} n!

Solved exercises

Exercise 1

There is a baseball team with 14 members. In how many ways can 5 positions be assigned for a game?

Solution

The set is made up of 14 elements and you want to assign 5 specific positions; that is, order matters. The permutation formula is applied where n available elements are taken by parts of a set that is formed by r.

_n P _{r =} n! ÷ (n - r)!

Where n = 14 and r = 5. It is substituted in the formula:

₁₄ P ₅ = 14! ÷ (14 - 5)!

₁₄ P ₅ = 14! ÷ (9)!

₁₄ P ₅ = 240 240 ways to assign the 9 game positions.

Exercise 2

If a family of 9 goes on a trip and buys their tickets with consecutive seats, how many different ways can they sit down?

Solution

It is about 9 elements that will occupy 9 seats consecutively.

P ₉ = 9!

P ₉ = 9 _* 8 _* 7 _* 6 _* 5 _* 4 _* 3 _* 2 _* 1 = 362 880 different ways of sitting.

References

1. Hopkins, B. (2009). Resources for Teaching Discrete Mathematics: Classroom Projects, History Modules, and Articles.
2. Johnsonbaugh, R. (2005). Discrete mathematics. Pearson Education,.
3. Lutfiyya, LA (2012). Finite and Discrete Math Problem Solver. Research & Education Association Editors.
4. Padró, FC (2001). Discrete mathematics. Politèc. of Catalunya.
5. Steiner, E. (2005). Mathematics for applied sciences. Reverte.