Learn more about our help with Assignments: Discrete Math
Search & Filtering
Discrete Mathematics
Mathematical Induction. Suppose that you know that a cyclist rides the first kilometre in an infinitely long road, and that if this cyclist rides one kilometre, then she continues and rides the next kilometre. Prove that this cyclist will ride every kilometre in that infinite road.
Discrete Mathematics
Explain 1. Game Tree 2. Decision Tree
Discrete Mathematics
Find the number of equivalence relations that can be defined on a set of 6 elements.
Discrete Mathematics
a) Obtain the Ferrar graph of the partition 8+7+6+5+5+3+2+1. Find the conjugate
partition. Is the partition self conjugate?
b) For the graph in Fig. Fig. 2 on the following page find a minimal colouring.
c) Is Petersen graph bipartite? Give reasons for your answer.
partition. Is the partition self conjugate?
b) For the graph in Fig. Fig. 2 on the following page find a minimal colouring.
c) Is Petersen graph bipartite? Give reasons for your answer.
Discrete Mathematics
A) Find the generating function of the recurrence
an = 4an−1 −4an−2 +1
with initial conditions a0 = 1, a1 = 1.
B) Express 3x4 +2x3 −2x2 +x in terms of [x]4, [x]3, [x]2 and [x]
an = 4an−1 −4an−2 +1
with initial conditions a0 = 1, a1 = 1.
B) Express 3x4 +2x3 −2x2 +x in terms of [x]4, [x]3, [x]2 and [x]
Discrete Mathematics
a) Let A be an 8×8 Boolean matrix (i.e. every entry is 0 or 1). If the sum of the entries in A is
51, prove that there is a row i and a column j in A such that the entries in row i and in column j
add up to more than 13. Further, show that there are at least 4 such pairs of rows and
columns.
b) If a planar graph has the degree sequence {2,2,3,3,4,4,4}, how many faces will it have? Draw
a planar graph with this degree sequence and number the faces to check your answer.
c) Give the order and the degree of the recurrence
a
2
n+2 = a
2
n +2an +4
Is the recurrence homogeneous?
51, prove that there is a row i and a column j in A such that the entries in row i and in column j
add up to more than 13. Further, show that there are at least 4 such pairs of rows and
columns.
b) If a planar graph has the degree sequence {2,2,3,3,4,4,4}, how many faces will it have? Draw
a planar graph with this degree sequence and number the faces to check your answer.
c) Give the order and the degree of the recurrence
a
2
n+2 = a
2
n +2an +4
Is the recurrence homogeneous?
Discrete Mathematics
a) Make a table of the values of the Boolean function
f(x1,x2,x3) = x2 ⊕(x1 ∧x3)
Write the function in DNF using the table.
b) Find the general form of the solution to a linear homogeneous recurrence with constant
coefficients for which the characteristic roots are 1 with multiplicity 1, −2 with multiplicity 2
and 2 with multiplicity 3. The relation also has a non-homogeneous part which is a linear
combination of n2n
and (−2)
n
f(x1,x2,x3) = x2 ⊕(x1 ∧x3)
Write the function in DNF using the table.
b) Find the general form of the solution to a linear homogeneous recurrence with constant
coefficients for which the characteristic roots are 1 with multiplicity 1, −2 with multiplicity 2
and 2 with multiplicity 3. The relation also has a non-homogeneous part which is a linear
combination of n2n
and (−2)
n
Discrete Mathematics
a) Let Fn denote the nth Fibonacci number. Show by induction that every natural number is
expressible as a sum
Fn1 +Fn2 +···+Fnk
where ni −ni+1 > 1 for each i ≥ 1.
b) Find the number of ways of tying up 7 different books into 4 bundles if the order of the books
in the bundles does not matter.
c) Give examples of trivially true and vacuously true statements.
expressible as a sum
Fn1 +Fn2 +···+Fnk
where ni −ni+1 > 1 for each i ≥ 1.
b) Find the number of ways of tying up 7 different books into 4 bundles if the order of the books
in the bundles does not matter.
c) Give examples of trivially true and vacuously true statements.
Discrete Mathematics
a) Which of the following sentences are statements? Give reasons for your answer.
i) Are the buses running today?
ii) What a pleasant weather!
iii) x2 +1 = 0 for a real value of x.
iv) Every odd number is a prime.
b) Let t(n) denote the number of ways in which 2n tennis players can be paired to play n matches.
Determine a recurrence equation for the sequence t(n).
c) Show that any tree with exactly two vertices of degree 1 is a path.
i) Are the buses running today?
ii) What a pleasant weather!
iii) x2 +1 = 0 for a real value of x.
iv) Every odd number is a prime.
b) Let t(n) denote the number of ways in which 2n tennis players can be paired to play n matches.
Determine a recurrence equation for the sequence t(n).
c) Show that any tree with exactly two vertices of degree 1 is a path.
Discrete Mathematics
Which of the following statements are true and which are false? Give reasons for your answer.
i) (∼ p∨q) and (p ← q) are logically equivalent.
ii) (m+n)! > m!+n! for m, n any positive integers.
iii) The number of distributions of m indistinguishable objects into n distinguishable containers is
the same as the number of non-negative integral solutions of the equation
x1 +x2 +...+xn = m.
iv) Sn, the number of subsets of a set with n elements, satisfies a second order linear homogeneous
recurrence equation with constant coefficients.
v) K3,4 is Hamiltonian.
i) (∼ p∨q) and (p ← q) are logically equivalent.
ii) (m+n)! > m!+n! for m, n any positive integers.
iii) The number of distributions of m indistinguishable objects into n distinguishable containers is
the same as the number of non-negative integral solutions of the equation
x1 +x2 +...+xn = m.
iv) Sn, the number of subsets of a set with n elements, satisfies a second order linear homogeneous
recurrence equation with constant coefficients.
v) K3,4 is Hamiltonian.
