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

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ 
TRƯỜNG THPT MAI ANH TUẤN
SÁNG KIẾN KINH NGHIỆM
MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN TỔ HỢP
Người thực hiện: Đào Anh Tuấn
Chức vụ: Giáo viên
SKKN thuộc lĩnh mực (môn): Toán
THANH HÓA, NĂM 2018
g
SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ 
TRƯỜNG THPT MAI ANH TUẤN
SÁNG KIẾN KINH NGHIỆM
MỘT SỐ PHƯƠNG PHÁP GIẢI BÀI TOÁN TỔ HỢP
Người thực hiện: Đào Anh Tuấn
Chức vụ: Giáo viên
SKKN thuộc lĩnh mực (môn): Toán
THANH HÓA, NĂM 2018
MỤC LỤC
 Nội dung
 Trang
1. Mở đầu
1
1.1. Lí do chon đề tài
1
1.2. Mục đích nghiên cứu
1
1.3. Đối tượng nghiên cứu
1
1.4. Phương pháp nghiên cứu
2
2. Nội dung của sáng kiến
2
2.1. Cơ sở lí luận của sáng kiến
2
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến
2
2.3. Nội dung chính của sáng kiến
2
Chương 1: Kiến thức cơ sở
2
1.1 Hoán vị, chỉnh hợp, tổ hợp
2
1.2 Hoán vị, chỉnh hợp, tổ hợp suy rộng
3
1.3 Nguyên lý đếm và bài toán đếm cơ bản
4
Chương 2: Một số phương pháp giải bài toán tổ hợp
5
2.1 Phương pháp đại lượng bất biến
5
2.2 Phương pháp đếm dùng hàm sinh
10
2.3 Phương pháp nguyên tắc cực hạn và sử dụng ánh xạ
16
2.4. Hiệu quả của sáng kiến kinh nghiệm 
24
3. Kết luận và kiến nghị
24
4. Tài liệu tham khảo
25
I. MỞ ĐẦU
1.1. Lí do chọn đề tài
 Toán tổ hợp là một chuyên đề cơ bản của toán học, đây là một dạng toán quan trọng trong trương trình phổ thông. Mặt khác trong kì thi đại học, đặc biệt trong các kì thi học sinh giỏi các cấp ta vẫn hay gặp các bài toán khó về tổ hợp. Để giúp học sinh phổ thông, và giáo viên ngoài những phương pháp giải bài toán tổ hợp quen thuộc ra, ta còn nắm thêm được một số kĩ thuật mới để giải một số dạng toán tổ hợp, với mục đích giúp các em có thêm những công cụ giải các bài toán tổ hợp hay và khó. Chính vì những lý do trên, tôi chọn đề tài nghiên cứu là “Một số phương pháp giải bài toán tổ hợp”. Mặc dù các phương pháp nêu trong đề tài, còn mới lạ đối với học sinh Trung học phổ thông, nhưng tôi cũng mạnh dạn đưa Đề tài này vào để các em có thêm cách nhìn mới về các bài toán tổ hợp, và thấy sự đa dạng trong các cách giải các bài toán .
1.2. Mục đích nghiên cứu 
 Mục đích nghiên cứu của Đề tài là trình bày một số kiến thức cơ bản về tổ hợp, đồng thời đưa ra một số cách xây dựng và giải bài toán tổ hợp nâng cao và mới lạ đối với học sinh Trung học phổ thông để các em có thêm nhiều hướng để giải quyết các vấn đề về bài toán tổ hợp.
1.3. Đối tượng nghiên cứu 
 Một số kiến thức về tổ hợp, đồng thời đưa ra một số phương pháp giải bài toán tổ hợp gồm: Phương pháp đại lượng bất biến; phương pháp đếm dùng hàm sinh; phương pháp nguyên tắc cực hạn; và sử dụng ánh xạ.
1.4. Phương pháp nghiên cứu
 Nghiên cứu các bài toán tổ hợp, các tài liệu bồi dưỡng học sinh giỏi, tài liệu hội thảo toán học, 
2. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
2.1. Cơ sở lí luận của sáng kiến kinh nghiệm
 Hệ thống hóa và đưa ra một số phương pháp giải bài toán tổ hợp. Đề tài đóng góp thiết thực cho việc giạy và học các chuyên đề toán trong trường trung học phổ thông, góp phần nâng cao chất lượng dạy học toán cho giáo viên và học sinh.
 Trong sáng kiến kinh nghiệm trên tôi đã đưa ra một số phương pháp mới trong toán học rời rạc, đó là đưa ra một số phương pháp giải bài toán tổ hợp gồm: Phương pháp đại lượng bất biến; phương pháp đếm dùng hàm sinh; phương pháp nguyên tắc cực hạn; và sử dụng ánh xạ, kết hợp với các bài toán thực tiễn gắn liền với toán Trung Học Phổ Thông nhằm giúp các em dễ dàng tiếp cận hơn với các phương pháp trên.
2.2. Thực trạng vấn đề trước khi áp dụng sáng kiến kinh nghiệm
 Năm học 2017-2018 khi chưa đưa ra các phương phải giải bài toán tổ hợp nâng cao trên, học sinh khi tiếp cận các đề thi học sinh giỏi thường gặp rất nhiều khó khăn. Một phần vì trong chương trình toán học phổ thông các phương pháp trên khá mới lạ, nên việc đưa và các e thường ban đầu bỡ ngỡ, đôi khi khó hiểu, dẫn đến nhiều khó khăn trong quá trình giảng dạy.
2.3. Nội dung chính của sáng kiến
Chương 1: Kiến thức cơ sở
 1.1. Hoán vị, chỉnh hợp, tổ hợp
1.1.1. Chỉnh hợp 
Định nghĩa 1.1. ([5]) Cho tập hợp gồm phần tử . Kết quả của việc lấy phần tử khác nhau từ phần tử của tập hợp và sắp xếp chúng theo một thứ tự nào đó được gọi là một chỉnh hợp chập của phần tử đã cho.
 Kí hiệu: là số các chỉnh hợp chập của phần tử.
 Công thức: (với ).
 Chú ý. Một chỉnh hợp chập được gọi là một hoán vị của phần tử.
.
1.1.2. Tổ hợp
 Định nghĩa 1.2. ([5]) Giả sử tập có phần tử ( 1). Mỗi tập con gồm phần tử của được gọi là một tổ hợp chập của phần tử đã cho .
 Kí hiệu: là số các tổ hợp chập của phần tử.
 Công thức: = 
 Chú ý.
 ;
 (0n);
 += (). 
1.2 Hoán vị, chỉnh hợp, tổ hợp suy rộng
1.2.1. Chỉnh hợp lặp
Định nghĩa 1.3. ([3]) Một cách sắp xếp có thứ tự r phần tử có thể lặp lại của một tập phần tử được gọi là một chỉnh hợp lặp chập r từ tập n phần tử. Ngoài ra, mỗi chỉnh hợp lặp chập từ tập phần tử là một hàm từ tập phần tử vào tập phần tử. Vì vậy số chỉnh hợp lặp chập r từ tập n phần tử là .
Định lý 1.1. ([3]) Số các chỉnh hợp lặp chập r từ tập n phần tử bằng .
Chứng minh. Rõ ràng có n cách chọn một phần tử từ tập n phần tử cho mỗi một trong r vị trí của chỉnh hợp khi cho phép lặp. Vì vậy theo quy tắc nhân, có chỉnh hợp lặp chập r từ tập n phần tử. 
1.2.2. Hoán vị lặp 
 Trong bài toán đếm, một số phần tử có thể giống nhau. Khi đó cần phải cẩn thận, tránh đếm chúng hơn một lần. 
Định lý 1.2. ([3]) Số hoán vị của n phần tử trong đó có n1 phần tử như nhau thuộc loại 1, có n2 phần tử như nhau thuộc loại 2,  và có nk phần tử như nhau thuộc loại k bằng .
Chứng minh. Để xác định số hoán vị trước tiên chúng ta nhận thấy có cách giữ n1 số cho n1 phần tử loại 1, còn lại n – n1 chỗ trống.
Sau đó có cách đặt n2 phần tử loại 2 vào hoán vị, còn lại n – n1 – n2 chỗ trống.
 Tiếp tục đặt các phần tử loại 3, loại 4 ,  , loại k – 1 vào chỗ trống trong hoán vị. Cuối cùng có cách đặt nk phần tử loại k vào hoán vị.
 Theo quy tắc nhân tất cả các hoán vị có thể là:
1.2.3. Tổ hợp lặp 
 Một tổ hợp lặp chập k của một tập hợp là một cách chọn không có thứ tự k phần tử có thể lặp lại của tập đã cho. Như vậy một tổ hợp lặp kiểu này là một dãy không kể thứ tự gồm k thành phần lấy từ tập n phần tử. Do đó có thể là .
Định lý 1.3. ([3]) Số tổ hợp lặp chập k từ tập n phần tử bằng .
Chứng minh. Mỗi tổ hợp lặp chập k từ tập n phần tử có thể biểu diễn bằng một dãy n-1 thanh đứng và k ngôi sao. Ta dùng n - 1 thanh đứng để phân cách các ngăn. Ngăn thứ i chứa thêm một ngôi sao mỗi lần khi phần tử thứ i của tập xuất hiện trong tổ hợp. 
 Mỗi dãy n - 1 thanh và k ngôi sao ứng với một tổ hợp lặp chập k của n phần tử . Do đó mỗi dãy ứng với một cách chọn k chỗ cho k ngôi sao từ chỗ chứa n – 1 thanh và k ngôi sao. Đó là điều cần chứng minh.
 Chú ý.
 Số tổ hợp có lặp chập của là: = .
Tổ hợp có lặp lại khi một phần tử có thể xuất hiện nhiều lần và thứ tự của các phần tử không cần để ý.
1.3 Nguyên lý đếm và bài toán đếm cơ bản
1.3.1. Nguyên lý cộng
Mệnh đề 1.1. ([3]) Cho A và B là hai tập hữu hạn. Nếu A Ç B = Æ. thì ½AB½= ½A½+ ½B½.
1.3.2. Nguyên lý nhân
Mệnh đề 1.2. ([3]) Nếu A và B là tập hữu hạn, thì .
Chương 2: Một số phương pháp giải bài toán tổ hợp
2.1 Phương pháp đại lượng bất biến
2.1.1 Giới thiệu về phương pháp đại lượng bất biến([2]) 
 Nhiều bài toán cho biết thực hiện một số thao tác trên một hệ đối tượng nào đó như các số, quân bài, quân cờ hoặc những biến đã cho. Tuy bài toán có phức tạp nhưng ẩn chứa những đại lượng bất biến như tính chẵn lẻ hoặc tổng, tích của các biến không thay đổi,... Nhờ phát hiện ra, hoặc xây dựng những biến cố có tính chất bất biến của bài toán, ta có thể dựa vào những bất biến đó để đi đến lời giải. Phương pháp đó gọi là phương pháp sử dụng bất biến, thường được dùng trong các bài toán tổ hợp. Những bài toán liên quan đến bất biến được chia làm hai loại:
 Những bài toán lấy bất biến làm kết luận phải tìm.
 Những bài toán lấy bất biến làm phương pháp giải.
