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

(a)x_i≥ 0 for ;1≤i≤6

(b) x_i≥ 1 for ;1≤i≤6

(c)x_i>0 for ;1≤i≤4 x₅=3 x₆=4

(d)x_i≥ 4 for ;1≤i≤3,and x_i≥ 2 for 4≤i≤6

(a) How many graphs are there with vertex set V? (7%)

(b) How many of the graphs in (1) contain the triangle 123? (8%)

(a) Please show the shortest path. The path should be represented by tracing a sequence of visited vertices, such as (a, b, f, z). (10%)

(b) Please evaluate the length of the shortest path. (5%)

(a) How many subsets of A contain at least one even integer? (7%)

(b) How many subsets of A contain only odd integers? (8%)

5. The derangement problem can be described as the following story. Assume that there are five customers   who hand over their hats   to the waiter at the restaurant. After the dinner, the waiter gives them back the hats at random. If the return order is , it is not a derangement because this order leaves fixed. However, if the return order is , we say that it is a derangement because no element is left in its original position. That means no customer can receive the correct hat. Please prove that the probability of derangement of a set with n elements converges to as n grows without bound. (Hint: Applying the inclusion-exclusion principle) (15%)

(a) Show that (you should give a detail explanation) the recurrence relation c_n for is: .

(b) Solve the recurrence relation (find an explicit formula) for c_n in part (a).