(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng

(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng(Luận văn thạc sĩ) Về phân hoạch số nguyên và ứng dụng

Các định nghĩa và ví dụ

Phân hoạch của một số nguyên dương n là một dãy hữu hạn các số nguyên dương không tăng, ký hiệu là λ 1, λ 2, λ 3, , λ r, sao cho tổng các số này bằng n, tức là λ 1 + λ 2 + + λ r = n.

, các sốλ i i = 1 r được gọi là các phần của phân hoạch Trong trường hợp này chúng ta viết λ = (λ 1 , λ 2 , λ 3 , , λ r ), kí hiệu là λ ` n (nghĩa là λ là một phân hoạch n).

Khi ký hiệu f s là số lần xuất hiện của một số nguyên cụ thể s trong phân hoạch λ (λ = (λ 1 , λ 2 , λ 3 , , λ r ) ` n), phân hoạch này có thể được biểu diễn dưới dạng λ = 1 f1 2 f2 3 f3 n f n, với f s phần của phân hoạch λ bằng s Do đó, ta có công thức f 1 + 2f 2 + + n f n = n Định nghĩa 1.1.2 cho biết p(n) là số lượng tất cả các phân hoạch của số nguyên n, và p(n) được gọi là hàm phân hoạch.

1 Với n = 1, ta có phân hoạch sau: p(1) = 1 : 1 = (1).

2 Với n = 2, ta có phân hoạch sau: p(2) = 2 : 2 = (2), 1 + 1 = 1 2

3 Với n = 3, ta có phân hoạch sau: p(3) = 3 : 3 = (3), 2 + 1 = (12), 1 + 1 + 1 = 1 3

4 Với n = 4, ta có phân hoạch sau: p(4) = 5 : 4 = (4), 3 + 1 = (13), 2 + 2 = 2 2

5 Với n = 5, ta có phân hoạch sau: p(5) = 7 : 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1

6 Với n = 6, ta có phân hoạch sau: p(6) = 11 : 6 = 5 + 1 = 4 + 2 = 4 + 1 + 1 = 3 + 3 = 3 + 2 + 1 = 3 + 1 + 1

7 Với n = 7, ta có phân hoạch sau: p(7) = 14 : 7 = 6 + 1 = 5 + 2 = 5 + 1 + 1 = 4 + 3 = 4 + 2 + 1 = 4 + 1 + 1 + 1

8 Với n = 8, ta có phân hoạch sau: p(8) = 22 : 8 = 7 + 1 = 6 + 2 = 6 + 1 + 1 = 5 + 3 = 5 + 2 + 1 = 5 + 1 + 1 + 1

Ta thấy hàm phân hoạch tăng khi n tăng p(10) = 42, p(50) = 204226 p(20) = 672, p(100) = 190569292. Định nghĩa 1.1.3 Tập hợp tất cả các phân hoạch một số nguyên n được kí hiệu là S

Nếu T ⊂ S Ta kí hiệu p(T, n) là tập tất cả các phân hoạch nguyên của n thuộc vào tập T.

Ví dụ 1.1.2 Ta ký hiệu:

• D là tập tất cả các phân hoạch của n thành những phần khác nhau.

• O là tập tất cả các phân hoạch của n thành những phần lẻ.

• C là tập tất cả các phân hoạch của n thành những phần lẻ lớn hơn 1.

Hàm sinh

Hàm sinh f(q) đối với dãy a0, a1, a2, được định nghĩa là chuỗi lũy thừa f(q) = Σ(n≥0) a_n q^n Đối với mỗi tập con H ⊂ Z+, ký hiệu “H” đại diện cho tập tất cả các phân hoạch của số nguyên n với các phần thuộc H Khi đó, p(“H”, n) là số lượng phân hoạch của n mà các phần đều nằm trong H.

Ví dụ 1.2.1 Nếu H 0 là tập tất cả các số nguyên dương lẻ thì “H 0”= O

Do đó, p(“H 0”, n) = p(O, n) Định nghĩa 1.2.3 cho rằng H ⊂ Z +, và ký hiệu “H”(≤ d) đại diện cho tập hợp tất cả các phân hoạch của n, trong đó các phần thuộc H và không có số nguyên nào xuất hiện quá d lần.

Khi H =N ta có: p(“N”(≤ 1), n) = p(D, n). Định lý 1.2.1 Giả sử H ⊂Z + và f (q) =X n≥0 p (“H”, n) q n , f d (q) =X n≥0 p (“H”(≤ d), n) q n

Khi đó với | q |< 1 ta có: f(q) = Y n∈H

Chứng minh. a) Để chứng minh Định lý, chúng ta sẽ sử dụng khai triển chuỗi hình học biểu diễn hàm 1−q 1 n như sau:

