Discrete Mathematics and Graph Theory
离散数学与图论练习代写 Practice Class 1 1.Complete the following definitions: (a) A function f : A → B is injective if ________________ (b) A function f : A → B is
Practice Class 1
1.Complete the following definitions:
(a) A function f : A → B is injective if ________________
(b) A function f : A → B is surjective if ________________
(c) A function f : A → B is bijective if ________________
2.Complete the following principles:
(a) (Difference Principle) If A is a subset of the finite set X, then ________________
(b) (Pigeonhole Principle) If f : X → Y is a function between nonempty finite sets, then there is some y ∈ Y such that ________________
3.Find a function f : N → N which is
(a) injective but not surjective.
(b) surjective but not injective.
(c) bijective and has the property that f(n) /= n for all n.
4.Suppose there are 135 students enrolled in a class. From that information alone, you can deduce that:
(a) there must be at least _______ of them who were born on the same day of the week;
(b) there must be at least _______ whose surnames begin with the same letter;
(c) there must be at least _______ of them who are left-handed;
(d) there must be at least _______ days this year which are not the birthday of any of them.
5.Count the subsets of the set {A,B,C,D,E,F,G}: 离散数学与图论练习代写
(a) which contain D
(b) which do not contain C
(c) which contain exactly 2 elements
6.If a function f : A → B is bijective, we define its inverse as the function f−1: B → A by the rule f−1(y) = x if y = f(x). For each of the following functions determine whether it is bijective. If so, write a formula for its inverse.
(a) f : R → R, f(x) = x2 + 1;
(b) f : R → R, f(x) = x3 + 1;
(c) f : N → N, f(n) = n3 + 1;
(d) f : R → Z, f(x) = ⌊x⌋;
7.For each of the following statements, write T for true or F for false.
(a) The Tower of Hanoi number hn, in binary, consists of n ones.
(b) Among any 36 people, there are 6 who were born on Monday.
(c) If |X| > |Y |, any function f : X → Y must be surjective.
(d) If |X| < |Y |, no function f : X → Y can be surjective.
(e) If |X| > |Y |, no function f : X → Y can be injective.
(f) If |X| < |Y |, any function f : X → Y must be injective.
(g) Any injective function f : X → X is bijective.
Practice Class 2 离散数学与图论练习代写
1.Complete the table giving the number of ways to make an ordered selection of k
things from n possibilities:
repetition allowed _______
repetition not allowed _______
2.Count the four-digit numbers (positive integers, first digit nonzero)
(a) which are neither 2069 nor 2969
(b) which have no repeated digits
(c) which are the same when reversed
(d) which are divisible by 5
(e) which are divisible by 7
(f) which are odd and have no repeated digits
(g) which are even and have no repeated digits
3.A restaurant offers 3- and 4-course meals. The courses must be chosen from entrées (8 possible), soups (4), mains (11) and desserts (7). At most one of each course may be chosen.
(a) How many possible 4-course meals are there?
(b) How many possible 3-course meals are there?
4.A regular dodecahedron has 12 faces, all of which are pentagons. At each vertex, three faces meet. 离散数学与图论练习代写
(a) The total number of edges is _______
(b) The total number of vertices is _______
5.How many ways can you distribute 4 different packages among 8 people A, B, C, D, E, F, G and H if:
(a) there are no restrictions
(b) the packages must go to different people
(c) everyone gets two packages or none
(d) all the packages must be shared between two persons
(e) all the packages must go to the same person
6.For each of the following statements, write T for true or F for false.
(a) The number of diagonals of a regular 10-gon is 70.
(b) The number of surjective functions from a set of size7 to another set of size 7 is 7!.
(c) The number of injective functions from a set of size 7 to another set of size 7 is 7!.
(d) The number of permutations of a set with n elements is 2n .
(e) The number of five-letter strings starting with A is 264 .
(f) Thenumberofsuchstringswhichhavenolettersrepeatedis26(4).
(g) There are 7! ways to group 8 people into 4 pairs.
Practice Class 3 离散数学与图论练习代写
1.Complete the Inclusion/Exclusion formulas:
(a) |A ∪ B| = _______
(b) |A ∪ B∪ C| = _______
2.Complete the table giving the number of ways to make an unordered selection of
k things from n possibilities:
repetition allowed _______
repetition not allowed _______
3.Count the subsets of the set {A,B,C,D,E,F,G}:
(a) which have 3 elements
(b) which have 3 elements and contain C
(c) whose intersection with {A,B,C,D} has size 2
4.How many ways are there to select, from a barrel of 45 numbered balls:
(a) six balls, and then colour one of them red
(b) one ball to colour red, and then five more balls
5.Count the four-digit numbers
(a) whose digits are two 1’s and two 2’s in some order
(b) whose digits are two 1’s, a 2, and a 3 in someorder
(c) whose digits are a 1, a 3, a 7, and a 0 in someorder
(d) whose digits decrease strictly from left to right
(e) whose digits increase strictly from left to right
6.Suppose A, B,C are subsets of a finite set X such that 离散数学与图论练习代写
|A| = 30, |B| = 40, |C| = 20, |A ∪ B| = 60, |A ∩ C| = 5, |B ∩ C| = 0.
(a) Find|A∪C|.
(b) Find|A∩B|.
(c) Find |A ∪ B∪ C|.
7.(It may help to know that S(7, 3) = 301.) How many ways can you distribute 7
packages among three people A, B, and C if:
(a) there are no restrictions
(b) the packages are all different andno-one must miss out
(c) the packages are all different and exactly one person must miss out
(d) the packages are all different and person A mustget three, person B and person C two each
(e) the packages are indistinguishable
(f) the packages are indistinguishable andno-one must miss out
(g) the packages are indistinguishable and exactly one person must miss out
(h) the packages are indistinguishable and person A must get three, person B and person C two each
8.For each of the following statements, write T for true or F for false.
(a) The product of any 5 consecutive integers is divisible by 120.
(b) There are 20 ways to split 6 people into two teams of 3.
