MATH 3855 Carleton University Discrete Structure Problems Homework Please take a look at the question first to make sure you can do it well.Please take a l

MATH 3855 Carleton University Discrete Structure Problems Homework Please take a look at the question first to make sure you can do it well.Please take a look at the question first to make sure you can do it well. MATH 3855A/MATH 3825A/COMP 3805A Discrete Structures and
Applications
Winter 2020, take-home exam
Student Name:
Total Pages: 4
Student ID:
Total Marks: 130
Instruction: Students in Math3825A should do a total of 110 marks and Students in
Math3855A or Comp3805A should do a total of 120 marks.
1. Let us assume that we have 8 toys to be distributed among 10 kids. How many ways
can we distribute the toys if
(a) the toys are distinguishable? Justify your answers by using appropriate principle(s). [2 marks]
(b) the toys are identical (indistinguishable)? Justify your answers by using appropriate principle(s). [2 marks]
(c) no kids receives more than one toy and the toys are distinguishable? Justify your
answers by using appropriate principle(s). [2 marks]
(d) no kids receives more than one toy and the toys are indistinguishable? Justify
your answers by using appropriate principle(s). [2 marks]
2. (a) In how many ways can the letters in the word CARLETON be arranged so that
it contains either CA or AC as sub-words? [2 marks]
(b) In how many ways can the letters in the word CARLETON be arranged so that
each arrangement contains either CAR or ON as sub-words (or both)? [2 marks]
(c) In how many ways can the letters in the word CARLETON be arranged so that
no two letters from {L, E, T } are next to each other? [2 marks]
(d) Find the number of partitions of a set X = {a, b, c, d} into 3 parts. [2 marks]
(e) Find the number of surjections from X = {a, b, c, d} to Y = {1, 2, 3}. [2 marks]
(f) Find the number of 11-letter words that can be made from letters of word MATHEMATICS? [2 marks]
(g) In how many ways can the string abacadaef be arranged so that there are no
consecutive a’s? [2 marks]
(h) Find the number of ways to distribute 6 different objects into 4 numbered boxes
such that all four boxes are non-empty. [2 marks]
(i) Find the number of ways to distribute 6 different objects into 4 numbered boxes
such that each of box 1 and box 4 contains exactly 2 objects, each of box 2 and
box 3 contains 1 object. [2 marks]
(j) How many integer solutions can we find for the equation x + y + z + w = 11
subject to x ≥ 2, y ≥ 2, z ≥ 1, and w ≥ 0? [2 marks]
3. (a) Show that in a group of 6 people, there are either 3 either mutual friends or 3
mutual strangers. [3 marks]
(b) Find the smallest number of people in a group such that there is actually about
a probability of 50 that two of them have the same birthday. Justify. [3 marks]
4. (a) Use the sieve principle to find the number of integer solutions of the equation
x1 + x2 + x3 + x4 + x5 = 14, with 0 ≤ x1 , x2 , x3 , x4 , x5 ≤ 6. [7 marks]
(b) Use the sieve principle to find φ(240). Then verify your answer by using the
formula of φ(n) in terms of prime factors. [5 marks]
5. The following are independent. You must provide explicit numbers in the following
questions. [8 marks]
(a) Find the number of ways to partition a set of 6 different objects into 4 parts.
(b) Find the number of ways to partition the positive integer 6 into 4 parts.
(c) Find the number of ways to write 6 as a sum of a sequence of 4 strictly positive
integers (ordered).
(d) Find the number of ways to partition the positive integer 6.
6. The following questions are independent. [5 marks]
(a) Find the generating function for the sequence 1, 2, 4, 8, 16, · · · and express it in
the format of a rational function. [2 marks]
(b) Find the nth term of the sequence corresponding to the generating function x(1 +
x)/(1 − x)3 . [3 marks]
7. The following questions are independent.
(a) Solve the homogeneous recurrence relation an+2 − 2an+1 − 3an = 0, where n ≥ 0
and a0 = 1 and a1 = 1. [4 marks]
(b) Use the generating function method to solve the following recurrence relation [8
marks]
u0 = 1, un+1 − 2un = n3n (n ≥ 0).
8. Use the generating functions to find the number of partitions of 18 in which each part
is an odd prime number. Give explicitly all these partitions. [8 marks]
9. Find the generating functions for the sequences whose nth term are [6 marks]
(a) p(n| each part occurs at most three times).
(b) p(n| each part is a power of 2).
(c) p(n| each odd part occurs at most four times). (This means that each odd part
(a part that is an odd number) can only occur at most four times, but each even
part (a part that is an even number) can be repeated for any number of times.)
10. Write down the generating function for the sequence whose nth term is
p(n | no even number occurs more than once as a part).
Hence show this number is equal to p(n | each part occurs at most 3 times). [5 marks]
11. The following questions are independent.
(a) Explain that any complete graph Kn contains a Hamiltonian cycle. Does the
graph G with degree sequence 4, 2, 2, 2, 2 contain a Hamiltonian cycle? Why? [4
marks]
(b) Find a necessary and sufficient condition on n such that the complete graph Kn
contains an Eulerian walk? [2 marks]
(c) Find a necessary and sufficient condition on n such that the complete graph Kn
contains a closed Eulerian walk? [2 marks]
(d) Find a necessary and sufficient condition on m, n such that the complete bipartite
graph Km,n contains a closed Eulerian walk? [2 marks]
(e) Find the chromatic number of the cycle graphs C5 and C6 respectively. [2 marks]
(f) Is the cycle graph C5 (with 5 vertices) bipartite? Is the cycle graph C6 (with 6
vertices) bipartite? [2 marks]
(g) Is graph G planar for each of the following graphs? If yes, show Euler’s formula
about the number of vertices, edges, and regions in G. If not, briefly explain why
G is non-planar? [6 marks]
(a) K10 .
(b) K2,5 (c) K5,5 .
12. The following questions are independent.
(a) Find the minimum distance δ for each of the following codes. [6 marks]
i. {0000, 1100, 1010, 1001, 0110, 0101, 0011, 1111} in V 4 .
ii. {10000, 01010, 00001} in V 5 .
iii. {000000, 101010, 010101} in V 6 .
In each case, state the number of error which can be detected and corrected.
(b) Given any word x in V n let S2 (x) denote the the set of words which can be
obtained by making not more than two errors in x. Show that
1
|S2 (x)| = (n2 + n + 2).
2
Deduce that if E is any code (not necessary linear) of length 8 which will correct
two errors, then |E| ≤ 6. [4 marks]
(c) What is the maximum dimension of a linear code of length 8 which will correct
two errors? Construct such a code. [4 marks]
(d) What are these parameters length n, dimension k, minimum distance δ for the
linear code associated with the check matrix


1 1 0 1 0 0 1
 0 0 0 1 1 0 1 


 1 0 1 1 0 0 1 
0 0 0 0 0 1 1
Write down all codewords belonging to this linear code. How many errors can C
detect? How many errors can C correct? If the word 1110001 is received, and
only one error has been made, what is the intended codeword? [6 marks]

Purchase answer to see full
attachment