Thực ra không có lý thuyết chung nào cho các bài toán mà trong đó có đại lượng bất biến. Phương pháp này chỉ hình thành như một cách phân loại bài tập có những ý tưởng chung trong lời giải. Vì thế tốt nhất là tìm hiểu phương pháp bất biến thông qua một số bài tập cụ thể.
Những bài tập lựa chọn ở đây phù hợp với trình độ THPT, đặc biệt là đối với học sinh khá giỏi. Mặt khác, trong khi lựa chọn những Bài toán điển hình, tôi cố gắng làm nổi bật những thao tác thường dùng khi sử dụng phương pháp bất biến trong những tình huống khác nhau.
2.1.2 Một số bài toán 
Dạng 1: Phát hiện bất biến trong bài toán
Bài toán 2.1 . Trên bảng ta viết 10 dấu cộng (+) và 15 dấu trừ (-) tại các vị trí bất kì. Thực hiện xóa hai dấu bất kì trong đó và viết vào đó một dấu cộng (+) nếu hai dấu vừa xóa là giống nhau và dấu trừ (-) nếu hai dấu vừa xóa khác nhau. Làm như vậy cho đến khi trên bảng chỉ còn một dấu. Hỏi trên bảng còn lại dấu gì?
Lời giải. Cách 1. Ta thay mỗi dấu cộng bằng số 1, mỗi dấu trừ bằng số -l. Thao tác thực hiện chính là xóa hai số và viết lại một số là tích của chúng. Vì thế tích của tất cả các số viết trên bảng sẽ không thay đổi, ở thời điểm xuất phát, tích các số trên bảng bằng -1, nên cuối cùng còn lại số -1, nghĩa là trên bảng còn lại dấu trừ.
 Cách 2. Ta thay mỗi dấu cộng bằng số 0, còn dấu trừ bằng số 1. Thao tác thực hiện là: Nếu tổng của hai số xóa đi là số chẵn thì ta viết lại số 0, nếu tổng là lẻ thì ta viết số 1. Như vậy tổng các số trên bảng sau khi thực hiện một thao tác hoặc là không thay đổi hoặc là giảm đi 2. Đầu tiên tổng các số trên bảng là một số lẻ, nên số cuối cùng trên bảng còn lại là số lẻ, vậy là số 1, nghĩa là trên bảng còn dấu trừ.
 Cách 3. Sau khi thực hiện một thao tác, ta thấy số các dấu trừ hoặc không đổi, hoặc giảm đi 2 đơn vị. Như vậy tính chẵn lẻ của số các dấu trừ cũng là một bất biến. Tại trạng thái ban đầu số các dấu trừ là số lẻ, nên khi còn lại một dấu, đó phải là dấu trừ.
 Phân tích ba cách giải ta thấy: Trong cách 1 ta thay các dấu bởi các số, và lợi dụng tính bất biến của tích các số viết trên bảng; cách 2 sử dụng bất biến là tính chẵn lẻ của tổng các số và cách 3 là sự bất biến của tính chẵn lẻ của số các dấu trừ. Như vậy trong cách giải ta sử dụng tính bất biến của tích, tổng, hoặc tính chẵn lẻ của các số. Qua cách giải trên ta thấy rằng khi gặp những lớp bài toán mà thao tác lặp đi, lặp lại, ta phải biến đổi và tìm ra những đại lượng bất biến của thao tác ta thực hiện. Chú ý rằng các thao tác ta thực hiện không phụ thuộc vào thứ tự các đối tượng được chọn.	
Bài toán 2.2. Trên bảng ta viết tâp hợp số gồm các số 0; 1 và 2. Cho phép xóa hai số khác nhau và điền vào đó số còn lại trong 3 số ( nghĩa là 2 thay cho 0 và 1; 1 thay cho 0 và 2; 0 thay cho 2 và 1). Chứng minh rằng nếu sau một số lần thực hiện thao tác trên, trên bảng chỉ còn lại một số duy nhất thì số đó không phụ thuộc vào thứ tự thực hiện các thao tác .
Lời giải. Ta thực hiện một lần thao tác thì số lượng mỗi loại trong ba loại số trên tăng lên hoặc giảm đi 1, suy ra số lượng các số thay đổi tính chẵn lẻ. Khi trên bảng chỉ còn lại một số, nghĩa là hai trong các số 0, 1 và 2 có số lượng bằng 0 còn số thứ ba bằng một. Như vậy ngay từ đầu số lượng hai số trong ba số trên bảng phải có cùng tính chẵn lẻ và số lượng loại số còn lại có tính chẵn lẻ khác. Vì thế không phụ thuộc vào thứ tự thực hiện thao tác, cuối cùng chỉ còn một trong các số 0, 1, và 2, số này chính là số thuộc loại mà số lượng loại số đó khác tính chẵn lẻ với số lượng hai loại số kia.
 Nhận xét. Trong chứng minh bài toán trên, nếu số lượng cả ba loại số trên bảng có cùng tính chẵn lẻ thì dù có thực hiện thao tác trên thế nào đi nữa, cuối cùng cũng không thể nào còn một số duy nhất trên bảng.	
