Scribd
Upload
87 views15 pages

Basic Counting Principles Explained

This document discusses basic counting principles including the product rule, sum rule, subtraction rule, division rule, and tree diagrams. The product rule states that if a procedure can be broken into two sequential tasks, the number of ways to complete the procedure is the number of ways to complete the first task multiplied by the number of ways to complete the second task. The sum rule says you can find the total number of ways to complete a task by adding the number of ways to complete the task through different methods. The subtraction rule accounts for ways that are duplicated between methods. The division rule can be used when a task can be completed in a certain number of ways and there is a fixed number of ways to complete each part of the task.

Uploaded by

Ahsan Imtiax
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
87 views15 pages

Basic Counting Principles Explained

This document discusses basic counting principles including the product rule, sum rule, subtraction rule, division rule, and tree diagrams. The product rule states that if a procedure can be broken into two sequential tasks, the number of ways to complete the procedure is the number of ways to complete the first task multiplied by the number of ways to complete the second task. The sum rule says you can find the total number of ways to complete a task by adding the number of ways to complete the task through different methods. The subtraction rule accounts for ways that are duplicated between methods. The division rule can be used when a task can be completed in a certain number of ways and there is a fixed number of ways to complete each part of the task.

Uploaded by

Ahsan Imtiax
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 15

BASIC COUNTING

PRINCIPLES
Presenter: Muhammad Uzair
2021-CS-17
2

CONTENTS
o Introduction

o The Product Rule

o The Sum Rule

o The Subtraction Rule

o The Division Rule

o Tree Diagrams
Basic Counting Principles
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.
THE 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.
5

EXAMPLE:
A new company with just two employees, Ali and
Ahmad, rents A floor of A building with
12 offices. How many ways are there to assign
different offices to these two employees?

SOLUTION: The procedure of assigning offices to these


two employees consists of assigning an office to Ali,
which can be done in 12 ways, then assigning an office to
Ahmad different from the office assigned to Ali, which can
be done in 11 ways. By the product rule, there are 12 ⋅ 11
= 132 ways to assign offices to these two employees.

Basic Counting Principles


THE 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.
7

EXAMPLE:
A student can choose a computer project from one
of three lists. The three lists contain 23, 15,
a n d 1 9 p o s s i b l e p r o j e c t s , r e s p e c t i v e l y. N o p r o j e c t i s
on more than one list. How many possible
projects are there to choose from?

SOLUTION: 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.

Basic Counting Principles


THE SUBTRACTION
RULE
If a task can be done in either n1 ways or n2 ways, then
the number of ways to do the task is n1 + n2 minus the
number of ways to do the task that are common to the
two different ways.
9

EXAMPLE:
A computer company receives 350 applications from
college graduates for a job planning a line of new
web servers. Suppose that 220 of these applicants
majored in computer science, 147 majored in
business, and 51 majored both in computer science
and in business. How many of these applicants
majored neither in computer science nor in
business?

Basic Counting Principles


THE DIVISION RULE
There are n∕d ways to do a task if it can be done using a
procedure that can be carried out in n ways, and for
every way w, exactly d of the n ways correspond to way
w.
11

EXAMPLE:
Suppose that an automated system has been
developed that counts the legs of cows in a pasture.
Suppose that this system has determined that in a
farmer’s pasture there are exactly 572 legs. How
many cows are there is this pasture, assuming that
each cow has four legs and that there are no other
animals present?

SOLUTION: Let n be the number of cow legs counted in a


pasture. Because each cow has four legs, by the division
rule we know that the pasture contains n∕4 cows.
C o n s e q u e n t l y, t he pasture with 572 cow legs has
572∕4 = 143 cows in it.

Basic Counting Principles


TREE DIAGRAM
Counting problems can be solved using tree diagrams. A
tree consists of a root, a number of branches leaving the
root, and possible additional branches leaving the
endpoints of other branches.
13

EXAMPLE:
How many bit strings of length four do not have two
consecutive 1s?

Basic Counting Principles


SUMM ARY
• If you have n numbers of dishes you can find out the ways in which they can
be presented.
• Counting helps you know the number of events that can occur and thus
help you make the decision.
THANK YOU

You might also like