easy paper

1

Sets and Counting Ch. # 2

2.1 Sets and Set Operations

Objectives

 Learn the basic vocabulary and notation of the theory

 Learn and apply the union, intersection, and complement operations

 Drew Venn Diagrams

1. A Set is any collection of objects. The objects are called elements.

2. A set is a well-defined set if there is a way of determining for sure whether a particular item is an element of the set.

Ex:

Which of the following sets are well-defined?

a. The set of all movies directed by Alfred Hitchcock b. The set of all great rock-and-roll bands c. The set of all possible two-person committees selected from a group of five people

Solution:

a. This set is well-defined; either a movie was directed by Hitchcock, or it was not. b. This set is not well-defined; membership is a matter of opinion. Some people would

say that the Ramones

c. This set is well-defined; either the two people are from the group of five, or they are not.

3. Sets can be defined in three common ways: a. A verbal description, “the set of all states in the United States that start with letter O”. b. A listing (Roster notation) of the members separated by commas between { }. c. Set-builder notation: { X / X is a U. S state that borders the Pacific Ocean}

4. Sets are usually denoted by capital letters, A,B, C, …

5. To list the elements in a set A we use braces. A = { 1, 3, 9, … }

6. The symbols  ,  indicate that an element is or is not an element of a set.

7. The same elements are not listed more than once in a set. { , , } { , }a b a a b

8. The order of the elements in a set is not important.

9. The empty set, denoted by φ, no elements { }.    ,  of every set.

Equal

Two sets A and B are equal, A = B, if the sets have exactly the same

elements.

Equivalent

Two sets A and B are equivalent, written A B , if they have the same

number of elements.

2

Ex:

Describe each of the following in words.

a. { x | x > 0 and x  } b. {persons | the person is a living former U.S. president} c. {women | the woman is a former U.S. president}

Solution:

a. The set of all x such that x is a positive real number b. The set of all people such that the person is a living former U.S. president c. The set of all women such that the woman is a former U.S. president

The set listed in part (c) has no elements; there are no women who are former U.S. presidents.

If we let W equal “the set of all women such that the woman is a former U.S. president,” then

n(W) = 0.

A set that has no elements is called an empty set and is denoted by Ø or by { }.

Since the empty set has no elements, n(Ø) = 0. In contrast, the set {0} is not empty; it has one

element, the number zero, so n({0}) = 1.

Universal set U:

The universal set is the set that contains all the elements under consideration in a given

discussion.

Any set A divides the universe into two regions.

Venn diagram

A Venn diagram is a diagram provides a pictorial view of sets. It is used to illustrate

relationships among sets.

In Venn diagram a rectangle depicts a universal set, and subsets of the universal sets are

drawn as circles.

The inside of circles represents the members of that set.

Relation between sets

We say that A is a subset of B, written A B , if every element of A is an element of B.

If A is a subset of B and A B , then we say that A is a proper subset of B " "A B

If A contains an element that is not in B, then A is not a subset of B (symbolized as A B).

Disjoint

The two sets A and B are disjoint if they have no elements in common. A B 

The two sets A and B are called also mutually exclusive.

3

Complement

The elements that are not in A are referred to as the complement of A, (Denoted by: /A ).

To represent a set A, shade the interior of A.  /A x x U and x A  

Intersection:

The intersection of set A and set B, denoted by A  B, is the set

consisting of all elements common to A and B.

 A B x x A and x B  

Union:

The union of set A and set B, denoted by A  B, is the set

consisting of all elements of A or B or both. (Or possibly in both)

 A B x x A or x B  

Cardinality

The cardinality of a set A is the number of elements in the set. Denoted by: ( )n A

Let:  , , ,S A B C  , ( ) 4n S  ,

Let:  X  , ( ) 1n X 

   1, ( ) 0n But n  

Formula for the Cardinality

For any sets X and Y:        n X Y n X n Y n X Y  

Operation within parentheses are performed first.

DE Morgan’s Laws

  / / /

X Y X Y

  / / /

X Y X Y

Ex:

