Một số phương pháp cơ bản giải toán tổ hợp

MỘT SỐ PHƯƠNG PHÁP CƠ BẢN GIẢI TOÁN TỔ HỢP
I. Phương pháp đếm nhiều lần.
 Cơ sở của phương pháp này là tính chất sau :
 Tính chất: Cho tập S gồm hữu hạn phần tử, khi đó mọi cách đếm số phần tử của S đều cho một kết quả.
 Tính chất này thường được áp dụng cho bài toán chứng minh một đẳng thức tổ hợp. Ta chia một tập S thành các tập con không giao nhau :
, với .
Khi đó
.
 Ví dụ 1: CMR với thì .
 Lời giải:
Cách giải đã biết: Khai triển rồi so sánh hệ số của ở hai vế.
 Cách giải khác: Đếm số cách chọn n phần tử từ 2n phần tử.
	Chọn trực tiếp n phần tử từ 2n phần tử ta có số cách chọn là .
	Chọn n phần tử từ 2n phần tử bằng cách chọn k phần tử từ n phần tử đầu và n-k phần tử từ n phần tử cuối. Khi đó số cách chọn với mỗi k là . Cho k chạy từ 0 đến n ta có ĐPCM.
Nhận xét:
Đây chỉ là một cách giải khác cho một dạng toán đã biết cách giải, tuy vậy có thể giúp học sinh có thêm nhiều sự lựa chọn trong bài làm của mình, nhất là đối với các học sinh cho rằng các công thức tổ hợp là rắc rối và khó áp dụng.
Tương tự với cách nhìn nhận như vậy, giáo viên có thể tự sáng tạo thêm nhiều đẳng thức cho học sinh làm bài tập.
Trong những ví dụ sau, chúng ta cần những kĩ thuật cao hơn để giải các bài toán Olimpic, cụ thể là phương pháp đếm đặc biệt trên các tập sắp thứ tự.
Ví dụ 2: CMR với thì :
Lời giải:
Xét số . Đếm số các bộ phần tử trong số trên. Rõ ràng ta có thể sắp thứ tự số này mà không làm ảnh hưởng đến kết quả của phép đếm. Như vậy sẽ có bộ như vậy. Xét cách đếm thứ 2 như sau: 
Bộ có thể viết rõ theo dạng :
Cố định :
Ta thấy vì bộ là các số từ đến có sắp thứ tự nên có thể nhận các giá trị với .
 Nếu thì , từ đó ta suy ra được số cách chọn số đầu tiên là và nên số cách chọn số sau là . Cho chạy từ đến k ta có ĐPCM.
Ví dụ 3: 
Cho các số nguyên dương, CMR .
Lời giải:
Con số gợi ý đến số tập con của tập có phần tử. từ đó ta có thể xét tập có số tập con là .
Phân tích : Tích cho ta liên hệ tới phép đếm thứ 2 như sau: 
 Coi là số tập con có n phần tử của , thêm vào đó phần tử thứ là , khi đó còn lại số và có tập con. Thêm các tập con đó vào tập có phần tử ở trên, theo đó, tích chính là số tập con có hơn n phần tử.
Đến đây ta thấy bài toán có thể trình bày như sau:
Xét các tập con của S có nhiều hơn n phần tử, trong đó ta sẽ cố định , với k chạy từ đến m. Khi đó số tập con như vậy thoả mãn là . Lấy tổng khi k chạy từ đến m, ta được số các tâp con có nhiều hơn n phần tử là . 
Tương tự, là số tập con có nhiều hơn m phần tử, hay nói cách khác là có không quá n phần tử.
Từ 2 nhận xét trên ta suy ra ĐPCM.
II. Phương pháp sử dụng song ánh
Ta nhắc lại một số kiến thức sau:
Cho hai tập X,Y và một ánh xạ f từ X tới Y.
f được gọi là đơn ánh nếu 
f được gọi là toàn ánh nếu 
f được gọi là song ánh nếu nó vừa là toàn ánh vừa là đơn ánh.
Mệnh đề: Cho hai tập X và Y có hữu hạn phần tử. Nếu có một song ánh từ X tới Y thì số phần tử của X bằng số phần tử của Y.
Ta xét một số ví dụ áp dụng:
Ví dụ 1: Cho một nhóm người mà trong đó mỗi cặp không quen nhau có đúng hai người quen chung, còn mỗi cặp quen nhau thì không có người quen chung. Chứng minh rằng số người quen của mỗi người là bằng nhau.
Lời giải: 
Giả sử a quen b và tập các người quen của a và b (không kể a, b) là A và B. Khi đó, mỗi người a’ thuộc A sẽ không quen b(do a và b không có người quen chung) nên ngoài người quen chung thứ nhất là a, họ chỉ có một người quen chung thứ hai b’, và rõ ràng b’ nằm trong B. từ đó, ta suy ra nếu a’ nằm trong A thì a’ quen với duy nhất một người trong B, tương tự ta cũng có nếu b’ nằm trong B thì b’ quen với duy nhất một người trong A. Và cuối cùng ta suy ra có một song ánh đi từ A tới B, số người quen của a và b là như nhau.
Nếu a không quen b thì họ có một người quen chung là c, và theo trên ta có a,b sẽ có cùng số người quen với c. Từ đó suy ra ĐPCM.
Ví dụ 2: Trong các xâu nhị phân có độ dài n, gọi A là số các xâu không chứa 3 số liên tiếp 0,1,0 và B là số các xâu có độ dài không chứa 4 số liên tiếp 0,0,1,1 hoặc 1,1,0,0. CMR B=2A.
Lời giải:
	Với mỗi xâu , xây dựng như sau: . Rõ ràng X thuộc A khi và chỉ khi Y thuộc B. Như vậy có một song ánh đi từ A tới các phần tử của B bắt đầu bằng 0. Từ mỗi xâu của B bắt đầu bằng 0 có tương ứng với một xâu cũng thuộc B theo quy tắc nên ta suy ra ngay được là số phần tử của B bằng hai lần số phần tử của A. ĐPCM.