Bài toán 2.3. Một hình vuông có cạnh 4 cm được chia thành 16 ô vuông, mỗi ô vuông có cạnh 1 cm. Tại mỗi một trong 15 ô nào đó ta đánh dấu cộng (+), ô còn lại đánh dấu trừ (-). Những dấu ở các ô vuông có thể thay đổi đồng thời theo hàng, một cột hoặc theo một đường chéo. Có khả năng sau hữu hạn lần đổi dấu theo nguyên tắc trên dẫn đến tất cả các ô vuông đều có dấu cộng (+) hay không? 
Lời giải. Ta thay dấu cộng (+), trừ (-) bằng các số tương ứng 1 và -1. Trạng thái ban đầu giả sử được mô tả bởi Hình 3.1. Có thể thấy rằng tích các số ở các ô được tô màu trong Hình 3.2 là một đại lượng bất biến, vì số ô dược tô màu trong mỗi hàng, mỗi cột, mỗi đường chéo là số chẵn, nên tích của chúng không đổi sau mỗi thao tác. Ở thời điểm xuất phát, tích đó bằng -1, nghĩa là trong các ô được tô màu luôn tồn tại một ô có số -1, suy ra không thể nhận được bảng không chứa một dấu trừ (-) nào.	
Dạng 2: Giải toán bằng đại lượng bất biến
 Bằng cách phát hiện ra những đại lượng bất biến trong bài toán ta có thể giải nhiều bài toán. Sau đây là một số bài tập giúp tìm hiểu thêm những cách tìm đại lượng bất biến trong giải toán.
Bài toán 2.4. Có ba đống sỏi gồm những viên sỏi nhỏ có số lượng tương ứng là 19, 8 và 9 (viên sỏi). Ta được phép chọn hai đống sỏi và chuyển từ mỗi đống sỏi đã chọn một viên sang đống sỏi thứ ba. Sau một số lần làm như vậy thì có khả năng tạo ra mọi đống sỏi đều có 12 viên sỏi hay không?
Lời giải. Đặt số viên sỏi trong ba đống sỏi tương ứng là a, b, c. Ta xét số dư chia cho 3 của những số này. Khi xuất phát, những số dư này là 1, 2, 0. Sau một lần chọn thay đổi, những số dư này là 0, 1, 2 vì hai đống sỏi có sự chuyển một viên sỏi đến đống thứ ba. Như vậy những số dư luôn luôn là 0, 1, 2 với những thứ tự khác nhau. Do đó tất cả các đống sỏi đều có 12 viên sỏi là không thể được (vì khi đó số dư là 0, 0, 0, vô lí). Vậy không thể tạo ra mọi đống sỏi đều có 12 viên sỏi .	
Bài toán 2.5. Hai người chơi một trò chơi với hai đống kẹo. Đống kẹo thứ nhất có 12 cái và đống thứ hai có 13 cái. Mỗi người chơi được lấy hai chiếc kẹo từ một trong hai đống hoặc chuyển một cái kẹo từ đống thứ nhất sang đống thứ hai. Người chơi nào không thể làm được những thao tác trên coi như là thua. Hãy chứng minh rằng người chơi đi lượt thứ hai không thể thua. Người đó có thể thắng không?
Lời giải. Ta kí hiệu S là giá trị tuyệt đối của số keọ trong đống thứ hai trừ đi số kẹo trong đống thứ nhất.
 Khởi đầu S = 13 - 12 = 1. Sau mỗi nước đi S sẽ giảm hoặc tăng lên 2.
 Như vậy số dư của S chia cho 4 có dạng 1, 3, 1, 3,.. Sau mỗi nước đi
của người thứ nhất số dư của S chia cho 4 luôn luôn là 3. Ta thấy rằng người chơi bị thua khi và chỉ khi đến lượt anh ta thì không còn cái kẹo nào ở đống thứ nhất và chỉ còn một cái kẹo ở đống thứ hai.
 Khi đó . Do đó người đi sau luôn luôn còn nước đi, do đó người đó không thua. Ta thấy rằng, hoặc là tổng số kẹo ở hai đống giảm đi hoặc là số kẹo ở đống thứ nhất giảm đi, như vậy trò chơi phải có kết thúc, do đó người chơi thứ hai phải thắng.	
