Generating Function問題(數學)?

1a)

答案和版主的一致, 寫得詳細些:
(1 - x)ⁿ = C(n,0) - C(n,1)x + C(n,2)x² - C(n,3)x³ + ... + (-1)ᵏ C(n,k)xᵏ + ... + (-1)ⁿ C(n,n)xⁿ

b)

考慮 (1 - x)ⁿ = (1 - x)ⁿ⁻¹ (1 - x)
⇒
C(n,0) - C(n,1)x + C(n,2)x² - C(n,3)x³ + ... + (-1)ᵏ C(n,k)xᵏ + ... + (-1)ⁿ C(n,n)xⁿ
=
[C(n-1,0) - C(n-1,1)x + C(n-1,2)x² - C(n-1,3)x³ + ... + (-1)ᵏ C(n-1,k)xᵏ + ... + (-1)ⁿ⁻¹ C(n-1,n-1)xⁿ⁻¹] (1 - x)
=
C(n-1,0) - [C(n-1,0) + C(n-1,1)]x + [C(n-1,1) + C(n-1,2)]x² - [C(n-1,2) + C(n-1,3)]x³ + ... +
(-1)ᵏ [C(n-1,k-1) + C(n-1,k)]xᵏ + ... + (-1)ⁿ⁻¹ [C(n-1,n-2)+C(n-1,n-1)]xⁿ⁻¹ + (-1)ⁿ C(n-1,n-1)xⁿ

令 x = 1 , 加減相消後即得

s
Σ (- 1)ᵏ C(n,k) = (-1)ˢ C(n-1,s) ;
k=0

特別地 , 當 s = n 時,
n
Σ (- 1)ᵏ C(n,k) = (-1)ⁿ⁻¹ C(n-1,n-1) + (-1)ⁿ C(n-1,n-1) = 0 。
k=0

2)

以 (c₁x)ᵐ 表小孩₁分得m塊糖(1 即分得0塊), 考慮生成函數:
(1 + c₁x + (c₁x)² + ... + (c₁x)ᵐ) (1 + c₂x + (c₂x)² + ... + (c₂x)ᵐ) ... (1 + cn x + (cn x)² + ... + (cn x)ᵐ) ,
展開後注意 xᵏ 之係數 ak, 它是關於c的一些k次單項式的和, 當中每個單項式都對應一種符合要求的分糖法,
且不重不漏,一一對應。於是 ak 是幾個k次單項式之和就有幾種分糖法,
只需令 c₁= c₂= ... = cn = 1 , 則生成函數(1 + x + x² + ... + xᵐ)ⁿ 即為所求. 其 xᵏ 之係數 ak 為分糖方法數。

3)

以(Ax)ᵐ 表共有m個A , m為偶數≤ n, 考慮生成函數:
(1 + (Ax)² + (Ax)⁴+ ... + (Ax)ᵐ) (1 + Bx + (Bx)² + ... + (Bx)ⁿ) (1 + Cx + (Cx)² + ... + (Cx)ⁿ) ,
令 A = B = C = 1 , 展開(1 + x² + x⁴+ ... + xᵐ) (1 + x + x² + ... + xⁿ) (1 + x + x² + ... + xⁿ) , 則
xⁿ 之係數 an 即為所求。

要具體求出an, 可就 n 的奇偶性分別討論:
當 n 是偶數:
若 A 有 0 個, 則 B、C 有 n+1 種分配,
若 A 有 2 個, 則 B、C 有 n -1 種分配,
若 A 有 4 個, 則 B、C 有 n -3 種分配, ...
若 A 有 n 個, 則 B、C 有 n+1 - n = 1 種分配,
共有 (n+1 + 1) (n/2 + 1) / 2 = (n+2)²/4 種分配.

當 n 是奇數:
若 A 有 0 個, 則 B、C 有 n+1 種分配,
若 A 有 2 個, 則 B、C 有 n -1 種分配,
若 A 有 4 個, 則 B、C 有 n -3 種分配, ...
若 A 有 n-1 個, 則 B、C 有 n+1 - (n-1) = 2 種分配,
共有 (n+1 + 2) ((n-1)/2 + 1) / 2 = (n+2)²/4 - 1/4 種分配.

綜合上述結論, there are (n+2)²/4 - (1 - (-1)ⁿ)/8 ways so that there is an even number of A's.