Hàm Sinh trong Tổ Hợp: Biểu Diễn Dãy Số Bằng Hàm Số

1. Giới Thiệu

Hàm sinh là một công cụ mạnh mẽ trong tổ hợp, cho phép chúng ta biểu diễn một dãy số bằng một hàm số. Kỹ thuật này đặc biệt hữu ích trong việc giải quyết các bài toán đếm, tìm công thức truy hồi, và chứng minh các đẳng thức tổ hợp.

Định nghĩa: Cho dãy số $(a_0, a_1, a_2, ...)$, hàm sinh của dãy số này là chuỗi lũy thừa hình thức:

$$G(x) = a_0 + a_1x + a_2x^2 + ... = \sum_{n=0}^{\infty} a_nx^n$$

Trong tài liệu này, chúng ta sẽ đi sâu vào cách xây dựng hàm sinh, các phép toán trên hàm sinh, và ứng dụng của nó trong giải quyết các bài toán tổ hợp.

2. Các Hàm Sinh Cơ Bản

2.1. Hàm Sinh cho Bài Toán Chọn Đối Tượng

Giả sử chúng ta có $k$ loại đối tượng, và chúng ta muốn chọn $n$ đối tượng từ các loại này. Gọi $a_n$ là số cách chọn $n$ đối tượng.

• Chọn tối đa 1 đối tượng từ mỗi loại: Nếu chúng ta có thể chọn tối đa 1 đối tượng từ mỗi loại, thì hàm sinh tương ứng là:

  $$G(x) = (1+x)^k = \sum_{n=0}^{k} \binom{k}{n} x^n$$

  Trong đó, hệ số của $x^n$ là $\binom{k}{n}$, biểu thị số cách chọn $n$ đối tượng từ $k$ loại.

• Chọn số lượng bất kỳ đối tượng từ mỗi loại: Nếu chúng ta có thể chọn bao nhiêu tùy ý đối tượng từ mỗi loại, thì hàm sinh tương ứng là:

  $$G(x) = \left(\frac{1}{1-x}\right)^k = (1-x)^{-k} = \sum_{n=0}^{\infty} \binom{n+k-1}{n} x^n$$

  Hệ số của $x^n$ là $\binom{n+k-1}{n}$, biểu thị số cách chọn $n$ đối tượng từ $k$ loại.

• Chọn ít nhất một đối tượng từ mỗi loại:

  $$G(x) = (x+x^2+x^3+\cdots)^k = x^k(1-x)^{-k} = \sum_{n=k}^{\infty} \binom{n-1}{k-1}x^n$$

  Hệ số của $x^n$ là $\binom{n-1}{k-1}$, biểu thị số cách chọn $n$ đối tượng sao cho mỗi loại có ít nhất một đối tượng.

• Chọn $r_i$ đến $s_i$ đối tượng từ loại $i$:

  $$G(x) = \prod_{i=1}^k (x^{r_i} + x^{r_i+1} + \dots + x^{s_i})$$

2.2. Hàm Sinh cho Phân Hoạch Số

Bài toán phân hoạch số là bài toán biểu diễn một số nguyên dương $n$ thành tổng của các số nguyên dương khác. Ví dụ, số 4 có thể được phân hoạch thành 5 cách: 4, 3+1, 2+2, 2+1+1, 1+1+1+1.

• Phân hoạch số $n$ thành các số nguyên dương: Hàm sinh cho số cách phân hoạch số $n$ là:

  $$G(x) = \frac{1}{(1-x)(1-x^2)(1-x^3)...}$$

  Hệ số của $x^n$ là số cách phân hoạch số $n$.

• Phân hoạch số $n$ thành các số nguyên dương khác nhau: Hàm sinh cho số cách phân hoạch số $n$ thành các số nguyên dương khác nhau là:

  $$G(x) = (1+x)(1+x^2)(1+x^3)...$$

  Hệ số của $x^n$ là số cách phân hoạch số $n$ thành các số nguyên dương khác nhau.

• Phân hoạch số $n$ thành tối đa $k$ số hạng:

  $$G(x) = \frac{1}{(1-x)(1-x^2)\cdots(1-x^k)}$$

  Hệ số của $x^n$ là số cách phân hoạch số $n$ thành tối đa $k$ số hạng.

2.3. Các Hàm Sinh Quan Trọng Khác

• Hàm sinh cho dãy số hằng: Cho dãy số $a_n = 1$ với mọi $n$, hàm sinh là:

  $$G(x) = 1 + x + x^2 + ... = \frac{1}{1-x}$$

