Luận văn Thạc sĩ Toán học: Bài toán phân hoạch số nguyên dương

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ..................................................

ĐINH THỊ THU HUẾ

BÀI TOÁN PHÂN HOẠCH SỐ NGUYÊN DƯƠNG

LUẬN VĂN THẠC SĨ TOÁN HỌC

Thái Nguyên - 2017

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC ..................................................

ĐINH THỊ THU HUẾ

BÀI TOÁN PHÂN HOẠCH SỐ NGUYÊN DƯƠNG

Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ CẤP Mã số : 60 46 01 13

LUẬN VĂN THẠC SĨ TOÁN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH. HÀ HUY KHOÁI

Thái Nguyên - 2017

Mục lục

MỞ ĐẦU 1

1 Một số kết quả kinh điển về bài toán phân hoạch số nguyên

dương 3

1.1 Lịch sử phát triển của bài toán phân hoạch số nguyên dương 3

1.2 Một số kết quả kinh điển . . . . . . . . . . . . . . . . . . . 11

. . . . . . . . . . . . 11 1.2.1 Công thức gần đúng cho p(n)

1.2.2 Hàm sinh của hàm phân hoạch . . . . . . . . . . . 13

. . . . . . . . . . . . . 22 1.2.3 Đồng nhất thức Rogers–Ramanujan . . . . . . . . . 18 1.2.4 Tính chất đồng dư của p(n)

1.2.5 Biểu diễn đồ thị của các phân hoạch và chứng minh

Định lí số ngũ giác của Euler . . . . . . . . . . . . . 27

2 Một số lớp bài toán phân hoạch số nguyên khác nhau và

các bài toán liên quan 31

2.1 Phân hoạch thành những phần phân biệt và ánh xạ đối hợp

của Franklin . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2 Phân hoạch thành những phần lẻ và song ánh Sylvester . . 34

2.3 Một số bài toán liên quan . . . . . . . . . . . . . . . . . . . 35

2.3.1 Một số bài toán chứng minh . . . . . . . . . . . . . 35

2.3.2 Bài toán chia kẹo của Euler . . . . . . . . . . . . . . 39

KẾT LUẬN 50

TÀI LIỆU THAM KHẢO 51

Danh mục các hình vẽ

Hình 2.1:..........................................................................................33

Hình 2.2:..........................................................................................33

Hình 2.3:..........................................................................................35

Hình 2.4:..........................................................................................36

MỞ ĐẦU

Bài toán biểu diễn số nguyên dương dạng tổng các số nguyên dương đã

có lịch sử lâu đời. Leibniz là người đầu tiên nghiên cứu bài toán này, sau

đó Euler, Sylvester, Hardy, Ramanujan, Andrews... là các nhà toán học có

những đóng góp quan trọng. Bài toán nói trên xuất hiện trong nhiều vấn

đề khác nhau của toán học và là đề tài nghiên cứu sôi nổi cho đến tận

ngày hôm nay (Các công trình của Okounkov, Giải thưởng Fields 2006, có

liên quan đến việc ứng dụng bài toán trên trong xác suất, hình học đại số,

cơ học thống kê,...). Dưới sự hướng dẫn tận tình của GS.TSKH. Hà Huy

Khoái, tác giả chọn đề tài:"Bài toán phân hoạch số nguyên dương".

Luận văn có mục tiêu giới thiệu bài toán biểu diễn số nguyên dương dưới

dạng tổng, từ lịch sử phát triển và những kết quả kinh điển, đến một số

kết quả gần đây. Luận văn cũng trình bày một số bài toán liên quan đến

bài toán nói trên.

Chương 1. Một số kết quả kinh điển về bài toán phân hoạch số nguyên dương

Với mục tiêu trên, tác giả tiến hành nghiên cứu hai chương:

1.1. Lịch sử phát triển của bài toán phân hoạch số nguyên dương

1.2. Một số kết quả kinh điển

Chương 2. Một số lớp bài toán phân hoạch số nguyên khác nhau và một số bài toán liên quan

2.1. Phân hoạch thành những phần phân biệt và ánh xạ đối hợp của

Franklin

2.2. Phân hoạch thành những phần lẻ và song ánh Sylvester

2.3. Một số bài toán liên quan.

Luận văn được hoàn thành dưới sự hướng dẫn, giúp đỡ tận tình của

GS.TSKH. Hà Huy Khoái, tác giả xin bày tỏ lòng biết ơn và kính trọng

sâu sắc đối với Giáo sư. Tác giả xin gửi lời cảm ơn chân thành đến Ban

giám hiệu, Phòng sau đại học và Khoa Toán-Tin trường Đại học Khoa học

- Đạị học Thái Nguyên đã tạo mọi điều kiện thuận lợi cho tác giả trong

suốt quá trình học tập và nghiên cứu tại trường. Xin chân thành cảm ơn

sự giúp đỡ của bạn bè, người thân trong thời gian qua.

Mặc dù đã có nhiều cố gắng, song do thời gian và trình độ còn hạn chế

nên bản luận văn khó tránh khỏi những thiếu sót nhất định. Tác giả rất

mong nhận được ý kiến đóng góp của quý độc giả để bản luận văn này

được hoàn thiện hơn.

Tác giả xin chân thành cảm ơn!

Thái Nguyên, tháng 06 năm 2017

Tác giả

Đinh Thị Thu Huế

Chương 1

Một số kết quả kinh điển về bài

toán phân hoạch số nguyên dương

Mục đích của chương này là trình bày lịch sử phát triển và một số kết

quả kinh điển về bài toán phân hoạch số nguyên dương. Tài liệu tham

khảo chính của Chương là [3], [4] .

1.1 Lịch sử phát triển của bài toán phân hoạch số nguyên

dương

Phân hoạch lần đầu tiên xuất hiện trong bức thư tay của Leibnitz viết

vào năm 1669 gửi cho John Bernoulli, ông hỏi Bernoulli liệu có kiểm tra

nhanh được số cách viết một số nguyên dương đã cho thành tổng của hai

hay nhiều số nguyên? Từ đây lý thuyết phân hoạch được hình thành và

là một nhánh quan trọng của lý thuyết số. Khái niệm phân hoạch các số

nguyên không âm cũng thuộc về toán học tổ hợp (xem [4]).

Định nghĩa 1.1 (xem [4]). Một phép phân hoạch của số nguyên dương n là một dãy không tăng hữu hạn của các số nguyên dương λ1 (cid:62) λ2 (cid:62) . . . (cid:62) λr sao cho (cid:80)r i=1 λi = n, λi được gọi là các phần hoặc các số hạng của phân hoạch. Đôi khi phân hoạch (λ1, λ2, . . . , λr) được kí hiệu bởi λ và ta viết là λ (cid:96) n hoặc | λ |= n.

Định nghĩa 1.2 (xem [4]). Hàm phân hoạch p(n) là số các phân hoạch của n.

Khi xét phép phân hoạch của n có một số chú ý sau (xem [4]):

Chú ý 1.1. Chúng ta thấy 0 có một phân hoạch, phân hoạch rỗng, nó không có phần tử nào. Ta quy ước p(0) = 1.

Chú ý 1.2. Thường viết tắt phần lặp bằng cách sử dụng lũy thừa.

Chú ý 1.3. Theo định nghĩa phân hoạch thứ tự không quan trọng. 4+3

và 3+4 đều là một phân hoạch của 7. Một tập hợp có thứ tự được gọi là

một phép hợp thành. Do đó, 4+3 và 3+4 là hai phép hợp thành khác nhau

của 7.

Ví dụ 1.1. Có năm phân hoạch của số 4 là 4, 31, 22, 212, 14. Có bảy phân hoạch của số 5 là 5, 41, 32, 312, 221, 213, 15.

Leibnitz quan sát có 3 phân hoạch của 3 (3, 21, 13), 5 phân hoạch của 4. Sau đó ông cũng quan sát được có 7 phân hoạch của 5 và 11 phân hoạch của 6. Điều này gợi ý, số phân hoạch của n bất kỳ luôn là một số nguyên

tố. Tuy nhiên, điều này không đúng khi tính toán được 15 phân hoạch của

7. Như vậy ngay từ những bước khởi đầu, bài toán phân hoạch đã dẫn đến

câu hỏi mở mà đến tận ngày hôm nay vẫn chưa có lời giải: tồn tại vô hạn hay hữu hạn n sao cho số phân hoạch n là một số nguyên tố? Bên cạnh đó là những câu hỏi về p(n) như: cấp tăng của nó như thế nào? Tính chẵn lẻ

của nó? Liệu nó có những tính chất số học đặc biệt nào? Có cách nào để tính p(n) hiệu quả không?(xem [3]).

Từ đây thiết lập những chủ đề khác nhau và lý thuyết phân hoạch được

phát triển xa hơn bởi nhiều nhà Toán học vĩ đại, nổi bật trong số họ là

Euler, Gauss, Jacobi, Cayley, Sylvester, Hardy, Ramanujan, Rademacher,

Schur, Mac Mahon, Gupta, Gordon, Andrews, Stanley. . . Công việc nghiên

cứu của Ramanujan cùng Hardy thực sự cách mạng hóa việc nghiên cứu về

thuyết phân hoạch. Bởi những ứng dụng vĩ đại của nó trong các lĩnh vực

khác nhau như xác suất thống kê, vật lý cơ học. . . lý thuyết phân hoạch

trở thành lĩnh vực nghiên cứu sôi nổi của lý thuyết số.

Có thể thấy p(n) tăng rất nhanh theo n. Thậm chí, nếu một người nào

đó có thể tập trung làm việc một cách hoàn hảo thì cũng phải mất 126000

năm để viết tất cả 3972999029388 phân hoạch của 200. Ramanujan đã tự hỏi mình một câu hỏi cơ bản: Chúng ta có thể tìm p(n) mà không cần viết tất cả các phân hoạch của n không?” Câu hỏi này đã được Hardy và

Ramanujan trả lời vào năm 1918. Họ đã đưa ra công thức gần đúng cho p(n). Tuy tiên D.H.Lehmer nhận thấy chuỗi Hardy – Ramanujan phân kỳ. Năm 1937, H. Rademacher thay thế điều kiện để nhận được p(n) là chuỗi

hội tụ. Hardy – Ramanujan – Rademacher lập ra công thức mở rộng cho p(n) nổi tiếng, đó là kết quả đáng ghi nhận nhất trong toán học. Nó cho thấy sự tương tác giữa một hàm số học p(n) và một số kỹ thuật tính toán. Nó không chỉ là công thức lý thuyết cho p(n) mà còn là công thức cho

phép tính tương đối nhanh (xem [4]– Tr 6).

Một số giá trị của p(n)

1 2 3 4 5 6

100

200

20

50

9 n : p(n) : 1 2 3 5 7 11 30 627 204226 190569292 3972999029388

Nhiều khi chúng ta chỉ cần quan tâm đến những bài toán không nhất thiết phải xét đến tất cả các phân hoạch của n mà chỉ các phân hoạch đặc biệt nào đó của n.

Ví dụ 1.2. Trong số 22 phân hoạch của số 8, chỉ có sáu phân hoạch chứa các phần là số lẻ 71, 53, 513, 3212, 315, 18 và cũng có 6 phân hoạch trong đó các phần tử phân biệt 8, 71, 62, 53, 521, 431.

Về vấn đề này đã được Euler bắt đầu nghiên cứu vào năm 1674. Ph.Naudé hỏi Euler về phân hoạch một số nguyên dương n thành m phần nhất định.

Đặc biệt, Naudé đã hỏi ông có bao nhiêu phân hoạch của 50 thành 7 phần

riêng biệt. Câu trả lời đúng là 522, điều này khó có khả năng thu được

bằng cách viết ra tất cả các phân hoạch của 50 thành 7 phần. Để giải

quyết vấn đề này Euler đã khám phá và giới thiệu hàm sinh của hàm phân

hoạch, các đồng nhất thức, định lí số ngũ giác, đó là sự đổi mới quan trọng

nhất trong toàn bộ nghiên cứu về phân hoạch. Hầu hết mọi phát hiện về

phân hoạch đều nhờ vào sự bắt đầu của Euler (xem [3]).

Từ cuối thế kỉ XVIII cho tới nửa đầu thế kỉ XIX không xuất hiện nhiều

bước tiến đáng ghi nhận trong nghiên cứu về phân hoạch. Tất nhiên điều

tương tự không xảy ra với toán học nói chung. Đã có sự xuất hiện những

nghiên cứu về lý thuyết biến phức và lý thuyết của hàm eliptic và chúng

đã mang lại ảnh hưởng sâu sắc tới nghiên cứu về phân hoạch. Legendre,

Gausse, Cauchy và những nhà toán học vĩ đại khác đã tìm ra được lời giải

thích cho công trình của Euler.

Trong một thế kỷ từ năm 1750 – 1850, trọng tâm chính của việc nghiên cứu là đưa ra công thức tường minh cho pm(n), số phân hoạch n thành các phần không lớn hơn m. P. Paoli, A. Dc Morgan, F.W. Herschsl, T. Kirkmar và H. Warburton, Cayley, Sylvester...đã nghiên cứu pm(n) với những giá trị nhỏ xác định của m và họ đưa ra được một số công thức

nhất định. Tuy nhiên, Sylvester mới là nhà toán học tiếp theo đưa ra được

cái nhìn thực sự mới cho vấn đề này(xem [3]– Tr 5). Sau khi xem xét một

vài cách mà phân hoạch thực sự có thể được đưa ra dưới dạng hình học, ông khẳng định rằng phân hoạch 5 + 5 + 4 + 3 + 3 có thể được biểu diễn

thuận tiện hơn nhiều dưới dạng:

∗ ∗

∗ ∗ ∗

∗ ∗ ∗ ∗ ∗

Sylvester gọi cách biểu diễn này là biểu đồ Ferrers của phân hoạch, đặt

tên theo nhà toán học N.M. Ferrers. Ông đã chú ý rằng ta có thể đếm số

nút ở các cột thay vì các hàng. Lấy ví dụ như biểu đồ ở trên có thể cho ta phân hoạch 5 + 5 + 5 + 3 + 2. Hai phân hoạch từ cùng một biểu đồ như

