課程名稱︰離散數學
課程性質︰必修
課程教師︰陳健輝
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2010.10.28
考試時限（分鐘）：120
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Solutions to Examination #1
(範圍:Combinatorics)
(For each problem, please provide your computation details, not only your
answer.)
1.Find a recurrence relation for the number of distinct outputs that may be
generated from the following stack. You are REQUIRED to explain your answer,
but NOT REQUIRED to solve the relation. (10%)
Output ← ←1, 2, ., ..., n Input
↑ ↓
Stack
Sol:Refer to pages 137-138 of lecture notes.
2.How many four-element subsets of {1, 2, ..., 15} are there that contain no
cconsecutive integers? (10%)
Sol:Refer to pages 62-63 of lecture notes.
3.Compute the number of ways to tile a 2 x n chessboard using horizontal
1 x 2 dominoes (which can also be used as vertical 2 x 1 dominoes) and
aquare 2 x 2 tiles. (10%)
Sol.Clearly, a[1] = 1 and a[2] = 3.
When n >= 3, let us consider the rightmost column of the chessboard.
If it is covered by one vertical(2 x 1) domino, then a[n] = a[n-1].
If it is covered by two horizontal (1 x 2) dominos, then a[n] = a[n-2].
If it is covered by one square (2 x 2) title, then a[n] = a[n-2].
Hence, a[n] = a[n-1] + 2a[n-2].
characteristic equation: r^2 - r - 2 = 0.
characteristic roots: 2, -1.
general solution: a[n] = c[1](-1)^n + c[2](s)^n.
a[1] = 1: (-1)c[1] + 2c[2] = 1.
s[2] = 3: c[1] + 4c[2] = 3.
→c[1] = 1/3, c[2] = 2/3.
Therefore, a[n] = (1/3)(-1)^n + (2/3)(s)^n, n >= 1.
4.Show that the number of partitions of n into m summands is equal to the
number of partitions of n into summands with m being the largest summand.
(10%)
Sol:Refer to pages 69-70 of lecture notes.
5.At a 12-week conference, Sharon met seven of her friends. During the
conference she met each friend at lunch 35 times, every pair of them 16
times, every trio eight times, every foursome four times, each set of five
twice, and each set of six once, but never all seven at once. If she had
luncg every day during the 84 days of the conference, did she ever have
lunch alone? (10%)
Sol.Denote Sharon's seven friends by f[1], f[2], ..., f[7].
Let c[i] be the condition that Sharon and f[i] had lunch together.
Then, the number of days Sharon had lunch alone is
N(c'[1]c'[2]c'[3]c'[4]c'[5]c'[6]c'[7]) = 84 - c(7,1)x35 + c(7,2)x16
-c(7,3)x8 + c(7,4)x4 - c(7,5)x2 + c(7,6)x1 = 0.
6.The number pf 20-digit quaternary (0, 1, 2, 3) sequences that contain at
least one 2 and an odd number of 0's can be expressed as a x 4^20 + b x 3^20
+c x 2^20 + d.
What are a,b,c, and d? (10%)
Sol. The number of 20-digit quaternary (0, 1, 2, 3) sequences that contain at
least one 2 and an odd number of 0's us tge cieffucuent of (x^20)/20! in the
following generating function:
(x + x^2/2! + x^3/3! +... + x^19/19!) x (x + x^3/3! + x^5/5! + ... + x^19/19!)
x (a + x + x^2/2! + x^3/3! + ... + x^18/18!)^2
= (e^x - 1) x (e^x - e^(-x))/2 x e^(2x)
= 1/2 x (e^4x - e^3x - e^2x + e^x),
which is 1/2 x (4^20 - 3^20 - 2^20 + 1).
a = d = 1/2, b = c = -1/2
7.Solve a[n] - 2a[n-1] = 4^(n-1), where n >= 1 and a[0] = 1, by the method of
generating functions. (10%)
Sol:Refer to page 132 of lecture notes.
8.In how many ways can two dozen identical robots be assigned to four assembly
lines with at least three, but no more than nine, robots assigned to each
line? (10%)
Sol.The answer is the coefficient of x^24 in
(x^3 + x^4 + ... + x^9)^4 = x^12(1 + x + x^2 + ... + x^6)^4,
where (1 + x + x^2 + ... + x^6)^4 = [(1-x)^7/(1-x)]^4 = (1-x^7)^4(1-x)^(-4).
The coefficient of x^12 in (1-x^7)^4(1-x)^(-4) is equal to
(4)(-1)^5 c(8,5) + c(15,12)
= 231
9.Professor Ruth has five graders to correct programs in her courses in
Java, C++, SQL, Perl, and VHDL. Graders Jeanne and Charles both dislike
SQL, Sandra wants to avoid C++ and VHDL. Paul detests Java and C++,
and Todd refuses to word in SQL and Perl. In how many ways can Professor
Ruth assign each grader to correct programs in one language, cover all five
languages, and keep everyone content? (10%)
Sol: r(C2,x) = 1 + 4x + 2x^2.
r(C,x) = (1 + 4x + 3x^2)(1 + 4x + 2x^2) = 1 + 8x + 21x^2 + 20x^3 + 6x^4
Let ci be the condition of assigning Grader-i with a course that he or she
dislikes.
Then N(c1'c2'c3'c4'c5') = 5! - 8 x 4! + 21 x 3! - 20 x 2! + 6 x 1! = 20.
10.For the binary string 001110, there are three runs: 00, 111, and 0.
Meanwhile, the string 000111 has only two runs: 000 and 111; wguke tge
string 010101 determines the six runs: 0, 1, 0, 1, 0, 1. For n = 1,
we consider two binary strings, namely 0 and 1; these two strings
(of length 1) determine a total of two runs. There are four binary strings
of length n = 2 and these strings determine 1 (for 00) + 2(for 01)+ 2
(for 10) + 1(for 11) = 6 runs. Find the number of runs determined by
the 2^n binary strings of length n, where n >= 1. (10%)
Sol,Let tn be the number of runs determined by the 2^n binary strings of
length n.
Consider the 2^(n-1) binary strings of length n that end with 0. Since half
of these 2^(n-1) binary strings end with 1, there are
t[n-1] + (1/2)(2^(n-1)) runs. Similarly, the 2^(n-1) binary strings of length
n that end with 1 determines the same number of runs.
Therefore, we have
t[n] = 2t[n-1] + 2^(n-1),
where n >= 2.
Since tnh = c(2^n), we assume tnp = kn(2^n). Thus,
kn(2^n) = 2k(n-1)2^(n-1) + 2^(n-1)
= kn(2^n) - k(2^n) + 2^(n-1),
from which k = 1/2 is determined.
Consequently, tn = tnh + tnp = c(2^n) + n(2^(n-1)).
Since t1 = 2, we have c = 1/2.
So, tn = (1/2)2^n + n(2^(n-1)) = (n+1)(2^(n-1)), where n >= 1.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.98