• Hàm sinh cho dãy số cấp số cộng: Cho dãy số $a_n = n$, hàm sinh là:

  $$G(x) = x + 2x^2 + 3x^3 + ... = \frac{x}{(1-x)^2}$$

• Hàm sinh cho dãy số $\binom{n}{k}$ (với $k$ cố định):

  $$G(x) = \sum_{n=0}^\infty \binom{n}{k} x^n = \frac{x^k}{(1-x)^{k+1}}$$

3. Các Phép Toán Trên Hàm Sinh

3.1. Phép Cộng và Phép Nhân

• Phép cộng: Cho hai dãy số $(a_n)$ và $(b_n)$ có hàm sinh $A(x)$ và $B(x)$ tương ứng, hàm sinh của dãy số $(a_n + b_n)$ là:

  $$A(x) + B(x) = \sum_{n=0}^{\infty} (a_n + b_n)x^n$$

• Phép nhân: Hàm sinh của tích Cauchy của hai dãy số $(a_n)$ và $(b_n)$, dãy số $(c_n)$ với $c_n = \sum_{k=0}^{n} a_k b_{n-k}$, là:

  $$A(x)B(x) = \left(\sum_{n=0}^{\infty} a_nx^n\right)\left(\sum_{n=0}^{\infty} b_nx^n\right) = \sum_{n=0}^{\infty} c_nx^n$$

3.2. Phép Dịch

• Dịch chỉ số: Cho dãy số $(a_n)$ có hàm sinh $G(x)$, dãy số $(b_n)$ được định nghĩa bởi $b_n = a_{n-k}$ (với $k$ là số nguyên dương), hàm sinh của $(b_n)$ là:

  $$G_b(x) = x^k G(x) = \sum_{n=0}^{\infty} a_n x^{n+k} = \sum_{n=k}^{\infty} a_{n-k} x^n = \sum_{n=k}^{\infty} b_n x^n$$

  Lưu ý rằng các số hạng từ $b_0$ đến $b_{k-1}$ đều bằng 0.

3.3. Phép Vi Phân và Tích Phân

• Phép vi phân: Cho dãy số $(a_n)$ có hàm sinh $G(x)$, dãy số $(na_n)$ có hàm sinh là:

  $$xG'(x) = x \frac{d}{dx} G(x) = x \frac{d}{dx} \sum_{n=0}^{\infty} a_n x^n = \sum_{n=0}^{\infty} n a_n x^n$$

• Phép tích phân: Cho dãy số $(a_n)$ có hàm sinh $G(x)$, dãy số $(a_n / (n+1))$ có hàm sinh là:

  $$\int \frac{G(x)}{x} dx = \int \frac{1}{x} \sum_{n=0}^{\infty} a_n x^n dx = \sum_{n=0}^{\infty} \frac{a_n}{n+1} x^{n+1}$$

4. Ứng Dụng của Hàm Sinh

4.1. Giải Bài Toán Đếm

Ví dụ 1: Có bao nhiêu cách chọn 10 viên bi từ 4 hộp bi, sao cho mỗi hộp có ít nhất 1 viên bi?

Giải:

Gọi $x_i$ là số bi được chọn từ hộp thứ $i$. Ta có bài toán tương đương với việc tìm số nghiệm nguyên dương của phương trình:

$$x_1 + x_2 + x_3 + x_4 = 10$$

với $x_i \geq 1$.

Hàm sinh tương ứng là:

$$G(x) = (x + x^2 + x^3 + ...)^4 = x^4 (1 + x + x^2 + ...)^4 = x^4 (1-x)^{-4}$$

Ta cần tìm hệ số của $x^{10}$ trong $G(x)$, tương đương với hệ số của $x^6$ trong $(1-x)^{-4}$:

$$(1-x)^{-4} = \sum_{n=0}^{\infty} \binom{n+3}{3} x^n$$

Vậy hệ số của $x^6$ là $\binom{6+3}{3} = \binom{9}{3} = 84$. Có 84 cách chọn.

Ví dụ 2: Tìm số nghiệm nguyên không âm của phương trình $x_1 + x_2 + x_3 = 15$ với điều kiện $0 \le x_1 \le 5, 0 \le x_2 \le 6, 0 \le x_3 \le 7$.

Giải:

Hàm sinh tương ứng là:

