Induction and Set theory : Addition Principle, Union and Pairwise Disjoint Finite Sets

Proposition 10.2.1: (the addition principle) Suppose that X and Y are disjoint finite sets. Then X U Y is finite and |X U Y| = |X| + |Y|. Corollary 10.2.2: For a positive integer n, suppose that X1, X2….,Xn is a collection of n pairwise disjoint finite sets (i.e. i does not = j => Xi Xj = empty set) Then X1 U X2 ...continues

Set Theory Proofs : Addition Principle

Let X and Y be finite sets. a) Suppose the X C Y and |X| = |Y|. Use 10.2.1 to prove X =Y. b)... Theorem 10.2.1 (The adddition principle): Suppose that X and Y are disjoint finite sets. Then X U Y is finite and | X U Y| = |X| + |Y|. Please see the attached file for the fully formatted problems.

Set Theory Proof : Inclusion-Exclusion Principle

3. This exercise is about the inclusion-exclusion principle. a) Let X and Y be finite ts and suppose that |X| = 11, |Y| = 6, and |X∩Y| =4. Find |XUY|. b) Suppose that U is a finite universal set. If |U| = 21, |XUY| = 11. |X| = 4 and |Y|= 10. find |XcUYc|. c) Each tile in a collection of 19 is a square or a triangle and ...continues

Proof problem

Need help in determining the following proof. (See attached file for full problem description) --- Thm 11.1.2 (the pigeonhole principle): Suppose that f:X Y is a function between non-empty finite sets such that |X| > |Y|. Then f is not an injection, i.e. there exist distinct elements x1 and x2 E (epsilon) X ...continues

Set Theory : Pairwise Disjoint Finite Sets and Addition Principle

Proposition 10.2.1: (the addition principle) Suppose that X and Y are disjoint finite sets. Then X U Y is finite and |X UY| = |X| + |Y|. Corollary 10.2.2: For a positive integer n, suppose that X1, X2….,Xn is a collection of n pairwise disjoint finite sets (i.e. i does not = j => Xi Xj = empty set) Then X1 U X2 U ...continues

Proving composite

Prove, using the given method, that 561 is composite. (See attached file for full problem description)

Pollard-Rho

Use the Pollard-Rho method... (See attached file for full problem description)

Polynomial division

What is the remainder... (See attached file for full problem description)

Encoding

Encoding problem (See attached file for full problem description)

Binomial Coefficients : Forming Committees

Binomial Coefficients must be computed. Comittees of 5 individuals ale to be formed from 8. a) How many such committees are there? b) How many committees of 5 can be formed from 8, given that two particular individuals are to be included on the committee? c) How many committees of 5 can be formed from 8, given that two parti ...continues