Phương pháp truy hồi trong giải toán tổ hợp

PHƯƠNG PHÁP TRUY HỒI TRONG GIẢI TOÁN TỔ HỢP Lê Phi Hùng  Trường THPT Chuyên Hà Tĩnh

A. ĐẶT VẤN ĐỀ

Đại số tổ hợp là một bộ phận của toán học rời rạc. Đây là một bộ phận có nội dung phong phú, hấp dẫn và được ứng dụng nhiều trong thực tế đời sống, đặc biệt là từ khi Tin học ra đời. Đối tượng nghiên cứu chủ yếu của đại số tổ hợp là mối quan hệ của các phần tử trong các tập hữu hạn.

Các bài toán đại số tổ hợp trong toán sơ cấp thường có nội dung phong phú, hấp dẫn nhưng luôn được đánh giá là khó. Thông thường nó đã được “thực tế hoá” hay “mô hình hoá”

để che đậy bản chất toán học bên trong. Phương pháp giải các bài toán đại số tổ hợp thường không có quy luật nào và điều quan trọng nhất là phải nắm được bản chất toán học sau lớp vỏ ngôn ngữ của bài toán.

Cách giải bài toán đại số tổ hợp nói chung liên quan mật thiết đến các công thức tổ hợp, cách đếm số phần tử của tập hữu hạn, quy nạp toán học, dãy số… Do vậy để tìm được cách giải của một bài toán đại số tổ hợp, người đọc phải có một số kiến thức và phương pháp giải toán nhất định.

Đại số tổ hợp là một trong những vấn đề được giảng dạy ở bậc trung học phổ thông.

Tuy nhiên chỉ một số ít kiến thức cơ bản về các công thức tổ hợp và nhị thức Niutơn được trình bày đại trà còn lại là được trình bày ở dạng chuyên đề dành cho học sinh các lớp chuyên Toán. Các chuyên đề này một phần nhằm phục vụ cho các kỳ thi học sinh giỏi cấp Quốc gia, khu vực và Quốc tế.

Đối với các bài toán đại số tổ hợp xuất hiện trong các kỳ thi chọn học sinh giỏi bậc phổ thông thường có một số phương pháp giải sau: Phương pháp sử dụng song ánh, Phương pháp truy hồi, Phương pháp hàm sinh, Phương pháp quỹ đạo,… Trong bài này, với tên gọi “Phương pháp truy hồi trong giải toán tổ hợp” chúng tôi xin trình bày một phương pháp để giải một số bài toán của đại số tổ hợp, đó là: Phương pháp truy hồi hay là Phương pháp đệ quy.

Bản chất của phương pháp này là: đưa bài toán có n đối tượng tham gia về bài toán có ít hơn n đối tượng tham gia bằng một quan hệ phụ thuộc nào đó gọi là quan hệ truy hồi hoặc quan hệ đệ quy. Sử dụng mối quan hệ này ta có thể tìm ra được kết quả bài toán vì nói chung đối với các số n nhỏ bài toán thường có kết quả rõ ràng.

Những ví dụ minh hoạ cho phương pháp ở trong bài viết này phần lớn được lấy từ các kỳ thi chọn học sinh giỏi. Người viết cố gắng đưa ra những gợi ý, hướng dẫn ý tưởng và lời giải đầy đủ các bài toán minh hoạ. Tất nhiên với những bài toán đó, người đọc vẫn có thể tìm được những lời giải khác với lời giải được trình bày.

B. NỘI DUNG

I. MỘT SỐ KIẾN THỨC VỀ DÃY TRUY HỒI TUYẾN TÍNH

Dãy truy hồi cấp k là dãy số được cho ở dạng

 

u_n với:

u

₁, u₂, …, u_k xác định và u_n

= f



u_n1,u_n2,...,u_nk



với mọi n ≥ k + 1.

Trong mục này chúng ta sẽ chỉ ra cách xác định công thức tính số hạng tổng quát của một số dãy truy hồi tuyến tính cơ bản và quen thuộc.

Vì dãy truy hồi tuyến tính cấp một chỉ là sự kết hợp giữa cấp số cộng và cấp số nhân và cũng để phù hợp với nội dung bài viết, ta xem xét kỹ hơn về dãy truy hồi tuyến tính cấp hai thuần nhất hệ số hằng.