Giả sử H ⊂Z + , vì Z + là tập sắp xếp thứ tự tốt, nên H là tập sắp thứ tự tốt, và ta có thể kí hiệu H = {h 1 , h 2 , h 3 , }, trong đó h i−1 < h i.

Trong đẳng thức đã cho, mỗi hạng tử ở phía phải là một luỹ thừa bậc của q, trong đó số mũ của q tương ứng với một phân hoạch của một số nguyên n nào đó Các phần trong phân hoạch này đều thuộc vào tập H Đối với mỗi giá trị cụ thể của n, ta có thể viết lại biểu thức: a1h1 + a2h2 + a3h3 + = n.

Vỡ vậy q a 1 h 1 +a 2 h 2 +a 3 h 3 +ããã = q n và trong tổng ở vế phải cú p(“H”, n) hạng tử bằng q n

Tiếp theo ta sẽ chứng minh tổng của vế phải của biểu thức trên là hội tụ khi q thoả mãn 0 < q < 1 Với mỗi tập hữu hạn H = {h 1 , h 2 , , h k } ⊂Z +

Giả sử M = h k , với mỗi n ≥ h k ta có:

Như vậy dãy PM j=0 p (“H”, j) p j là dãy tăng và bị chặn trên nên nó hội tụ.Mặt khác

Ta có đồng nhất thức (1.1). b) Để chứng minh đồng nhất thức (1.2) ta có:

Và sau đó, lập luận hoàn toàn tương tự như ở phần a) ta có (1.2).

Hệ quả 1.2.1 ( Euler) Với mọi số nguyên dương n ta có: p(O, n) = p(D, n).

Chứng minh. Áp dụng Định lý 1.2.1 ta có:

Hệ quả 1.2.2 Giả sử N d là tập các số nguyên dương không chia hết cho d Khi đó ta có p (“N d+1 ”, n) = p (“N”(≤ d), n) với mọi số nguyên n.

=X n≥0 p (“N d+1 ”, n) q n Suy ra điều phải chứng minh.

Biểu đồ Ferres

Biểu đồ Ferres cho phân hoạch λ = (λ1, λ2, , λr) là một bảng hình chữ nhật, trong đó số cột bằng λ1 và số hàng tương ứng với số phần khác 0 của λ Cụ thể, hàng đầu tiên chứa λ1 ô vuông, hàng thứ hai có λ2 ô vuông, và hàng thứ r có λr (với λr ≠ 0) ô vuông.

1 λ = (4, 2, 2, 1) ` 9 biểu đồ Ferres của λ là:

2 à = (2, 1, 1, 1, 1) ` 6 biểu đồ Ferres của à là:

3 γ = (4, 3, 2, 1) ` 10 biểu đồ Ferres củaγ là:

Định nghĩa 1.3.2: Giả sử λ = (λ₁, λ₂, , λᵣ) là một phân hoạch với n phần, ta có thể xác định một phân hoạch mới λ₀ = (λ₀₁, λ₀₂, , λ₀ₛ) sao cho mỗi λ₀ᵢ là số ô vuông ở cột thứ i (tính từ trái sang phải) trong biểu đồ Ferrers của λ Khi đó, λ₀ được gọi là phân hoạch liên hợp của λ.

Ta có biểu đồ Ferres của λ 0 1 , λ 0 2 , λ 0 3 , λ 0 4 là:

Theo nhận xét 1.3.1, nếu λ là một phân hoạch của n thì λ 0 cũng là phân hoạch của n Định lý 1.3.1 chỉ ra rằng số lượng phân hoạch của n không vượt quá m bằng với số phân hoạch của n mà không có phần nào lớn hơn m.

Ta kí hiệu A là các lớp các phân hoạch của n có nhiều nhất m phần, kí hiệu

B là lớp các phân hoạch của n trong đó không có phần nào vượt quá m.

Mỗi λ ∈ A được biểu diễn dưới dạng λ = (λ 1 , λ 2 , , λ r ) với r ≤ m và λ r ≠ 0 là một phân hoạch của n Liên hợp λ 0 = (λ 0 1 , λ 0 2 , , λ 0 r ) cũng là một phân hoạch thoả mãn điều kiện λ 0 1 = r, là số phần ≥ 1 của phân hoạch λ Do đó, ta có λ 0 1 ≤ m, từ đó suy ra rằng λ 0 i ≤ m cho mọi i = 1, , s.

Trong bài viết này, chúng ta xem xét ánh xạ f: A → B được xác định bởi f(λ) = λ₀, với λ₀ thuộc tập B Do đó, từ mối quan hệ (λ₀)₀ = λ, f trở thành ánh xạ từ B đến A, đồng thời là ánh xạ ngược của chính nó, chứng minh rằng f là một song ánh Kết luận, ta có |A| = |B|.

2 + 2 + 2; 3 + 2 + 1; 3 + 3.} Định lý 1.3.2 Số các phân hoạch của (a − c) có đúng (b − 1) phần không vượt quá c bằng số phân hoạch của a − b có đúng (c − 1) phần không vượt quá b.

M ký hiệu cho tập hợp tất cả các phân hoạch của (a − c) với đúng (b − 1) phần không vượt quá c Tương tự, N đại diện cho tập hợp các phân hoạch của (a − b) có đúng (c − 1) phần không vượt quá b.

Giả sử λ = (λ 1 , λ 2 , , λ b−1 ) là một phần tử bất kì của M, với điều kiện λ i ≤ c và tổng Pb−1 i=1 λ i = (a − c) Biểu đồ Ferres của λ có (b − 1) hàng và số cột không vượt quá c Để biến đổi biểu đồ Ferres của λ, bước đầu tiên là thêm một dòng mới lên trên hàng đầu tiên, với đúng c ô vuông.

Khi nhận được biểu đồ Ferres của phân hoạch λ ∗ cho số nguyên a với b hàng và c cột, bước tiếp theo là xóa cột đầu tiên, từ đó tạo ra biểu đồ Ferres cho phân hoạch của số nguyên (a − b) với số dũng ≤ b và số cột giảm còn (c − 1) Cuối cùng, xác định biểu đồ Ferres của phân hoạch à 0 liên hợp của à, biểu đồ này sẽ có đúng (c − 1) hàng và số cột ≤ b.

Sau ba bước trờn ta nhận được phần tử à 0 hoàn toàn xỏc định thuộc tập hợp

N Tương ứng trờn đó xỏc định ỏnh xạ φ : M → N thoả món φ(λ) = à 0

Ta dễ dàng chứng minh được φ là một song ánh vì vậy số phần tử của M bằng số phần tử của N. Định lý này được chứng minh.

Ví dụ 1.3.4 Trường hợp a = 20, c = 7, b = 5 và λ = (5, 4, 2, 2)

Trong ví dụ này ta có: λ ` 13 = a − c