trên được gọi là liên hợp.

Định nghĩa 1.3 (xem [3]). Phân hoạch n là tự liên hợp nếu liên hợp của

nó trùng với chính nó.

Ví dụ 1.3. Phân hoạch 7+6+4+4+2+2+1 của 26

∗

∗ ∗

∗ ∗ ∗ ∗

∗ ∗ ∗ ∗ ∗ ∗

∗ ∗ ∗ ∗ ∗ ∗ ∗

Như vậy, Sylvester khẳng định một cách tiếp cận hoàn toàn mới đối với

phân hoạch. Cách chứng minh của Fabian Franklin cho định lý số ngũ giác

của Euler sẽ cho ta biết về giá trị của lối suy nghĩ mới này. Franklin từng

là một học trò của Sylvester tại trường đại học John Hopkins và chứng

minh của Franklin đã lột tả được sức mạnh trong ý tưởng của Sylvester.

Hans Rademacher cho rằng nghiên cứu của Franklin là những thành tựu

có ý nghĩa đầu tiên của toán học Mỹ. Nó có thể được xem như là điểm

khởi đầu của một loạt những nghiên cứu sâu sắc về phân hoạch.

Phân hoạch được nghiên cứu ở nhiều khía cạnh khác nhau. MacMahon

đã nghiên cứu những dạng khác nhau của phân hoạch và ông là người đầu

tiên nghiên cứu về phân hoạch phẳng.

Định nghĩa 1.4 (xem [4]). Một phân hoạch phẳng π của n là một ma trận các số dương, không tăng theo mỗi dòng, mỗi cột và (cid:80) ni,j = n. Mỗi ni,j là một bộ phận của π.

n1,1 n1,2 n1,3 n2,1 n2,2 n2,3 n3,1 n3,2 n3,3 . .

. .

. . . . . . . . . . . . . . .

Ví dụ 1.4. Các phân hoạch phẳng của 3

1 1 1 1 , 1 1 , 1 , 2 1 , 2 , 3 1

1

Phân hoạch phẳng được gọi là đối xứng nếu ni,j = nj,i với mọi i, j.

Ví dụ 1.5. Phân hoạch phẳng của 18

6 4 1 2 4 1

Nếu các phần của π giảm chặt theo mỗi hàng thì ta nói rằng π là nghiêm ngặt hàng. Nếu các phần của π là giảm chặt mỗi cột thì ta gọi π là nghiêm ngặt cột. Nếu π vừa nghiêm ngặt hàng, vừa nghiêm ngặt cột thì ta gọi π

là nghiêm ngặt hàng và cột. Phân hoạch nghiêm ngặt cột cũng giống như

bảng Young được sử dụng trong lý thuyết bất biến.

Phân hoạch phẳng được ứng dụng trong phép biểu diễn lý thuyết nhóm

đối xứng, hình học đại số và trong nhiều vấn đề tổ hợp. Phân hoạch phẳng cùng với nhiều nhất k dòng được gọi là phân hoạch k-dòng. Ký hiệu tk(n) là số phân hoạch k dòng của n. Phân hoạch phẳng là lĩnh vực được nghiên

cứu tích cực. Tuy nhiên ở đây chúng ta chỉ nói đến đồng dư Ramanujan tk(n). F– Phân hoạch:(xem [4])

Một phân hoạch Frobenius suy rộng (một F – phân hoạch) của n là một

ma trận 2 hàng các số nguyên

(cid:32) (cid:33)

a1, a2, . . . b1, b2, . . .

i=1 ai + (cid:80)r

i=1 bi.

trong đó, a1 (cid:62) a2 (cid:62) . . . (cid:62) ar (cid:62) 0, b1 (cid:62) b2 (cid:62) . . . (cid:62) br (cid:62) 0 sao cho n = r + (cid:80)r

Ví dụ 1.6. Cho n = 3, với giá trị tương ứng r = 1, 1, 1, 2, 2 và cho phép

lặp tối đa 2 lần ở bất kì hàng nào thì các F – phân hoạch

(cid:32) (cid:32) (cid:33)

(cid:33) , (cid:33) , (cid:33) , (cid:33) (cid:32) 0 , 2 (cid:32) 1 1

1, 0 0, 0

0, 0 1, 0

(cid:32) 2 0

Chú ý : Các phân hoạch được gán cho Frobenius vì ông là người đầu

tiên nghiên cứu chúng trong lý thuyết biểu diễn nhóm với các giả thiết a1 > a2 > . . . > ar (cid:62) 0, b1 > b2 > . . . > br (cid:62) 0.

φk(n) ký hiệu số các F– phân hoạch của n sao cho mỗi số hạng xuất hiện nhiều nhất k lần trong mỗi hàng. Một F – phân hoạch được gọi là

một F-phân hoạch k-màu nếu trong mỗi hàng các phần là phân biệt, và

lấy từ k – bản sao của các số nguyên không âm có thứ tự như sau

01 < 02 < . . . < 0k < 11 < 12 < . . . < 1k < 21 < 22 < . . . < 2k < ...

Ký hiệu cφk(n) là số các phân hoạch k-màu của n. Ta sẽ đề cập ngắn

gọn tính chất đồng dư Ramanujan của φk(n),cφk(n) ở phần sau.

Euler đã nói về các đồng nhất thức trong phân hoạch, nhưng các kết

quả của ông không thu được nhiều sự chú ý cho đến những năm đầu

của thế kỉ 20, khi đồng nhất thức Rogers- Ramanujan trở nên nổi tiếng

(xem [3],[4]). Nó được phát hiện đầu tiên bởi Rogers vào năm 1894 và bởi

Ramanujan vào năm 1913. Sự phát hiện của Rogers được viết trong một

bài báo nằm trong một cuốn Kỉ yếu của Hội Toán học Luân Đôn. Bài viết

của ông đã bị lãng quên cùng thời gian. Về phần Ramanujan, ông không

chứng minh được khám phá của mình nên đã gửi những đồng nhất đó

tới S.H. Hardy, Hardy cũng không thể chứng minh chúng. Ông lại chuyển

chúng cho Littlewood, MacMahon và Perron, và không ai có thể chứng

minh được. Không ai nghĩ là chuyển chúng cho Rogers, vì vậy phát hiện

của Ramanujan vẫn chưa được chứng minh. Mac Mahon đã nói không có

lý do gì để nghi ngờ tính đúng đắn của nó, nhưng nó vẫn chưa được xác

minh. Vào năm 1917, Ramanujan đã đọc được bài viết của Rogers trong

một tờ báo cũ, niềm vui lớn với ông vì tìm được sự tương đồng. Ông đã

viết thư trao đổi với Rogers. Năm 1919, Ramanujan xuất bản một bài

báo trong đó có hai chứng minh (một của Rogers và một của Ramanujan)

và một nhận xét của Hardy. Sau khi xuất bản, kết quả đó nổi tiếng với

tên gọi đồng nhất Rogers- Ramanujan. Đồng nhất Rogers – Ramanujan là

một trong những công thức đẹp nhất của toán học. Nghiên cứu về đồng

nhất thức trong phân hoạch vẫn tiếp tục. Mười bốn năm sau, Hardy nhận

xét về nghiên cứu của Lehmer, Alder và Rademacher: “Có thể thấy rằng

không có đồng nhất nào tương ứng với modun cao hơn 5”. Kết quả này

hóa ra là sai lầm. Năm 1963, B. Gordon đã thực hiện những bước đầu

tiên hướng tới sự khảo sát đầy đủ định lý kiểu này và đã đưa ra định lí

Gordon. Định lý Gordon dẫn đến sự bùng nổ các kết quả. Năm 1982, G.

Andrews đã đưa ra tương tự giải tích của định lí B. Gordon, D. Bressoud

làm nên đột phá lớn về tổ hợp trong nghiên cứu về đồng nhất thức của

phân hoạch. Những kết quả này được ứng dụng trong nhiều lĩnh vực khác

nhau. G.Andrews và R. Askey đã chứng minh một mối liên hệ giữa đồng

nhất Rogers – Ramanujan và đa thức trực giao. J. Lepowsky, A. Feingold,

S. Milne và R. Wilson đã tìm thấy một liên hệ với đại số Lie, F.Dyson tìm

thấy các ứng dụng của đồng nhất Rogers – Ramanujan trong vật lý hạt

và R.J.Baxtes trong cơ học thống kê.

Dyson lại đưa ra cách tiếp cận mới về phân hoạch, năm 1944 ông công

bố một công trình trong Tạp chí khoa học Eureka của sinh viên khoa toán

Cambridge, trong đó ông đưa ra khái niệm hạng của phân hoạch .

Định nghĩa 1.5 (xem [5]–Tr5). Phân hoạch λ có a(λ), l(λ) lần lượt là phần lớn nhất và số các phần của λ. Khi đó r(λ) = a(λ) − l(λ) được gọi là hạng của λ.

Ông phát biểu giả thuyết nói rằng hạng sẽ cho một cách diễn giải tổ

hợp về các đồng nhất thức của Ramanujan. Khi vẫn còn là một sinh

viên, Dyson không chứng minh được giả thuyết này. Năm 1948, Atkin và

Swinnerton-Dyer đã chứng minh được giả thuyết và được công bố vài năm

sau.

Dyson chuyển đến Hoa Kì và đã công bố giả thuyết của ông dưới dạng

một bài toán ngắn trong tờ báo Toán học Hoa Kì hàng tháng . Nathan

Fine rất quan tâm đến bài toán và đưa ra ba định lý để liệt kê các phân

hoạch xác định hạng. Những kết quả của ông có vẻ bí ẩn và hẳn còn

giữ nguyên ở trạng thái đó nếu không có sự xuất hiện của cuốn sách

"Basic hypergeometric series and applications” và bài báo của Dyson "A

new symmetry of partitions". Không biết đến nghiên cứu của Fine, Dyson

khám phá lại một trong những thành quả của Fine chưa được công bố, gọi

nó là " phép đối xứng mới" và chứng minh nó bằng phương pháp tổ hợp.

Sau đó ông suy ra điều kiện cho công thức và thu được một cách chứng

minh mới rất đơn giản cho định lý số ngũ giác của Euler.

Thật đáng tiếc, ngoại trừ công trình của Andrews "Định lí phân hoạch

của N.J. Fine", dường như không có ai nhận thấy thực ra ánh xạ Dyson,

đôi khi gọi liên hợp của Dyson, có thể được dùng để chứng minh theo

tổ hợp những kết quả của Fine. Nhưng ngay cả Andrews dường như cũng

không biết rằng dùng ánh xạ của Dyson chứng minh được hai định lý khác

của Fine.

Đầu thế kỷ XX, Revet, Alfred Young trong một loạt bài viết về lý thuyết

bất biến đã đưa ra các phân hoạch và các biến thể của chúng (bây giờ gọi

là bảng Young) trong lý thuyết biểu diễn của nhóm đối xứng.

Vào nửa cuối của thế kỷ XX, các ứng dụng của phân hoạch phát triển

rất nhanh, T. W. B. Hughes đã phát triển ứng dụng (cả hai chiều) giữa đại

số Lie và phân hoạch. J. Leponsky và những người khác cho thấy làm thế

nào để hiểu và chứng minh đồng nhất Rogers – Ramanujan trong đại số Lie

và một số ứng dụng của phân hoạch xuất hiện trong vật lý. Đặc biệt công

trình của Rodrey Baxter cho thấy rằng đồng nhất Rogers – Ramanujan

quyết định trong nghiên cứu hoạt động của dung dịch Heli trên một tấm

than chì. Phân hoạch cùng ứng dụng của nó vẫn là vấn đề được nghiên

cứu sôi nổi đến tận ngày nay.

1.2 Một số kết quả kinh điển

1.2.1 Công thức gần đúng cho p(n)

Để trả lời cho câu hỏi của Ramanujan "Có cách nào để tính p(n) hiệu quả không?", một số nhà toán học đã đưa ra các công thức cho p(n).

Cayley (năm 1855) và Sylvester (năm 1882) đã đưa ra một số công thức cho pk(n) với k nhỏ, ở đây pk(n) là số phân hoạch của n thành các phần không lớn hơn k (xem [3]–Tr13). Ví dụ:

(1.1)

],

p2(n) = [

(1.2)

},

p3(n) = {

(n + 1) 2 (n + 3)2 12

trong đó [x] là số nguyên lớn nhất không vượt quá x, {x} là số nguyên gần x nhất.

Một trong những bất ngờ lớn nhất trong lịch sử của nghiên cứu phân

v (cid:88)

hoạch là năm 1918, Hardy và Ramanujan đã đưa ra công thức gần đúng cho p(n) (xem [4]):

(1.3)

p(n) =

Ak(n)(un − k)exp(un/k) + O(n−1),

(12)1/2 (24n − 1)un

k=1

√

π

24n − 1

, v = O

n và

ở đây, un =

6

(cid:88)

Ak(n) =

ωh,ke−2nhπi/k,

0≤h

trong đó ωh,k là căn bậc 24 của đơn vị. Một vài số hạng đầu tiên của (1.3) cho giá trị phần nguyên trong p(n) là chính nó. Tuy tiên D.H.Lehmer nhận thấy chuỗi Hardy – Ramanujan (1.3) phân kỳ. Nhưng H. Rademacher đã chứng minh được rằng nếu thay (un−k)exp(un/k) bởi (un−k)exp(un/k)+ (un+k)exp(−un/k) thì nhận được chuỗi hội tụ đối với p(n). Năm 1937,Hardy – Ramanujan – Rademacher đưa ra công thức mở rộng cho p(n) nổi tiếng

dưới đây

(cid:34) (cid:35)

sinh π

∞ (cid:88)

k [ 2

24)]1/2

1 √

(1.4)

p(n) =

,

Ak(n) · k1/2

d dx

