111年 - 111 教育部公費留學考試試題：離散數學#125727

1. [10%] How many subsets of size 5 from a set that contains n elements?

2. [10%] We flip a coin for 15 times and obtain a result of x times of coin facing up and y times of coin facing down. What is the most likely outcome of (x, y)? Apparently, we have x + y = 15. What is the probability to have such outcome (x, y)?

3. [15%] Which series is bigger, ? We have:

4. [15%] If both a + b and ab are even, then both a and b are even. Prove or disprove the statement.

5. [15%] Solve the recurrence equation given by:
a_n+2 - 2a_n + a_n+1 = 0, a₀ = 0, a₁ = 1.

6. [15%] Which of the following graphs, K₆ (complete graph with 6 vertices) or K₇ (complete graph with 7 vertices) has closed Euler walk? Explain your answer as clear as possible. That is, in closed Euler walk, we allow each edge to be visited exactly once, and the initial vertex and ending vertex are the same. Can we modify the graph(s) to make it/them possible to contain a closed Euler walk?

Def 1.
A tree consists of a root, and zero or more subtrees T₁, T₂, ..., T_k. Also, there is an edge from the root to the rootof each subtree.

Now someone modifies the definition and give the following alternative one:
Def 2.
A tree consists of a root, and one or more subtrees T₁, T₂,..., T_k. Also, there is an edge from the root to the root of each subtree.
Can you describe what will happen if we choose the second one as the definition instead? What trees can be generated by the two definitions?