Transcript Fibonacci’s Numbers

COUNTING METHOD
THE ADDITION PRINCIPLE
INCLUSION-EXCLUSION PRINCIPLE
THE MULTIPLICATION PRINCIPLE
EX1) ADDING GROUPS OF STUDENTS
Dr. Abercrombie has 15 students in an
abstract algebra class and 20 students in
a linear algebra class. How many different
students are in these two classes?
 Case1
: if there is no students in both
classes
 Case2:
classes
if there are 3 students in both
EX2)
A city has two daily newspapers, A and B say.
The following information was obtained from a
survey of 100 city residents: 35 people subscribe
to A, 60 subscribe to B, and 20 subscribe to
both.
1.
2.
3.
4.
How many people subscribe to A but not to B?
How many subscribe to B but not to A?
How many do not subscribe to either paper?
Draw a Venn diagram for the newspaper
survey.
EX3)
The menu for a
restaurant is listed
as follows:
How many different
dinners consist of
1 appetizer, 1 maincourse, and 1 beverage ?
EX4)
(1) How many strings of length 4 can be
formed using the letters ABCDE if
repetitions are not allowed?
(2) How many strings of part(1) begin with
letter B ?
(3) How many strings of part(1) do not
begin with letter B ?
EX5)
Let X be an n-element set.
(1) How many subsets of X are formed?
(2) How many ordered pairs of (A, B) satisfy
A B X
?
PERMUTATIONS


A permutation of a set of objects is an
arrangement of the objects in a specific order
without repetition.
P (n,r) — a permutation of n objects taken r at
a time without repitition
COMBINATIONS


A combination of a set of n object taken r at a
time without repetition is an r -element subset of
the set of n objects. The arrangement of the
elements in the subset does not matter.
C (n,r ) — a combination of n objects taken r at
a time without repetition
EX6) FROM A COMMITTEE OF 10 PEOPLE CONSISTING
OF 6 WOMEN AND 4 MEN,
(1) In how many ways can we choose a
chairperson, a vice-chairperson, and a secretary,
assuming that one person cannot hold more than
one position?
(2) In how many ways can we choose a
subcommittee of 3 people?
In a permutation, order is vital.
In a combination, order is irrelevant.
EX6) FROM A COMMITTEE OF 10 PEOPLE CONSISTING
OF 6 WOMEN AND 4 MEN,
(3) In how many ways can we choose a
subcommittee consisting of 3 women and 2 men?
(4) In how many ways can we choose a
subcommittee of equal number of women and
men?
(5) In how many ways can we choose a
subcommittee of 5 people with at least 2 women?
EX7)COMBINATIONS

If a fair coin is flipped 9 times, how many
different ways are there to have 7 or more heads?
EX8) PERMUTATIONS
(1) How many possibilities are there that everyone
of 25 member of a group has a different birthday?
(2) How many possibilities are there that at least
two of 25 members of a group have a common
birthday?
EX9)DISTRIBUTION 1

How many routes are there from the lower-left
corner of n × n square grid to the upper-right
corner if we are restricted to traveling only to the
right or upward?
EX10)DISTRIBUTION 2



How many nonnegative integer solutions are there
to the equation
x  y  z?  w  10
How many positive integer solutions are there to
the equation x  y  z  w  ?10
How many solutions with x  1, y  2, z  3, w? 0


The number of distributions of r identical
objects into n different places is
C (n  r  1, r )
or
C (n  r  1, n  1)
EX11)