3(x − 1 (x − 1/24)1/2

π

2

k=1

x=n

ở đây Ak(n) được định nghĩa như trên. Công thức (1.4) là một trong những kết quả đáng ghi nhận nhất trong toán học. Nó cho thấy sự tương tác giữa một hàm số học p(n) và một số kỹ thuật tính toán. Nó không chỉ là công thức lý thuyết cho p(n) mà còn là công thức cho phép tính tương

đối nhanh. Ví dụ, nếu chúng ta tính 8 số hạng đầu tiên của chuỗi đối với n = 200 thì kết quả là 3972999029388, đó là kết quả chính xác p(200), và p(1000) ≈ 2.4 × 1031, khá gần với giá trị đúng của p(1000) (lớn hơn giá trị đúng khoảng 1.415%). Năm 2012, tìm được số nguyên tố p(82352631)

gồm 10101 chữ số thập phân. Phương pháp vòng được phát triển để chứng minh công thức p(n) về sau rất hữu ích trong phát triển lý thuyết hàm

modular.

1.2.2 Hàm sinh của hàm phân hoạch

Leonhard Euler đã trả lời câu hỏi của Naudé có bao nhiêu phân hoạch

của 50 thành 7 phần riêng biệt bằng cách đưa ra hàm sinh (xem [3]). Sử dụng ký hiệu hiện đại, chúng ta giả sử D(m, n) ký hiệu số phân hoạch n thành m phần thì

∞ (cid:89)

(cid:88)

D(m, n)zmqn = (1 + zq1)(1 + zq2)(1 + zq3) . . . =

(1 + zqj).

m,n≥0

j=1

Đồng nhất thức này trở nên rõ ràng khi chúng ta nhân những thừa số

bên phải với nhau. Số hạng tổng quát là:

(zqi1)(zqi2) . . . (zqij) = zjqi1+i2+...+ij.

∞ (cid:89)

Chú ý rằng

(1 + zqj) = (1 + zq)

(1 + (zq)qj).

j=1

Ta có phương trình hàm cho hàm sinh của D(m, n)

(cid:88) (cid:88)

D(m, n)zmqn = (1 + zq)

D(m, n)zmqn+m.

m,n≥0

So sánh hệ số của zmqn cả hai vế ta thấy:

D(m, n) = D(m, n − m) + D(m − 1, n − m).

∞ (cid:88)

Phương trình cho phép tính toán dễ dàng các giá trị của D(m, n). Naudé cũng đã hỏi Euler: Hàm sinh của p(n) là gì? Số các phân hoạch của n là bao nhiêu? Để trả lời câu hỏi đó Euler đã áp dụng cùng một nguyên tắc trong tính toán D(m, n) rất hiệu quả, cụ thể

p(n)qn = (1 + q1 + q1+1 + q1+1+1 + q1+1+1+1 + . . .)

n=0

× (1 + q2 + q2+2 + q2+2+2 + q2+2+2+2 + . . .) × (1 + q3 + q3+3 + q3+3+3 + q3+3+3+3 + . . .)

.

∞ (cid:89)

(1 + qn + qn+n + qn+n+n + qn+n+n+n + . . .)

=

n=1 ∞ (cid:89)

(1 + qn + q2n + q3n + q4n + . . .)

=

n=1 ∞ (cid:89)

=

1 1 − qn .

n=1

∞ (cid:88)

Hay

(1.5)

.

p(n)qn =

1 (q; q)∞

n=0

∞ (cid:89)

Ở đây, | q |≤ 1 và (q; q)n được định nghĩa bởi

,

(a; q)n =

(1 − aqi) (1 − aqn+i)

i=1

đối với hằng số a tuỳ ý. Quy ước p(0) = 1. Nếu n là số nguyên dương thì rõ ràng

(a; q)n = (1 − a)(1 − aq)...(1 − aqn−1),

và

((a; q)n).

(a; q)∞ = (1 − a)(1 − aq)(1 − aq2) . . . = lim n→∞

(cid:81)∞ Vào thời điểm này, Euler nhận ra rằng khai triển chuỗi luỹ thừa của i=1(1 − qn) quan trọng đối với tính toán p(n). Ông khám phá ra bằng

∞ (cid:89)

thực nghiệm

(1 − qn) = (1 − q − q2 + q5 + q7 − q12 − q15 + q22 + q26 + . . .)

n=1

∞ (cid:88)

=

(−1)n.qn(3n−1)/2.

n=−∞

Nhiều năm sau khám phá của mình, Euler đã thành công trong việc tự

mình đưa ra chứng minh cho phát hiện này. Công thức này nổi tiếng với

tên gọi định lý số ngũ giác của Eulers.

∞ (cid:88)

Định lí 1.1. (Định lí số ngũ giác của Euler) Cho | q |< 1 ta có

(1.6)

(−1)sqs(3s−1)/2.

(q; q)∞ =

s=−∞

∞ (cid:88)

Chúng ta sẽ tìm hiểu chứng minh định lí này ở phần sau. Kết hợp Định lí số ngũ giác của Euler và hàm sinh của p(n) ta có:

(1.7)

(−1)n.qn(3n−1)/2)

p(n)qn = 1.

( n=−∞

n=0

So sánh hệ số của qN trong hai vế của đồng nhất thức cuối cùng này,

Euler đã tìm ra phép truy hồi cho p(N ) : p(0) = 1,

p(N ) − p(N − 1) − p(N − 2) + p(N − 5) + p(N − 7) − . . . = 0, N > 0.

Không ai có thể tìm được một thuật toán hiệu quả hơn trong việc tính toán p(N ). Nó tính được đầy đủ các giá trị của p(n) khi n ≤ N với thời gian O(N 3/2). Quan hệ truy hồi này được sử dụng bởi P.A. MacMahon để tính toán p(n) với 1 ≤ n ≤ 200 và bởi H. Gupta để xác định p(n) với 201 ≤ n ≤ 300. Nếu muốn tính toán giá trị nào đó của p(n) trên máy

tính, thì máy tính có lẽ là sẽ sử dụng :

(cid:88)

p(N ) =

(−1)k−1.qk(3k±1)/2p(n).

k(3k±1)/2+n=N,0≤n

Việc đưa ra hàm sinh của Euler là đổi mới quan trọng nhất trong toàn

bộ nghiên cứu về phân hoạch. Hầu như mọi phát hiện về phân hoạch đều

nhờ vào sự khởi đầu của Euler.

Tiếp theo tác giả đưa ra một số định lí liên quan tới hàm phân hoạch.

Tài liệu tham khảo chính là bài giảng "Partitions" của Bruce Berndt

< http://www.math.uiuc.edu/ berndt/master-partitions.pdf >, bản cập

nhật ngày 15/4/2017.

Nếu ta kí hiệu pm(n) là số phân hoạch của n thành các phần không lớn

∞ (cid:88)

hơn m thì rõ ràng

=

pm(n)qn

1 (q, q)m

n=0

Định lí 1.2. Giả sử pm(n) ký hiệu số phân hoạch của n thành các phần không lớn hơn m , p(m, n) là số phân hoạch của n thành đúng m phần. Khi đó, pm(n) = p(m, n).

Chứng minh: Xét biểu đồ Ferrers của n, như trong hình dưới là biểu đồ

Ferrers của 29 = 7+7+6+5+2+2

∗ ∗

∗ ∗ ∗

∗ ∗ ∗ ∗

∗ ∗ ∗ ∗ ∗ ∗

Biểu đồ trên cho ta phân hoạch của p(6; 29). Thay vì đọc phân hoạch

từ trên xuống dưới, ta đọc biểu đồ Ferrers từ trái sang phải. Như vậy,

trong hình trên với phân hoạch này, cụ thể là 29 = 6 + 6 + 4 + 4 + 4 + 3 + 2, được đếm theo p6(29). Mỗi phân hoạch như vậy được đếm theo p(m; n) liên kết duy nhất với phân hoạch đếm theo pm(n). Rõ ràng, điều này thiết lập một song ánh cho các phân hoạch đếm bằng p(m; n) với các phân hoạch đếm bằng pm(n). Do đó, ta có điều phải chứng minh.

∞ (cid:88)

Định lí 1.3. Giả sử Q(n) ký hiệu số phân hoạch của n thành các phần phân biệt. Khi đó hàm phân hoạch cho Q(n) được cho bởi

(1.8)

Q(n)qn = (−q; q)∞.

n=0

Chứng minh: Chú ý rằng (−q; q)∞ chỉ sinh ra hai số hạng đầu tiên của mỗi dãy trong vế phải của (1.5). Như vậy, trong mỗi phân hoạch của n, mỗi số nguyên không lớn hơn n có thể xuất hiện trong một phân hoạch cụ thể của n nhiều nhất một lần. Định lý được chứng minh.

Định nghĩa 1.6. Giả sử po(n) ký hiệu số phân hoạch của n thành các phần lẻ và pe(n) ký hiệu số phân hoạch của n thành các phần chẵn .

∞ (cid:88)

Nhận thấy rằng

(1.9)

=

po(n)qn và

pe(n)qn.

1 (q, q2)∞

1 (q2, q2)∞

n=0

Định lí 1.4. Với mỗi n ≥ 1 thì

(1.10)

Q(n) = po(n).

∞ (cid:88)

Chứng minh: Từ định lí 1.3 và công thức (1.9) ta có

Q(n)qn = (−q; q)∞ =

(−q; q)∞(q; q)∞ (q; q)∞

n=0

∞ (cid:88)

=

po(n)qn.

(q2; q2)∞ (q; q)∞

1 (q; q2)∞

n=0

Suy ra điều phải chứng minh.

Định lý 1.4 là do Euler phát hiện và minh hoạ một trong những khía

cạnh hấp dẫn của lý thuyết phân hoạch, cụ thể là, số lượng phân hoạch của n trong một kiểu cụ thể thường bằng số phân hoạch của một kiểu

hoàn toàn khác. Ta đề cập đến một ví dụ nổi tiếng khác trong minh hoạ.

Đồng nhất thức đầu tiên trong hai đồng nhất Rogers – Ramanujan có mô tả tổ hợp như sau. Số phân hoạch của một số nguyên dương n thành các phần khác nhau ít nhất là 2 bằng số phân hoạch n thành các phần đồng

dư với 1 hoặc 4 modulo 5. Ví dụ, hai tập hợp các phân hoạch của 8 là

8 = 7 + 1 = 6 + 2 = 5 + 3;

6 + 1 + 1 = 4 + 4 = 4 + 1 + 1 + 1 + 1 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

∞ (cid:88)

Định lí 1.5. Với mỗi n ≥ 1 thì

(1.11)

=

p(n)qn.

qn2 (q; q)2 n

n=0

Chứng minh: Xét các nút nằm bên dưới hình vuông Durfee có kích thước s đối với một phân hoạch tùy của n. Chúng ta lưu ý rằng có biểu diễn đồ thị của một phân hoạch π1 của m1, ở đây m1 bằng số nút nằm bên dưới hình vuông Durfee. Hơn nữa, mỗi phần không lớn hơn s. Bây giờ kiểm tra

các nút bên phải của hình vuông Durfee. Đọc từ trái sang phải, chúng ta có một phân hoạch π2 của một số m2 với mỗi phần không lớn hơn s. Ví dụ, nếu π là phân hoạch của 7 + 7 + 6 + 5 + 2 + 2 thể hiện trong hình dưới đây thì s = 4, π1 là phân hoạch 2 + 2, và π2 là phân hoạch 4 + 3 + 2. Số lựa chọn cho π1 là p({1, 2, ...s}, m1) =: ps(m1), và số lựa chọn cho π2 là

p({1, 2, ...s}, m2) =: ps(m2). Lưu ý rằng n = s2 + m1 + m2.

∗ ∗

∗ ∗ ∗

∗ ∗ ∗ ∗

∗ ∗ ∗ ∗ ∗ ∗

∞ (cid:88)

Hàm sinh cho tất cả các phân hoạch của n, với s cố định là

.

qn (cid:88)

qs2+m1+m2 =

ps(m1)ps(m2) =

qs2 (q; q)2 s

n=0

m1=0

m2=0

n=s2+m1+m2

Bây giờ chúng ta tổng hợp công thức trên qua s, 0 ≤ s < ∞, để sinh ra

∞ (cid:88)

tất cả các phân hoạch. Như vậy

p(n)qn =

.

qs2 (q; q)2 s

n=0

s=0

1.2.3 Đồng nhất thức Rogers–Ramanujan

Công thức này là công thức phải chứng minh.

Dưới đây tác giả trình bày lại kết quả kinh điển về đồng nhất thức

Rogers–Ramanujan và các kết quả liên quan. Tài liệu tham khảo chính là

[4].

Hai đồng nhất thức “Tổng – Tích” dưới đây được biết tới do Rogers –

∞ (cid:89)

∞ (cid:88)

Ramanujan và là một trong những công thức đẹp nhất của toán học.

(1.12)

=

(1 − q5n−1)−1(1 − q5n−4)−1,

qn2 (q; q)n

n=1

n=0

∞ (cid:88)

∞ (cid:89)

và

(1.13)

=

(1 − q5n−2)−1(1 − q5n−3)−1.

qn2+n (q; q)n

n=0

n=1

Hai đồng nhất thức mang lại cảm hứng nghiên cứu vô tận cho các nhà toán học. Mac Mahon đã đưa ra diễn giải tổ hợp cho công thức (1.12),(1.13)

tương ứng.

Định lí 1.6. Số phân hoạch của n thành các phần sao cho hiệu giữa hai phần bất kì ít nhất bằng 2 bằng số phân hoạch của n thành các phần đồng dư với ±1 (mod 5).

Định lí 1.7. Số phân hoạch của n thành các phần nhỏ nhất là 2 và hiệu giữa hai phần bất kì ít nhất bằng 2 bằng số phân hoạch của n thành các phần đồng dư với ±2 (mod 5).

Năm 1963, B.Gordon đã khái quát Định lý 1.6 và 1.7 bởi định lí dưới

đây:

Định lí 1.8. (Gordon) Cho k ≥ 2 và 1 ≤ i ≤ k, giả sử Bk,i(n) ký hiệu số phân hoạch của n có dạng b1 + b2 + . . . + bs, ở đây bj − bj+k−1 ≥ 2 và có nhiều nhất i − 1 số bj bằng 1. Giả sử Ak,i(n) ký hiệu số phân hoạch của n thành các phần (cid:54)≡ 0; ±i(mod2k + 1), khi đó Ak,i(n) = Bk,i(n) với mọi n.

Định lí Gordon đã dẫn đến sự bùng nổ các kết quả. Rõ ràng Định lý 1.6 là trường hợp đặc biệt k = i = 2 của Định lý 1.8 và Định lý 1.7 là trường hợp đặc biệt khi k = i + 1 = 2.

Năm 1982, G.E.Andrews đưa ra tương tự giải tích của Định lý 1.8:

2 +...+N 2

1 +N 2

k−1+Ni+Ni+1+...+Nk−1

Định lí 1.9. (G.E.Andrews ) Với k ≥ 2 và 1 ≤ i ≤ k,| q |< 1,

qN 2

(cid:88)

(q; q)n1(q; q)n2 . . . (q; q)nk−1

n1,n2,...,nk−1≥0

(cid:89) (1.14)

(1 − qn)−1.

=

n(cid:54)≡0,±i

(mod 2k+1)

trong đó Nj = nj + nj+1 + . . . + nk−1.

Dễ dàng nhìn thấy nó giống hệt công thức (1.12),(1.13) trong trường

hợp đặc biệt k = i = 2 và k = i + 1 = 2 của Định lí 1.9 .

Sự giải thích lý thuyết phân hoạch sâu hơn trong trường hợp đồng nhất thức q-chuỗi đã được nghiên cứu bởi một số nhà toán học, như Gordon,

Connor, Hirschhorn, Agarwal và Andrews, Subbarao. Trong tất cả các

kết quả, chỉ phân hoạch thông thường được sử dụng. Tương tự với giải

thích tổ hợp của MacMahon (Định lí 1.6, 1.7) về đồng nhất thức Rogers – Ramanujan(công thức (1.12) và (1.13)). Năm 1984, Andrews sử dụng n−

phân hoạch màu, đưa ra giả thuyết mà năm 1985 Agarwal đã chứng minh.

Định lí 1.10. Số phân hoạch với “n bản sao của n” của ν sao cho mỗi cặp số hạng mi, rj có hiệu trọng số dương bằng số phân hoạch thông thường của n thành các phần (cid:54)≡ 0, ±4( mod 10).

Ví dụ 1.7. Cho ν = 6, chúng ta có 8 phân hoạch liên quan mỗi loại 61, 62, 63, 64, 65, 66, 51 + 11, 52 + 11 của loại thứ nhất và

51, 32, 321, 313, 23, 2212, 214, 16,

của loại thứ hai.

Định lí 1.11. Số phân hoạch với “n bản sao của n” của ν sao cho mỗi cặp số hạng mi, rj có hiệu trọng số không âm bằng số phân hoạch thông thường của n thành các phần (cid:54)≡ 0, ±6( mod 14).

n(3n−1) 2

Định lý 1.10 và 1.11 là giải thích tổ hợp của đồng nhất q-chuỗi sau đây:

q

∞ (cid:88)

∞ (cid:89)

=

(1 − q10n)(1 − q10n−4)(1 − q10n−6),(1.15)

(q; q)n(q; q2)n

1 (q; q)∞

n=0

n=1

∞ (cid:89)

∞ (cid:88)

và

=

(1 − q14n)(1 − q14n−6)(1 − q14n−8).(1.16)

qn2 (q; q)n(q; q2)n

1 (q; q)∞

n=0

n=1

Động lực ban đầu cho Định lý 1.10 và 1.11 đến từ sự cố gắng để hiểu

vế trái của đồng nhất thức dưới đây :

Đối với σ1 = 0, σi = 0 hay 1, σi + σi+1 ≤ 1,

(cid:88)

q(σ2−σ1σ3)·1+(σ3−σ2σ4)·2+(σ4−σ3σ5)·3+...

σ2,...,σm,...

(cid:89)

=

(1 − qn)−1).