Ví dụ 3: Cho tập S gồm các số nguyên dương trong đoạn . Gọi T là tập tất cả các tập con khác rỗng của S. Với mỗi X trong T, kí hiệu m(X) là trung bình cộng của các phần tử của X. Tính , với lấy theo tất cả các tập X thuộc T (VMO-2003).
Lời giải:
Xây dựng song ánh như sau: , rõ ràng f là song ánh và , từ đó suy ra 
III. Phương pháp truy hồi
Trong các bài toán đếm có yêu cầu tính đại lượng f phụ thuộc n (fn), ta có thể dùng công thức truy hồi tính fn theo các đại lượng fn-1,fn-2,
Ta xét một số ví dụ sau để thấy rõ hiệu quả cũng như cách áp dụng phương pháp này. Bắt đầu bằng một ví dụ đơn giản.
Ví dụ 1: Cho số nguyên , tìm số các hoán vị của sao cho tồn tai duy nhất một chỉ số để .
Lời giải:
Gọi là số các hoán vị thoả mãn bài toán. Chú ý rằng số các hoán vị để chính bằng số các hoán vị của sao cho tồn tai duy nhất một chỉ số để vì . Hay số hoán vị để bằng . Còn nếu thì số hoán vị chính bằng số cách chọn ra phần tử trong phần tử còn lại để xếp ra trước () phần tử còn lại sẽ xếp ra sau (hiển nhiên). Và ta đựơc . Dùng quy nạp ta tính được .
Ví dụ 2: Cho A và E là hai đỉnh đối diện của một hình tám cạnh đều. Tại 1 đỉnh khác đỉnh E, ếch có thể nhảy tới các đỉnh kề của nó. Nếu tới E, ếch bị kẹt tại đó. Gọi là số đường đi của ếch để nó đến E sau n bước nhảy. CMR
(IMO-79)
Lời giải:
Kí hiệu các đỉnh như hình bên
 là hiển nhiên.
Gọi là số đường đi từ C(hoặc G) tới E sau n bước nhảy. Qua hai bước đầu tiên, ếch có 2 cách để về A hoặc 1 cách tới C hoặc G. Như vậy ta có :
(1)
Sau 2 bước tiếp theo, tại C hoặc G với (ếch chưa tới E ngay), ếch có 2 cách nhảy về C và 1 cách nhảy về A. Từ đây ta cũng suy ra:
(2)
Từ (1) và (2) ta suy ra và do đó . Để ý rằng và dùng phương trình đặc trưng ta suy ra ĐPCM.
Ví dụ 3: Có bao nhiêu cách tô m màu cho n điểm trên đường tròn sao cho 2 điểm kề nhau thì có màu khác nhau? (VPMO-08)
Lời giải:
Bài toán tương đương việc đếm số các dãy sao cho . 
Trong tập các dãy sao cho . . Gọi và lần lượt là tập các dãy sao cho và . Yêu cầu bài toán tương đương việc tính số phần tử của . Ta có hai nhận xét sau: 
Với mỗi dãy thuộc , ta bỏ đi phần tử thì sẽ được một dãy thuộc , hay .
Số phần tử của là (Chọn có m cách, , có m-1 cách) mà nên 
Từ hai nhận xét ở trên, ta suy ra được rằng , mà .
IV. Ứng dụng số phức để giải toán tổ hợp
	Ta nhắc lại một số kiến thức sau:
Phương trình có p nghiệm phức .
Pt có p-1 nghiệm là , với .
Gọi là một nghiệm bất kì của phương trình thì tập nghiệm của pt là . Ngoài ra là một hoán vị của với .
Cho đa thức . Với ta có:
Vì nên tổng của các là .
Cho , . Khi đó
Ta xét một số áp dụng:
Ví dụ 1: Cho p là một số nguyên tố lẻ và số nguyên dương n nguyên tố cùng nhau với p. Tìm số các bộ gồm là số tự nhiên sao cho tổng chia hết cho p trong đó mỗi số đều không lớn hơn n-1.
Lời giải:
Xét đa thức và đặt 
Bằng cách triển khai đa thức F(x) ta có thể viết trong đó là số các bộ , với mỗi sao cho . Vậy số các bộ gồm p-1 số tự nhiên thoả mãn điều kiện bài toán, bằng tổng của các số với k chia hết cho p. Ta biết rằng tổng của các số với k chia hết cho p bằng với 
Chú ý rằng nếu và với k, j = 1, 2,, p-1. Do đó với k, j = 1, 2,, p-1.
 Nhân các đẳng thức trên với , ta được
 với .
 Vì nên suy ra . Chú ý rằng , từ đó số các bộ thoả mãn điều kịên bài toán là .
 Ví dụ 2: Cho ba số nguyên dương m, n, p trong đó chia hết cho m và m lớn hơn p. Tìm số các bộ gồm p số nguyên dương sao cho tổng chia hết cho m, trong đó mỗi số đều không lớn hơn n.
Lời giải:
 Xét đa thức , trong đó là các bộ với . Vậy số các bộ thoả mãn yêu cầu bài toán bằng tổng của các số với . Mà với . Ta có : 
- với .
- Vì nên .
Để ý rằng với . Từ đó ta suy ra:
Lấy tổng với j chạy từ 1 đến m-1, ta được 
Để ý rằng k không chia hết cho m với , vì và:
Nên 
Chú ý rằng , từ đó suy ra số các bộ thoả mãn bài toán là:
.
V. Một số bài tập
 B1: CMR .
 B2: CMR 
 B3: CMR .
 B4: CMR 
B5:
Người ta xếp n nam sinh và n nữ sinh thành 1 hàng rồi tìm cách cắt thành hai khúc sao cho mỗi khúc có số nam sinh bằng số nữ sinh. Gọi A là số cách xếp mà không thể cắt khúc được, B là số cách xếp mà chỉ có thể cắt theo 1 cách duy nhất, CMR .
B6:
Tính trung bình cộng các số N gồm n>1 chữ số thoả mãn các điều kiện:
N chỉ gồm các chữ số 1,2,4,5 và hiệu hai số liền nhau luôn lớn hơn 1
N chia hết cho 11.
B7:
Gọi là số hoán vị của tập có đúng k điểm cố định. CMR
.(IMO-87)
B8:
Tính trung bình cộng của tất cả các số N gồm 2008 chữ số thoả mãn và N chỉ chứa các chữ số 1,2,3,4,5.
B9:
Tìm số tập con của tập gồm 1,2,,n sao cho trong mỗi tập con đó chứa ít nhất 2 phần tử là hai số tự nhiên liên tiếp.
B10:
N đường tròn chia mặt phẳng thành bao nhiêu phần nếu bất cứ cặp đường tròn nào cũng xắt nhau tại 2 điểm và không có 3 đường tròn nào có điểm chung.(VMO-97)
 B 11:
Cho p là một số nguyên tố lẻ và số nguyên dương n. Tìm số các bộ gồm p-1 số tự nhiên sao cho tổng chia hết cho p, trong đó mỗi số không lớn hơn n-1.
B 12:
Cho p là một số nguyên tố lẻ và n nguyên dương lớn hơn 2p. Tìm số các tập con X của tập , biết rằng X chứa đúng 2p phần tử và tổng các phần tử của X chia hết cho p.
B 13:
Cho 2 số nguyên dương m và n trong đó . Tính số các bộ 5 số nguyên dương {x,y,z,t,u} thoả mãn điều kiện tổng 5 số chia hết cho m, trong đó mỗi số đều không lớn hơn n.
B 14:
Cho p là một số nguyên tố lẻ. Tìm số các tập con X của , biết rằng X có p phần tử và tổng các phần tử của X chia cho p có số dư là 1.