0

0

1504 days ago,
534 views

PowerPoint PPT Presentation
Including Elements Disjoint Sets. Hypothesis: Let {A1,

Tallying Elements of Disjoint Sets: The Addition Rule Lecture 29 Section 6.3 Mon, Mar 19, 2007

Counting Elements in Disjoint Sets Theorem: Let { A 1 , … , A n } be a segment of a set A . At that point |A | = |A 1 | + … + |A n |. Culmination: Let { A 1 , … , A n } be a gathering of pairwise disjoint limited sets. At that point |A 1 … A n | = |A 1 | + … + |A n |.

Counting Elements in Subsets Theorem: Let An and B be limited sets with B A . At that point |A – B | = |A | – |B |. Verification: { B , A – B } is a parcel of A . In this way, |B | + |A – B | = |A |. In this way, |A – B | = |A | – |B |.

Counting Elements in Unions of Sets Theorem: Let An and B be any limited sets. At that point |A B | = |A | + |B | – |A B |. Verification: One can check that ( A B ) – B = A – ( A B ). Moreover, B A B and A B A . In this way, |A B | – |B | = |A | – |A B |. In this way, |A B | = |A | + |B | – |A B |.

Putnam Problem A-1 (1983) what number positive whole numbers n are there to such an extent that n is a correct divisor of no less than one of the numbers 10 40 , 20 30 ? Let A = { n | n partitions 10 40 }. Let B = { n | n separates 20 30 }. At that point |A B | = |A | + |B | – |A B |.

Putnam Problem A-1 (1983) Prime factorization: 10 40 = 2 40 5 40 . Hence, n | 10 40 if and just if n = 2 a 5 b where 0 a 40 and 0 b 40. There are 41 41 = 1681 such numbers. Also, 20 30 = 2 60 5 30 , so there are 61 31 = 1891 divisors of 20 30 .

Putnam Problem A-1 (1983) Finally, a number is in A B on the off chance that it partitions both 10 40 and 20 30 . That implies that it partitions the gcd of 10 40 and 20 30 . The gcd of 2 40 5 40 and 2 60 5 30 is 2 40 5 30 . Thusly, there are 41 31 = 1271 such numbers.

Putnam Problem A-1 (1983) Thus, 1681 + 1891 – 1271 = 2301 numbers partition either 10 40 or 20 30 .

Number of Elements in the Union of Three Sets Theorem: Let A , B , and C be any three limited sets. At that point |A B C | = |A | + |B | + |C | – |A B | – |A C | – |B C | + |A B C |. Include sets each one in turn, Subtract sets two at any given moment, Add sets three at any given moment.

Number of Elements in the Union of Three Sets Theorem: Let A , B , and C be any three limited sets. At that point |A B C | = |A | + |B | + |C | – |A B | – |A C | – |B C | + |A B C |. Include sets each one in turn, Subtract sets two at any given moment, Add sets three at any given moment.

Number of Elements in the Union of Three Sets Theorem: Let A , B , and C be any three limited sets. At that point |A B C | = |A | + |B | + |C | – |A B | – |A C | – |B C | + |A B C |. Include sets each one in turn, Subtract sets two at any given moment, Add sets three at any given moment.

Proof, proceeded with Proof: |A B C | = |A B | + |C | – | ( A B ) C |.

Proof, proceeded with Proof: |A B C | = |A B | + |C | – | ( A B ) C | = |A | + |B | – |A B | + |C | – | ( A B ) C |.

Proof, proceeded with Proof: |A B C | = |A B | + |C | – | ( A B ) C | = |A | + |B | – |A B | + |C | – | ( A B ) C | = |A | + |B | – |A B | + |C | – | ( A C ) ( B C )| .

Proof, proceeded with Proof: |A B C | = |A B | + |C | – | ( A B ) C | = |A | + |B | – |A B | + |C | – | ( A B ) C | = |A | + |B | – |A B | + |C | – | ( A C ) ( B C )| = |A | + |B | – |A B | + |C | – |A C | – |B C | + | ( A C ) ( B C )| .

Proof, proceeded with Proof: |A B C | = |A B | + |C | – | ( A B ) C | = |A | + |B | – |A B | + |C | – | ( A B ) C | = |A | + |B | – |A B | + |C | – | ( A C ) ( B C )| = |A | + |B | – |A B | + |C | – |A C | – |B C | + | ( A C ) ( B C )| = |A | + |B | – |A B | + |C | – |A C | – |B C | + |A B C | .

Proof, proceeded with Proof: |A B C | = |A B | + |C | – | ( A B ) C | = |A | + |B | – |A B | + |C | – | ( A B ) C | = |A | + |B | – |A B | + |C | – | ( A C ) ( B C )| = |A | + |B | – |A B | + |C | – |A C | – |B C | + | ( A C ) ( B C )| = |A | + |B | – |A B | + |C | – |A C | – |B C | + |A B C |. = |A | + |B | + |C | – |A B | – |A C | – |B C | + |A B C |.

Proof, proceeded with Proof: |A B C | = |A B | + |C | – | ( A B ) C | = | A | + |B | – |A B | + |C | – | ( A B ) C | = |A | + |B | – |A B | + |C | – | ( A C ) ( B C )| = |A | + |B | – |A B | + |C | – |A C | – |B C | + | ( A C ) ( B C )| = |A | + |B | – |A B | + |C | – |A C | – |B C | + |A B C |. = |A | + |B | + |C | – |A B | – |A C | – |B C | + |A B C |.

The Inclusion/Exclusion Rule Theorem: Let A 1 , … , A n be limited sets. At that point |A 1 … A n | = i |A i | – i j > i |A i A j | + i j > i k > j |A i A j A k | : |A 1 … A n |.

The Inclusion/Exclusion Rule The Inclusion/Exclusion Rule can be demonstrated by enlistment.

Number of Elements in the Union of Four Sets Let U be the arrangement of all sets of particular cards from a deck of 52 playing cards. What number of sets are there in which no less than one of the two cards is dark or a face card?

Number of Elements in the Union of Four Sets Let A = all sets where 1 st card is dark. B = all sets where 1 st card is a face card. C = all sets where 2 nd card is dark. D = all sets where 2 nd card is a face card. Locate the quantity of components in | A B C D |.

Number of Elements in the Union of Four Sets what number sets are there in which no less than one of the two cards is dark or a face card?

A B E D C The Inclusion/Exclusion Rule Suppose five sets converge as showed in the accompanying Venn graph.

A B E D C The Inclusion/Exclusion Rule State the condition of the consideration/rejection administer for these sets.

D A B C The Inclusion/Exclusion Rule Do the same for these sets.

SPONSORS

No comments found.

SPONSORS

SPONSORS