n(cid:54)≡0,±4( mod 10)

Dưới những điều kiện σi = 0 hoặc σi = 0 ; σi + σi+1 ≤ 1, mỗi giá trị trong ngoặc là 1 hoặc 0, hoặc -1, vì vậy số mũ giống như bộ sưu tập của

2, 1-2+3

3, 2-3+4, 1-2+3-4+5

4, 3-4+5, 2-3+4-5+6, 1-2+3-4+5-6+7 Ta hiểu bộ sưu tập như những khối và biểu thị chúng bằng 11, 21, 22, . . . Andrews và Baxter phát hiện ra rằng, những đồng nhất thức mà ta nhận

được từ tổng ở trên là những đồng nhất thức mà hiệu nhỏ nhất giữa các khối là 3. Vậy khối mi bất kì là (m − i + 1) − . . . ± (m + i − 1) và khối bất kì nj là (n − j + 1) − . . . ± (n + j − 1), bây giờ mi ≥ nj + 3 nghĩa là m − i + 1 ≥ n + j − 1 + 3 hoặc m − n − i − j > 0, tức là hiệu trọng số ((mi − nj)) > 0.

Năm 1987, Agarwal và Andrews đã tổng quát hoá Định lí 1.10 và 1.11

bằng định lí:

Định lí 1.12. (Agarwal và Andrews) Cho 0 ≤ t ≤ k − 1, k ≥ 2, giả sử At(k, ν) ký hiệu số phân hoạch của ν với “n + t bản sao của n”, sao cho nếu hiệu trọng số của mọi cặp số hạng mi, rj là không dương, thì nó chẵn và lớn hơn hoặc bằng −2min(i − 1, j − 1, k − 3). Nếu t ≥ 1 thì với i nào đó, ii+t là một phần. Giả sử Bt(k, ν) ký hiệu số phân hoạch của n thành các phần (cid:54)≡ 0, ±2(k − t) (mod 4k + 2). Khi đó At(k, ν) = Bt(k, ν) cho mọi ν.

Rõ ràng Định lý 1.10 và 1.11 là trường hợp đặc biệt với k = t + 2 = 2

và k = t + 3 = 3, tương ứng của Định lý 1.12

Agarwal, Andrews và Bressoud đã cho phiên bản giải tích cho Định lý

1.12.

2+...+mr

2+a1m1+...+armr+(mr

2 )χ(k lẻ)

Định lí 1.13. (Agarwal, Andrews và Bressoud) Cho 0 ≤ t ≤ k − 1, k ≥ 2, giả sử r = [ k 2 ] và χ(A) là 1 nếu A đúng, là 0 nếu A sai. Nếu k − r − 1 ≤ t ≤ k − 1 thì

qm1

(cid:88)

(q; q)m1−m2 . . . (q; q)mr−1−mr(q; q)mr(q; q2)mr+1

m1≥m2≥...mr≥0

(cid:89) (1.17)

=

(1 − qn)−1,

n(cid:54)≡0,±2(k−t)( mod 4k+2)

2+...+mr

2−m1−...−mt+(mr

2 )χ(k lẻ)(1−qmt )

ở đây, ai = 1 + χ(i ≥ k − t). Nếu 0 ≤ t ≤ r thì

qm1

(cid:88)

(q; q)m1−m2 . . . (q; q)mr−1−mr(q; q)mr(q; q2)mr

m1≥m2≥...mr≥0

(cid:89) (1.18)

=

(1 − qn)−1,

n(cid:54)≡0,±2(k−t)( mod 4k+2)

ở đây, q−m1−...−mt(1 − qmt) được xác định là 1 nếu t = 0.

Đồng nhất (1.12) và (1.13) là trường hợp đặc biệt khi k = t + 2 = 2 và

k = t + 3 = 3 tương ứng của Định lý 1.13.

Đồng nhất Rogers – Ramanujan là một trong những công thức đẹp nhất

của toán học. Đây vẫn là vấn đề được nghiên cứu sôi nổi đến ngày nay.

Chúng có ứng dụng trong nhiều lĩnh vực khác nhau, trong vật lí hạt, trong

1.2.4 Tính chất đồng dư của p(n)

cơ học thống kê.

Trong phần nầy tác giả trình bày một số kết quả về tính chất đồng dư

của p(n). Tài liệu tham khảo chính là [4].

Bằng cách quan sát tỉ mỉ bảng giá trị của p(n) của Macmahon với n từ

1 đến 200, Ramanujan đã đưa ra phỏng đoán đồng dư sau:

(1.19)

p(5m + 4) ≡ 0

(mod 5),

(1.20)

p(7m + 5) ≡ 0

(mod 7),

(1.21)

p(11m + 6) ≡ 0

(mod 11).

n :

4 9

19

24 . . . 14 p(n) : 5 30 135 490 1175 . . .

Cũng có nhiều đồng dư với modul 52, 72, 112, chẳng hạn

p(25m + 24) ≡ 0

(mod 52)

Tất cả các đồng dư trên đều được thể hiện trong giả thuyết nổi tiếng

của Ramanujan:

Nếuδ = 5a7b11c, 24n ≡ 1

(mod δ) thì p(n) ≡ 0

(mod δ).

Ramanujan đã chứng minh giả thuyết này với 52, 72, 112, trong khi Krec- mar vào 1933 đã chứng minh cho 53 và G.N.Watson năm 1936 chứng minh cho 5a. Giả thuyết của Ramanujan được cho là đúng cho đến năm 1934, khi S.Chowla sử dụng bảng p(n) của H.Gupta với n ≤ 300 đã chỉ ra giả thuyết sai với n = 243, vì p(243) = 133978259344888 không chia hết cho 73 và 24.243 ≡ 1 (mod 73).

Năm 1936, Watson sửa đổi giả thuyết và chứng minh:

Nếu 24n ≡ 1

(mod 7b) thì p(n) ≡ 0

(mod 7[(b+2)/2]).

Tính đúng đắn của Giả thuyết Ramanujan đã được kiểm nghiệm bởi Lehmer cho các giá trị đầu tiên của n kết hợp với các modun 113 và 114. Năm 1959, Lehmer chứng minh giả thuyết đối với 113. Cuối cùng năm 1967, A.O.L.Atkin giải quyết vấn đề bằng chứng minh (1.21) đối với 11c tổng quát. Toàn bộ những trường hợp đúng của giả thuyết có thể được

tổng hợp lại trong định lý sau:

Định lí 1.14. Nếu δ = 5a7b11c và 24n ≡ 1 (mod δ) thì

p(n) ≡ 0

(mod 5a7[(b+2)/2]11c).

Để nhận được những cách giải thích tổ hợp của đồng dư Ramanujan (1.19)-(1.21), như đã nói trước đây, năm 1944 Dyson đưa ra định nghĩa

“hạng của phân hoạch” là phần lớn nhất trừ đi số các phần. Ông phỏng đoán sự giải thích tổ hợp dưới đây của đồng dư (1.19)-(1.20) tương ứng:

Định lí 1.15. Nếu viết π ∼ π(cid:48) khi hạng r, r(cid:48) của π và π(cid:48) là đồng dư (mod5) thì các lớp tương đương của phân hoạch của 5n + 4 cảm sinh bởi ∼ có số lượng như nhau.

Định lí 1.16. Nếu viết π ∼ π(cid:48) khi hạng r, r(cid:48) của π và π(cid:48) là đồng dư (mod7) thì các lớp tương đương của phân hoạch của 7n + 5 cảm sinh bởi ∼ có số lượng như nhau.

Năm 1953, Atkin và Swinnerton đã chứng minh Định lý 1.15, 1.16. Dyson nhận thấy hạng không tách phân hoạch của 11n + 6 thành 11 lớp

bằng nhau. Sau đó ông dự đoán phải có những thống kê phân hoạch khác

(mà ông gọi là “crank” - c-hạng) để có thể cho một giải thích tổ hợp đồng dư thứ ba của Ramanujan (1.21).

Năm 1988, Andrews và Garvan định nghĩa c-hạng của một phân hoạch

như sau:

Định nghĩa 1.7. Cho một phân hoạch π, giả sử l(π) ký hiệu phần lớn nhất của π, ω(π) ký hiệu số các số 1 trong π và µ(π) là số các phần của π lớn hơn ω(π). Khi đó “c-hạng” c(π) là

(cid:40)

khi ω(π) = 0

c(π) =

l(π) µ(π) − ω(π) khi ω(π) (cid:54)= 0.

Họ đã đưa ra lời giải thích tổ hợp sau đây của đồng dư thứ ba của

Ramanujan (1.21):

Định lí 1.17. Nếu viết π ∼ π(cid:48) khi c(r), c(r(cid:48)) là đồng dư (mod 11) thì các lớp tương đương của phân hoạch của 11n + 6 cảm sinh bởi ∼ có số lượng

như nhau.

Năm 1986, Garvan đưa ra các giải thích tổ hợp khác của đồng dư Ra-

manujan bằng cách sử dụng phân hoạch véc tơ. Ông định nghĩa phân hoạch véc tơ (cid:126)π của n là bộ ba (π1, π2, π3), ở đây π1 là các phân hoạch thành các phần phân biệt, π2 và π3 là các phân hoạch thông thường, sao cho tổng các phần của mỗi thành phần riêng lẻ của véc tơ (cid:126)π là n. Hạng của (cid:126)π được định nghĩa là số các phần của π2 trừ đi số các phần của π3. Giả sử Nv(m, t, n) ký hiệu số các phân hoạch véc tơ của n trong đó hạng đồng dư với m modulo t.

Giải thích tổ hợp của Garvan cho (1.19)-(1.21) là

,

Nv(0, 5, 5n + 4) = Nv(1, 5, 5n + 4) = . . . = Nv(4, 5, 5n + 4) =

,

Nv(0, 7, 7n + 5) = Nv(1, 7, 7n + 5) = . . . = Nv(6, 7, 7n + 5) =

p(5n + 4) 5 (1.22) p(7n + 5) 7 (1.23)

(1.24)

.

Nv(0, 11, 11n + 6) = Nv(10, 11, 11n + 6) = . . . =

p(11n + 6) 11

Năm 1991, Agarwal và Subbarao nhận được vô hạn đồng dư kiểu Ra- manujan cho phân hoạch hoàn hảo. Một phân hoạch hoàn hảo của số n là

một phân hoạch chứa trong nó đúng một phân hoạch của mỗi số nhỏ hơn n, nếu các phần lặp lại được xem là không phân biệt. Số phân hoạch hoàn hảo của n được ký hiệu bởi per(n).

Ví dụ 1.8. per(7) = 4 vì có 4 phân hoạch hoàn hảo của 7 là 413, 421, 231, 17.