= 20 − 17 λ ∗ ` 20 = a à ` 15 = a − b = 20 − 5 à 0 ` 15 thoả mãn chúng (c − 1) = b phần không vượt quá 5.

Vậy ta cú tương ứng λ = (5, 4, 2, 2) 7→ à = (5, 3, 3, 2, 1, 1).

Ví dụ 1.3.5 Với a = 14, b = 5, c = 4 Khi đó, ánh xạ φ ta có các kêt quả sau:

Định lý 1.3.3 đưa ra các ký hiệu p e (D, n) và p o (D, n) để biểu thị số lượng phân hoạch của n với các điều kiện nhất định Cụ thể, p e (D, n) đại diện cho số phân hoạch với số phần chẵn và các phần khác nhau, trong khi p o (D, n) thể hiện số phân hoạch với số phần lẻ và cũng khác nhau Định lý này khẳng định rằng hiệu số giữa p e (D, n) và p o (D, n) có một giá trị cụ thể, góp phần làm rõ mối quan hệ giữa các loại phân hoạch này.

0 trong các trường hợp còn lại.

D là tập hợp tất cả các phân hoạch của n, trong đó các phần tử là khác nhau và không trùng lặp Chúng ta sẽ thiết lập một ánh xạ từ D đến D xác định theo cách dưới đây.

Trước hết với mỗi phân hoạch λ = (λ 1 , , λ r ) ∈ D đặt S(λ) = λr, đây là số lớn nhất trong dãy trên.

Kí hiệu δ(λ) là số nguyên j lớn nhất thoả mãn quan hệ λ j = λ 1 − j + 1 (?)

Rõ ràng rằng tập hợp các số nguyên dương luôn tồn tại và có giá trị lớn nhất do bị chặn Tập hợp các số j thỏa mãn quan hệ đã cho là khác rỗng, vì chúng ta luôn có λ 1 = λ 1 − 1 + 1, dẫn đến δ(λ) ≥ 1 Cụ thể, với λ = (7, 6, 4, 3, 2), chúng ta có thể thấy rõ điều này.

Ta có s(λ) = 2, quan hệ λ j = λ 1 − j + 1 chỉ thoả mãn với j = 1 và j = 2

Ta có s(λ) = 4, quan hệ λ j = λ 1 − j + 1 thoả mãn với j = 1, j = 2, j = 3, j = 4 vậy δ(λ) = 4.

Ta xây dựng một tương ứng từ D đến D xác định như sau:

Trường hợp 1: Nếu s(λ) ≤ δ(λ) trong trường hợp này ta sẽ cộng thêm 1 vào các phần λ 1 , λ 2 , , λ s(λ) và xoá đi phần nhỏ nhất λ n , ta nhận được λ 0

Trường hợp 2: Nếus(λ) > δ(λ), khi đó ta sẽ bớt đi một của các phầnλ 1 , λ 2 , , λ δ(λ) và thêm vào một phần mới sau cùng là λ r+1 = δ(λ).

Tương ứng λ 7→ λ 0 được xác định trong cả hai trường hợp đều thay đổi tính chẵn lẻ của số phần của λ; cụ thể, nếu số phần của λ là chẵn thì số phần của λ 0 sẽ là lẻ, và ngược lại Hơn nữa, các xác định tương ứng này vẫn cung cấp phân hoạch λ 0 của n, với điều kiện λ 0 thuộc D, ngoại trừ một trường hợp cụ thể.

Trong trường hợp này ta nhận đượcλ 0 = (2r − 1, 2r − 2, , r)là phân hoạch có (r + 1) phần nhưng có 2 phần bằng nhau nên λ 0 ∈ / D.

Trong trường hợp này ta nhận được λ 0 = (2r, 2r − 1, , r + 2) và

Từ đó suy ra nếu n 6= 1 2 r(3r ± 1)thì p o (D, n) = p e (D, n) Còn nếun = 1 2 r(3r ± 1) thì p e (D, n) = p o (D, n) + (−1) r Định lý đã được chứng minh.

X(p e (D, n) − p 0 (D, n)) q n theo Định lý 1.3.3. Để hoàn thành việc chứng minh ta chỉ ra rằng:

Mỗi phân hoạch với các phần khác nhau có dấu tương ứng là (-1)^(a1 + a2 + ), trong đó giá trị bằng +1 nếu phân hoạch có số phần chẵn và bằng -1 nếu có số phần lẻ.

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

+ ã ã ã = 0, (1.3) trong đó ta quy ước: p(M ) = 0 với tất cả M < 0.

Ta kí hiệu a n là vế trái của (1.3) Khi đó

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

Giả thuyết của M.Merca và một số kết quả mới về hệ số đa thức đối với phân hoạch và đối với những phân hoạch thành những phần lẻ 18

Đặt vấn đề

Phân hoạch λ có thể được biểu diễn dưới dạng t1 + 2t2 + + nt_n = n và t1 + t2 + + t_n = k, cho thấy rằng phân hoạch λ có k phần Trong biểu diễn này, mỗi số nguyên j xuất hiện trong phân hoạch đúng t_j lần.

0 ≤ t j ≤ n Như vậy nếu t j = 0 thì số j không xuất hiện trong phân hoạch đó.

Nếu λ là một phân hoạch của n thành những phần khác nhau, thì ta có t j ≤ 1 với mọi j = 1, 2, , n Trong trường hợp λ là một phân hoạch của n thành những phần lẻ, ta có t 2 = t 4 = = t 2r = 0 với 2r ≤ n Định nghĩa 2.1.1: Ký hiệu p(n, k) là số các phân hoạch của n thành k phần Định nghĩa 2.1.2: Nếu λ = (λ 1, λ 2, , λ k) = 1 t 1 2 t 2 n t n.

= (t 1 + t 2 + ã ã ã + t n )! t 1 !t 2 ! ã ã ã t n ! = k! t 1 !t 2 ! ã ã ã t n ! được gọi là hệ số đa thức được xác định bởi phân hoạch λ đã cho.

Năm 1959 N.J.Fine đã đưa ra và chứng minh được mối quan hệ sau đây giữa các hệ số nhị thức và hệ số đa thức:

Hệ số đa thức trong mệnh đề 2.1.1 cho thấy rằng nếu k là một ước của n, thì tồn tại một phân hoạch cho biểu thức 1 + 2t2 + + nt n = n, thỏa mãn điều kiện t1 + t2 + + tn = k.

= 1. b) Nếu n mod k > 0, thì đối với một phân hoạch bất kỳ của n có dạng t 1 + 2t 2 + ã ã ã + nt n = n thoả món t 1 + t 2 + ã ã ã + t n = k, ta luụn cú:

Chứng minh. a) Khi k là ước của n, ta có n = k.s.

Khi đú tồn tại một phõn hoạch t 1 + 2t 2 + ã ã ã + st s + ã ã ã + nt n = n mà cỏc t i = 0 với i 6= s và t s = k.

Với phân hoạch đó ta có

Dễ dàng thấy rằng ngoài phân hoạch trên, mọi phân hoạch còn lại khác của n đều có

Chỉ có một phân hoạch duy nhất thỏa mãn điều kiện đã cho Nếu n mod k > 0, giả sử t1 + 2t2 + + nt_n = n là một phân hoạch bất kỳ của n với t1 + t2 + + t_n = k, thì trong phân hoạch này sẽ có ít nhất hai số i và j thỏa mãn t_i ≠ 0 và t_j ≠ 0 Để đơn giản, ta có thể giả thiết rằng i = 1 và j = 2 Khi đó, hệ số đa thức của phân hoạch có thể được biến đổi theo cách nhất định.

Vì vậy ta luôn có

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

Mệnh đề 2.1.2 Cho n, k là hai số nguyên dương, k ≤ n khi đó ta có:

Chứng minh. a) Từ định nghĩa của hàm p(n) và hàm p(n, k) ta có: p(n) = n

X k=1 p(n, k ) b) Theo công thức xác định mối quan hệ giữa hệ số đa thức và hệ số nhị thức của Fine ta có:

Tổng ở vế trái của đẳng thức có số hạng tử tương ứng với số phân hoạch của n thành k phần, cụ thể là cóp(n, k) hạng tử Theo Mệnh đề 2.1.1, nếu n mod k = 0, thì chỉ có một hạng tử bằng 1, trong khi các hạng tử còn lại đều lớn hơn hoặc bằng 2 Ngược lại, nếu n mod k > 0, tất cả các hạng tử của vế trái đều lớn hơn hoặc bằng 2.

Ta được điều cần chứng minh.

Hệ số đa thức đối với các phân hoạch của n và giả thuyết M.Merca 21

This section presents new results by M Merca in the paper "New Upper Bounds for the Number of Partitions into a Given Number of Parts," published in the Journal of Number Theory, vol 142, 2014, pages 298-304 Definition 2.2.1 defines M_m(n, k) as the number of polynomial coefficients that satisfy specific conditions.

Ví dụ Với n = 8, m = 6 và k = 3 ta có M 6 (8, 3) = 2.

Mệnh đề 2.2.1 Giả sửn, k và m là các số nguyên dương thoả mãn k ≤ n Khi đó ta có: a) p(n, k) = P m≥1 M m (n, k), b) P m≥1 mM m (n, k) =

Chứng minh. a) Từ định nghĩa 2.1.1 và định nghĩa 2.2.1 ta suy ra: p(n, k) = X m≥1

Tổng P m≥1 mM m (n, k) là tổng của tất cả các hạng tử, tương ứng với các hệ số đa thức được xác định bởi các phân hoạch của n thành k phần, với giá trị m tùy ý.

 và do đó theo biểu thức (2.1) có:

. c) Từ Mệnh đề 2.1.1 ta thấy có đúng một phân hoạch thoả mãn:

 = 1 khi n mod k = 0, còn khi n mod k > 0 thì không có phân hoạch thoả mãn

Vì vậy M 1 (n, k) = δ 0,n mod k d) Ta thấy để

= 2, thỡ phõn hoạch t 1 + 2t 2 + ã ã ã + nt n = n với trường hợp này theo chứng minh Mệnh đề 2.1.1 thì

 ≥ k, từ đó suy rak = 2 và t i = 1, t j = 1 Như vậy ta cóit i + jt j = n và (i, j )chính là nghiệm của phương trình x + y = n, phương trình này có

 cặp nghiệm Từ đó suy ra M 2 (n, k) = δ 0,k

Ta được điều cần chứng minh. Định lý 2.2.1 Cho k, n và p là ba số nguyên dương Nếu p là một số nguyên tố lẻ thì ta có:

Ta có nhận xét sau đây:

Nếu hệ số đa thức

Theo giả thiết rằng p là số nguyên tố, ta có k - p Trong cả hai trường hợp p < k và p > k, không tồn tại phân hoạch nào có dạng t₁ + 2t₂ + + ntₙ = n với tổng Pₙ i=₁ tᵢ = k thỏa mãn.

Trong trường hợp này M p (n, k) = 0. b) Xét trường hợp p = k ta có:

= k! t 1 !(k − t 1 )! ã (k − t 1 )! t 2 !t 3 ! ã ã ã t n ! = k = p Đẳng thức xảy ra khi có ít nhất 2 chỉ số t i 6= 0 và t j 6= 0 và một trong hai số đó bằng 1, số còn lại bằng (p − 1).

Như vậy số các phân hoạch của n thoả mãn

 = k bằng số các cặp nghiệm khác nhau của phương trình 2 ẩn x(p − 1) + y = n.

• Khi p- n (hay n mod p > 0) phương trình này có các cặp nghiệm là

• Khi p | n (hay n mod p = 0) thỡ sẽ cú t sao cho p ã t = n và ta cú một cặp nghiệm (t, n − t(p − 1)) = (t, t), ta phải loại cặp nghiệm này, trong trường hợp này có số nghiệm là j n−1 p−1 k

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

Một câu hỏi được đặt ra là khi m không phải là số nguyên tố, việc xác định

M m (n, k) có còn giống như trên nữa hay không ?

M.Merca đã kiểm tra và tính được với m ∈ {4, 8, 9, 16} ( nghĩa là m là luỹ thừa của một số nguyên tố) ta có:

Tuy nhiên M.Merca đã không chứng minh được công thức này trong trường hợp tổng quát m = p q (m là luỹ thừa của một số nguyên tố).

Vì vậy ông đã đưa ra một giả thuyết (còn gọi là Giả thuyết 1 của M.Merca).

Giả thuyết 1 của M.Merca Cho k, n, p và r là bốn số nguyên dương Nếu p là một số nguyên tố thoả mãn p r > 2 thì ta có:

M.Merca chỉ ra rằng nếu m không phải là luỹ thừa của một số nguyên tố, công thức tính M m (n, k) sẽ trở nên phức tạp hơn rất nhiều.

Cụ thể đối với m ∈ {6, 10, 22} M.Merca đã tính được các kết quả sau:

. Định lý 2.2.2 Cho k, n và t là ba số nguyên dương Khi đó ta có: p(n, k) ≤ 1 t

Dấu bằng xảy ra khi t = k!.

Vì k, n và t là ba số nguyên dương, khi đó ta có:

Mặt khác p(n, k) = P m≥1 M m (n, k) nên ta có:

Hơn nữa với t 1 + t 2 + ã ã ã + t n = k ta cú:

Theo Định nghĩa M(n, k) là số các hệ số đa thức thoả mãn

Nên suy ra rằng M m (m, k) = 0 với m > k!

Từ (2.5) chia cả hai vế cho t (t 6= 0) p(n, k) ≤ 1 t

Trong trường hợp t = 3, từ cách tính M 1 (n, k) và M 2 (n, k) trong Mệnh đề 2.2.1 ta suy ra ngay hệ quả sau đây:

Hệ quả 2.2.1 Cho k, n là hai số nguyên dương, khi đó ta có : p(n, k) ≤ 1

Khi t = 4, từ cách tính M 1 (n, k), M 2 (n, k) trong Mệnh đề 2.2.1 và M 3 (m, k) trong Định lý 2.2.2 ta có hệ quả dưới đây.

Hệ quả 2.2.2 Cho n, k là hai số nguyên dương, khi đó ta có: p(n, k) ≤ 1

Chứng minh giả thuyết 1 của M.Merca

Phần này sẽ trình bày chứng minh giả thuyết 1 của M.Merca của VictorJ.W.Guo trong bài báo “Proof of a conjecture of Mircea Merca”, đăng trênJ.Number Theory năm 2015, vol.147, p590-593.

Bổ đề 2.3.1 Cho n, k là hai số nguyên dương thoả mãn 2 ≤ k ≤ n 2 Khi đó hệ số nhị thức

 không phải là luỹ thừa của một số nguyên tố.

Với mọi p là số nguyên tố thì bậc p-adic của n! có thể được tính như sau: ord p n! =

Ta chứng minh bằng phương pháp phản chứng như sau:

 là một luỹ thừa của một số nguyên tố, chẳng hạn

Vì bx + yc − bxc − byc ≤ 1

Suy ra rằng r ≤ a, ở đó a = max i, trong các i thoả mãn p i ≤ n Từ đó suy ra p r ≤ n.

Mặt khác do 2 ≤ k ≤ n 2 , ta có

> n, trái với bất đẳng thức ở trên.

Vậy hệ số nhị thức

 không phải là một luỹ thừa của một số nguyên tố. Định lý 2.3.1 (Giả thuyết 1 của M.Merca)

Cho k, n, p và r là bốn số nguyên dương, nếu p là số nguyên tố thoả mãn p r > 2 thì:

Ta cần xác định số M p r (n, k ), đây chính là số các hệ số đa thức thoả mãn:

Trước tiên ta sẽ chỉ ra rằng trong các số t 1 , t 2 , , t n Chỉ có đúng hai số t i và t j khác không.

Thực vậy, giả sử ngược lại rằng, trong đó các số t 1 , t 2 , , t n có ít nhất ba số khác 0, chẳng hạn là t 1 , t 2 , t 3 6= 0 Khi đó rõ ràng t 1 + t 2 + t 3 ≥ 3 và ta có:

Kí hiệut a = max {t 1 , t 2 , t 3 }ta có ngay

 và do đó cũng là ước của

Tuy nhiên theo Bổ đề 2.3.1 thì

không phải là luỹ thừa của một số nguyên tố.

Mâu thuẫn trên đây khẳng định rằng chỉ có đúng hai số t i và t j khác 0.

Hơn nữa cũng từ Bổ đề 2.3.1 ta có ngay một trong hai số khác không đó phải bằng 1 và từ biểu thức

= p r suy ra số còn lại bằng p r − 1.

Hay nói cách khác từ biểu thức

= p r sẽ suy ra được rằng

Nếu k = p r thì ta thấy ngay rằng M p r (n, k) bằng số các nghiệm nguyên dương (x, y) với x 6= y của phương trình vô định trên, nghĩa là:

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

Hệ số đa thức đối với các phân hoạch của n thành những phần lẻ 29

Số phân hoạch nguyên của n thành các phần lẻ được ký hiệu là Q(n), trong khi Q0(n) đại diện cho số phân hoạch nguyên của n thành các phần lẻ lớn hơn 1.

Nhận xột 2.4.1 Một phõn hoạch nguyờn củan cú dạng n = λ 1 + λ 2 + ã ã ã + λ k = t 1 + 2t 2 + ã ã ã + nt n hoàn toàn phụ thuộc vào cỏc t j 6= 0.

Ví dụ 2.4.2 Với n = 8 các phân hoạch thuộc O ở trên có thể được viết như sau:

Vì vậy với những phân hoạch nguyên n thành những phần lẻ ta cú t 2 = t 4 = ã ã ã = t 2r = 0 với (2r ≤ n) nờn ta cú: n = t 1 + 2t 2 + ã ã ã + nt n

Vì vậy ta có thể đánh chỉ số lại theo tương ứng: t 2r−1 = t r với 1 ≤ r ≤l n

Khi đó ta có Pd n 2 e r=1 (2r − 1)t r =Pd n 2 e r=1 a r t r với a r = 2 r − 1, 1 ≤ r ≤ n

Vì vậy đối với những phân hoạch nguyên của n thành những phần lẻ dưới dạng: λ = λ 1 + λ 3 + ã ã ã + λ k = t 1 + 2t 2 + ã ã ã + nt n = d n 2 e X r=1 a r t r thì hệ số đa thức phân hoạch đó viết dưới dạng:

= k! t 1 !t 2 ! ã ã ã t d n 2 e ! Định nghĩa 2.4.2. a) Ta kí hiệu Q k (n) là số các hệ số đa thức thoả mãn:

(2k − 1)t k = n b) Kí hiệu Q 0 k (n) là số các hệ số đa thức thoả mãn:

Nhận xét 2.4.2 Theo định nghĩa trên ta thu được:

Mệnh đề 2.4.1 Kí hiệu τ(n) là số các ước nguyên dương của n, khi đó ta có: a) Q 1 (n) =

, nếu n là số chẵn. Định lý 2.4.1 Cho p là số nguyên tố và cho r là số nguyên dương với p r > 2. Các hàm sinh của Q p r (n) được cho bởi:

Với mọi số nguyên dương n và k, ta có: l 1 2 j n k km

Khi p là số nguyên tố lẻ và r là số nguyên dương, đồng nhất ta được

1 − x 2p r , |x| < 1. Đồng nhất lần cuối cùng theo hàm sinh của n k

(1 − x)(1 − x k ) , |x| < 1 với k là số nguyên dương.

2 r mod 2=1, ta có n = 2 r k với k lẻ Vậy p = 2 và r > 1, ta có:

1 − x 2 r+1 Suy ra điều phải chứng minh.

Ứng dụng của hệ số đa thức đối với các phân hoạch thành những phần lẻ để biểu diễn các số Fibonacci và số Padovan

hoạch thành những phần lẻ để biểu diễn các số Fibonacci và số Padovan

In 2014, M Merca published a paper titled "New Upper Bounds for the Number of Partitions into a Given Number of Parts" in the Journal of Number Theory, volume 142, pages 298-304 In this paper, Merca presented and proved Theorem 2.5.1, which involves two sequences, {a_n} for n ≥ 0 and {b_n} for n ≥ 0, that satisfy specific conditions.

(−1) k a k b n−k = δ 0,n trong đó δ i,j là ký hiệu Delta Kronecker, khi đó ta có: a n a 0 = X t 1 +2t 2 +ããã+nt n =n

= (t 1 + t 2 + ã ã ã + t n )! t 1 !t 2 ! ã ã ã t n ! là các hệ số đa thức xác định bởi phân hoạch nguyên của n t 1 + 2t 2 + ã ã ã + nt n = n

Trong phần này ta sẽ sử dụng Định lý trên để biểu diễn các số Podovan và các số Fibonacci. Định nghĩa 2.5.1 (Định nghĩa số Padovan)

Dãy số Padovan {P n } n≥0 là một dãy số nguyên được xác định bởi quan hệ truy hồi.

P n = P n−2 + P n−3 Một vài số hạng ban đầu của dãy Padovan là:

1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21 Định lý 2.5.2 Với n > 0, ta có:

Ta xét hai dãy số dương được xác định như sau Dãy {a n } n≥0 thoả mãn: a n =

1 khi n = 0 n mod 2 khi n 6= 0,dãy {b n } n≥0 thoả mãn b n =

P n khi n 6= 0, trong đó P n là số Padovan thứ n Khi đó ta có: n

Ta có thể xét thành hai trường hợp n là chẵn và n là lẻ Bằng phương pháp quy nạp ta có thể chứng minh được ngay là với n ≥ 1 ta có: n

Vì vậy, ta có thể áp dụng Định lý 2.5.2 đối với hai dãy {a n } n≥0 và {b n } n≥0 trong trường hợp n = 3t 3 + 5t 5 + ã ã ã +l n

2 m t d n 2 e = d n 2 e X k=1 a r t r với a r = 2r − 1 Từ đó ta có: b n b 0 = n

= 1 với r = 2, , l n 2 m Hơn nữa ta có: t 2 + t 3 + ã ã ã + t d n 2 e ≡ n(mod2).

Vì b n = P n , b 0 = 1 nên định lý được chứng minh. Định lý 2.5.3 Với n là một số nguyên dương (n > 1), ta có:

Theo Định lý 2.5.2, ta thấy:

Với mỗi m xác định, Q 0 m (n) là hệ số đa thức, nghĩa là trong tổng của vế phải của biểu thức (2.9) có Q 0 m (n) hạng tử có dạng cụ thể.

=X m≥1 mQ 0 m (n) = P n Định lý được chứng minh.

Nếu k là một thứ tự nguyên tố lớn hơn 2 và Q k (n) > 0 thì

Q 0 k (n) = Q k (n) − 1 −j n − 1 k − 1 k mod 2 ã δ 0,(n−1) mod (k−1) (2.12) Trong đó bxc là ký hiệu của số nguyên lớn nhất nhỏ hơn hoặc bằng x.

Gọi M k (n) biểu thị số các hệ số đa thức thoả mãn:

Guo đã chỉ ra rằngM p r (n)bằng với số nghiệm nguyên dương(x, y)của phương trình

Q p r (n) là số lượng nghiệm nguyên dương (x; y) của phương trình (2.13) với x, y lẻ và x khác y Trong khi đó, Q 0 p r (n) là số nghiệm nguyên dương (x; y) của (2.13) với x, y lẻ, x, y > 1 và x khác y Nếu Q p r (n) > 0, thì (1; y) với y lẻ là một nghiệm của (2.13), và (x; 1) với x lẻ là nghiệm của (2.13) khi và chỉ khi p r − 1 chia hết cho n − 1, từ đó suy ra (2.12) Định nghĩa 2.5.2 đưa ra khái niệm về số Fibonacci.

Dãy Fibonacci là dãy vô hạn của các số tự nhiên bắt đầu bằng hai phần tử 0 và

Dãy Fibonacci được thiết lập theo quy tắc rằng mỗi phần tử luôn bằng tổng của hai phần tử trước nó Công thức truy hồi của dãy Fibonacci là: F(n) = F(n-1) + F(n-2), với F(0) = 0 và F(1) = 1.

F (n − 1) + F (n − 2) khi n > 2 Định lý 2.5.4 Cho n là một số nguyên dương ta có

Ta xét hai dãy số dương được xác định như sau Dãy {a n } n≥0 thoả mãn: a n =

1 khi n = 0 n mod 2 khi n 6= 0,dãy {b n } n≥0 thoả mãn b n =

F n khi n 6= 0, trong đó F n là số Fibonacci thứ n Khi đó ta có: n

Ta có thể xét thành hai trường hợp n là chẵn và n là lẻ Bằng phương pháp quy nạp ta có thể chứng minh được ngay là với n ≥ 1 ta có: n

Vì vậy, ta có thể áp dụng Định lý 2.5.2 đối với hai dãy {a n } n≥0 và {b n } n≥0 trong trường hợp n = t 1 + 3t 3 + ã ã ã +l n

2 m t d n 2 e = d n 2 e X k=1 a r t r với a r = 2r − 1 Từ đó ta có: b n b 0 = n

= 1 với r = 1, , l n 2 m Hơn nữa ta có: t 1 + t 2 + ã ã ã + t d n 2 e ≡ n(mod2).

Vì b n = F n , b 0 = 1 nên định lý được chứng minh.

Qua thời gian tìm hiểu và nghiên cứu luận văn đã được thu những kết quả sau:

• Giới thiệu các kiến thức cơ bản phân hoạch của một số nguyên được trình bày qua các định nghĩa và ví dụ.

• Nghiên cứu về hàm sinh, nghiên cứu về biểu đồ Ferres.

• Hệ số đa thức đối với các phân hoạch của n và giả thuyết M.Merca.

• Chứng minh giả thuyết 1 của M.Merca.

• Hệ số đa thức đối với các phân hoạch của n thành những phần lẻ.

• Ứng dụng của hệ số đa thức đối với các phân hoạch thành những phần lẻ để biểu diễn các số Fibonacci là số Padovan.