Định nghĩa. Dãy số

 

u_n xác định bởi: u₁, u₂ cho trước, u_n2au_n1bu_n với mọi n

= 1, 2, … trong đó a, b là các số thực bất kỳ được gọi là dãy truy hồi tuyến tính cấp hai thuần nhất hệ số hằng.

Ta gọi phương trình x² axb (*) là phương trình đặc trưng của dãy số trên. Có 3 trường hợp xảy ra:

Trường hợp 1: Phương trình (*) có hai nghiệm thực phân biệt x₁, x₂. Khi đó số hạng tổng quát của

u

_n là: u_n  A₁.x₁ⁿA₂.x₂ⁿ với n = 1, 2, … và A₁, A₂ là các hằng số thực được xác định từ u₁, u₂.

Trường hợp 2: Phương trình (*) có nghiệm kép x₀. Khi đó số hạng tổng quát của u_n là: u_n  A₁.x₀ⁿA₂.n.x₀ⁿ =



A₁A₂n



x₀ⁿ với mọi n = 1, 2, … và A₁, A₂ là các số thực được xác định từ u₁, u₂.

Trường hợp 3: Phương trình (*) có hai nghiệm phức liên hợp x₁i và i

x₂ . Khi đó ta tính   ²² và  là góc mà



 

tan . Số hạng tổng quát của un là: ^un ^n



^A₁cos^n^A₂sin^n



với với n = 1, 2, … và A₁, A₂ là các số thực được xác định từ u₁, u₂.

Một số dãy truy hồi cho ở dạng các hệ phương trình cũng có thể đưa về vận dụng dãy số trên. Ta chỉ xét ví dụ tìm số hạng tổng quát của các dãy (x_n), (y_n) xác định bởi: x₁, y₁ cho trước, x_n1 px_nqy_n, y_n1rx_nsy_n với mọi n = 1, 2… và p, q, r, s là các hằng số.

Từ hệ trên ta có:

x_n2 = px_n1qy_n1

= px_n1q(rx_nsy_n) = px_n1qrx_ns(qy_n) = px_n1qrx_ns(x_n1 px_n)

hay là

n n

n p s x ps qr x

x_2(  ) (  ) .

Hơn nữa ta có được x₁ và x₂  px₁qy₁, nên theo cách tính số hạng tổng quát của phương trình tuyến tính cấp hai thuần nhất hệ số hằng ta tính được x_n. Thay hệ trên sẽ tính được y_n.

Chú ý rằng cũng có một cách khác để xác định số hạng tổng quát của các dãy (x_n), (y_n) cho bởi công thức trên. Đó là ta sẽ xác định các số A, B thích hợp để tính được số hạng tổng quát của các dãy x_n Ay_n và x_nBy_n. Khi đó ta sẽ tính được số hạng tổng quát của các dãy (x_n), (y_n).

II. MỘT SỐ BÀI TOÁN MINH HOẠ

Bài toán 1. Trong mặt phẳng cho n đường thẳng (n  N*) trong đó bất kỳ hai đường thẳng nào cũng cắt nhau và không có ba đường nào đồng quy. Tính số phần mặt phẳng mà các đường thẳng đó chia ra.

Lời giải. Gọi Pn là số phần mặt phẳng mà n đường thẳng có tính chất trên chia ra. Ta có P1 = 2. Với n > 1 thì số phần mặt phẳng mà n – 1 đường thẳng chia ra là Pn–1. Xét đường thẳng thứ n. Đường thẳng này bị n – 1 đường thẳng trước cắt theo n  1 giao điểm hay là bị chia ra thành n phần. Mỗi phần này chia đôi phần mặt phẳng mà nó đi qua, do đó sẽ thêm n phần. Vậy ta có công thức truy hồi:

Pn = Pn–1 + n với mọi n > 1.

Đến đây ta có:

Pn = (Pn Pn 1) + (Pn 1  Pn 2) + … + (P2  P1) + P1 = n + (n  1) + ... + 2 + 2 = 1