Agrwal và Subbarao đã chứng minh định lý sau:

Định lí 1.18. (Agrwal và Subbarao) Với n ≥ 1, k ≥ 2 và q là số nguyên

tố thì

(1.25)

per(nqk − 1) ≡ 0

(mod 2k−1).

Định lý đưa đến vô số đồng dư kiểu Ramanujan cho phân hoạch hoàn hảo. Ví dụ khi k = 3, q = 2, thay n bằng n + 1 ở công thức (1.25) thì thu được: per(8n + 7) ≡ 0 (mod 4). Đồng dư này về cấu trúc rất giống đồng dư Ramanujan (1.19) – (1.21).

Năm 1964, Cheema và Gordon đã tìm được những đồng dư sau đây đối

với phân hoạch hai và ba dòng

Định lí 1.19. (Cheema và Gordon)

(1.26)

(mod 5), ν ≡ 3, 4

(mod 5)

t2(ν) ≡ 0

và

(1.27)

(mod 3).

t3(3ν + 2) ≡ 0

Nhiều đồng dư loại này đã được tìm ra bởi Gandhi vào năm 1967. Kết

quả của ông được đưa ra trong định lý sau:

Định lí 1.20. (Gandhi)

(1.28)

(mod 2),

t2(2ν) ≡ t2(2ν + 1)

(1.29)

(mod 3),

t3(3ν) ≡ t3(3ν + 1)

(1.30)

(mod 2),

t4(4ν) ≡ t4(4ν + 1) ≡ t4(4ν + 2)

(1.31)

(mod 2),

t4(4ν + 3) ≡ 0

(1.32)

(mod 5),

t5(5ν + 1) ≡ t5(5ν + 3)

(1.33)

(mod 5).

t5(5ν + 2) ≡ t5(5ν + 4)

Tương tự với các đồng dư của Ramanujan cho p(n), đồng dư liên quan

F – phân hoạch màu và không màu cũng được tìm thấy. Dưới đây là hai

đồng dư của Andrews tìm được vào năm 1984

(1.34)

(mod 5),

φ2(5n + 3) ≡ cφ2(5n + 3) ≡ 0

và

(1.35)

(mod p2),

cφp(n) ≡ 0

ở đây p nguyên tố, p \ n .

Năm 1985, Kolitsch tổng quát hóa (1.35) và chứng minh đồng dư dưới

đây

(cid:88) (1.36)

µ(d)cφ m

≡ 0( mod m2).

n d

d\(m,n)

Rõ ràng (1.36) quy về (1.35) khi m = p là số nguyên tố.

Đồng dư sau giữa F- phân hoạch màu và không màu được Garvan tìm

ra 1986.

Cho p là số nguyên tố, thì

(1.37)

(mod p).

φp−1(n) ≡ cφp−1(n)

Ramanujan đã chứng minh nhiều đồng nhất thức khác quan hệ với tính

∞ (cid:88)

∞ (cid:89)

chất đồng dư của phân hoạch, như

(1.38)

p(5n + 4)qn = 5

(1 − q5n)5 (1 − qn)6 .

n=0

n=1

Kết quả này G.H.Hardy nhận xét là đại diện nghiên cứu tốt nhất của

Ramanujan. Các nghiên cứu về đồng dư kiểu Ramanujan là một lĩnh vực

1.2.5 Biểu diễn đồ thị của các phân hoạch và chứng minh Định lí số

ngũ giác của Euler

nghiên cứu sôi động.

Sau khi xem xét nhiều phương pháp mà phân hoạch có thể được cho

dưới dạng hình học, Sylvester đưa ra một công cụ hiệu lực khác để nghiên

cứu các phân hoạch, đó là việc biểu diễn chúng bằng đồ thị. Sylvester gọi

cách diễn đạt này là biểu đồ Ferrers của phân hoạch, đặt tên theo nhà toán

học N. M. Ferrers. Trong phần này tác giả trình bày về biểu đồ Ferrers

của phân hoạch và chứng minh Định lí số ngũ giác của Euler của Fabian

Franklin. Tài liệu tham khảo chính là [3].

Mỗi phân hoạch λ được liên kết với đồ thị Gλ ( hoặc biểu đồ Ferrers), gồm những điểm có các tọa độ nguyên (i, j) trong mặt phẳng, sao cho nếu λ = (λ1, λ2, . . . λn) thì (i, j) ∈ Gλ khi và chỉ khi

0 ≥ i ≥ −n + 1, 0 ≤ j ≤ λ|i|+1 − 1.

Khái niệm đó sẽ được hiểu đơn giản qua một số ví dụ dưới đây.

Ví dụ 1.9. Biểu diễn đồ thị của phân hoạch 5 + 5 + 5 + 3 + 2

∗ ∗ ∗

∗ ∗ ∗ ∗

∗ ∗ ∗ ∗ ∗

Ở dòng thứ i của biểu diễn đồ thị của (λ1, λ2, . . . λn) chứa λi điểm.

Ông đã chú ý ngay rằng ta có thể đếm số nút ở các cột thay vì các hàng. Lấy ví dụ như biểu đồ ở trên có thể cho ta phân hoạch 5+5+4+3+3. Hai

phân hoạch từ cùng một biểu đồ như trên được gọi là liên hợp. Sylvester

khẳng định một cách tiếp cận hoàn toàn mới đối với phân hoạch. Để hiểu

biết về giá trị của lối suy nghĩ mới này, chúng ta sẽ xem xét chứng minh

của Fabian Franklin cho Định lý số ngũ giác của Euler. Chứng minh của

ông đã lột tả được sức mạnh của ý tưởng của Sylvester.

∞ (cid:89)

Định lý số ngũ giác của Euler có thể được viết lại một cách thuần túy như một khẳng định về phân hoạch. Giả sử D(m, n) ký hiệu số phân hoạch của n thành m phần, khi đó

(cid:88) (1.39)

(1 − qn) =

(−1)mD(m, n)qn.

n=1

m,n≥0

Như vậy, hệ số của qn trong công thức (1.39) là hiệu giữa số các phân hoạch n thành một số chẵn các phần phân biệt (chẳng hạn kí hiệuQ0 n) và số các phân hoạch n thành số lẻ phần phân biệt (chẳng hạn kí hiệu Q1 n). Như vậy, Định lý số ngũ giác của Euler có thể được viết lại dưới dạng:

(cid:40)

(1.40)

| Q0

n | − | Q1

n |=

(−1)j 0

nếu n = j 3j±1 2 nếu n nhận giá trị khác

Ý tưởng của Franklin để chứng minh công thức (1.40) là tìm một song ánh giữa phân hoạch của n thành số chẵn các phần phân biệt tương ứng với phân hoạch của n thành số lẻ các phần phân biệt. Để công thức (1.40)

luôn đúng, ánh xạ này cần xét trong một trường hợp đặc biệt.

Chúng ta tiếp tục xét phân hoạch π với các phần phân biệt. Ta định nghĩa s(π) là số phần nhỏ nhất của phân hoạch π, và σ(π) là độ dài của dãy dài nhất các số nguyên liên tiếp xuất hiện trong phân hoạch π và chứa số hạng lớn nhất của π. Ví dụ, nếu phân hoạch π là 9 + 8 + 7 + 5 + 4 + 2 thì s(π) = 2, σ(π) = 3. Chúng ta có thể hình dung ra s(π) và σ(π) khi nhìn vào biểu đồ Ferrers của phân hoạch π. Sau đó Franklin định nghĩa

một ánh xạ của phân hoạch với những phần riêng biệt.

∗

∗ ∗

σ(π)

∗ ∗ ∗

∗ ∗ ∗ ∗

∗ ∗ ∗ ∗ ∗

∗ ∗ ∗ ∗ ∗ ∗

∗ ∗ ∗ ∗ ∗ ∗ s(π)

Trường hợp 1: s(π) ≤ σ(π). Trong biểu đồ Ferrers của π, dịch chuyển các nút ở s(π) tới vị trí song song với các nút phía trên xác định σ(π). Như vậy, khi áp dụng di chuyển này thì 9 + 8 + 7 + 5 + 4 + 2 trở thành 10 + 9 + 7 + 5 + 4

∗

∗ ∗

∗ ∗ ∗

∗ ∗ ∗ ∗

∗ ∗ ∗ ∗ ∗

Trường hợp 2: s(π) > σ(π). Trong biểu đồ Ferrers của π, dịch chuyển các nút ở σ(π) sao cho chúng

tạo thành phần bé nhất của phân hoạch biến đổi.Vì vậy, nếu ta xét phân hoạch10 + 9 + 7 + 5 + 4 ta thấy rằng s(π) = 4, σ(π) = 2 và phân hoạch biến đổi là 9 + 8 + 7 + 5 + 4 + 2.

Tuy nhiên, ánh xạ của Franklin gặp khó khăn mỗi khi hai tập nút trong biểu đồ Ferrers xác định s(π) và σ(π) không rời nhau. Nếu chúng rời

nhau, ánh xạ của Franklin không đưa đến khó khăn nào. Thực vậy, nếu s(π) < σ(π) trong trường hợp 1, hay là s(π) > σ(π) + 1 trong trường hợp

2, mọi điều nêu trên đều thực hiện được. Trường hợp đặc biệt 1: s(π) = σ(π) và tập xác định s(π), σ(π) không rời

nhau. Rõ ràng chúng ta không thể làm phép biến đổi như trong trường hợp 1. Như vậy, phân hoạch với j phần riêng biệt

j + (j + 1) + (j + 2) + . . . . + (2j − 1) = j(3j − 1)/2,

không có ảnh qua ánh xạ Franklin. Chẳng hạn,

∗

∗ ∗

σ(π) = j

∗ ∗ ∗

∗ ∗ ∗ ∗

∗ ∗ ∗ ∗ s(π) = j

Trường hợp đặc biệt 2: s(π) = σ(π) + 1 và tập xác định s(π) và σ(π)

không dời nhau. Ví dụ

∗

∗ ∗

σ(π) = j

∗ ∗ ∗

s(π) = j + 1

Bây giờ ta không thể làm phép biến đổi như trong trường hợp 2. Như vậy, phân hoạch với j phần riêng biệt (j +1)+(j +2)+. . . .+(2j) = j(3j +1)/2

không có ảnh qua ánh xạ Franklin.

n | − | Q1

n | là (−1)j khi n hoặc là j(3j −1)/2 hoặc là j(3j + 1)/2, và là 0 trong trường hợp khác. Nói cách khác, chúng ta đã chứng minh (1.40) và do đó chứng minh được (1.39).

Chúng ta kết luận rằng | Q0

Nghiên cứu của Franklin được xem như là điểm khởi đầu của một loạt

những nghiên cứu sâu sắc về phân hoạch. Chứng minh đầu tiên của Isaai

Schur về đồng nhất thức Rogers – Ramanujan dựa nhiều vào phương pháp

của Franklin. Gần đây hơn, trên cơ sở những kết quả của Schur, A. Garsia

và S. Miler vào năm 1981 đã đưa ra một chứng minh thuần tuý là tương

ứng một - một cho đồng nhất thức Rogers – Ramanujan. Có lẽ thành tựu

nổi bật nhất là chứng minh vào năm 1985 bởi D. Zeilberger và D. Bressoud

về giả thuyết q – Dyson .

Chương 2

Một số lớp bài toán phân hoạch số

nguyên khác nhau và các bài toán

liên quan

2.1 Phân hoạch thành những phần phân biệt và ánh xạ đối

hợp của Franklin

Trong phần này tác giả trình bày một kết quả về phân hoạch thành

những phần phân biệt. Tài liệu tham khảo chính là [5].

Ta bắt đầu với kết quả dưới đây từ tác phẩm "Some new results on

n và D1

partitions" của N.J. Fine (1948):

Định lí 2.1. (Fine) Giả sử D0 n là tập hợp những phân hoạch λ của n thành những phần phân biệt, sao cho phần lớn nhất a(λ) = λ1 là chẵn, lẻ, tương ứng. Khi đó

 

| D0

n | − | D1

n |=

 nếu n = k 3k+1 1 2 −1 nếu n = k 3k−1 0 nếu trường hợp khác.

Điều đó có lẽ gợi ý ta so sánh Định lí 2.1 với một tương tự Định lí số

n và Q1

ngũ giác của Euler, mà có thể được phát biểu như sau:

n là tập hợp những phân hoạch λ của 1 là chẵn, lẻ,

Định lí 2.2. (Euler) Giả sử Q0 n thành những phần phân biệt, sao cho số các phần l(λ) = λ(cid:48)

tương ứng. Khi đó

(cid:40)

| Q0

n | − | Q1

n |=

(−1)k 0

nếu n = k 3k±1 nếu trường hợp khác.

Tất nhiên, sự tương tự này đã không được để ý đến. Chính Fine thừa nhận rằng Định lí 2.1 "mang một số điểm tương đồng với Định lý số ngũ

giác của Euler, nhưng chúng ta đã không thể thiết lập bất kỳ liên hệ thực

sự nào giữa hai định lý". Lehmer cũng khẳng định lại:"Kết quả này tương

đương với một định lí nổi tiếng của Euler".

Như chúng ta sẽ thấy dưới đây, Định lí 2.1 có một cách chứng minh gần

giống với chứng minh dùng ánh xạ đối hợp nổi tiếng bởi Franklin cho Định lí 2.2. Franklin đã công bố chứng minh của ông, ngay trước khi xuất hiện

tác phẩm nổi tiếng của Sylvester. Hai công trình thiết lập nên lý thuyết

tổ hợp song ánh, một lĩnh vực nở rộ trong nửa cuối của thế kỷ XX.

Thật khó trách Fine vì không phát hiện ra mối quan hệ. Trong thời đó,

song ánh vẫn còn hiếm khi được sử dụng để chứng minh các kết quả tổ

hợp. Từ những năm sáu mươi, phương pháp này mới trở nên phổ biến, với

nhiều bài viết chứng minh đồng nhất thức phân hoạch bởi phương pháp

song ánh. Ánh xạ đối hợp của Franklin hoàn toàn không bị lãng quên, và

được sử dụng nhiều lần để chứng minh nhiều dạng chính xác hóa khác

