SKKN Ứng dụng của hàm sinh trong việc giải các bài toán tổ hợp

A. më ®Çu
I – Đặt vấn đề:
Hàm sinh (Generating Function) trong toán học là một trong các công cụ mạnh để giải quyết một số dạng bài toán khó. Lí thuyết hàm sinh đã được biết đến từ lâu và được nghiên cứu khá kĩ lưỡng, tuy nhiên những tài liệu đã được sơ cấp hoá và được dịch ra tiếng Việt thành các bài viết chuyên đề hiện tại không nhiều. Trong quá trình giảng dạy cho học sinh chuyên Toán, tôi nhận thấy có nhiều dạng bài toán nếu biết vận dụng khéo léo công cụ hàm sinh thì lời giải rất đơn giản trong khi nếu không dùng công cụ này lời giải sẽ rất phức tạp, thậm chí không thể giải được bằng các phương pháp thông thường như: Các bài toán tìm công thức tổng quát của dãy số; các bài toán tổ hợp Tuy nhiên, để nắm vững lý thuyết hàm sinh một cách đầy đủ đối với học sinh các lớp đầu cấp THPT là không đơn giản, vì trong lý thuyết này cần sử dụng không ít kiến thức toán cao cấp ở bậc đại học.
Để giải quyết vấn đề đó, tôi đã tìm cách đơn giản hoá một số kiến thức cho phù hợp với đối tượng học sinh và thử áp dụng vào giảng dạy đối với học sinh lớp 10 chuyên Toán. Kết quả thu được rất khả quan và đã được đúc rút thành SKKN với tiêu đề “Ứng dụng phương pháp hàm sinh để tìm công thức tổng quát của một số dãy số” (SKKN năm 2012, đã được Hội đồng chấm SKKN của ngành xếp loại A). Tuy nhiên, kết thúc chuyên đề này, mặc dù các em học sinh đã nhận thấy mối liên hệ giữa hàm sinh với các bài toán đếm (Tổ hợp) nhưng vẫn còn gặp nhiều khó khăn khi vận dụng hàm sinh để giải quyết. Trong đó, vấn đề khó khăn nhất là: Làm thế nào để xây dựng được hàm sinh cho các đối tượng “rời rạc”, rất khó “nắm bắt” trong các bài toán Tổ hợp?
Tiếp nối ý tưởng của SKKN trước, sau khi đã trang bị thêm cho học sinh một số kiến thức cơ bản trong chương trình THPT (Số phức) vào lớp 11, tôi tiếp tục đơn giản hoá một số kiến thức toán cao cấp nhằm giúp học sinh có thể nắm bắt và vận dụng được công cụ hàm sinh để giải quyết các bài toán Tổ hợp (dạng bài toán được cho là khó nhất trong các đề thi HSG). Theo dõi qua quá trình giảng dạy cho thấy, nhiều học sinh trong lớp đã có thể xử lý được những bài toán Tổ hợp cơ bản bằng phương pháp hàm sinh và bước đầu biết cách xây dựng hàm sinh để xử lý những bài toán khó. Những học sinh khá đã có thể sử dụng tương đối thành thạo hàm sinh để giải quyết linh hoạt những bài toán khó. Vì vậy, tôi tiếp tục chọn viết vấn đề này để trao đổi kinh nghiệm giảng dạy với các đồng nghiệp, đồng thời cũng là để làm tư liệu cho những năm giảng dạy tiếp theo của mình.
Sáng kiến kinh nghiệm này được trình bày theo cấu trúc. 
1. Trình bày những kết quả cơ bản có liên quan của Số phức và toán cao cấp dưới dạng đơn giản nhât. 
2. Vận dụng lý thuyết vào giải toán.
3. Đưa ra một hệ thống bài toán chọn lọc nhằm nâng cao kỹ năng.
II - Mục đích:
	Tiếp tục nâng cao kỹ năng giải toán cho học sinh lớp 11 khi đã được trang bị kiến thức hàm sinh (dưới dạng đơn giản nhất) ở lớp 10 và một số kiến thức về Số phức ở lớp 11.
