99年國立交通大學資訊聯招離散數學

1.

Let Y be a set. The notation 2^Y denotes the set of all subsets of Y. For example, 2^{α,β} = {{}, {α}, {β }, {α, β }}. Let U, V be two sets. The notation U × V denotes the set {(a, b) | a ∈ U, b ∈ V}. Let X be a non-empty set. A subset S of X × X is symmetric if and only if it satisfies the following condition:
              if (a, b) ∈ S then (b, a) ∈ S, for all elements a, b ∈ X.
Let P = {1, 2, 3} and Q = {1, 2}. How many subsets of (2_P × Q) × (2^P × Q) are symmetric?

2.

Let Fib(n) denote the predicate "n is a Fibonacci number" and Prime(n) denote the predicate "n is a prime". Please translate the following statement into a formula in predicate logic: "There is a Fibonacci number that is a prime."

3.

What is the remainder of 2⁹⁹ divided by 33?

4.

Consider the arithmetic sequence: 1, 4, 7, …, 100. Find the least k such that among any k distinct numbers randomly chosen from the above arithmetic sequence, there are two whose sum is exactly 104.

5.

Given 9 left parentheses and 9 right parentheses, how many properly nested sequence of parentheses can be formed? A sequence of left and right parentheses is properly nested if (1) the number of left parentheses in any prefix of the sequence is no less than the number of right parentheses and (2) the number of left parentheses is equal to the number of right parentheses in the whole sequence. For example, "[ [ [ ] [ ] [ [ ] ] ] [ [ ] ] ]" is properly nested whereas "[ [ ] ] ] [ [ ]" is not. Intuitively, the usual arithmetical expressions, such as ((a + b) ∗ (c − d)), are all properly nested.

An m-ary tree is a rooted tree each of whose internal vertices has no more than m children. The height of a rooted tree is the largest path length from the root to any vertex. Let h denote the height of an m-ary tree.

6.

The maximal number of leaves in an m-ary tree of height h.

An m-ary tree is a rooted tree each of whose internal vertices has no more than m children. The height of a rooted tree is the largest path length from the root to any vertex. Let h denote the height of an m-ary tree.

7.

Let a_h denote the maximal number of vertices in an m-ary tree of height h. Give a recurrence relation of a_h and also an initial condition.

An m-ary tree is a rooted tree each of whose internal vertices has no more than m children. The height of a rooted tree is the largest path length from the root to any vertex. Let h denote the height of an m-ary tree.

8.

If m = 2, give an explicit form of a_h.

9.

Let R = {(a, b), (b, c), (c, c)} be a relation on set {a, b, c}. What is the reflexive closure of R?

10.

Let x₁ ∈ {1, 3, 5}, x₂ ∈ {1, 2, 3}, and x₃ ∈ {0, 1, 2, 3, …}, and an be the number of solutions of x₁ + x₂ + x₃ = n. Give the generating function g(x) of an.

11.

Let e, v, and r, respectively, denote the number of edges, vertices, and regions of a planar representation of a connected simple planar graph. Please give Euler's formula of planar graphs.

12.

Give the binary tree represent of the equation (x + (y/z)) + 1.

13.

Consider a connected graph with 10 vertices. If all its edges are with weight 1, what is the weight of its minimum spanning tree?

Solve the linear recurrence relation a_n = 5a_n−1 − 6a_n−2 + 2n + 1.

14.

Solve the linear recurrence relation a_n = 5a_n−1 − 6a_n−2 + 2n + 1.

15.

Solve the linear recurrence relation a_n = 5a_n−1 − 6a_n−2 + 2n + 1.

16.