nhau của định lí số ngũ giác của Euler, thậm chí gần đây nhất, để chứng

minh một đồng nhất thức phân hoạch mới. Điều đáng tiếc là việc áp dụng

định lý của Fine bị bỏ qua trong rất nhiều năm.

n ∪ D1 n tập hợp tất cả các phân hoạch thành các phần phân biệt. Giả sử λ ∈ Dn và giả sử [λ] là biểu đồ Young tương ứng với λ. Kí hiệu s(λ) là độ dài của phần ngắn nhất trong λ, và b(λ) là độ dài của dãy các phần liên tiếp: a, a − 1, a − 2, . . . trong các hình vuông của [λ], như hình 2.1. Bây giờ, nếu s(λ) ≤ b(λ), di chuyển đường nằm ngang để gắn vào đường chéo. Tương tự, nếu s(λ) > b(λ), di chuyển

Chứng minh. Kí hiệu Dn = D0

đường chéo để gắn vào dưới đường nằm ngang. Nếu chúng ta không thể

Hình 2.1: Biểu đồ Young [λ] tương ứng với một phân hoạch λ = (9, 8, 7, 6, 4, 3) ở đây s(λ) = 3, b(λ) = 4

và α(λ) = (10, 9, 8, 6, 4)

2m − 1

m + 1

Hình 2.2: Điểm bất động của của ánh xạ đối hợp Franklin.

di chuyển, thì giữ nguyên. Điều này xác định ánh xạ đối hợp của Franklin α : Dn −→ Dn.

Lưu ý là α thay đổi tính chẵn lẻ của số các phần, trừ khi λ là điểm bất

động. Quan sát rằng chỉ những điểm bất động của ánh xạ đối hợp và biểu đồ Young là đường phủ, và s(λ) − b(λ) là 0 hoặc 1 (xem hình 2.2). Số các

, được gọi là số ngũ giác.

3k ± 1 2

n | − | Q1

n | là ±1 khi n là một số ngũ giác, và là 0 trong trường

n | − | D1

hình vuông trong những biểu đồ này là k Do đó, | Q0 hợp khác. Định lý 2.2 được chính minh .

Tương tự, lưu ý là α thay đổi tính chẵn lẻ của bộ phận lớn nhất. Lại theo cách đó, chúng ta có | D0 n | là ±1 khi n là một số ngũ giác, và là 0 trong trường hợp khác. Định lý 2.1 hoàn toàn được chứng minh .

2.2 Phân hoạch thành những phần lẻ và song ánh Sylvester

Định lý Euler phát biểu rằng số các phân hoạch của n thành những phần lẻ bằng số phân hoạch của n thành các phần phân biệt (Định lí 1.4). Sử

dụng tài liệu tham khảo chính [5], tác giả trình bày một kết quả mới khác

n và O3 Định lí 2.3. (Fine) Giả sử O1 n là tập hợp những phân hoạch λ của n thành các phần lẻ, sao cho phần lớn nhất a(λ) là đồng dư 1 và 3 (mod 4) tương ứng. Khi đó:

trong tác phẩm "Some new results on partitions" của N.J. Fine (1948).

| O1

n | nếu n là chẵn,

| O1

n |=| D0 n |=| D1

n |, | O3 n |, | O3

n |=| D1 n |=| D0

n | nếu n là lẻ.

Rõ ràng, Định lý 2.3 của Fine là sự chính xác hóa định lý của Euler.

Kết quả sau đây của Fine là một mở rộng :

Định lí 2.4. (Fine) Với k > 0 bất kì, số phân hoạch µ (cid:96) n thành các phần phân biệt, sao cho a(µ) = k bằng số phân hoạch λ (cid:96) n thành các phần lẻ, sao cho a(λ) + 2l(λ) = 2k + 1.

Andrews đã chứng minh một cách tổ hợp Định lý 2.4 , nhưng không nhận thấy nó suy ra Định lý 2.3 . Lý do thực tế có thể là Định lý 2.3 được ghép thành đôi cùng với Định lý 2.4, trong khi chứng minh dùng hai luận cứ tổ hợp cổ điển khác nhau. Chứng minh của cả hai Định lý 2.3 và Định lý 2.4 suy ra từ song ánh nổi tiếng của Sylvester, đôi khi gọi là xây dựng

cái móc nối. Song ánh này là ánh xạ giữa phân hoạch thành các phần lẻ

và phân hoạch thành các số khác nhau, và nó cho một chứng minh tổ hợp

định lý của Euler.

Song ánh của Sylvester là công cụ khác trong lý thuyết tổ hợp các phân

hoạch. Nó đã được trình bày lại bằng nhiều cách khác nhau.

Chứng minh. Ký hiệu On tập tất cả các phân hoạch thành các phần lẻ. Định nghĩa song ánh Sylvester ϕ : On −→ Dn như trình bày trong Hình 2.3. Nhận thấy rằng a(µ) = (a(λ) − 1)/2 + l(λ) cho mọi µ = ϕ(λ). Viết

lại công thức này thành a(λ) + 2l(λ) = 2a(µ) + 1, Định lí 2.4 được chứng

minh .

Chú ý rằng l(λ) ≡ n (mod 2) với mọi λ ∈ On. Từ phương trình trên

có kết luận

ϕ : O1

n −→ D0

n, O3

n −→ D1

n khi n chẵn,

và

ϕ : O1

n −→ D1

n, O3

n −→ D0

nkhi n lẻ.

Hình 2.3: Song ánh của Sylvester ϕ : (7, 5, 3, 3) −→ (7, 6, 4, 1)

Định lí 2.3 được chứng minh.

2.3 Một số bài toán liên quan

Bài toán phân hoạch một số nguyên dương thực sự là bài toán hấp dẫn.

Với bài toán liên quan tới phân hoạch, chúng ta có thể tiếp cận bằng hàm

sinh, đây là cách nhìn tổng quát, cũng có những bài toán lại dễ tiếp cận

bằng phương án song ánh và ta cũng có thể sử dụng lập luận tổ hợp. Chính

vì lẽ đó đã có rất nhiều bài toán thi học sinh giỏi ứng dụng bài toán này.

2.3.1 Một số bài toán chứng minh

Tác giả đã sử dụng một số tài liệu chính là [1], [2], [6].

Bài toán 2.1 (xem [6]). Chứng minh rằng số phân hoạch tự liên hợp của n bằng số phân hoạch của n thành các phần lẻ và khác nhau.

Giải

Đối với mỗi phân hoạch tự liên hợp, ta có thể xem xét biểu đồ Ferrer

của nó.

Hình 2.4: Song ánh giữa phân hoạch tự liên hợp của n và phân hoạch của n thành các phần lẻ và khác

nhau.

Với mỗi ô vuông trong đường chéo chính, ta gắn các ô vuông bên phải

vào phía trên của nó. Xét các tập được hình thành bởi phần tử của đường

chéo chính và các ô vuông được gắn vào nó. Vì số ô vuông( phía trên và

bên phải) là như nhau, mỗi tập có số lẻ các phần. Hơn nữa không có hai

tập nào có cùng số ô vuông, vì biểu đồ giảm dần. Với cách này ta thấy phép gắn rõ ràng là song ánh giữa phân hoạch tự liên hợp của n và phân hoạch của n thành các phần lẻ và từng đôi phân biệt. Ta có điều phải

chứng minh.

Bài toán 2.2 (xem [6]). Chứng minh rằng nếu p(m) là số phân hoạch của m thì hàm sinh của dãy (p(0), p(1), p(2), . . .) là

(cid:19) (cid:18) 1 (cid:19) (cid:18) 1 (cid:19) (cid:18) 1 (cid:89)

. . . .

1 1 − xn =

1 − x

1 − x2

1 − x3

n≥1

Giải Giả sử (n1, n2, . . . , nk) là một phân hoạch nào đó của m. Xét số hạng

1 1 − xn = 1 + xn + x2n + x3n + . . . , trong tích số. Trong số hạng đó ta sẽ xét đơn thức xrn.n, trong đó rn là số lần n xuất hiện trong phân hoạch. Rõ ràng khi làm như vậy với mỗi một số hạng, ta thu được 1 để thêm vào hệ số của đơn thức xm trong tích số. Từ đó mỗi tích số của số hạng kiểu này thêm 1 vào hệ số của xm cảm sinh theo cùng một cách một phân hoạch

của m, hệ số cuối cùng phải là p(m), như vậy ta có điều phải chứng minh.

Bài toán 2.3 (xem [6]). Chứng minh rằng số phân hoạch của n sao cho các phần của chúng từng đôi một khác nhau bằng số phân hoạch của n

thành các phần lẻ.

Giải

1

k>1

Cách giải thứ nhất (sử dụng hàm sinh): Giả sử q(m) là số của phân hoạch của m với các phần từng đôi khác nhau và q∗(m) là số phân hoạch của m thành các phần lẻ. Lập luận tương tự như bài trên , với q(m) chúng ta chỉ quan tâm đến trường hợp khi rn = 0 hoặc rn = 1 cho mỗi n. Do đó hàm sinh của nó là (cid:81) n≥1(1 + xn). Với q∗(m) chúng ta quan tâm đến việc lập luận khi n là lẻ, vì thế chúng ta được hàm sinh (cid:81) 1 − x2k−1 . Lưu ý rằng

(cid:89) (cid:89)

(1 + xn) =

1 − x2n 1 − xn .

n≥1

Do đó trong tử số chúng ta có tất cả các số hạng có dạng 1 − xt với t chẵn và trong mẫu số chúng ta có tất cả các số hạng có dạng 1 − xt. Khi ta rút gọn chỉ các số hạng lẻ còn lại trong mẫu số, ta có điều phải chứng minh. Cách giải thứ hai (sử dụng song ánh): Giả sử (n1, n2, . . . , nk) là một phân hoạch nào đó của n sao cho tất cả các phần tử của nó khác nhau. Thì mỗi ni có thể được viết 2aibi, ở đây bi là số lẻ. Chúng ta loại bỏ mỗi ni và thay thế chúng bằng bi nhưng 2ai lần. Bằng cách này, chúng ta có được một phân hoạch của n chỉ với các phần lẻ. Chúng ta sẽ thấy rằng

hàm được xác định theo cách này là song ánh. Điều này chứng tỏ rằng có một hàm ngược. Tức là chúng ta đưa ra một phân hoạch (n1, n2, . . . , nk) của n chỉ với những phần lẻ và chúng ta muốn xây dựng một phân hoạch với các phần khác nhau. Khi đó giả sử bi xuất hiện ci lần. Chúng ta biết rằng ci có thể được viết một cách duy nhất như một tổng của các lũy thừa khác nhau của 2, như 2ai,1 + 2ai,2 + . . . + 2ai,s. Chúng ta loại bỏ tất cả các bi và viết những số 2ai,1bi, 2ai,2bi, . . . , 2ai,sbi. Điều này tạo ra một phân hoạch của n ở đó tất cả các phần khác nhau. Rõ ràng là hai hàm được xây

dựng là hàm ngược của nhau vì vậy chúng đều song ánh và chúng ta đang

có điều phải chứng minh.

Bài toán 2.4 (USAMO, 1986). Gọi ℘[n] là tập hợp các phân hoạch π của một số nguyên dương n ≥ 1, với mọi cách phân hoạch π, ta định nghĩa A(π) là số các số 1 xuất hiện trong π, và định nghĩa B(π) là số các số nguyên phân biệt xuất hiện trong π. (Ví dụ: nếu n = 13 và π là cách phân hoạch 1 + 1 + 2 + 2 + 2 + 5, thì A(π) = 2 và B(π) = 3). Chứng minh rằng với mọi n cố định, tổng của A(π) chạy khắp các cách phân hoạch π của n bằng tổng của B(π) chạy khắp các cách phân hoạch π của n hay

(cid:88) (cid:88)

B(π).

A(π) =

π∈℘[n]

π∈℘[n] B(π). Gọi S là tập hợp {1, 2, . . . , n}, chúng

Giải Ta tính giá trị của (cid:80)

ta đi đếm số các i với mọi i ∈ S như sau:

n (cid:88)

(cid:32) (cid:33)

F (x) =

−

.

(cid:81)n (cid:81)n

1 j=1,j(cid:54)=i(1 − xj)

i=1

1 j=1(1 − xj) Rút gọn lại ta thu được hệ sinh của (cid:80)

.

F (x) =

π∈℘[n] B(π) là x (1 − x) (cid:81)n j=1(1 − xj)

π∈℘[n] A(π) với chú ý rằng ta có song ánh giữa các phân hoạch có i số 1 với i ∈ S và tập hợp n − i phần tử mà không chứa

Ta tính giá trị của (cid:80)

số 1 nào, rồi ghép lại với nhau ta được một phân hoạch của n. Với cách

phân hoạch mà không có số 1 được biểu diễn như sau:

f (x) =

.

(cid:81)n

1 j=2(1 − xj)

Bây giờ với mỗi i, ta có i số một, cho nên hệ số của xn−i trong khai π∈℘[n] A(π)

triển f (x) phải được nhân với i. Từ đó ta có thể tính được (cid:80) như sau: (cid:33) (cid:32) n (cid:88)

ixi

f (x).

i=1

π∈℘[n] A(π) là

Từ đó dẫn đến hệ sinh của (cid:80)

x

G(x) =

(1 − x)2 f (x).

So sánh cách hệ số của F (x) và G(x) ta thu được điều phải chứng minh.

Bài toán 2.5 (Korea, 1995). Cho m và n là các số nguyên dương với

n >

m(m + 1). Chứng minh rằng số phân hoạch n thành m thành phần

1 2

khác nhau bằng số phân hoạch của n −

m(m + 1) thành nhiều nhất m

1 2

phần.

Giải

Với bài này ta sẽ sử dụng phép song ánh. Với mỗi phân hoạch n thành m phần khác nhau giả sử là (n1, n2, . . . , nm) với n1 < n2 < n3 < . . . < nm ta biến đổi thành (n1 − 1, n2 − 2, . . . , nm − m) ứng với một phân hoạch

n −

m(m + 1) thành nhiều nhất m phần vì ta dễ thấy ni − i ≥ 0 với mọi

1 2

i = 1, 2, . . . , m. Ta có điều phải chứng minh.