2 ) 1 (n 

n .

Vậy ta có Pn = 1 2

) 1 (n 

n với mọi n  N*.

Bài toán 2. Xác định số các hoán vị (a1, a2, …, an) của (1, 2, …, n) với n ≥ 2 sao cho chỉ có duy nhất một chỉ số i  {1, 2, …, n – 1} thoả mãn ai > ai + 1.

Lời giải. Ta gọi Sn là số các hoán vị thoả mãn bài toán. Chia các hoán vị đó thành hai nhóm:

Nhóm 1: an = n. Khi đó ta thấy số hoán vị ở nhóm này là Sn – 1 vì mỗi hoán vị trong nhóm này là một hoán vị của bài toán đối với n  1 số ghép thêm số n ở cuối cùng.

Nhóm 2: ai = n với i  {1, 2, …, n – 1}. Khi đó với mỗi ai = n thì số hoán vị thoả mãn điều kiện bài toán bằng số các chọn i –1 số trong n – 1 số, tức là C_n^k_^₁¹. Do đó số hoán vị cần tìm ở nhóm này là:

2 1 1

1 0

1 _ ... _^

  _n   _nⁿ

n C C

C =



^





 1 1

1 1 n

i i

Cn = 2^n–1 – 1.

Ta có hệ thức truy hồi: Sn = Sn 1 + 2^n1  1 với mọi n  3. Từ đây ta có thể viết:

S3 = S2 + (2²  1) S4 = S3 + (2³  1)

...

Sn = Sn1 + (2^n1  1) Cộng lại ta có:

Sn = S2 + (2² + 2³ + ... + 2^n1)  (n  2) = 2ⁿ  n  1 (vì S2 = 1) Vậy ta có Sn = 2ⁿ  n  1 với mọi n  2.

Bài toán 3. Cho hàm số f(x) x³6x²9x và đặt )))f_n(x) f(f(...f(x với n lần f , n  N*. Tìm số nghiệm của phương trình f_n(x)0.

Lời giải. Xét hàm số f(x)x³6x²9x trên R.

Ta có f'(x)3x²12x9, 0

) ( ' x 

f 

x

= 1 hoặc

x

= 3.

Bảng biến thiên: (chú ý f(0)0 và f(4)4)

Từ bảng biến thiên ta thấy f(x)0 có hai nghiệm

x

= 0,

x

= 3. Do đó 0

)

2(x 

f  f(x) = 0 hoặc )f(x = 3.

Cũng theo bảng biến thiên trên thì f₂(x)0 có 2 + 3 = 5 nghiệm. Vì f_k1(x)0 có hai nghiệm )

2(x

f_k  {0, 3}và f_k1(x)3 có 3 nghiệm )f_k2(x  (0, 4)\{0, 3}. Tiếp tục quá trình này ta thấy 3f_k1(x) có

3

^k1 nghiệm x  (0, 4)\{0, 3}.

Như vậy, nêu gọi số nghiệm của 0f_n(x) là

s

_n thì:

Với n = 1 ta có

s

₁ = 2.

Với n > 1 ta có:

s

_n =

s

_n1 + 3^n1 .

Đến đây có thể tìm công thức tổng quát của sn như bài toán 2, nhưng cũng có thể khai triển:

s

_n =

s

_n1 + 3^n1 =

x  1 3 +

) ( ' x

f + 0  0 +

) (x

f 4 +

 0

= (s_n2 + 3^n2) + 3^n1

= … =

s

₁ + (33²...3^n1)

= 2 +

1 3

1 .3 3

1



 

n

= 2 1 3ⁿ .

Công thức này đúng cho cả trường hợp n = 1 nên số nghiệm của phương trình 0

) (x 

f_n là

s

_n= 2

1

3ⁿ  với mọi n  N*.

Bài toán 4. Cho số tự nhiên n  N*. Xét tổng S = x1y1 + x2y2 + … + xnyn trong đó xi, yi  {0; 1} với mọi giá trị i = 1, 2, …n. Gọi A, B tương ứng là số các tổng trên mà S là lẻ và chẵn. Chứng minh rằng:

1 2

1 2



 _nⁿ B

A .

Lời giải. Đặt Sn = x1y1 + x2y2 + … + xnyn trong đó xi, yi  {0; 1} với mọi i = 1, 2, … n. Gọi An, Bn là số các tổng mà Sn tương ứng là lẻ và chẵn, ta có ngay A1 = 1, B1 = 3.

Với n > 1, thì do Sn = Sn–1 + xnyn và có ba bộ (xn, yn) làm cho xnyn chẵn (bằng 0) và chỉ một bộ (xn, yn) làm cho xnyn lẻ nên ta có:

An = 3.An–1 + Bn–1 và Bn = An + 3.Bn–1.

Chúng ta có thể tính An, Bn trong trường hợp này bằng cách đưa về dãy truy hồi tuyến tính cấp hai và dùng phương trình đặc trưng, nhưng ta có thể viết:

An + Bn = 4(An–1 + Bn–1) = … = 4^n–1(A1 + B1) = 4ⁿ và An – Bn = 2(An–1 – Bn–1) = … = 2^n–1(A1 – B1) = – 2ⁿ. Lần lượt cộng và trừ từng vế cho nhau ta được:

An = 2^n–1(2ⁿ – 1) và Bn = 2^n–1(2ⁿ + 1) với mọi n  1.

Từ đó

1 2

1 2



 

 _nⁿ

n n

B A B

A . Bài toán được chứng minh.

Bài toán 5. Cho số nguyên dương n. Có bao nhiêu số tự nhiên có n chữ số, chia hết cho 3 với các chữ số đều thuộc tập hợp



3;4;5;6



?

Lời giải. Gọi An là tập hợp các số tự nhiên cho n chữ số lập từ các chữ số trong tập



3;4;5;6



, chia hết cho 3; Bn là tập hợp các số tự nhiên cho n chữ số lập từ các chữ số trong tập



^3;4;5;6



và không chia hết cho 3. Đặt a_n  A_n và b_n  B_n . Ta cần tính a_n.

Một số thuộc tập A_n1 chỉ có thể thu được theo hai trường hợp sau đây:

+ Trường hợp 1: Lấy một số thuộc A_n rồi thêm số 3 hoặc 6 vào phía sau.

+ Trường hợp 2: Lấy một số thuộc B_n rồi thêm đúng một trong hai số 4 hoặc 5 vào sau số đó.

Như vậy ta có: A_n1 2A_n  B_n hay a_n12a_n b_n (1).

Tương tự với các số thuộc tập B_n1 ta cũng có b_n12a_n 3b_n (2).

Từ (1) ta có b_n a_n12a_n và b_n1 a_n2 2a_n1 thay vào (2) được



_{n n}



n n

n a a a a

a _2 2 _1 2 3 _12 hay a_n2 5a_n14a_n với mọi n1.

Tính trực tiếp được a₁2 và a₂ 6, cùng với hệ thức truy hồi trên ta có kết quả cần tính là

3 2 4 

 ⁿ

an với mọi n1.

Bài toán 6. Cho các điểm A1, A2, …, An với n  2 theo thứ tự đó nằm trên một đường thẳng. Người ta tô màu tất cả các điểm này bởi 5 màu: xanh, đỏ, vàng, cam và tím thoả mãn hai điều kiện:

+) mỗi điểm tô một màu

+) hai điểm Ai, Ai+1 (i = 1, 2, …, n  1) thì hoặc luôn được tô cùng màu hoặc là một trong hai điểm được tô màu xanh.

Hỏi có bao nhiêu cách tô như vậy?

Lời giải. Gọi an là số cách tô thoả mãn điều kiện có điểm cuối được tô xanh, bn là số cách tô thoả mãn điều kiện có điểm cuối không được tô xanh. Ta tính trực tiếp được a2 = 5, b2

= 8. Xét khi n > 2:

Rõ ràng khi An được tô xanh thì An1 có thể được tô xanh hoặc không xanh nên an = an1 + bn1 (1).

Nếu An không được tô xanh thì nó được tô bởi một trong 4 màu còn lại và An1 phải được tô xanh hoặc cùng màu với An (khác màu xanh). Từ đó suy ra

bn = 4an1 + bb1 (2).

Kết hợp (1), (2) cùng với a2 = 5, b2 = 8 ta có:

2an + bn = 3(2an1 + bn1) = … = 3^n2(2a2 + b2) = 3^n2.18 = 2.3ⁿ và bn 2an = (1)(bn12an1) = … = (1)^n2(b2  2a2) = 2.(1)ⁿ. Giải hệ này ta được an =

2 ) 1 ( 3ⁿ  ⁿ

, bn = 3ⁿ(1)ⁿ với mọi n  2. Vậy số cách tô màu cần tìm là:

S = an + bn = 2

) 1 (

3^n1  ⁿ với mọi n  2.

Bài toán 7. Cho số tự nhiên n > 1. Gọi f_n là số các hoán vị (a1,a2, …, an) của (1, 2,

…, n) thoả mãn điều kiện: a₁ = 1 và a_ia_i1 2 với mọi i = 1, 2, …, n  1. Xác định số dư khi chia f₂₀₁₄ cho 3.

Lời giải. Ta có f₂ = 1, f₃ = 2, f₄ = 4. Với n  5, xét một hoán vị có tính chất trong đề bài toán. Vì a₁a₂ = 1a₂  2 nên a₂ = 2 hoặc

a

₂ = 3.

+) Nếu a₂ = 2 thì (a2, a3 …, an) cũng là một hoán vị của (2, 3, …, n) thoả mãn

