課程名稱︰組合學
課程性質︰研究所
課程教師︰葉永南
開課學院：理學院
開課系所︰數學所
考試日期（年月日）︰2006.12.25
考試時限（分鐘）：
是否需發放獎勵金：
我要獎勵金~~~~
（如未明確表示，則不予發放）
試題 :
1.Prove the inverse pair:
a_n = sigma (n取k) b_(n-ck),
k >= 0
b_n = sigma (-1)^k { (n-k(c-1)-1取k) - c*(n-k(c-1)-1取k-1) }a_(n-ck)
k >= 0
for n >= 0, where c is an integer. This is called a Chebyshev inverse pair.
2. By using decomposition (Subsets):
=======================================================================
Let S_k be the set pf all k-subsets of Nn for n >= 0. Then
~ k
S_k -> N_+ ╳ N:{σ_1~σ_k}_n |-> (j_1 ~ J_(k+1)),
where σ_1 < ... < σ_k, σ_i - σ_(i-1) = j_i for i = 1 ~ k+1,
σ_0 = 0 and σ_(k+1) = n.
=======================================================================
Show that the number of k-subsets of Nn with m circular successions is
(n/k)(k取m)(n-k-1取k-m-1)
3. (a) From the Jacobi triple product identity:
=======================================================================
∞
Pi ( 1+yq^(2m-1) )( 1+(y^-1)(q^(2m-1)) )(1-q^(2m)) = sigma(y^k)(q^(k^2))
m>=1 k=-∞
=======================================================================
Deduce that:
Pi (1 - q^l)^3 = sigma (-1)^k (2k+1) q^(k+1取2)
l>=1 k>=0
(b) Combine Euler's pentagonal number theorem with part (a) to obtain
an expansion for F(q) = q Pi (1-q^l)^4. Hence, by noting that:
l>=1
q Pi (1 - q^i)^-1 = F(q) Pi (1-q^l)^(-5),
i>=1 l>=1
deduce that p(5n+4) = 0 (mod 5)
4. Prove that the number of vertices at height h in planted planetrees on
n nonroot vertices is:
{(2h+1)/(n+h)}(2n-1取n-h-1)
5. Show that the number of {0,1} sequence of length l with no occurrences
of 11101011 or 101111 is
[x^l] (1+x^5+x^6-x^8-x^9-x^10)(1-2x+x^5-2x^7+x^9+x^11)^-1
6. (a) Let A = [a_ij] n by n, be a symmetric matrix of indeterminates. Show
that the number of distinct monomials in the expansion of |A| is
b_n = [x^n/n!] (1-x)^(-1/2) exp(x/2 + x^2/4).
(b) Show that b_(n+1) = (n+1)b_n - (n取2)b_n-2, n >=0,
and b_0 = 1, b_i = 0 for i < 0.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.77.51
※ 編輯: TassTW 來自: 61.228.77.51 (01/23 00:48)