2.3.2 Bài toán chia kẹo của Euler

Bài toán chia kẹo của Euler, được phát biểu như sau: " Có n chiếc kẹo giống nhau chia cho m em bé. Hỏi có mấy cách chia kẹo?" Bài toán tưởng

như đơn giản nhưng lại là một bài toán khó đối với nhiều học sinh. Tuy

nhiên, nếu nắm được ý nghĩa và cách giải quyết bài toán thì đây sẽ là một

bài toán tổ hợp khá hay và thú vị. Chính vì lẽ đó, có rất nhiều bài toán

thi học sinh giỏi đã ứng dụng bài toán này.

Ta phát biểu lại bài toán như sau:

Bài toán 2.6 (xem [2]). Tìm số nghiệm nguyên không âm của phương

trình:

x1 + x2 + . . . + xm = n, (n, m ∈ N∗).

Nhận xét: Trong cách chia này có em sẽ không nhận được kẹo. Nói cách khác có thể có xi = 0 và quan tâm đến thứ tự sắp xếp. Giải

Với mỗi bộ x1, x2, . . . , xm thỏa mãn x1 + x2 + . . . + xm = n tương ứng gồm n số 1 và m − 1 số 0 (đây

0 11 . . . 1 (cid:124) (cid:123)(cid:122) (cid:125) x2

1-1 với bộ 11 . . . 1 (cid:124) (cid:123)(cid:122) (cid:125) x1

0 . . . 0 11 . . . 1 (cid:124) (cid:123)(cid:122) (cid:125) xm là kĩ thuật song ánh). Để có một bộ số cần tìm chúng ta cần chọn m − 1 vị trí trong m + n − 1 vị trí để đặt chữ số 0 và còn lại đặt chữ số 1. Suy ra số cách chia kẹo là: d = C m−1

m+n−1

Bài toán 2.7 (xem [2]). Tìm số nghiệm nguyên dương của phương trình:

x1 + x2 + . . . + xm = n, (n, m ∈ N∗).

Nhận xét: Nếu phát biểu theo bài toán chia kẹo thì trong cách chia bài này em nào cũng nhận được kẹo. Nói cách khác có xi > 0 và quan tâm đến thứ tự sắp xếp.

Giải

Đặt yi = xi − 1 (Với i = 1, m) ta có:

y1 + y2 + . . . + ym = x1 + x2 + . . . + xm − m = n − m.

Vậy

• Nếu n < m phương trình vô nghiệm.

• Nếu n ≥ m, quay trở lại bài toán ban đầu số nghiệm của phương trình

trên chính là số nghiệm của phương trình là: d = C m−1 n−1

Bài toán tổng quát (xem [2]): Cho m số tự nhiên a1, a2, . . . , am. Tìm

số nghiệm tự nhiên của phương trình:

x1 + x2 + . . . + xm = n,

thỏa mãn xi ≥ ai, (∀i = 1, m). Giải

Đặt yi = xi − ai(∀i = 1, m) và S = a1 + a2 + . . . + am nên ta có: y1 + y2 + . . . + ym = x1 + x2 + . . . + xm − (a1 + a2 + . . . + am) = n − S.

• Nếu n < S, phương trình vô nghiệm.

• Nếu n = S, phương trình có 1 nghiệm.

• Nếu n > S, phương trình có C m−1

n+m−S−1 nghiệm.

Bài toán 2.8 (xem [2]). Tìm số nghiệm nguyên không âm của phương

trình:

x + y = n với x ≤ y.

Giải (Đây là lời giải của thầy Nguyễn Vũ Lương –Trường THPT Chuyên

KHTN)

(cid:105) : Vì x ≤ y nên từ phương trình suy ra x ≤ (cid:104)n 2 (cid:105)

+ 1 =

+ 1 giá trị

• Nếu n chia hết cho 2 thì x có thể nhận

(cid:104)n 2

n 2

(cid:105) và y tính được theo x ( vì y = n − x) suy ra ta có (cid:104)n 2 (cid:105)

+ 1 bộ (x,y) nguyên không âm thỏa mãn x + y = n và x ≤ y.

0, 1, 2, . . . , (cid:104)n 2

(cid:105) (cid:105) và x có thể nhận

• Nếu n không chia hết cho 2 suy ra x ≤

+ 1

(cid:104)n 2 (cid:104)n 2 (cid:105) giá trị và có

+ 1 bộ (x,y) nguyên không âm thỏa mãn bài toán.

(cid:104)n 2

Bài toán 2.9 (xem [2]). Tìm số nghiệm nguyên không âm của phương

trình

x + y + z = n,

thỏa mãn điều kiện x ≤ y ≤ z.

Giải (Đây là lời giải của thầy Nguyễn Vũ Lương –Trường THPT Chuyên

KHTN)

• Kí hiệu r1xyz là nghiệm số của phương trình thỏa mãn x < y < z.

Tương tự có r1xzy, r1yzx, r1yxz, r1zxy, r1zyx. Do vai trò của x, y, z hoàn toàn bình đẳng trong phương trình x + y + z = n. Ta có: r1xyz = r1xzy = r1yzx = r1yxz = r1zxy = r1zyx = r1.

• Kí hiệu r2xyz là nghiệm số của phương trình thỏa mãn x = y < z.

Tương tự có r2yzx, r2zxy. Ta có: r2xyz = r2yzx = r2zxy = r2.

• Kí hiệu r4 là nghiệm số của phương trình thỏa mãn x = y = z.

• Kí hiệu r3xyz là nghiệm số của phương trình thỏa mãn x < y = z.

Tương tự có r3yzx, r3zxy. Ta có: r3xyz = r3yzx = r3zxy = r3.

Tất cả các bộ số nguyên không âm (x, y, z) thỏa mãn x + y + z = n

n+2 =

mỗi bộ số sẽ thuộc một trong những trường bằng C 2

.

(n + 2)(n + 1) 2

(n + 2)(n + 1) 2 hợp trên nên ta có 6r1 + 3r2 + 3r3 + r4 = Ta có: r2 + r3 + r4 chính là số nghiệm của phương trình 2u + v = n (vì từ phương trình x + y + z = n ta có thể có 2 số hạng x = y hoặc y = z hoặc z = x và tất nhiên bao gồm trường hợp x = y = z). Giả sử x = y sẽ bao gồm x = y > z, x = y < z, x = y = z. Phương trình 2u + v = n ⇔ u + (u + v) = n. Đặt t = u + v ≥ u thu được u + t = n với u ≤ t.

(cid:105) Theo như bài toán trên, số nghiệm của phương trình này là

+ 1 hay

(cid:104)n 2 (cid:105)

+ 1.

(cid:104)n 2

(cid:105) (cid:105)

−

.

(cid:104)n − 1 3 (cid:104)n 3

r2 + r3 + r4 = Xét: • Nếu n chia hết cho 3 ⇒ r4 = 1. • Nếu n không chia hết cho 3 ⇒ r4 = 0 hay r4 = Vì x ≤ y ≤ z bao gồm x < y < z hoặc x = y < z hoặc x < y = z hoặc x = y = z. Vậy số nghiệm thỏa mãn yêu cầu của bài toán là d = r1 + r2 + r3 + r4. Từ những dữ liệu trên ta có:

(cid:105)

d =

− 3r2 − 3r3 − r4

+ r2 + r3 + r4

(cid:104)(n + 2)(n + 1) 2

+

=

(r2 + r3) +

r4

5 6

=

+

(r2 + r3 + r4) +

r4

(cid:105) (cid:17) (cid:105) (cid:105)(cid:17)

=

+

+ 1

+

−

.

1 6 (n + 2)(n + 1) 12 (n + 2)(n + 1) 12 (n + 2)(n + 1) 12

1 2 1 2 1 2

1 3 (cid:16)(cid:104)n 3

1 3

(cid:16)(cid:104)n 2 (cid:104)n 2

Bài toán 2.10 (xem [2]). Tìm số nghiệm nguyên không âm của phương trình thỏa mãn: x1 + x2 + x3 + x4 = n với x1 ≤ x2 ≤ x3 ≤ x4.

Giải (Lời giải của Nguyễn Long Nhật và Nguyễn Hùng Quang – Trường

Chuyên KHTN)

Bổ đề Burnside: "Nếu φ là các tập thuộc tập X. Với mỗi ϕ thuộc φ với X ϕ biểu thị các phần tử trong tập X được xác định bởi ϕ. Bổ đề Burnside xác định số quỹ đạo khác nhau của bài toán, biểu thị

(cid:88)

|X/φ| : |X/φ| =

ν(ϕ),

1 |φ|

ϕ∈φ

4 = 6(ϕ).

trong đó ν(ϕ) là số phần tử của từng tập." • Nếu ϕ = id : v(ϕ) là số nghiệm của phương trình x1 + x2 + x3 + x4 = n ⇒ v(ϕ) = C 3 n+3 và có 1(ϕ). • Nếu ϕ ∈ ∅ : v(ϕ) là số nghiệm của 2x + y + z = n và C 2 Ta có x ∈ {0; 1; . . . ; (cid:105) } và phương trình n − 2x + 1 với mỗi x. (cid:104)n 2 (cid:105) (cid:105) (cid:17) (cid:105) (cid:17)

+ 1

(n + 1) −

+ 1

(cid:16)(cid:104)n 2 (cid:104)n 2 (cid:105) (cid:16)(cid:104)n 2 (cid:19)

⇒ v(ϕ) = (cid:80) (cid:105)

(cid:104)n 2 x=0 (n − 2x + 1) = (cid:17) (cid:18)(cid:104)n + 1 (cid:105)

=

+ 1

.

(cid:16)(cid:104)n 2

2 C 2

4 = 3(ϕ).

• Nếu ϕ ∈ ∅ : v(ϕ) là số nghiệm của phương trình 2x + 2y = n và 1 2 *) Nếu n lẻ, phương trình vô nghiệm.

*) Nếu n chẵn, phương trình có

+ 1 nghiệm.

(cid:105) (cid:105) (cid:105)(cid:19)

⇒ v(ϕ) =

+ 1

−

.

(cid:16)(cid:104)n 2 (cid:17) (cid:18)(cid:104)n 2

n 2 (cid:104)n − 1 2

(cid:105)

• Nếu ϕ ∈ ∅ : v(ϕ) là số nghiệm của phương trình 3x + y = n và 2.4 = 8(ϕ). ⇒ v(ϕ) =

+ 1.

(cid:104)n 3

• Nếu ϕ ∈ ∅ : v(ϕ) là số nghiệm của phương trình 4x = n và

= 6(ϕ).

4! 4

(cid:105) (cid:105)

⇒ v(ϕ) =

−

.

(cid:104)n 4 (cid:104)n − 1 4 Tổng các số ϕ là 1+6+3+8+6=24.

Theo Bổ đề Burnside số nghiệm của phương trình ban đầu là:

(cid:32) (cid:19) (cid:105) (cid:105) (cid:105) (cid:105) (cid:105)(cid:19) (cid:17) (cid:18)(cid:104)n + 1

+ 1

+ 3

+ 1

−

C 3

n+3 + 6

1 24

(cid:16)(cid:104)n 2

2

(cid:16)(cid:104)n 2 (cid:17) (cid:18)(cid:104)n 2 (cid:104)n − 1 2

(cid:105) (cid:17) (cid:105)

+8

+ 1

+ 6

−

(cid:105)(cid:19) (cid:33) . (cid:16)(cid:104)n 3 (cid:18)(cid:104)n 4 (cid:104)n − 1 4

Bài toán tổng quát (xem [2]): Tìm số nghiệm nguyên không âm của

phương trình

x1 + x2 + . . . + xm = n với x1 ≤ x2 ≤ . . . ≤ xm.

Giải

Có thể áp dụng Bổ đề Burnside hoặc dùng phương thức đệ quy như sau: Giả sử Mn,m là tập hợp các kết quả của phương trình và P (n, m) số tập thỏa mãn của các yếu tố của phương trình. Chúng ta dễ dàng nhận thấy rằng: P (0, k) = 1 với mọi k, P (n, k) = P (n, n) cho tất cả các k ≥ m. Do đó, ta giả định thêm rằng n cố định, chúng ta có 1 < m ≤ n. Ta chia nhỏ các tập Mn,m vào thành các tập Ti(i = 1, 1, . . . , m − 1) nên Ti chứa chính xác những kết quả của bài toán trong đó No thỏa mãn điều kiện:

0 = x1 = x2 = . . . = xi < xi+1 < xi+2 < . . . < xm.

Ta có (x1, x2, . . . , xm) −→ (xi+1 − 1, xi+2 − 1, . . . , xm − 1), định nghĩa một song ánh từ Ti đến Mn−m+i,m−i từ 0 ≤ xi+1 − 1 ≤ xi+2 − 1 ≤ . . . ≤ xm − 1, (xi+1 − 1) + (xi+2 − 1) + . . . + (xm − 1) = n − m + i, và ánh xạ: (y1, y2, ..., ym−i) −→ (0, 0, . . . , 0, y1 + 1, y2 + 1, . . . , ym−i + 1). Có nghĩa là |Ti| = |Mn−m+i,m−i|, và do đó có thể viết:

P (n, m) = P (n − 1, 1) + P (n − 2, 2) + . . . + P (n − m, m), (1 < m ≤ n)

và với phương trình cụ thể ta có thể tính được kết quả cụ thể.

Một số bài tập áp dụng

Bài 2.1 (xem [2]). Tìm số nghiệm nguyên không âm của phương trình

x + y + z + t = 1000, với t ≤ 499.

Giải

1003 được chia ra như sau:

Số nghiệm thỏa mãn x + y + z + t = 1000 là C 3

• Thỏa mãn yêu cầu đề bài t ≤ 499.

503.

• Không thỏa mãn yêu cầu đề bài t ≥ 500. Xét t ≥ 500 ta có x + y + z + (t − 500) = 500. Đặt t1 = t − 500 ta thu được số nghiệm trong trường hợp này là C 3 Vậy đáp số của bài toán là d = C 3

503.

1003 − C 3

Bài 2.2 (xem [1]). Tìm số nghiệm nguyên không âm của bất phương trình

x + y + z ≤ 8.

i=0 C 2