1 2

 _i

i a

a với mọi i = 2, 3, …, n  1. Do vậy số lượng hoán vị dạng này là f_n1.

+) Nếu a₂ = 3 thì a₃ {2, 4, 5}. Giả sử a_k = 2 với 3 < k < n thì lúc đó a_k12 2 và 2a_k1 2 suy ra a_k1 a_k1 4, mâu thuẫn. Do đó a₃ = 2 hoặc a_n = 2.

i) Nếu a₃ = 2  a₄ = 4  (a4, …, an) cũng là một hoán vị của (4, 5, …, n) thoả mãn a_i a_i1 2 với mọi i = 4, 3, …, n  1. Do vậy số lượng hoán vị dạng này là f_n3.

ii) Nếu a_n = 2 thì a_n1 = 4, mà a₃ {2, 4, 5} nên a₃ = 5. Khi đó lý luận tương tự liên tiếp ta sẽ có a_n2 = 6, a₄ = 7, …, a_nk 2k2, a_k 2k1… Trường hợp này chỉ có một hoán vị duy nhất.

Như vậy ta có: f₂ = 1, f₃ = 2, f₄ = 4 và f_n = f_n1 + f_n3 +1 với mọi n  5. Ta bổ sung thêm f₁ = 1 thì dãy {f_n mod 3}^_n1 tuần hoàn chu kỳ 8 với bộ lặp là (1, 1, 2, 1, 0, 0, 2, 0).

