课程名称︰离散数学 课程性质︰系必修 课程教师︰陈健辉 开课学院：电资学院 开课系所︰资讯系 考试日期（年月日）︰2009/10/28 考试时限（分钟）：120 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : 范围:Combinatorics (For each problem, please provide your computation details, not only your answer.) 1. How many 8-digit quaternary (0, 1, 2, 3) sequences are there that they each contain exactly two 3's or none at all? (10%) 2. Solve a[n+2] - 6a[n+1] + 9a[n] = 3*2^n + 7*3^n for n>=0 with a[0] = 1 and a[1] = 4. (10%) 3. Compute the number of integer solutions for x1+x2+x3+x4 = 24, where 4<=xi<=9 for i = 1, 2, 3, 4. (10%) 4. In how many ways can 24 bottles of soft drinks, 12 of type A and 12 of type B, be distributed among five surveyors so that each surveyor gets at least one bottle of type A and at least two bottles of type B? (10%) 5. Compute the number of ways to park motorcycles and compact cars in a row of n spaces, provided each cycle requires one space, each compact needs two, and all n spaces are used up. Assume that all cycles are identical in appearance, as are the cars. (10%) 6. In how many ways can one arrange all of the letters INFORMATION so that no pair of consecutive letters (i.e., "IN", "NI", "IO", "OI", "NO", and "ON") occurs twice? For example, IINNOOFRMTA and FORTMAIINON are counted, but INFORINMOTA and NORTFNOIAMI are not counted, because the latter two contain "IN" and "NO", respectively, twice. Notice that it is impossible that two "IN"s and two "NI"s (similarly, for "IN" and "IO", "IN" and "ON", "NI" and "OI", "NI" and "NO", "IO" and "OI", "IO" and "NO", "OI" and "ON", and "NO" and "ON") occur simultaneously. You are perprmitted to write your answer as a conbination of some factorials, e.g., 11!+7*10!+5*8!=2*6!. (10%) 7. Two dice, denoted by R and G, are rolled six times. Under the condition of (R, G)不属於{(1,2), (1,3), (2,3), (2,4), (4,5), (5,5)}, compute the number of ways for each of R and G to occur 1,2,...,6(for example, (1,2), (3,3), (2,6), (5,5), (4,1), (6,4) and (5,4), (1,6), (6,3), (3,5), (4,2), (2,1) are two ways). (10%) 8. Define φ(n) to be the number of integers m so that 1<=m<=n and gcd(m, n) = 1, where n>=2 is an integer. For example, φ(2) = 1, φ(3) = 2, φ(4) = 2, and φ(5) = 4. Prove IN DETAIL that when n = (p1)^a *(p2)^b *(p3)^c, φ(n) = n(1-1/p1)(1-1/p2)(1-1/p3), where p1, p2, and p3 are three distinct prime numbers. (10%) 9. Pauline takes out a loan of 200,000 dollars that is to be paid back in 20 years with the interest rate 5% per year. The constant payment at the end of each year is (200,000/w)*([x*(1.05)^20]/[y*(1.05)^20 + z]). Please find w, x, y, and z. (10%) 10. Solve b[n+1] = b[n] + b[n-1] +...+b[1] + b[0] with n>=0 and b[0] = 1. (10%) 11. Please remember what (funny or impressive or encouraging or ..., but NOT RELATED TO DISCRETE MATHEMATICS) things did the professor Chen mention in the class. Write down any two of them. (10%) -- 心中有变数，就不用变数代换法 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.30.88