99年國立中山大學資工所離散數學

Determine the number of integer solutions of the following equations:

1.

x₁ + x₂ + x₃ + x₄ = 17 where xi ≥ 0 for i = 1, 2, 3, and 4.

Determine the number of integer solutions of the following equations:

2.

x₁ + x₂ + x₃ + x₄ + x₅ = 17 where xi > 0 for i = 1, 2, 3, 4, and 5.

Determine the number of integer solutions of the following equations:

3.

x₁ + x₂ + 9x₃ + x₄ + x₅ = 19 where x_i ≥ 0 for i = 1, 2, 3, 4, and 5.

Let Σ be an alphabet.

4.

If Σ = {1, 2, 3, 4}, what is |Σ³|?

Let Σ be an alphabet.

5.

If Σ = {a, b, c, d, e}, how many strings in Σ^* have length at most 5?

Let Σ be an alphabet.

6.

If Σ = {ab, c, de}, what is the length of the string abcde?

7.

Find the coefficient of x⁷² in (x⁶ + x⁷ + x⁸ + ...)¹⁰.

Let A be a set with |A| = n, and let R be a binary relation on A that is reflexive and antisymmetric.

8.

What is the maximum value for |R|?

Let A be a set with |A| = n, and let R be a binary relation on A that is reflexive and antisymmetric.

9.

How many antisymmetric relations can have this size?

Let A be a set with |A| = n.

10.

If n = 5, how many binary relations on A are symmetric but not reflexive?(Your final answer should be an integer, not a formula.)

Let A be a set with |A| = n.

11.

If n = 4, how many binary relations on A are neither reflexive nor symmetric?(Your final answer should be an integer, not a formula.)

12.

Use Chinese Remainder Theorem to find a simultaneous solution for the system of three congruences: x ≡ 5 (mod 15), x ≡ 4 (mod 14), x ≡ 0 (mod 13) where 2500 < x < 4500.

13.

How many units are there in Z₂₀₀?

14.

15.

Let G = (V, E) be a connected planar graph or multigraph with |V| = 2000 and |E| = 2500. What is the number of regions in the plane determined by a planar embedding (or, depiction) of G.

Solve the following recurrence relations:

16.

a_n − 5a_n−1 − 6a_n−2 = 0, n ≥ 2, a₀ = 0, a₁ = 1.

Solve the following recurrence relations:

17.

a_n+1 − 2a_n = 2ⁿ, n ≥ 0, a₀ = 2.