Từ đây ta được: 0f₂₀₁₄  f₆  (mod 3) hay f₂₀₁₄ chia hết cho 3.

Bài toán 8. Cho một tứ diện đều ABCD có cạnh là 1 mét. Một con bọ xuất phát từ đỉnh A, di chuyển theo quy tắc: tại mỗi đỉnh nó đến nó sẽ chọn một trong 3 cạnh tại đỉnh đó để di chuyển theo cạnh đó đến đỉnh khác. Tìm số cách đi để con bọ trở lại đỉnh A khi nó đã đi được đúng n mét với n  N*.

Lời giải. Gọi a_n, b_n, c_n, d_n là số cách đi để đúng sau khi đi được n mét con bọ sẽ tương ứng đến A, B, C, D. Với mỗi n > 1,

i) Do tính đối xứng của các đỉnh B, C và D nên bn =

c

_n = d_n, (1)

ii) Muốn đi đến A phải từ B, C hoặc D đi thêm 1 mét nữa nên:

an = b_n1 + c_n1 + d_n1, (2) iii) Tương tự: b_n = a_n1 + c_n1 + d_n1 (3)

Từ (1) và (2) ta có: a_n = 3b_n1  a_n1 = 3b_n. Kết hợp với (3) ta được: a_n1 = 3b_n = 3(a_n1 + c_n1 + d_n1) =

= 3(a_n1 + 2b_n1) = 3a_n1 + 2a_n B

A

C D

hay là

1

an = 2a_n + 3a_n1 với mọi n > 1.

Dãy số này có phương trình đặc trưng t² 2t3, có các nghiệm t3 và t1 nên số hạng tổng quát của dãy có dạng:

n n

n A B

a  .3  .(1) với mọi n  N*.

Kết hợp với a₁ = 0, a₂ = 3 ta tính được kết quả:

