99年國立成功大學資工所離散數學線上測驗

2.: Let A = {a, b, c, d} and B = {1, 2, 3, 4}, which of the following statement is NOT true?
(A): There are 4¹⁰ closed binary operations on A that have an identity.
(B): There are 2¹⁶ relations from A to B.
(C): There are 4! one-to-one functions from A to B.
(D): There are 4! onto functions from A to B.
(E): There are 4⁶ closed binary operations on A that are commutative.

3.: Which of the following statement is true?
(A): A Δ (B ∩ C) = (A Δ B) ∩ (A Δ C), Δ: symmetric difference.
(B)
(C): Negation of ∃x [(p(x) ∨ q(x)) → r(x)] is ∀x[(p(x) ∨ q(x)) ∧ ¬r(x)]
(D): If A = {01}, B = {01, 000, 0111}, we can say AB = {01, 000, 0101, 0111, 01000, 010111}.
(E): None of the above

4.: Which of the following statement is true?
(A): The sum of all the coefficients in the expansions of (x − 3y + 3)¹⁰ is (−2)¹⁰.
(B): Consider the 2¹⁹compositions of 20, the number of compositions in which each summand even is 2^10.
(C): The number of derangements of 1, 2, 3, 4, 5, 6, 7, 8 start with 5, 6, 7, and 8, in some order is 9².
(D): If n is formed by using the digits 3, 3, 4, 5, 5, 6, 7. The number of positive integers n that exceed 4,000,000 is 720.
(E): None of the above.

5.: In a social network, we want to match each of four women with one of five men.
According to the information they provided, we can draw the following conclusions.
• Woman 1 would not be compatible with man 1, 3, or 5.
• Woman 2 would not be compatible with man 2, or 4.
• Woman 3 would not be compatible with man 3, or 5.
• Woman 4 would not be compatible with man 4.
In how many ways can the service successfully match each of the four women with a compatible partner?

6.: Find the exponential generating function for the number of ways to arrange n letters, n ≥ 0, selected from the word "MISSISSIPPI".

7.: in (a), what is the exponential generating function if the arrangement must contain at least two I's.

模擬測驗