Bài toán 2.6. Tại một hội nghị có 2n quan khách. Mỗi vị khách được mời có nhiều nhất n-1 kẻ thù. Chứng minh rằng các vị khách có thể ngồi quanh một bàn tròn sao cho không ai ngồi cạnh kẻ thù của mình.
Lời giải. Trước tiên ta xếp các vị khách ngồi vào vị trí bất kì. Gọi H là số những đôi thù địch ngồi cạnh nhau. Ta phải tìm thuật toán để làm giảm số H khi H >0. Giả sử (A,B) là cặp thù địch với B ngồi bên phải A ( Hình 3.3). Ta phải tách được cặp này ra. Điều này thực hiện được nếu có một cặp khác cạnh nhau (A’,B’), mà (A,A’) và (B,B’) không là những cặp kẻ thù. Khi đó ta đổi chỗ B và A’ (Hình 3.4) và H sẽ giảm. Chỉ còn chứng minh rằng một cặp (A’,B’) như trên luôn luôn tồn tại với B’ ngồi bên phải A’ mà A’ là bạn của A và B’ là bạn của B. Ta khởi đầu từ A và đi theo chiều ngược kim đồng hồ(đi về phía phải ) quanh bàn. Ta sẽ bắt gặp ít nhất n người bạn (không phải kẻ thù) của A. Về phía phải mỗi người bạn của A có ít nhất n chỗ. Những chỗ này không thể bị chiếm hết bởi các kẻ thù của B vì B chỉ có nhiều nhất n-1 kẻ thù. Như vậy tồn tại người bạn A’ của A mà về phía phải người này là B’ mà B’ là người bạn của B.	
2.2 Phương pháp đếm dùng hàm sinh
2.2.1 Tóm tắt lí thuyết
*Định nghĩa 2.1([4]) Hàm sinh của dãy số thực là hàm số được xác định bởi 
*Định nghĩa 2.2([4]) Cho dãy số thực Hàm số cho bởi được goi là hàm sinh dang mũ của dãy.
Một số đẳng thức liên quan đến hàm sinh
* Hai mệnh đề thường được sử dụng 
+ Mệnh đề 2.1([4]) Cho hàm sinh 
Đạt ar là hệ số của xr trong khai triển của G(x) thì: 
+ Mệnh đề 2.2 ([4]) (Công thức xác định hệ số tích của hai hàm sinh) Cho hai hàm sinh của hai dãy (an); (bn) lần lượt là:
Đặt 
= Khi đó hệ số của xr trong đó khai triển của G(x) là: 
Quy tắc xoắn: ([4]) Gọi A(x) là hàm sinh cho dãy cách chọn các phần tử từ tập A(x), B(x) là hàm sinh cho dãy cách chọn các phần tử từ tập B. Nếu A và B rời nhau thì hàm sinh cho số cách chọn các phần tử từ tập là A(x).B(x).
Chú ý: 
- Thứ tự các phần tử không quan trọng.
- Việc chọn các phần tử ở A và B giống với cách chọn phần tử của .
 - Ý tưởng phương pháp hàm sinh như sau: Giả sử ta cần tìm công thức tổng quát của một dãy số nào đó. Từ công thức truy hồi hoặc những lý luận tổ hợp trực tiếp, ta tìm được hàm sinh :
 - Khai triển A(x) thành chuỗi và tìm hệ số của xn trong khai triển đó ta tìm được . Cho hàm số có đạo hàm mọi cấp tại x=a, khi đó khai triển Taylor hàm số tại a là: 
Bài toán 2.7. Giả sử có 4 loại kẹo: Chanh, dâu, sôcôla, sữa. Tìm hàm sinh cho số cách chọn n cái kẹo thỏa mãn các điều kiện khác nhau sau đây:
Mỗi loại kẹo xuất hiện số lẻ lần.
Số kẹo của mỗi loại kẹo chia hết cho 3.
Không có kẹo socola và có nhiều nhất 1cái kẹo chanh.
 Lời giải. a) Vì mỗi loại kẹo xuất hiện là như nhau nên ta chỉ cần tìm hàm
