99年國立高雄大學資工所離散數學

What is the number of ways to seat 7 people at 5 circular tables with at least one person at each table if

1.

The table is labeled?

What is the number of ways to seat 7 people at 5 circular tables with at least one person at each table if

2.

The table is not distinguished?

3.

Determine whether the following argument form is valid. Justify your answer.
p ∨ q
q → r
∴ ¬r → p

4.

Show that ∀n ∈ Z, if 4|n利用反證法, 即證明當n為奇數時, 4 不整除n3
假設n為奇數, 則n = 2k + 1, for some k ∈ Z
⇒n3 = (2k +1)3 = 8k 3 +12k 2 + 6k +1 = 4(2k3 + 3k 2 + k) + 2k +1
因為2k + 1 必定為奇數不可能被4整除, 所以4 不整除n3, then n is even

5.

Show that ∀n ∈ Z, n ≥ 0, 6|(2n³ + 4n).

Let A = {1, 2, 3}. Find a relation R ⊆ A × A such that

6.

R is reflexive, symmetric, antisymmetric, and transitive.

Let A = {1, 2, 3}. Find a relation R ⊆ A × A such that

7.

R is not reflexive, not symmetric, not antisymmetric, and not transitive.

8.

Show that ∀k ∈ Z⁺, there exists n ∈ Z⁺ such that 2^k | (3ⁿ − 1).

Let x₁, …, x₂₀ ∈ Z, x₁, …, x₂₀ ≥ 1, and x₁ + ... + x₂₀ = 30.

9.

Show that there exist i and j such that i ≤ j and x_i + ... + x_j = 9.

Let x₁, …, x₂₀ ∈ Z, x₁, …, x₂₀ ≥ 1, and x₁ + ... + x₂₀ = 30.

10.

Show that there exist i and j such that i ≤ j and x_i + ... + x_j = 10.

For A = {1, 2, 3, 4}, and B = {u, v, w, x, y}, determine the number of one-to-one functions f : A → B

11.

when f(1) ≠ u; f(2) ≠ v; f(3) ≠ w; and f(4) ≠ x.

12.

when f(1) ≠ u, v; f(2) ≠ v; f(3) ≠ w; and f(4) ≠ x, y.

13.

Apply the topological sorting algorithm to the above three Hasse diagrams, respectively. How many total orders can be constructed in each Hasse diagram?

14.

What is a lattice?

15.

Is the poset whose Hasse diagram is shown in (iii) a lattice? Justify your answer.

Given any planar embedding of a connected graph G = (V, E), we have |V| − | E| + |R| = 2.

16.

Given any planar simple graph G = (V, E) with |V| ≥ 3, we have |E| ≤ 3|V| − 6.

Given any planar embedding of a connected graph G = (V, E), we have |V| − | E| + |R| = 2.

17.

K₅ is not planar.