Discrete Mathematics
Assignment 2
离散数学问题代写 In how many ways can the numbers 0 through (2n – 1) be arranged in 2 rows of length n in such a way such that ···
Question 1 (20 marks)
In how many ways can the numbers 0 through (2n – 1) be arranged in 2 rows of length n in such a way such that each row and each column is increasing? Examples (with n = 5):
and
Hint: Catalan Numbers.
Question 2 (20 marks) 离散数学问题代写
A periodic point of a function f : X → X is a point x∈ X for which there is a number p (a period ) with f p(x) = x (f p denotes the composite (f º. . .º f ) of f with itself p times ）. A xpoint is a periodic point with minimal period p = 1, that is, a point x∈ X such that f (x) = x.
For X ={ 1, 2, . . . n}, count the number of functions f : X→ X such that each periodic point is a xpoint.
Hint: What kind of vertebrate do you get when you apply Joyal’s bijection on a function like this?
Question 3 (20 marks) 离散数学问题代写
The chromatic polynomial of a graph G is the function PG(k) that gives the number of ways to color the vertices of G using k colors, such that no two adjacent vertices have the same color.
a）If L is a path (linear graph) with n vertices, show that PL(k) = k(k −1)n−1.
b）Let Cnbe the cyclic graph with n Find PC3(k).
c）Show that for n > 3, PCn (k) satis es therecurrence:
PCn (k) = k(k − 1)n−1 − PCn−1 (k) .
d）Solve the recurrence above to nd a short expression forPCn (k).
Question 4 (20 marks) 离散数学问题代写
In this problem, we investigate the edge-chromatic number χE(Kn) of complete graphs Kn.
a）Show that coloring the edge ij with color i + j (mod n) gives a valid edge coloring ofKn.
b）Show that if n is odd, then χE(Kn) =n.
c）Show that if n is even, then χE(Kn) = n −1.
Hint: Kn is Kn−1 with one extra vertex, and n − 1 is odd…
Question 5 (20 marks) 离散数学问题代写
The goal of this problem is to prove some of the many cases of the 4-colors theorem. Let our four colors be: red, blue, green and yellow.
Assume that the 4-colors theorem is proven for all planar graphs with less than n vertices and that G is a graph with n vertices that contains the following subgraph.
We remove the four vertices w, x, y, z in the middle, resulting in a smaller planar graph, and let the induction hypothesis give us a coloring of the six outer vertices a, b, c, d, e, f . We call such a coloring a con guration. Then…
a）Suppose that the induction hypothesis gave us the following con guration. Conclude that G is4-colorable.
b）Suppose instead that we have the following con guration. Use the Kempe-Chain argument to modify the coloring on G so that you can complete it and conclude that G is4-colorable.
Hint: Consider the possible connected components of Red-Yellow subgraph GRY or the Green-Blue subgraph GttB…
c）Now, say that the induction hypothesis gave us the following con guration. Use another Kempe-Chain argument to modify the coloring in order to end up with the coloringin part (a) or (b). Deduce that G is 4-colorable again in that case.
Note: Now you have a fairly good idea of how the 4-colors theorem was originally proved. The idea is to build a tree (actually, a forest) of con gurations that are reducible to one another by a Kempe-Chain argument, so that the leaves of this forest can be completed directly like in (a). The issue is that the forest built by Appel and Haken’s program has 1936 nodes rather than just the 3 nodes you just checked, which is why the help of a computer was required.
其他代写：英国代写 北美作业代写 homework代写 作业加急 program代写 project代写 assignment代写 加拿大代写 python代写 report代写 paper代写 essay作业代写 作业代写 java代写 matlab代写 finance代写
合作平台：essay代写 论文代写 写手招聘 英国留学生代写