$$G(x) = (1+x+x^2+x^3+x^4+x^5)(1+x+x^2+x^3+x^4+x^5+x^6)(1+x+x^2+x^3+x^4+x^5+x^6+x^7)$$ $$= \frac{1-x^6}{1-x} \cdot \frac{1-x^7}{1-x} \cdot \frac{1-x^8}{1-x} = (1-x^6)(1-x^7)(1-x^8)(1-x)^{-3}$$

Ta cần tìm hệ số của $x^{15}$ trong $G(x)$.

$$(1-x)^{-3} = \sum_{n=0}^{\infty} \binom{n+2}{2} x^n$$ $$(1-x^6)(1-x^7)(1-x^8) = 1 - x^6 - x^7 - x^8 + x^{13} + x^{14} + x^{15} - x^{21}$$

Hệ số của $x^{15}$ trong $G(x)$ là:

$$\binom{15+2}{2} - \binom{9+2}{2} - \binom{8+2}{2} - \binom{7+2}{2} + \binom{2+2}{2} + \binom{1+2}{2} + \binom{0+2}{2}$$ $$= 136 - 55 - 45 - 36 + 6 + 3 + 1 = 6$$

4.2. Tìm Công Thức Truy Hồi

Ví dụ 3: Cho dãy số Fibonacci $F_n$ với $F_0 = 0$, $F_1 = 1$, và $F_n = F_{n-1} + F_{n-2}$ với $n \geq 2$. Tìm hàm sinh của dãy Fibonacci.

Giải:

Gọi $G(x)$ là hàm sinh của dãy Fibonacci:

$$G(x) = \sum_{n=0}^{\infty} F_n x^n = F_0 + F_1 x + \sum_{n=2}^{\infty} F_n x^n$$

Sử dụng công thức truy hồi $F_n = F_{n-1} + F_{n-2}$:

$$G(x) = x + \sum_{n=2}^{\infty} (F_{n-1} + F_{n-2}) x^n = x + \sum_{n=2}^{\infty} F_{n-1} x^n + \sum_{n=2}^{\infty} F_{n-2} x^n$$ $$G(x) = x + x \sum_{n=2}^{\infty} F_{n-1} x^{n-1} + x^2 \sum_{n=2}^{\infty} F_{n-2} x^{n-2} = x + x \sum_{n=1}^{\infty} F_n x^n + x^2 \sum_{n=0}^{\infty} F_n x^n$$ $$G(x) = x + x (G(x) - F_0) + x^2 G(x) = x + x G(x) + x^2 G(x)$$

Từ đó, ta có:

$$G(x) (1 - x - x^2) = x$$

Vậy hàm sinh của dãy Fibonacci là:

$$G(x) = \frac{x}{1 - x - x^2}$$

4.3. Chứng Minh Đẳng Thức Tổ Hợp

Ví dụ 4: Chứng minh rằng $\sum_{k=0}^{n} \binom{n}{k} = 2^n$.

Giải:

Ta xét hàm sinh $(1+x)^n$.

$$(1+x)^n = \sum_{k=0}^{n} \binom{n}{k} x^k$$

Đặt $x = 1$:

$$(1+1)^n = \sum_{k=0}^{n} \binom{n}{k} 1^k$$ $$2^n = \sum_{k=0}^{n} \binom{n}{k}$$

Vậy đẳng thức được chứng minh.

5. Bài Tập Vận Dụng

1. Có bao nhiêu cách chia 20 viên bi giống nhau vào 3 hộp khác nhau sao cho mỗi hộp có ít nhất 2 viên bi?
2. Tìm số nghiệm nguyên không âm của phương trình $x_1 + x_2 + x_3 + x_4 = 18$ với điều kiện $x_1 \leq 7, x_2 \leq 8, x_3 \leq 9, x_4 \leq 10$.
3. Tìm hàm sinh của dãy số $a_n = n^2$.
4. Chứng minh rằng $\sum_{k=0}^{n} \binom{n}{k}^2 = \binom{2n}{n}$.
5. Tìm công thức cho số Catalan $C_n$ thông qua hàm sinh.

6. Kết Luận

Hàm sinh là một công cụ mạnh mẽ và linh hoạt trong tổ hợp. Việc nắm vững các khái niệm cơ bản và các phép toán trên hàm sinh sẽ giúp bạn giải quyết nhiều bài toán phức tạp một cách hiệu quả. Hy vọng tài liệu này sẽ giúp các bạn học sinh lớp 11 hiểu rõ hơn về hàm sinh và ứng dụng của nó.