Nhận xét: Đứng trước bài toán này, nhiều người sẽ giải quyết được qua kết quả của Bài toán 1 bằng cách xét 9 phương trình x + y + z = i(∀i = 0, 8). với số nghiệm là (cid:80)8 2+i = 165. Tuy nhiên nếu vế phải của bất phương trình là số lớn hơn thì việc tính toán mất nhiều thời gian. Sáng tạo hơn

ta xét lời giải sau:

Giải

Đặt t = 8 − (x + y + z) ≥ 0 ta thu được bài toán tương đương

x + y + z + t = 8,

11 = 165.

(với x, y, z, t là những số nguyên không âm). Đáp số của bài toán là d = C 3 Tổng quát: Số nghiệm nguyên không âm của bất phương trình

x1 + x2 + ... + xm ≤ n

n+m.

là C m

Bài 2.3 (xem [2]). Tìm bộ số nguyên không âm (x, y, z, t) thỏa mãn:

1 ≤ x ≤ y ≤ z ≤ t ≤ 1000.

Giải

Đặt a1 = x − 1 ≥ 0, a2 = y − x ≥ 0, a3 = z − y ≥ 0, a4 = t − z ≥ 0,

a5 = 1000 − t ≥ 0. Ta có

a1 + a2 + a3 + a4 + a5 = 999.

1003.

Đáp số: C 4

Bài 2.4 (xem [2]). Tìm số nghiệm nguyên không âm của phương trình sau

x1 + x2 + x3 + x4 = 30, (5 ≤ xi ≤ 10, ∀i = 1, 4).

Giải

Đặt yi = xi −5, ∀i = 1, 4). Từ giả thiết suy ra 0 ≤ yi ≤ 5. Ta có phương

trình: y1 + y2 + y3 + y4 = 10, (∀i = 1, 4). Gọi X là tập hợp các nghiệm nguyên không âm của phương trình. Khi đó |X| = C 3 13. Gọi A, B, C, D lần lượt là các tập hợp thỏa mãn y1 + y2 + y3 + y4 = 10 và 5 ≤ yi. Theo bài 1, ta có: |A| = |B| = |C| = |D| = C 3 8 . |A ∩ B| = |A ∩ C| = |A ∩ D| = |B ∩ C| = |B ∩ D| = |C ∩ D| = 0. |A ∩ B ∩ C| = |A ∩ C ∩ D| = |B ∩ C ∩ D| = |A ∩ B ∩ D| = 0. |A ∩ B ∩ C ∩ D| = 0.

8 = 62.

13 − 4.C 3

Áp dụng nguyên lí bù trừ ta có số nghiệm bằng: |X| = (|A|+|B|+|C|+|D|−|A∩B|−|A∩C|−|A∩D|−|B∩C|−|B∩D|− |C∩D|+|A∩B∩C|+|A∩C∩D|+|B∩C∩D|+|A∩B∩D|−|A∩B∩C∩D|). Vậy đáp số là: C 3

Bài 2.5 (xem [2]). Tìm số nghiệm nguyên không âm của phương trình sau

x1 + x2 + x3 + x4 = 14 và |xi| ≤ 5(∀i = 1, 4).

Giải

Vì |xi| ≤ 5 ⇒ −5 ≤ xi ≤ 5. Đặt yi = xi + 5(∀i = 1, 4)

⇒ y1 + y2 + y3 + y4 = 34 với 0 ≤ yi ≤ 10(∀i = 1, 4). Làm tương tự Bài toán 2.4 ta có kết quả.

Bài 2.6 (xem [1]). Có bao nhiêu số nguyên dương nhỏ hơn 1000000 mà

tổng các chữ số bằng 19?

Nhận xét: Số tự nhiên thỏa mãn yêu cầu bài toán phải là số có 3, 4, 5 hoặc 6 chữ số lấy từ tập{0; 1; . . . ; 9}. Với trường hợp có 3 chữ số thì các

chữ số không thể nhận số 0. Từ đó ta có lời giải cho bài toán như sau:

Giải

• Trường hợp 1 (số có 3 chữ số): Gọi số có ba chữ số thỏa mãn yêu cầu bài toán là x1x2x3. Lúc này, số các số tự nhiên thỏa mãn bài toán chính là số nghiệm nguyên thỏa mãn hệ (cid:40)

x1 + x2 + x3 = 19 1 ≤ xi ≤ 9, i = 1, 3.

Bằng cách đặt yi = xi − 1, i = 1, 3. Lúc đó, bài toán trở thành tìm nghiệm nguyên không âm của hệ phương trình (cid:40)

y1 + y2 + y3 = 16 0 ≤ yi ≤ 8, i = 1, 3.

18; | Ai |= C 2

18 − 3C 2 9 .

Gọi A là tập nghiệm của hệ với các yi ≥ 0 và Ai là tập nghiệm của hệ với các yi ≥ 9. Ta có: | A |= C 2 9 ; | Ai ∩ Aj |= 0. Vậy nghiệm của hệ là: C 2

• Trường hợp 2 (số có 4 chữ số): Lập luận tương tự như trường hợp 1

11 số.

12 − 3C 3

21 − C 3

nhưng với chú ý các chữ số có thể bằng 0 trừ chữ số đầu tiên. Kết quả là C 3

• Trường hợp 3 (số có 5 chữ số): Kết quả là C 4

22 − C 4

13 − 4C 124 số.

• Trường hợp 4 (số có 6 chữ số): Kết quả là C 5

13 số.

14 − 5C 5

23 − C 5

Vậy kết quả bài toán là 30492 số.

Bài 2.7 (xem [2]). Có 8 viên bi giống nhau và 12 hộp bi khác nhau. Hỏi có

bao nhiêu cách sắp xếp 8 viên bi đó vào các hộp sao cho tổng số bi trong

hộp 1,2,3 là chẵn?

Giải Gọi số bi trong các hộp lần lượt là a1, . . . , a12.

Đặt a1 + a2 + a3 = x =⇒ x chẵn.

• Nếu x = 0 ⇒ có a4 + . . . + a12 = 8. Số nghiệm (a, . . . , a12) là C 8

16. Số

nghiệm (a1, a2, a3) là 1.

• Nếu x = 2 ⇒ có a4 + . . . + a12 = 6. Số nghiệm (a4, . . . , a12) là C 8

14. Số

nghiệm (a1, a2, a3) là C 2 4 .

• Nếu x = 4 ⇒ có a4 + . . . + a12 = 4. Số nghiệm (a4, . . . , a12) là C 8

12. Số

nghiệm (a1, a2, a3) là C 2 6 .

• Nếu x = 6 ⇒ có a4 + . . . + a12 = 2. Số nghiệm (a4, . . . , a12) là C 8

10. Số

nghiệm (a1, a2, a3) là C 2 8 .

• Nếu x = 8 ⇒ có a4 + . . . + a12 = 0. Số nghiệm (a4, . . . , a12) là 1. Số

nghiệm (a1, a2, a3) là C 2 10.

Vậy số cách xếp bi vào hộp là 47043 cách.

Bài 2.8 (VMO-2012). Cho một nhóm gồm 12 chàng trai và 5 cô gái, các cô gái được kí hiệu là G1; G2; G3; G4; G5. Có 17 chiếc ghế được xếp thành hàng ngang. Người ta xếp nhóm người đã cho ngồi vào các chiếc ghế đó

sao cho các điều kiện sau được thỏa mãn:

a) Mỗi ghế một người ngồi; b) Thứ tự ngồi của các cô gái từ trái qua phải là G1; G2; G3; G4; G5; c) Giữa G1 và G2 có ít nhất 3 chàng trai; d) Giữa G4 và G5 có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai.

Hỏi có mấy cách sắp xếp?

Giải

Đánh số các ghế từ trái qua phải theo thứ tự từ 1 đến 17.Gọi:

(cid:40)

x1 là số chàng trai được xếp bên trái G1; x2 là số chàng trai được xếp giữa G1 và G2; x3 là số chàng trai được xếp giữa G2 và G3; x4 là số chàng trai được xếp giữa G3 và G4; x5 là số chàng trai được xếp giữa G4 và G5; x6 là số chàng trai được xếp bên phải G5 ; Khi đó, ta có x1 + x2 + x3 + x4 + x5 + x6 = 12 x1 ≥ 0; x2 ≥ 3; x3 ≥ 0; x4 ≥ 0; 1 ≤ x5 ≤ 4; x6 ≥ 0. Bằng cách đặt y2 = x2 − 3; y5 = x5 − 1;. Lúc đó, số cách phân ghế cho

các cô gái chính là số nghiệm nguyên không âm của hệ (cid:40)

thu được kết quả là: C 4

x1 + y2 + x3 + x4 + y5 + x6 = 8 y5 ≤ 3. Ta lần lượt cho y5 nhận các giá trị 0; 1; 2; 3 và áp dụng Bài toán 2.4 ta 10 + C 4

9 = 1161 cách.

11 + C 4

12 + C 4

Vì 12 chàng trai có thể hoán đổi vị trí cho nhau nên số cách xếp thỏa

mãn yêu cầu bài toán là: 12!.1161 cách.

Bài 2.9 (HSG Tỉnh Quảng Trị 2014). Có 17 cây cau trồng xung quanh

một cái ao hình tròn. Người ta muốn chặt đi 4 cây. Hỏi có mấy cách chặt

sao cho không có 2 cây kề nhau bị chặt?

Giải

Ta đánh số thứ tự các cây từ 1 đến 17 và chia ra hai trường hợp như sau:

• Trường hợp 1: Giả sử cây số 1 bị chặt. Lúc này, các cây ở vị trí số 2

và 17 sẽ không bị chặt. Như vậy, ta sẽ chặt đi 3 cây ở vị trí số 3 đến

số 16 sao cho không có 2 cây kề nhau bị chặt. Ta xem các cây từ số 3 đến số 16 nằm trên một hàng dọc theo thứ tự từ trái qua phải. Gọi x1 là số cây bên trái cây thứ nhất bị chặt; x2 là số cây giữa cây thứ nhất và thứ hai bị chặt; x3 là số cây giữa cây thứ hai và thứ ba bị chặt; x4 là số cây bên phải cây thứ ba bị chặt. Lúc đó, ta có: (cid:40)

x1 + x2 + x3 + x4 = 11 x2 ≥ 1; x3 ≥ 1.

Bằng cách đặt y2 = x2 − 1; y3 = x3 − 1;. Lúc đó, số cách chặt cây chính là số nghiệm nguyên không âm của phương trình:

x1 + y2 + y3 + x4 = 9.

12 cách.

Áp dụng Bài toán 2.4 ta được kết quả là C 3

• Trường hợp 2 : Giả sử cây số 1 không bị chặt. Lúc này, các cây ở vị trí số

2 và 17 có thể được chặt. Bây giờ, ta xem các cây từ số 2 đến số 17 như

trên một hàng dọc. Lí luận như trường hợp 1, ta có hệ (cid:40)

x1 + x2 + x3 + x4 + x5 = 12 x2 ≥ 1; x3 ≥ 1; x4 ≥ 1.

Bằng cách đặt y2 = x2 − 1; y3 = x3 − 1; y4 = x4 − 1. Lúc đó, số cách chặt cây chính là số nghiệm nguyên không âm của phương trình:

x1 + y2 + y3 + y4 + x5 = 9.

12 cách.

Áp dụng Bài toán 2.4 ta được kết quả là C 4

Vậy, số cách chặt đi 4 cây cau thỏa mãn bài toán là 935 cách.

KẾT LUẬN

Luận văn được hoàn thành tại trường Đại học Khoa học - Đạị học Thái

Nguyên dưới sự hướng dẫn của GS.TSKH. Hà Huy Khoái. Luận văn đã

đạt được các mục tiêu đề ra:

- Tác giả giới thiệu một bức tranh toàn cảnh về bài toán biểu diễn số

nguyên dương dưới dạng tổng, từ lịch sử phát triển và những kết quả kinh

điển, đến một số kết quả gần đây. Trong thực tế bài toán đã truyền cảm

hứng cho rất nhiều nhà toán học trên toàn cầu và vẫn kích thích các nhà

toán học đến ngày nay, mọi nỗ lực của họ là phát triển một lý thuyết hoàn

chỉnh của phân hoạch cổ điển Euler. Con đường tìm ra chân lý toán học

rất gian nan và không phải lúc nào cũng suôn sẻ. Luận văn cũng đưa ra

những sai lầm trong quá trình nghiên cứu bài toán và những cơ hội bị bỏ

lỡ do hoàn cảnh lịch sử. Qua đó độc giả hiểu hơn về những chông gai trên

con đường khoa học và nuôi dưỡng lòng đam mê khám phá.

- Tác giả trình bày bài toán phân hoạch thành những phần phân biệt,

thành những phần lẻ, cùng với áp dụng của ánh xạ đối hợp của Franklin

và song ánh Sylvester để chứng minh một số định lí liên quan, đồng thời

đã đưa một số bài toán liên quan đến bài toán phân hoạch trong bồi dưỡng

học sinh giỏi.

Tài liệu tham khảo

Tiếng Việt

[1] Phan Chiến Thắng, Bài toán chia kẹo của Euler và ứng

dụng,

20GDTrH/EULER.pdf >. [Bản cập nhật ngày 15/4/2017].

[2] Bài toán chia kẹo của Euler,

/165688 % E1% BB% 81-b% C3% A0i-to% C3% A1n-chia-k% E1%

Tiếng Anh

BA% B9o-c% E1% BB%A7a-euler/>. [Bản cập nhật ngày 15/4/2017].

[3] G. Andrew,Partitions,

theory/... /andrews /chapter.pdf >. [Bản cập nhật ngày 15/4/2017].

[4] A.K.Agarwal (2009), Partition Theory: Yesterday and Today, Lecture

Notes, Centre for Advanced Study in Mathematics, Panjab University,

Chandigarh-160014, India, 2009.

[5] Igor Pak (2003), On Fine’s partition theorems, Dyson, Andrews,

and missed opportunities, The Mathematical Intelligencer, volume 25,

number 1, 2003.

[6] Pablo Soberón (2013), Problem-Solving Methods in Combinatorics:

An Approach to Olympial Problems, Birkhãuser.