Discrete Math : Probability, Functional Relations, Partitions and Primary Keys

Please see the attached file for the fully formatted problems. Name ________________________________ SSN __________________ CMSC 203 - Homework Assignment 4 - Due December 9, 2003 1. (a) Suppose I have a cooler full of cans of Coke, Pepsi, Sprite, Mountain Dew, Dr. Pepper, and Slice sodas. How many distinct ways can I line these up on a table if the cooler contains 5 of each type of soda? (b) Suppose I have a large collection of coins consisting of Pennies, Nickels, Dimes, Quarters, Half-Dollars, and Dollars. How many ways can I select distinct combinations of 50 coins if I must have 5 of each type in each collection? Name ________________________________ SSN __________________ ... click for more

Equivalence Classes

Let P, P' be equivalence relations on a set A. Let n, n' be the number of equivalence classes of p, p', respectively. A) define an equivalence relation p'' as follows: xp''y <=> (xpy) and (xp'y) what is the least number of equivalence classes of p''? What is the greatest number of equivalence classes of p''? B)define an equivalence relation p''' as follows: xp'''y <=> (xpy) or (xp'y) what is the least number of equivalence classes of p'''? What is the greatest number of equivalence classes of p'''?

Equivalence Relations and Classes

Let L be a subset of {a,b}* Define a relation R (R sub L) on S* as follows: L for All of x, y is a member of S*, (x,y) are members of R if for all of z, xz are members of L iff yz are members of L A) Show that R is an equivalence relation B) Suppose L={a^i b^i where i >= 0} What can you say about the index of R (number of classes)? is it finite or infinite? Show some classes and elements in these classes to justify your answer? c) Suppose L={a^i b^j where i,j >= 0} What can you say about the index of R (number of classes)? is it finite or infinite? Show some classes and elements in these classes to justify your answer? D) Suppose L={a^i b^3i where... click for more

Set Theory : Proof

(A union B)* = (A*B*)* = (A* union B*)*

Graph Theory.

Show that it is impossible for an odd number of people in a group to each know exactly 2k+1 other people in the group for any integer k.