1. Let        1, 2,3, 4,5,6,7,8,9 , 2, 4,6,8 , 1,3,5,7 , 5,7U A B C    a. Draw Venn diagram for: , ,A C B C A B

b. Find the cardinality of these sets: , ,A C B C A B

 , .. .. .. .of every set   

4

2. Given the sets A = {1, 2, 3} and B = {2, 4, 6}, find the following.

a. A  B (the intersection of A and B)

b. A  B (the union of A and B) Solution:

a. The intersection of two sets consists of those elements that are

common to both sets; therefore, we have: A  B = {1, 2, 3}  {2, 4, 6}= {2}

b. The union of two sets consists of all elements that are in at least one of the sets; therefore, we

have: A  B = {1, 2, 3}  {2, 4, 6}= {1, 2, 3, 4, 6}

5

2.2 Applications of Venn Diagrams

Objectives

Use Venn Diagrams to analyze the results of surveys

Develop and apply De Morgan’s Laws of complements.

Surveys are often used to divide people or objects into categories.

Because the categories sometimes overlap, people can fall into more than one category.

Venn diagrams and the formulas for cardinal numbers can help researchers organize the data.

When we draw two overlapping circles within a universal set, four regions are formed. Every element

of the universal set U is in exactly one of the following regions, as shown in the Figure:

I in neither A nor B

II in A and not in B

III in both A and B

IV in B and not in A

1. Of 350-sophomore class, 174-are male, 207-have cars, 65-of the male have cars. How many female do not have a car?

2. In a survey of 50-students, 18- taking Math. and 35-student are taking English. If 6-students were taking both, how many were not taking either?

3. A survey of 75-college students showed the following data: 40-had a car; 50-had a computer; 32-had a TV;

16-had a car and TV; 35-had a car and computer; 25-had a computer and a TV;

15-had all three.

How many students had none of the 3 items?

6

2.3 Introduction to combinatory

Objectives

 Develop and apply the fundamental principle of counting

 Develop and evaluate factorials

There are several counting methods:

a. Tree grams.

b. Fundamental Counting Principle.

c. Permutation.

d. Combination.

Fundamental Counting Principle

For a sequence of two events, the first event occur m ways and the second event occur n

ways, the events together can occur a total of m.n ways. (Gives the number of ways of

performing two or more tasks)

Tree Diagram

Factorial: For any whole number n, the factorial of n is defined by n!

n ! = n (n-1) (n-2) (n-3) … 3 . 2. 1 , also

0 ! = 1

1 ! = 1

 ! 1 !n n n 

Ex:

1. Evaluate:  6 2 !

2. Evaluate: 100!

98!

Ex:

Consider a club with five members, in how many ways could the club elects a president,

and secretary?

Using FCP: = (5) (4) (3) = 60

7

2.4 Permutations and Combinations

Objectives

 Develop and apply the Permutation Formula

 Develop and apply the Combination Formula

 Determine the number of Distinguishable Permutations.

Permutation Formula

The number of permutations, or arrangements, of r-elements selected without

replacement from n-elements, (r  n), denoted by, n r P is:

  n r

! P

!

n

n r 



Select without replacement, and order is important.

Combination Formula

The number of distinct combinations, or subsets, of r-elements selected without

replacement from n-elements, (r  n), denoted by, n r C is:

  n r

!

! !

n C

n r r 



Select without replacement, and order is not important.

Distinguishable Permutations of identical items

The number of distinguishable permutations (or arrangements) of n items in which x-

items are identical, y-items are identical, , z-items are identical, and so on, is !

! ! ! ! ...

n

x y z  

Pascal’s Triangle

Pascal's Triangle is an arithmetical triangle each new row is formed by adding the two

previous numbers; each row begins and ends with a one

R0 1

R1 1 1

R2 1 2 1

R3 1 3 3 1

R4 1 4 6 4 1

R5 1 5 10 10 5 1

D0 D1 D2 D3 D4 D5

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

Ex:

1. Consider a club of 7 - members, in how many ways could the club elects 3 – members committee?

2. Evaluate: 9 10 4 2

2,3,4 6 2 1

,        

             

3. Consider a club with five members, in how many ways could the club elects a president, and secretary?

8