离散数学问题代写 Discrete  Mathematics代写

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 P_G(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 P_L(k) = k(k −1)ⁿ⁻¹.

b）Let C_nbe the cyclic graph with n Find P_C3(k).

c）Show that for n > 3, P_Cn (k) satis es therecurrence:

P_Cn (k) = k(k − 1)ⁿ⁻¹ − P_Cn−1 (k) .

d）Solve the recurrence above to nd a short expression forP_Cn (k).

 

Question 4 (20 marks)  离散数学问题代写

In this problem, we investigate the edge-chromatic number χ^E(K_n) of complete graphs K_n.

a）Show that coloring the edge ij with color i + j (mod n) gives a valid edge coloring ofK_n.

b）Show that if n is odd, then χ^E(K_n) =n.

c）Show that if n is even, then χ^E(K_n) = n −1.

Hint: K_n is K_n−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 G_RY or the Green-Blue subgraph G_ttB…

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代写 论文代写 写手招聘 英国留学生代写