3. จงพิสูจน์ว่า $$\sum_{k=0}^{\left\lfloor\frac{n+2016}{2}\right\rfloor}(-1)^{k}\binom{n+2016}{k}\binom{2n-2k+2014}{n+2015}=\binom{n+2016}{2017}$$ (15 คะแนน)
4. กำหนดให้ $sK_n$ คือกราฟที่มีจุดยอด $n$ จุด และมีเส้นเชื่อมระหว่างจุดยอดสองจุดใดๆ $s$ เส้น
ให้ $G, H$ เป็นกราฟสองกราฟใดๆ นิยามกราฟ $G\vee_t H$ คือการยูเนียนกันของ $G,H$ และเพิ่มเส้นเชื่อมเข้าาไประหว่างจุดหนึ่งใน $G$ กับอีกจุดหนึงใน $H$ $t$ เส้น
ให้ $G,H$ เป็นกราฟสองกราฟใดๆ จะได้ว่า $G\mid H$ ก็ต่อเมื่อเราสามารถแบ่ง $H$ เป็นกราฟหลายๆกราฟ ที่ทุกๆ กราฟที่ถูกแบ่งจะสมสัณฐานกับ $G$
จงแสดงว่าถ้า $K_3\mid sK_m\vee_t sK_n$ แล้ว
(i) $2\mid s(m-1)+tn$ และ $6\mid sm(m-1)+sn(n-1)+2tmn$ (5 คะแนน)
(ii) $\dfrac{t}{s}\leq \dfrac{m^2-m+n^2-n}{mn}$ (10 คะแนน)
ขอ Hint ข้อ 3 กับ 4 (ii) หน่อยครับ
|