an = 4

) 1 .(

3

3ⁿ  ⁿ với mọi n  N*.

Bài toán 9. Cho số tự nhiên n  N* và có n cặp vợ chồng tham gia lễ hội hoá trang.

Có bao nhiêu cách ghép họ thành n cặp nhảy sao cho không có cặp nào là vợ chồng?

Lời giải. Ký hiệu các cặp vợ chồng là C1, V1, …, Cn, Vn và sn là số cách sắp xếp n cặp nhảy sao cho không có cặp nào là vợ chồng. Với n  3, vì có n  1 cách sắp xếp Cn với Vi (i  n) nên ta xét hai trường hợp:

Trường hợp 1: ghép Cn với Vi (i  n) và ghép Ci với Vn. Khi đó có n  1 cách ghép Cn với Vi , loại đi 2 cặp Cn, Vn; Ci , Vi có sn2 cách ghép n  2 cặp còn lại. Trường hợp này sẽ có (n1)sn2 cách.

Trường hợp 2: ghép Cn với Vi (i  n) và không ghép Ci với Vn. Khi đó cũng có n  1 cách ghép Cn với Vi, loại đi hai người đó, ghép tuỳ ý những người còn lại sẽ có n  1 cách.

Trường hợp này sẽ có (n1)sn1 cách.

Do vậy, kết hợp cả hai trường hợp trên ta có hệ thức truy hồi:

sn = (n1)(sn1 + sn2) với mọi n  3.

Đây là dãy truy hồi cấp hai không phải hệ số hằng nhưng ta có thể làm theo cách sau đây:

Biến đổi



1 2



1 _ ( 1) _

   

 _{n n n}

n ns s n s

s = … =

 

1^n2



s₂1.s₁



Tính trực tiếp được s1 = 0, s2 = 1, thay vào ta có:

1

 _n

n ns

s =

 

^{1n }

! ) 1 ( )!

1 (

!

1

n n

s n

s_{n n}   ⁿ

 ^ Từ đây suy ra

! n s_n =

! ) 1 ... (

! 2 1

! 1 1 1

n

 n







 .

Vậy cuối cùng ta có: 

 



     

 !

) 1 ... (

! 2 1

! 1 1 1

! n

n s

n

n với mọi n  N*.

Bài toán 10. Tìm số các dãy n phần tử x₁x₂...x_n trong đó

x

_i  {0, 1, 2} sao cho số phần tử 1 trong mỗi dãy đó là một bội số của 3.

Lời giải. Ta gọi một dãy n phần tử x₁x₂...x_n với

x

_i {0, 1, 2} là một n  dãy và gọi an, b_n, c_n là số các n  dãy mà có số phần tử 1 khi chia cho 3 tương ứng được số dư là 0, 1, 2. Với n  2, xét một n  dãy có số phần tử 1 chia hết cho 3.

+) Nếu x_n  {0, 2} thì (n1)  dãy x₁x₂...x_n1 cũng có số phần tử 1 chia hết cho 3.

+) Nếu x_n = 1 thì (n1)  dãy x₁x₂...x_n1 có số phần tử 1 chia cho 3 dư 2.

Từ đó ta có a_n = 2a_n1 + c_n1 (1)

Hoàn toàn tương tự cũng ta có : b_n = 2b_n1+ a_n1 (2) và c_n = 2c_n1 + b_n1 (3).

Một mặt khác, số lượng n  dãy là: a_n + b_n + c_n = 3 (4). ⁿ Từ (4) suy ra b_n = 3  ⁿ a_n  c_n . Thay vào (3) được:

cn = 2

c

_n1 + b_n1 = 2c_n1 + 3^n1 

a

_n1 

c

_n1 =

3

^n1 

a

_n1 +

c

_n1. Khi đó từ (1) ta có a_n  2a_n1 = c_n1 nên:

a_n1  2a_n = c_n = 3^n1  a_n1 + c_n1 =

= 3^n1  a_n1 + (a_n  2a_n1) = 3^n1 + a_n  3a_n1 hay a_n1  3a_n + 3a_n1 = 3^n1.

Từ đây, đặt u_n = a_n  3^n1 thì ta được: u_n1  3u_n + 3u_n1 = 0. Phương trình đặc trưng của dãy này là x²3x30 có hai nghiệm phức

2 3 3

1

x   i và

2 3 3

2

x   i = x₁.

Theo dạng lượng giác thì 



 



 

 sin6

cos6

1 3



 i

x nên nghiệm tổng quát của dãy

 

