115年 - 115 國立嘉義大學_碩士班招生考試試題_資訊工程學系：離散數學#143915

一、Prove by mathematical induction that

\[ (1+x)^n = C_0^n + C_1^n \times x + C_2^n \times x^2 + \dots + C_n^n \times x^n, n \in \mathbb{N}. \]
(20%)

(1) Is (p∨ q) ∧ (¬p ∨ r) ⟶ (q ∨ r) a tautology (i.e., “always true”)? Please explain your answer. Note that ¬? denotes “not p” and ⟶ denotes “p implies q”. (10%)

(2) Please prove that (p ∨ ¬q) ∧ (¬p ∨ q) and (¬q ∧ ¬p) ∨
(p ∧ q) are logically equivalent by using only laws of propositional logic. (10%)

三、Please calculate the number of positive integers greater than 1 (> 1) and not exceeding 150 (≤ 150) that are divisible by none of 3, 5, or 7 by using The Principle of Inclusion–Exclusion. You should explain your answer. (10%)

四、Paul has two coolers. Cooler 1 contains 8 cans of cola and 3 cans of lemonade. Cooler 2 contains 5 cans of cola and 7 cans of lemonade. Paul randomly selects one can from Cooler 1 and transfers it into Cooler 2. Subsequently, Betty randomly selects two cans from Cooler 2. Given that both of Betty's selections are cans of cola, what is the probability that the can Paul initially transferred was lemonade? (10%)

五、Solve the following recurrence relation:
a_n + 6a_n-1− 16a_n-2 = 6, given that a₀ = 0 and a₁ = 2.

六、Determine whether the poset (Partially Ordered Set) (S, ⊆) is a
lattice where ? ={∅, {1}, {2}, {4}, {1,2}, {1,4}, {3,4}, {1,2,4},{2,3,4}, {1,2,3,4}}

Please draw its Hasse diagram and explain your answer. (10%)

(1) Let G = (V, E) be an undirected graph with d components, where |V| = b and |E| =c  . Please prove that c ≥ b − d . (10%)

(2) Consider the complete bipartite graphK_m,n , where the vertex set is partitioned into two disjoint sets V₁ and V₂with |V₁ | = m and |V₂ | = n. Derive the necessary and sufficient conditions for ? and ? such that K_m，n contains an Eulerian path but NO Eulerian circuit. (Consider all possible cases for m and n ). (10%)