sinh cho số cách chọn một loại kẹo.
Ta có
0 cách chọn 0 cái kẹo;
1cách chọn 1cái kẹo;
cách chọn 2 cái kẹo;
cách chọn 3 cái kẹo;
...................................
 Vậy hàm sinh cho số cách chọn một loại kẹo là: Áp dụng quy tắc xoắn ta được hàm sinh cho số cách chọn n cái kẹo từ 4 loại kẹo là
 b, Ta có số cách chọn kẹo thỏa mãn điều kiện số kẹo của mỗi loại chia hết cho 3 là:
1 cách chọn 0 cái kẹo;
0 cách chọn 1 cái kẹo;
 0 cách chọn 2 cái kẹo;
 0 cách chọn 3 cái kẹo;
 0 cách chọn 4 cái kẹo;
0 cách chọn 5 cái kẹo;
0 cách chọn 6 cái kẹo.
Hàm sinh cho số cách chọn mội loại kẹo thỏa mãn điều kiện là: 
Vậy hàm sinh cho số cách chọn n cái kẹo từ 4 loại kẹo thỏa mãn điều kiện là: 
d, Hàm sinh cho số cách chọn kẹo socola là : 1;
Hàm sinh cho số cách chọn kẹo chanh là : 1+ x ;
Hàm sinh cho số cách chọn kẹo dâu là: 
Hàm sinh cho số cách chọn kẹo sữa là: 
Vậy hàm sinh cho số cách chọn n cái kẹo từ 4 loại kẹo thỏa mãn điều kiện là: 
2.2.2 Các dạng bài toán dùng hàm sinh.
*. Bài toán chọn các phần tử riêng biệt.
Bài toán 2.8. Có bao nhiêu cách chọn n phần tử phân biệt từ tập hợp k phần tử.
Lời giải. Bài toán này có thể giải quyết dễ dàng bằng công thức tổ hợp. Nhưng lần này chúng ta sẽ sử dụng hàm sinh. Cụ thể
Đầu tiên ta xét tập hợp có một phần tử . Ta có:
1 cách chọn 0 phần tử;
1 cách chọn 1 phần tử;
 0 cách chọn 2 phần tử trở lên.
Suy ra hàm sinh cho số cách chọn n phần tử từ tập là .
Tương tự như vậy, hàm sinh cho số cách chọn n phần tử từ tập cũng là (không phụ thuộc vào sự khác biệt giữa các ).
Tiếp tục xét tập 2 phần tử ta có:
1 cách chọn 0 phần tử;
2 cách chọn 1 phần tử;
1 cách chọn 2 phần tử;
 0 cách chọn 3 phần tử trở lên.
Suy ra hàm sinh cho số cách chọn n phần tử từ tập là: 
Tiếp tục áp dụng quy tắc này ta sẽ được hàm sinh cho số cách chọn các phần tử từ tập k phần tử: 
Ta có . Như vậy hệ số của trong là và bằng số cách chọn n phần tử phân biệt từ tập k phần tử.
*. Bài toán chọn các phần tử có lặp
 Để hiểu cách giải bài toán này trước tiên ta phải mở rộng, ta có quy tắc xoắn.
 Gọi là hàm sinh cho cách chọn các phần tử từ tập hợp A và là hàm sinh cho cách chọn các phần tử từ tập hợp B. Nếu A và B rời nhau thì hàm sinh cho cách chọn các phần tử từ tập là 
 Quy tắc này đúng cho cả trường hợp chọn các phần tử phân biệt, cũng đúng cho trường hợp chọn nhiều lần cùng một phần tử.
Bài toán 2.9. Có bao nhiêu cách chọn k phần tử từ tập hợp có n phần tử, trong đó cho phép một phần tử có thể được chọn nhiều lần.
Lời giải. Chia tập n phần tử thành hợp của n tập ; mỗi tập gồm duy nhất một phần tử thuộc tập n phần tử.
Với mỗi tập t