Ktl-icon-tai-lieu

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

Được đăng lên bởi Ngô Minh Tú
Số trang: 3 trang   |   Lượt xem: 3563 lần   |   Lượt tải: 15 lần
Phương pháp truy hồi trong bài toán tổ hợp
Trần Văn Minh Chiến – ĐHSP Hà Nội
Email: Sptoanchien@gmail.com
Tổ hợp là một trong những dạng toán hay và khó, thường gặp trong những đề thi
chọn học sinh giỏi. Bài viết này giới thiệu với các bạn một phương pháp khá hiệu quả
trong việc giải một bài toán tổ hợp, đặc biệt là các bài toán đếm, đó là phương pháp truy
hồi.
Đặc trưng của phương pháp này là phải thiết lập được hệ thức truy hồi giữa phép
đếm cần tính Sn với Sn-1, Sn-2,… Qua việc giải hệ thức truy hồi ta sẽ xác định được S n. Để
xác định công thức tường minh của S n qua hệ thức truy hồi ta có thể dùng một số phương
pháp như sai phân, hàm sinh…
Sau đây là một số ví dụ:
Bài toán 1:
Xếp n học sinh ngồi quanh một bàn tròn. Ngăn hàng đề có tất cả m loại đề thi. Hỏi
có bao nhiêu cách phát đề cho học sinh sao cho không có 2 học sinh nào ngồi cạnh nhau
có cùng đề thi?
Lời giải:
 Gọi Sn là số cách phát đề cho học sinh sao cho không có 2 học sinh nào ngồi cạnh
nhau có cùng đề thi
 Cố định một học sinh làm vị trí đầu tiên và các học sinh bên tay phải của học sinh
đó là vị trí thứ 2, thứ 3,…, thứ n.( học sinh ở vị trí thứ n ngồi cạnh học sinh ở vị
trí thứ nhất)
 Ta thấy:
Nếu học sinh ở vị trí thứ nhất và học sinh ở vị trí thứ n-1 có đề thi khác nhau
thì sẽ có m-2 cách phát đề cho học sinh ở vị trí thứ n.
Nếu học sinh ở vị trí thứ nhất và học sinh ở vị trí thứ n-1 có đề thi giống nhau
thì có m-1 cách phát đề cho học sinh ở vị trí thứ n.
 Do đó ta có hệ thức:
Sn = (m-2)Sn-1 + (m-1)Sn-2
(n ≥ 4)
 Sử dụng phương pháp sai phân để tính Sn. Xét phương trình đặc trưng:
x2 - (m-2)x - (m-1) = 0
↔x = -1˅ x = m-1
Sn = a(-1)n + b(m-1)n
 Do
S2
=
m(m-1),
S3
=
m(m-1)(m-2),
suy
ra:
2
a+ b(m-1) = m(m-1) và
-a +b(m-1)3= m(m-1)(m-2)
=>a=m-1 và b=1
 Vậy Sn = (m-1)(-1)n + (m-1)n
(n≥2) ▄
Bài toán 2:
Cho A và E là 2 đỉnh đối tâm của 1 hình bát giác đều. Một con ếch bắt đầu nhảy từ
A. Tại bất cứ đỉnh nào trừ E, con ếch có thể tới một trong 2 đỉnh kề. Nếu ếch nhảy tới E
thì nó dừng lại. Tính số cách để ếch nhảy từ A tới E mất đúng n bước.(n>4)
Lời giải:





Gọi an là số cách để ếch nhảy từ A đến E mất đúng n bước.(n>4)
Dễ thấy a2n-1=0, n≥1 (vì để nhảy từ A tới E cần một số chẵn bước nhảy).
Sau 2 bước nhảy, ếch chỉ có thể đên B hoặc C hoặc trở về A. Do đó:

a2n= 2(a2n-2+ b2n-2)
trong đó: bn là số cách nhảy để ếch nhảy từ B( hoặc C) đến E mất đúng n bước.


Từ B (hoặc C), sau 2 bước nhảy ếch chỉ có thể trở về B hoặc đến A (do n>4). Suy
ra:

b2n = 2b2n-2 + an-2


Từ 2 hệ thức truy h...
Phương pháp truy hồi trong bài toán tổ hợp
Trần Văn Minh Chiến – ĐHSP Hà Nội
Email: Sptoanchien@gmail.com
Tổ hợp một trong những dạng toán hay khó, thường gặp trong những đề thi
chọn học sinh giỏi. Bài viết này giới thiệu với các bạn một phương pháp khá hiệu quả
trong việc giải một bài toán tổ hợp, đặc biệt các bài toán đếm, đó phương pháp truy
hồi.
Đặc trưng của phương phápy phải thiết lập được hệ thức truy hồi giữa phép
đếm cần tính S
n
với S
n-1
, S
n-2
,… Qua việc giải hệ thức truy hồi ta sẽ xác định được S
n
. Để
xác định công thức tường minh của S
n
qua hệ thức truy hồi ta có thể dùng một số phương
pháp như sai phân, hàm sinh…
Sau đây là một số ví dụ:
Bài toán 1:
Xếp n học sinh ngồi quanh một bàn tròn. Ngăn hàng đề có tất cả m loại đề thi. Hỏi
bao nhiêu cách phát đề cho học sinh sao cho không có 2 học sinh nào ngồi cạnh nhau
có cùng đề thi?
Lời giải:
Gọi S
n
là số cách phát đề cho học sinh sao cho không có 2 học sinh nào ngồi cạnh
nhau có cùng đề thi
Cố định một học sinh làm vị trí đầu tiên và các học sinh bên tay phải của học sinh
đó vị trí thứ 2, thứ 3,…, thứ n.( học sinh vị trí thứ n ngồi cạnh học sinh vị
trí thứ nhất)
Ta thấy:
Nếu học sinh vị tthứ nhất và học sinh ở vị trí thứ n-1 có đề thi khác nhau
thì sẽ có m-2 cách phát đề cho học sinh ở vị trí thứ n.
Nếu học sinh ở vị trí thứ nhất và học sinh ở vị trí thứ n-1 có đề thi giống nhau
thì có m-1 cách phát đề cho học sinh ở vị trí thứ n.
Do đó ta có hệ thức:
S
n
= (m-2)S
n-1
+ (m-1)S
n-2
(n ≥ 4)
Sử dụng phương pháp sai phân để tính S
n
. Xét phương trình đặc trưng:
x
2
- (m-2)x - (m-1) = 0
↔x = -1˅ x = m-1
S
n
= a(-1)
n
+
b(m-1)
n
Do S
2
= m(m-1), S
3
= m(m-1)(m-2), suy ra:
a+ b(m-1)
2
= m(m-1) và
-a +b(m-1)
3
= m(m-1)(m-2)
=>a=m-1 và b=1
Vậy S
n
= (m-1)(-1)
n
+ (m-1)
n
(n≥2) ▄
Bài toán 2:
Cho A và E là 2 đỉnh đối tâm của 1 hình bát giác đều. Một con ếch bắt đầu nhảy từ
A. Tại bất cứ đỉnh nào trừ E, con ếchthể tới một trong 2 đỉnh kề. Nếu ếch nhảy tới E
thì nó dừng lại. Tính số cách để ếch nhảy từ A tới E mất đúng n bước.(n>4)
Lời giải:
Phương pháp truy hồi trong bài toán tổ hợp - Trang 2
Phương pháp truy hồi trong bài toán tổ hợp - Người đăng: Ngô Minh Tú
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
3 Vietnamese
Phương pháp truy hồi trong bài toán tổ hợp 9 10 874