u_n là

 





 



 

 sin 6

cos 6

3  n

n B A

u_n ⁿ với mọi n ≥ 1. Hơn nữa từ a₁2, a₂ 4 ta có u₁1,

2 1

u do đó tính được 3

 2

A , B0. Vì vậy ta có ^un ²

 

^{3 n 2cosn}₆^

  với mọi n  N* hay

kết quả cần tìm là a_n =

 

cos 6 3

2 ^n2 n

+ 3^n1 với mọi n  N*.

III. MỘT SỐ BÀI TOÁN LUYỆN TẬP

Bài toán 11. Trong mặt phẳng cho n đường tròn (n  N*) trong đó bất kỳ hai đường tròn nào cũng cắt nhau tại hai điểm phân biệt và không có ba đường nào có điểm chung. Tính số phần mặt phẳng mà các đường tròn đó chia ra.

Đáp số: n² – n + 2 phần với mọi n  N*.

Bài toán 12. Có bao nhiêu xâu gồm n ký tự (n  1) với các kí tự 0, 1, 2 sao cho không có hai ký tự 0 đứng cạnh nhau.

Hướng dẫn: Gọi sn là số các xâu như thế. Tính được s1 = 3, s2 = 8 và hệ thức truy hồi sn = 2s_n1 + 2s_n2 với mọi n  3. Suy ra được kết quả

sn =



^{(1 3) 2 (1 3) 2}



3 4

1  ⁿ   ⁿ với mọi n  N*.

Bài toán 13. Có n học sinh n  2 tham gia kỳ thi trắc nghiệm được bố trí ngồi trên một bàn tròn. Đề thi trắc nghiệm có m mã đề (m  2). Hỏi có bao nhiêu cách phát đề cho các thí sinh sao cho hai thí sinh gần nhau đều nhận được hai đề có mã khác nhau.

Hướng dẫn: Gọi Sn là số cách phát đề thoả mãn bài toán.

Tính trực tiếp được S2 = m(m  1) và S3 = m(m  1)(m  2) và hệ thức truy hồi:

Sn = (m  2)Sn1 + (m  1)Sn2 với mọi n  4.

Kết quả: Sn = (m1)ⁿ(m1)(1)ⁿ với mọi n  2.

Bài toán 14. Một con ếch nhảy từ đỉnh A đến đỉnh đối tâm E của một hình bát giác đều. Tại mỗi đỉnh của bát giác trừ đỉnh E, con ếch nhảy một bước đến một trong hai đỉnh kề với nó. Khi đến đỉnh E con ếch dừng lại và ở luôn tại đó luôn. Gọi

u

_n là số đường đi phân biệt của con ếch đi từ A đến E bằng đúng n bước nhảy.

Chứng minh rằng: 0u_2n1 và u_2n =



^{(2 2) 1 (2 2) 1}



2

1  ⁿ   ⁿ .

Bài toán 15. Cho số nguyên dương n, ký hiệu T là tập hợp gồm 2n số nguyên dương đầu tiên. Hỏi có bao nhiêu tập con S của T có tính chất: trong S không tồn tại các số a, b mà

 

n b

a  1; . (Lưu ý rằng tập rỗng là tập con có tính chất nên trên).

Đáp số:

       

4

1 2 2 1 2 3 2 1 2

3 ^{n n n}

un         với mọi n  1.

C. KẾT LUẬN

Bài toán tổ hợp trong các đề thi học sinh giỏi là bài toán khó. Để giải quyết được nó, ngoài việc nắm vững những kiến thức cơ bản còn cần những phương pháp hợp lý và sự sắc bén của tư duy. Trong các ví dụ minh hoạ trên đây, chúng tôi đã cố gắng phân tích hoặc trình bày lời giải một cách tường minh nhất để người đọc dễ theo dõi. Các bài toán luyện tập cũng được hướng dẫn hoặc cho đáp số cụ thể. Do khuôn khổ bài viết cũng như sự hạn chế về thời gian và khả năng của tác giả nên sẽ không tránh khỏi được những thiếu sót. Rất mong người đọc lượng thứ và đóng góp những ý kiến quý báu để người viết bổ sung, sửa chữa. Chúng tôi xin chân thành cảm ơn!

Hà Tĩnh, tháng 8 năm 2014