techtud's picture
Combinatorics
Counting | Basic Counting Principles | Product rule | Sum rule | Principle of Inclusion-Exclusion

Introduction:

Counting problems arise throughout mathematics and computer science. For example, we must count the successful outcomes of experiments and all the possible outcomes of these experiments to determine probabilities of discrete events. We need to count the number of operations used by an algorithm to study its time complexity.  

Basic Counting Principles:  

We first learn two basic counting principles, the product rule and the sum rule.  

Product rule:

Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1n2 ways to do the procedure.  

Sum rule:

If a task can be done either in one of n1 ways or in one of n2 ways, where none of the set of n1 ways is the same as any of the set of n2 ways, then there are n1 +n2 ways to do the task.  

Principle of Inclusion-Exclusion:

The principle of inclusion-exclusion says that in order to count only unique ways of doing a task, we must add the number of ways to do it in one way and the number of ways to do it in another and then subtract the number of ways to do the task that are common to both sets of ways.

The principle of inclusion-exclusion is also known as the subtraction principle.  

For two sets of ways A1 and A2, the enumeration would like-

| A1 U A2 | = | A1 | + | A2 | - |A1 ∩ A2 |

 

Contributor's Info

Created:
0Comment
Counting problems
Content covered: 
Counting problems
More Less
0Comment
A student can choose a computer project from one of three lists. The t...

A student can choose a computer project from one of three lists. The three lists contain 23, 15, and 19 possible projects, respectively. No project is on more than one list. How many possible projects are there to choose from?

Answer
The student can choose a project by selecting a project from the first list, the second list, or the third list. Because no project is on more than one list, by the sum rule there are 23 + 15 + 19 = 57 ways to choose a project.
0Comment
There are 32 microcomputers in a computer center. Each microcomputer h...
There are 32 microcomputers in a computer center. Each microcomputer has 24 ports. How many different ports to a microcomputer in the center are there?
Answer
The procedure of choosing a port consists of two tasks, first picking a microcomputer and then picking a port on this microcomputer. Because there are 32 ways to choose the micro- computer and 24 ways to choose the port no matter which microcomputer has been selected, the product rule shows that there are 32 · 24 = 768 ports.
0Comment
New company with just two employees, Sanchez and Patel, rents a floor ...
New company with just two employees, Sanchez and Patel, rents a floor of a building with 12 offices. How many ways are there to assign different offices to these two employees?
Answer
The procedure of assigning offices to these two employees consists of assigning an office to Sanchez, which can be done in 12 ways, then assigning an office to Patel different from the office assigned to Sanchez, which can be done in 11 ways. By the product rule, there are 12 · 11 = 132 ways to assign offices to these two employees.
0Comment

  • This quiz contains 5 questions on the topic Counting Problems
  • Learn well before you attempt the quiz

Difficulty Level:  intermediate