III - Đối tượng áp dụng: Học sinh lớp 11 chuyên Toán.
IV- Nhiệm vụ nghiên cứu :
Đơn giản hoá một số kiến thức toán cao cấp để học sinh có thể nắm bắt đầy đủ về cách vận dụng hàm sinh trong giải toán.
Hướng dẫn học sinh xây dựng hàm sinh trong các bài toán Tổ hợp thông qua một số ví dụ cụ thể (nhiệm vụ chính).
B. NỘI DUNG
1. Một vài tính chất của căn nguyên thuỷ bậc n của đơn vị.
Trong phần này nhắc lại một số kiến thức cơ bản về số phức mà học sinh lớp 11 đã được trang bị.
Định nghĩa: là một căn bậc n của đơn vị và được gọi là căn nguyên thủy bậc n của đơn vị nếu mọi số nguyên dương ta có 
Từ định nghĩa, kết hợp với các tính chất của số phức biểu diễn dưới dạng mũ, ta dễ dàng chứng minh được kết quả sau:
Định lý 1: Nếu là một căn nguyên thủy bậc n của đơn vị thì:
 	 với . 
Đặc biệt với ta có 
Định lý 2: Kí hiệu với là một số nguyên dương là một căn nguyên thuỷ bậc của đơn vị. Khi đó mọi đa thức , với = 0 nếu , đều có: 
Chứng minh: Ta có nhận xét: 
Tổng nếu chia hết (do nên). 
Trong trường hợp khác ta có và . Khi đó:
Định lý được chứng minh.
Cũng từ nhận xét trong chứng minh định lý 2, ta dễ dàng chứng minh được kết quả sau.
Định lý 3: Nếu , với p là một số nguyên tố, khi đó:
2. Đạo hàm của tích các hàm số, đạo hàm riêng của hàm nhiều biến:
2.1 Đạo hàm của tích các hàm số:
Định lý 4: Nếu hàm số với là các hàm số có đạo hàm thì:
.
Định lý này dễ dàng chứng minh được bằng quy nạp theo . Trường hợp là công thức quen thuộc.
2.2 Đạo hàm riêng của hàm nhiều biến:
Vì chương trình THPT chưa học khái niệm đạo hàm riêng nên ở đây không đưa ra định nghĩa đầy đủ, chính xác. Với mục đích hướng dẫn học sinh vận dụng cách tính đạo hàm riêng vào một số hàm nhiều biến đơn giản nên chỉ tiếp cận khái niệm qua ví dụ.
Ví dụ: Cho hàm số . Khi đó, đạo hàm riêng của hàm theo biến được ký hiệu và được tính như đạo hàm của hàm số theo biến (biếnđược coi là tham số). 
Như vậy: 
Tương tự ta có: 
3. Xây dựng hàm sinh:
Hàm sinh có thể được áp dụng trong các bài toán đếm. Nói riêng, các bài toán chọn các phần tử từ một tập hợp thông thường sẽ dẫn đến các hàm sinh. Khi hàm sinh được áp dụng theo cách này, hệ số của chính là số cách chọn n phần tử. 
3.1. Chọn các phần tử khác nhau:
Hàm sinh cho dãy các hệ số nhị thức được suy ra trực tiếp từ định lý nhị thức
Như vậy hệ số của trong ( bằng số cách chọn phần tử phân biệt từ một tập hợp gồm k phần tử. Ví dụ, hệ số của là cũng là số cách chọn 2 phần tử từ tập hợp k phần tử. Tương tự, hệ số của là số cách chọn phần tử từ tập hợp k phần tử và bằng 0.
3.2. Xây dựng các hàm sinh để đếm:
Thông thường ta có thể dịch mô tả của bài toán đếm thẳng sang ngôn ngữ hàm sinh để giải. Ví dụ, ta có thể chứng tỏ rằng sẽ sinh ra số các cách chọn n phần tử phân biệt từ tập hợp k phần tử mà không cần dùng đến định lý nhị thức hay các hệ số nhị thức. 
Ta làm như sau: Đầu tiên, xét tập hợp có một phần tử . Hàm sinh cho số cách chọn n phần tử từ tập hợp này đơn giản là . Ta có 1 cách chọn không phần tử nào, 1 cách chọn 1 phần tử và 0 cách chọn hai phần tử trở lên. Tương tự, số cách chọn n phần tử từ tập hợp cũng cho bởi hàm sinh . Sự khác biệt của các phần tử trong hai trường hợp trên là không quan trọng.
Ta có nguyên lý quan trọng sau đây: hàm sinh cho số cách chọn các phần tử từ hợp của hai tập hợp bằng tích các hàm sinh cho số cách chọn các phần tử từ mỗi tập hợp. 
Ví dụ: Theo nguyên lý, hàm sinh cho số cách chọn các phần tử từ tập hợp là: 
Có thể kiểm chứng rằng đối với tập hợp 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ử và 0 cách chọn 3 phần tử trở lên.
Tiếp tục áp dụng quy tắc này, ta sẽ được hàm sinh cho số cách chọn n phần tử từ tập hợp k phần tử là: 
Đây chính là công thức hàm sinh mà ta đã nhận được bằng cách sử dụng định lý nhị thức. Nhưng trong trường hợp này, chúng ta đã đi thẳng từ bài toán đếm đến hàm sinh.
Ta có thể mở rộng điều này thành một nguyên lý tổng quát.
Định lý 5: (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 là rời nhau thì hàm sinh cho cách chọn các phần tử từ A È B là .
Lưu ý: Quy tắc này là khá đa nghĩa, vì cần hiểu chính xác cách chọn các phần tử từ một tập hợp có nghĩa là thế nào? Rất đáng chú ý là Quy tắc xoắn vẫn đúng cho nhiều cách hiểu khác nhau của từ cách chọn. Ví dụ, ta có thể đòi hỏi chọn các phần tử phân biệt, cũng có thể cho phép được chọn một số lần có giới hạn nào đó, hoặc cho chọn lặp lại tuỳ ý. Một cách đơn giản, giới hạn duy nhất là:
(1) thứ tự chọn các phần tử không quan trọng.
(2) những giới hạn áp dụng cho việc chọn các phần tử của A và B cũng áp dụng cho việc chọn các phần tử của A È B (Chặt chẽ hơn, cần có một song ánh giữa các cách chọn n phần tử từ A È B với bộ sắp thứ tự các cách chọn từ A và B chứa tổng thể n phần tử)
Chứng minh. 
Định nghĩa 	
Trước tiên ta tính tích và biểu diễn hệ số thông qua các hệ số a và b. Ta có thể sắp xếp các số hạng này thành dạng bảng như sau:
Chú ý rằng các số hạng có cùng luỹ thừa của xếp trên các đường chéo. Nhóm tất cả các số hạng này lại, ta thấy rằng hệ số của trong tích bằng
Bây giờ ta chứng minh rằng đây cũng chính là số cách chọn n phần tử từ . Một cách tổng quát, ta có thể chọn n phần tử từ bằng cách chọn j phần tử từ A và phần tử từ B, trong đó j là một số từ 0 đến n. Điều này có thể được thực hiện bằng cách. Lấy tổng từ 0 đến n, ta có: cách chọn phần tử từ . Đó chính là giá trị đã được tính ở trên.
3.3. Chọn các phần tử có lặp:
Ta xét bài toán ví dụ sau: 
Bài toán 1: Có bao nhiêu cách chọn 12 cây kẹo từ 5 loại kẹo? 
Tổng quát: Có bao nhiêu cách chọn ra k phần tử từ tập hợp có n phần tử, trong đó ta cho phép một phần tử có thể được chọn nhiều lần? 
Ta sẽ xây dựng hàm sinh cho bài toán này.
Giả sử ta chọn n phần tử (có lặp) từ tập hợp chỉ có duy nhất một phần tử. Khi đó có 1 cách chọn 0 phần tử, 1 cách chọn 1 phần tử, 1 cách chọn 2 phần tử  Như thế, hàm sinh của cách chọn có lặp từ tập hợp có 1 phần tử bằng
Áp dụng định lý 5 (Quy tắc xoắn) ta có (hàm sinh của cách chọn các phần tử từ hợp của các tập hợp rời nhau bằng tích của các hàm sinh của cách chọn các phần tử từ mỗi tập hợp):
Vậy, hàm sinh của cách chọn các phần tử từ tập hợp phần tử có lặp là: .
4. Xây dựng hàm sinh trong các bài toán tổ hợp:
Bài toán mở đầu: Có bao nhiêu nhiêu cách sắp một giỏ trái cây thoả mãn các điều kiện ràng buộc sau:
Số táo phải chẵn
Số chuối phải chia hết cho 5
Chỉ có thể có nhiều nhất 4 quả cam
Chỉ có thể có nhiều nhất 1 quả đào
Ví dụ, để sắp một giỏ 6 trái cây ta chỉ có 7 cách sắp sau:
	Táo	6	4	4	2	2	0	0	
	Chuối 	0	0	0	0	0	5	5	
	Cam 	0	2	1	4	3	1	0	
	Đào	0	0	1	0	1	0	1
Nhận xét: Các điều kiện ràng buộc của bài toán quá phức tạp và dường như không thể giải quyết được. Tuy nhiên, nếu ta xem xét bài toán bằng hàm sinh thì lời giải hết sức bất ngờ.
Giải: 	Trước hết, ta tìm hàm sinh cho số cách chọn táo:
Có 1 cách chọn 0 quả táo, có 0 cách chọn 1 quả táo (vì số táo phải chẵn), có 1 cách chọn 2 quả táo, có 0 cách chọn 3 quả táo Như vậy ta có hàm sinh cho số cách chọn táo là: 
Tương tự, hàm sinh cho số cách chọn chuối là:
Bây giờ, ta có thể chọn 0 quả cam bằng 1 cách, 1 quả cam bằng 1 cách,  Nhưng ta không thể chọn hơn 4 quả cam, vì thế ta có hàm sinh cho số cách chọn cam là:	 
Tương tự, hàm sinh cho số cách chọn đào là:
Theo quy tắc xoắn, hàm sinh cho cách chọn từ cả 4 loại trái cây bằng:
Vậy số cách sắp giỏ trái cây gồm n trái cây đơn giản bằng .
	Sau đây, ta xem xét một số bài toán giải bằng phương pháp hàm sinh và chú ý cách xây dựng hàm sinh trong từng bài toán.
Bài toán 1: Một con xúc xắc gọi là “chuẩn” có các mặt đánh dấu bởi các chấm mà số chấm lần lượt là: 1, 2, 3, 4, 5, 6. Khi ta tung hai con xúc xắc “chuẩn”, dễ dàng tính được xác suất của tổng số chấm ở các mặt xuất hiện. Chẳng hạn, xác suất khi tung hai con xúc xắc nhận được tổng số chấm ở các mặt xuất hiện bằng 2 là 1/36, còn xác suất nhận được tổng số chấm ở các mặt xuất hiện bằng 7 là 1/6.
Hỏi có thể tạo ra một cặp xúc xắc “không chuẩn” từ một cặp xúc xắc “chuẩn” bằng cách đánh dấu lại số chấm ở các mặt (không làm thay đổi cấu trúc của các con xúc xắc đó, số chấm ở mỗi mặt phải là số nguyên dương) sao cho xác suất của tổng số chấm ở các mặt xuất hiện khi tung hai con xúc xắc đó không đổi so với khi tung hai con xúc xắc “chuẩn”? Chẳng hạn, trên một mặt của một con xúc xắc không chuẩn ta đánh dấu 8 chấm, trên con xúc xắc còn lại có hai mặt được đánh dấu mỗi mặt 3 chấm. Nhưng xác suất của tổng số chấm ở các mặt xuất hiện khi tung hai con xúc xắc này bằng 2 vẫn là 1/36, và xác suất của tổng số chấm ở các mặt xuất hiện bằng 7 vẫn là 1/6.
Giải: Xét một con xúc xắc chuẩn, ta xây dựng hàm sinh số lần xuất hiện mặt chứa chấm bằng cách: gán cho mặt chứa chấm bởi ký hiệu và số lần xuất hiện mặt chấm bằng hệ số của . Khi đó hàm sinh số chấm ở các mặt của con xúc xắc chuẩn là:
Rõ ràng, khi tung hai con xúc xắc chuẩn, hàm sinh của tổng số chấm xuất hiện trên mặt hai con xúc xắc là:
:
Trong đó là ký hiệu cho tổng số chấm ở các mặt xuất hiện bằng và hệ số của là số lần xuất hiện của cặp các mặt xuất hiện có tổng số chấm bằng . Chẳng hạn, xét tổng số chấm xuất hiện trên hai con xúc xắc chuẩn khi gieo bằng 6. Ta thấy trong tích trên có các cặp sau có tích bằng là , , , , và , vậy hệ số của là 5. Nói cách khác, ta có 5 cách phân tích số 6 thành tổng số chấm xuất hiện trên các mặt của mỗi con xúc xắc chuẩn là: 
1 + 5, 2 + 4, 3 + 3, 4 + 2, và 5 + 1
 Do đó đa thức tích:
có các hệ số của bằng số các cách phân tích số thành tổng số chấm xuất hiện trên mặt các con xúc xắc chuẩn trong phép gieo hai con xúc xắc. 
Ta có thể áp dụng phương pháp này cho trường hợp các con xúc xắc không chuẩn. Kí hiệu: và là số các chấm trên các mặt của hai con xúc xắc không chuẩn, và hàm sinh của các số này trên mỗi con xúc xắc không chuẩn tương ứng là: và . 
Tương tự trên, tích biểu diễn hàm sinh cho tổng số chấm xuất hiện trên các mặt của phép gieo hai con xúc xắc không chuẩn. Do giả thiết, xác suất tổng số chấm xuất hiện trên mặt khi gieo hai con xúc xắc không chuẩn trùng với xác suất khi gieo hai con xúc xắc chuẩn, ta suy ra: 
Giả sử:
 và
trong đó và là các số nguyên không âm thoả mãn với .
Do nên mỗi đa thức phải chia hết cho , từ đó . Mặt khác, từ cách xác định ban đầu ta phải có , nghĩa là , suy ra . 
Nếu ta có thì và như vậy các con xúc xắc đều phải là xúc xắc chuẩn. 
Như vậy chỉ có duy nhất trường hợp và (trường hợp hoàn toàn tương tự), khi đó:
Như vậy, ta có thể xây dựng hai con xúc xắc không chuẩn thoả mãn bài toán bằng cách đánh dấu lại số chấm trên các mặt của mỗi con bởi các số: 1; 3; 4; 5; 6; 8 và 1; 2; 2; 3; 3; 4.
Bài toán 2: (Rumania MO 2003) 
Có bao nhiêu số có chữ số, các chữ số thuộc tập {2,3,7,9} và chia hết cho 3?
Giải: Ta có một số chia hết cho 3 nếu và chỉ nếu tổng các chữ số của nó chia hết cho 3. Như vậy yêu cầu bài toán tương đương với việc tìm số các số có chữ số mà tổng các chữ số của nó chia hết cho 3. Ta có mỗi chữ số của số thỏa mãn có giá trị là một trong các số 2,3,7 hoặc 9. Do đó hàm sinh cho mỗi chữ số sẽ là . Xét hàm sinh:
Trong đó là số các số có chữ số từ {2,3,7,9} mà có tổng các chữ số là . Khi đó số các số cần tìm là:
. 
Gọi là căn nguyên thủy bậc ba của đơn vị, ta có
 và .
Khi đó: 	
Suy ra:
.
Vậy ta có các số cần tìm là :
Bài toán 3: 
Cho các số nguyên dương phân biệt với thoả mãn: . Chứng minh rằng là một luỹ thừa của 2.
Giải:
Xét hai hàm sinh:
 và 
Ta có: và .
Vậy ta có: , hay .
Mặt khác: nên ta có thể viết: , trong đó . Do đó , suy ra:
.
Với , ta có , hay . Vậy là một luỹ thừa của 2.
Trong các bài toán trên ta thấy các hàm sinh xây dựng được chỉ có một biến duy nhất, nguyên nhân là do các bài toán này chỉ đòi hỏi một thông tin ràng buộc. Trong thực tế, việc xây dựng hàm sinh không thể chỉ dựa trên một biến (vì một biến chỉ cho ta một thông tin duy nhất!). Đối với những bài toán đòi hỏi nhiều thông tin ta cần xét hàm sinh với nhiều biến hơn. Những bài toán tiếp theo cho ta thấy việc xây dựng hàm sinh ràng buộc nhiều thông tin cần sử dụng nhiều hơn một biến.
Bài toán 4: (IMO 1995) 
Cho là một số nguyên tố lẻ. Tìm số các tập con của tập thỏa mãn:
(i) có đúng p phần tử và 
(ii) Tổng tất cả các phần tử của chia hết cho p.
Giải:
Rõ ràng với mỗi ta không thể xét hàm sinh của phép chọn phần tử trong tập bởi vì tích không thể hiện được tập có đúng p phần tử. Vấn đề đặt ra là đại lượng cần tính bao hàm hai thông tin: kích thước tập và tổng các phần tử của tập. Vì thế ta phải xét hàm sinh có dạng: trong đó là số các tập con phần tử của có tổng các phần tử là n. Khi đó số các tập con cần tính là Để xây dựng hàm sinh ta cần xác định hàm sinh cho cách chọn mỗi phần tử m của tập . Với mỗi 1 ≤ m ≤ 2p ta có m được chọn thì m sẽ thuộc vào một tập con A (có đúng p phần tử và tổng các phần tử chia hết cho p), ngược lại m không được chọn thì m không thuộc vào tập con nào có dạng đó. Do đó hàm sinh cho phép chọn m là . Suy ra: .
Đặt là căn nguyên thuỷ bậc p của đơn vị. Khi đó theo định lý 2, ta có:
Ta tính , với 0 ≤ k ≤ p − 1. 
Khi k = 0,. 
Với 1 ≤ k ≤ p − 1. Ta có gcd(k, p) = 1 nên .
 Suy ra:
Vậy từ (1) suy ra: . Đây chính là các hệ số của các luỹ thừa của trong . 
Từ đó suy ra số cần tính bằng hệ số của trong tổng trên và bằng . 
Vậy số các tập con thoả mãn bài toán là: .
Bài toán 5 (USA MO 1989) 
Ta gọi phân hoạch của số nguyên n ≥ 1 nghĩa là n có thể biểu diễn thành tổng của một hoặc nhiều số nguyên dương theo thứ tự không giảm (ví dụ n = 4 khi đó các phân hoạch là 1 + 1 + 1 + 1, 1 + 1 + 2, 1 + 3, 2 + 2, và 4 ). Với mỗi phân hoạch xác định là số các số 1 xuất hiện trong và xác định là số các số nguyên dương phân biệt xuất hiện trong (ví dụ n = 13 và là phân hoạch 1 + 1 + 2 + 2 + 2 + 5, khi đó = 2 và = 3). Chứng minh rằng với mỗi n cố định, ta có:
Giải:
Đặt và. 
Để chứng minh bài toán ta sẽ đi xây dựng hai hàm sinh và , sau đó chứng tỏ thì ta sẽ có với mọi n.
Trước tiên để xây dựng ta cần kiểm soát hai thông tin sau: tổng của các phân hoạch và số các số 1 trong các phân hoạch đó. 
Với số nguyên có trong phân hoạch , hàm sinh cho các cách chọn là 
Với , nếu số 1 được chọn lần thì ứng với lần chọn đó ta biểu diễn bởi , tuy nhiên để biết thêm về số lần số 1 xuất hiện trong ta gán thêm cho biến để chỉ rằng nếu 1 được chọn lần thì nó cũng xuất hiện lần trong . Do đó hàm sinh cho là 
Xét :
Trong đó ta dùng biến để kiểm soát tổng của phân hoạch và biến kiểm soát số lần xuất hiện của số 1 trong phân hoạch, là số các phân hoạch của có số 1. Bằng cách sử dụng tổng của chuỗi số, ta có thể viết dưới dạng đơn giản 
Ta chú ý rằng số tất cả các số 1 có trong tất cả các phân hoạch của mà mỗi phân hoạch có đúng số 1 là , như vậy hệ số trong (theo cách xác định là tổng số tất cả các số 1 xuất hiện trong tất cả các phân hoạch của số nguyên ) sẽ được tính bằng tổng số các phân hoạch trong đó số 1 xuất hiện đúng một lần cộng với hai lần số các phân hoạch trong đó số 1 xuất hiện 2 lần, cộng với ba lần số các phân hoạch trong đó số 1 xuất hiện 3 lần  Do đó:
Suy ra: 
Xét đạo hàm riêng của theo biến , ta có: 
Cho , ta có: 
 Lại do: nên 
Do đó: 
Tương tự, ta thiết lập hàm bằng cách xét hàm:
Trong đó là số các phân hoạch của với phần tử phân biệt. Biến biểu diễn cho các phần tử trong phân hoạch và biến biểu diễn số lần xuất hiện của phần tử nào đó trong phân hoạch.
Tương tự trên ta có số tất cả các số phân biệt có trong tất cả các phân hoạch của mà mỗi phân hoạch có đúng số phân biệt là , như vậy hệ số trong (theo cách xác định là số các số nguyên dương phân biệt xuất hiện trong tất cả các phân hoạch của số nguyên ) sẽ được tính bằng tổng số các phân hoạch trong đó có đúng 1 số xuất hiện cộng với hai lần số các phân hoạch trong đó có 2 số phân biệt xuất hiện, cộng với ba lần số các phân hoạch trong đó có 3 số phân biệt xuất hiện Do đó:
Suy ra: .
Tương tự trên ta có: , trong đó
 , với .
Vậy ta có: .
Suy ra: 
(Do )
Từ (1) và (2) suy ra, do đó với mọi n.
Bài toán 6:
Cho số nguyên dương và , trong đó chia hết cho . Tính số các bộ bốn số nguyên dương sao cho tổng chia hết cho và 
HD: Sử dụng định lý 1 và 3
5. Một số bài toán áp dụng:
Bài 1: Cho p là một số nguyên tố lẻ và số nguyên dương k không vượt quá p − 1. Tìm số tập con k phân tử của {1,2,  , p}, sao cho tổng các phần tử của mỗi tập con đó đều chia hết cho p.
Bài 2: (IMO Shortlist 1998) Cho là dãy không giảm các số tự nhiên sao cho mọi số tự nhiên đều có thể biểu diễn một cách duy nhất dưới dạng với
 không nhất thiết phân biệt.
Bài 3: (USA MO 1996) Xác định (kèm chứng minh) tập con X của tập các sô nguyên với tính chất sau: mọi số nguyên n có đúng một nghiệm của phương trình a + 2b = n với .
Bài 4: Tính tổng .
Bài 5: Chứng minh rằng . 
Bài 6: (China 1996) Cho số nguyên dương n. Tìm số các đa thức với hệ số thuộc tập {0,1,2,3} thỏa mãn .
Bài 7: (Putnam 1957) Gọi là số các cách biểu diễn n thành tổng gồm 1 và 2, xếp theo thứ tự. Ví dụ 4 = 1 + 1 + 2 = 1 + 2 + 1 = 2 + 1 + 1 = 2 + 2 = 1 + 1 + 1 + 1 (ta có). Gọi là số các cách biểu diễn n thành tổng các số nguyên lớn hơn 1. Ví dụ 6 = 4 + 2 = 2 + 4 = 3 + 3 = 2 + 2 + 2 ta có .