Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH
KHOA TỐN

KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC
Bộ Mơn: Đại Số

Đề tài:

Bóng Của Một Đoạn Trong Multiset

Giáo Viên Hướng Dẫn: TS.Trần Huyên
Sinh Viên: Phạm Văn Trí
MSSV: K34101098

TP. Hồ Chí Minh
Tháng 4 – 2012


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

TRƯỜNG ĐẠI HỌC SƯ PHẠM THÀNH PHỐ HỒ CHÍ MINH
KHOA TỐN

KHĨA LUẬN TỐT NGHIỆP ĐẠI HỌC
Bộ Mơn: Đại Số

Đề tài:

Bóng Của Một Đoạn Trong Multiset

Giáo Viên Hướng Dẫn: TS.Trần Huyên
Sinh Viên: Phạm Văn Trí
MSSV: K34101098

TP. Hồ Chí Minh
Tháng 4 – 2012


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

LỜI MỞ ĐẦU
Khái niệm bóng của một tập con của tập n phần tử được đề xuất và sử dụng có
hiệu quả lần đầu tiên bởi nhà toán học Sperner vào năm 1928, khi ơng tìm cách
giải quyết bài tốn ước lượng độ lớn cho các hệ antichain trong poset P(S) – poset
các tập con của tập S hữu hạn gồm n phần tử.
Khái niệm bóng của tập hợp đã được Sperner sử dụng như một kỹ thuật để
đánh giá thành công cận trên cho độ lớn các antichain, càng về sau càng tìm được
nhiều ứng dụng trong lý thuyết combinatorics. Đặc biệt năm 1963, nhà toán học
Kruskal khi kết hợp khái niệm bóng này với một thứ tự tuyến tính, mà sau này
được biết đến với tên gọi là thứ tự nén đã cho ra một kết quả nổi tiếng của lý thuyết
combinatorics. Đó là định lý Kruskal – Katona liên quan tới việc đánh giá cận dưới
cho độ lớn bóng của các tập con cùng lực lượng.
Về sau, các nhà tốn học đã mở rộng khái niệm bóng cho các tập sắp thứ tự và
đạt được nhiều kết quả mới.

Trong luận văn này, chúng ta chủ yếu giải quyết vấn đề: Với những điều kiện
cần và đủ nào thì bóng của một đoạn là một đoạn trong multiset . Để giải quyết vấn
đề trên, đầu tiên ta xem xét và giải quyết yêu cầu đặt ra trong môi trường tập đơn
bội, sau đó là phát triển và giải quyết vấn để trong môi trường tập đa bội .Và tất
nhiên, sau khi giải quyết vấn đề ,chúng ta sẽ nhìn nhận và so sánh những điểm
tương đồng và sai khác trong hai trường hợp và xem xét rằng: liệu kết quả của
trường hợp tập đa bội có cịn đúng với trường hợp tập đơn bội hay không ?
“Vạn sự khởi đầu nan”, việc tiếp cận với kiến thức mới quả là vơ cùng khó
khăn, phải trải qua một q trình để tìm hiểu và nhận thức. Và trong quá trình ấy
em vơ cùng biết ơn sự chỉ dạy tận tình, nhiệt huyết của thầy Trần Huyên, giáo viên


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

hướng dẫn luận văn tốt nghiệp bộ môn Đại số. Em xin được phép gửi đến thầy lời
chúc sức khỏe và lời cảm ơn chân thành nhất.
Qua giai đoạn tìm hiểu và giải quyết vấn đề, em cảm thấy vô cùng phấn khởi
và mong muốn có nhiều cơ hội để phát triển vấn đề trong tương lai. Mặc dù đã rất
cố gắng nhưng chắc chắn vẫn cịn nhiều sai sót, em rất mong được sự góp ý chân
thành của quý thầy cô và bạn bè. Mọi chi tiết xin liên hệ về
email: . Xin chân thành cảm ơn rất nhiều.
TP.HCM, ngày 22 tháng 4 năm 2012
Sinh viên:
Phạm Văn Trí


Bóng của đoạn trong Multiset


Luận văn tốt nghiệp đại học
MỤC LỤC

LỜI MỞ ĐẦU ............................................................................................................1
CHƯƠNG I: KIẾN THỨC CHUẨN BỊ ....................................................................6
I. Poset (partially ordered set) ................................................................................6
II. Hàm hạng: .........................................................................................................8
III. Mức: .................................................................................................................8
IV. Bóng: ................................................................................................................8
V. Đoạn, đoạn đầu: ..............................................................................................10
VI. Thứ tự từ điển: ...............................................................................................10
VII. Sơ lược về lịch sử dẫn đến vấn đề:...............................................................10
CHƯƠNG II: BĨNG CỦA ĐOẠN TRONG MULTISET ......................................13
I. Bóng của đoạn trong poset các tập con của tập đơn bội: .................................14
1. Từ tập con của tập đơn bội cho đến vector tọa độ: ......................................14
2. Các kết quả chính: ........................................................................................16
2.1. Các Bổ Đề: ................................................................................................16
2.2 Các Định Lý: ..............................................................................................19
II. Bóng của đoạn trong multiset: ........................................................................26
1. Mệnh đề 1: ...................................................................................................27
2. Mệnh đề 2: ...................................................................................................31
3. Mệnh đề 3: ...................................................................................................33
4. Mệnh đề 4: ...................................................................................................34
5. Mệnh đề 5: ...................................................................................................35
CHƯƠNG III: NHỮNG ĐIỂM TƯƠNG ĐỒNG VÀ SAI KHÁC TRONG HAI
TRƯỜNG HỢP TRÊN ............................................................................................43
1. Bóng của một đoạn đầu: ..................................................................................43
2. Bóng của đoạn mà hai đầu mút có tọa độ khác khơng đầu tiên là như nhau: .44
3. Bóng của đoạn mà hai đầu mút có tọa độ khác không đầu tiên là khác nhau: 45
TÀI LIỆU THAM KHẢO .......................................................................................46



Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

CHƯƠNG I: KIẾN THỨC CHUẨN BỊ
I. Poset (partially ordered set)

1. Poset:
Poset là một tập hợp với thứ tự bộ phận, tức P = ( S ,  ) với  là một thứ tự bộ
phận trên S .
Ví dụ 1.1: ( ,|) là một poset.
*

Thật vậy:

∀x ∈ * , ta có x | x ( thỏa tính phản xạ).
a | b
b | a

Giả sử: 

=
b ka
l 1
⇒
⇒ a =lka ⇒ lk =1 ⇒ 
⇒ a =b ( thỏa tính phản xứng).
a

lb
=
k
1


a | b b = ka
⇒
⇒ c = lka ⇒ a | c ( thỏa tính bắc cầu).
=
b
|
c
c
lb



Giả sử 

Và rõ ràng quan hệ ước số " | " là thứ tự bộ phận.
Vậy ( ,|) là một poset.
*

Ví dụ 1.2: (,|) khơng là poset vì khơng thỏa tính chất phản xứng.

2 | −2
nhưng −2 ≠ 2 .
2
|

2
−


Chẳng hạn lấy 

Ví dụ 1.3: Gọi P ( S ) là tập hợp chứa tất cả các tập con của S . Và ⊂ là thứ tự bao
hàm thì ( P ( S ), ⊂) là một poset.
Thật vậy:

A ⊂ A, ∀A ∈ P( S ) (phản xạ).


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

A ⊂ B
⇒ A=
B (phản xứng).
B ⊂ A

Giả sử 

A ⊂ B
⇒ A ⊂ C (bắc cầu).
B
⊂
C



Giả sử 

Và rõ ràng quan hệ bao hàm là quan hệ thứ tự bộ phận.
Vậy ( P ( S ), ⊂) là một poset.
2. Trội, trội trực tiếp:
Xét Poset ( S ,  ) và x, y ∈ S .
i) Nếu x  y thì ta nói y là trội của x hay x được trội bởi y .
ii) Ta nói y là trội trực tiếp của x nếu y trội x và không tồn tại z ≠ x, y sao
cho: x  z  y .
3. Phần tử tối đại, tối tiểu:
Trong poset ( S ,  ) , một phần tử m được gọi là tối đại (tương ứng là tối tiểu) nếu

m khơng có trội thực sự ( tương ứng khơng là trội thực sự của phần tử nào cả).
Hay:

∀x ∈ A,(m  x) ⇒ (m =x)
(tương ứng ∀x ∈ A,( x  m) ⇒ ( x =m) ).
4. Phần tử lớn nhất, phần tử nhỏ nhất:
Trong poset ( S ,  ) , a được gọi là phần tử lớn nhất (tương ứng nhỏ nhất) nếu :

x  a, ∀x ∈ S (tương ứng a  x, ∀x ∈ S ).
Ví dụ 4.1:
Poset ( P ( S ), ⊂) có phần tử nhỏ nhất là ∅ , phần tử lớn nhất là S .


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học


Poset (* |) có phần tử nhỏ nhất là 1.
 Lưu ý:
Trong 1 poset, phần tử lớn nhất nếu tồn tại là phần tử tối đại duy nhất (tương tự
cho phần tử nhỏ nhất và tối tiểu).
Trong 1 poset hữu hạn, nếu có duy nhất phần tử tối đại thì đó là phần tử lớn nhất
(tương tự cho phần tử nhỏ nhất và tối tiểu).
II. Hàm hạng:

Cho poset P = ( S ,  ) , giả sử có 1 ánh xạ r từ poset P vào  sao cho:

r (a ) = 0 nếu a là phần tử tối tiểu của P ,
(b) r (a ) + 1 nếu b là trội trực tiếp của a .
Và r=
Thì r được gọi là hàm hạng của P .
Khi đó, P cũng được gọi là 1 poset có hạng .
III. Mức:

Cho poset P = ( S ,  ) có hàm hạng r . Ta định nghĩa mức thứ k của P là:

Pk =
{a ∈ P : r (a ) =
k}
IV. Bóng:

Cho P là một poset có hạng với các mức P0 , P1 , P2 ,... . Với k ≥ 1 và a ∈ Pk ,
bóng của a được định nghĩa là:

∆a = {x ∈ Pk −1 : a là trội trực tiếp của x}
Và bóng của A ⊂ Pk là:


∆A =  ∆a
a∈A

Sau đây là một số Ví dụ về poset có hạng mà ta sẽ dùng đến trong các phần kế tiếp.
Như thông lệ, ta ký hiệu A chỉ số phần tử của A . Và để đơn giản ký hiệu, vector

( x1 , x2 ,..., xk ) được viết là x1 x2 ...xk nếu khơng có gì nhầm lẫn.


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

Ví dụ 4.1: Poset ( P ( S ), ⊂) , với P ( S ) là tập hợp các tập con của S = {1, 2,..., n}
là một poset có hạng với các đặc trưng:
Phần tử: a là tập con của S .
Thứ tự bộ phận: a ⊂ b .
Hàm hạng: r ( a ) = a là số phần tử của a .

{a ⊂ S : a =
k} .
Mức thứ k : Pk ( S ) =
{b a : b =
k − 1}
Bóng của a ∈ Pk ( S ) =⊂
Ví dụ 4.2: Poset S ( k1 , k2 ,..., kn ) các tập con của tập đa bội gồm n phần tử, trong
đó phần tử thứ i lặp ki lần trong đó k1 ≤ k2 ≤ ... ≤ kn , ki ∈  , với quan hệ " ≤ "
*

là một poset có hạng với các đặc trưng sau:

Phần tử: x = x1 x2 ...xn với 0 ≤ xi ≤ ki , xi ∈ 

=
Thứ tự bộ phận:
với x x=
1 x2 ...xn , y

*

y1 y2 ... yn thì

x ≤ y ⇔ xi ≤ yi , ∀i =1,..., n .
Hàm hạng: r ( x) = x1 + x2 + ... + xn

k}.
{x ∈ S : r ( x ) =
Mức thứ k : Pk =
=
Bóng
của x x1 x2 ...xn ∈ Pk :
Trước hết ta định nghĩa bóng thành phần thứ i của x là:

∆i x =
∅ nếu xi = 0 và=
∆ i x x1 x2 ..( xi − 1)..xn nếu xi > 0 .
Thì: ∆x = ∪∆ i x
Ví dụ 4.3: Poset Β các vector Bool

x x1 x2 ...xk , k ∈  , xi ∈ {0,1} .
Phần tử:=

*


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

y1 y2 ... yn thì x ≤ y nếu k ≤ n và

=
Thứ tự bộ phận:
với x x=
1 x2 ...xk , y

∃i1 < i2 < ... < i=
yi1 ,...
=
xk yik .
k : x1
Hàm hạng: Với x = x1 x2 ...xk thì r ( x)= k= dim x .

{x ∈ B : dim x =
k}, P0 =
{∅}.
Mức thứ k : Pk =

=
Bóng
của x x1 x2 ...xk ∈ Pk :
Gọi ∆ j x là vector có được bằng cách bỏ đi x j thì: ∆x = {∆ j x,1 ≤ j ≤ n} .

V. Đoạn, đoạn đầu:

Cho poset có hạng P , trên mức mỗi mức Pk , ta trang bị thêm một thứ tự tuyến tính

" ≤ " , với a, b ∈ Pk , ta định nghĩa:
Đoạn [ a; b] = {x ∈ Pk : a ≤ x ≤ b} , và

{x Pk : x ≤ a}
Đoạn đầu xác định bởi a là: IS (a ) =∈
VI. Thứ tự từ điển:

=
b1b2 ...bn ,ta nói a < b nếu ∃s ∈ ,1 ≤ s ≤ n sao cho:
Cho a a=
1a2 ...an , b

=
at bt , t < s và as < bs .
VII. Sơ lược về lịch sử dẫn đến vấn đề:

n
k 

n
k 

Chúng ta ký hiệu   = Cnk nếu n ≥ k ,và   = 0 nếu n < k .
Từ năm 1928, Sperner đã chứng minh rằng :

n

k 

n 
 A.
−
k
1



Nếu A ⊂ Pk ( S ) với S = {1, 2,..., n}, thì ta có:   ∆A ≥ 
Vấn đề tự nhiên đặt ra là tìm cận dưới lớn nhất của ∆A .


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

Một cách tổng quát, với Pk là mức thứ k của poset có hạng P và m ∈  cho
trước, tìm A ⊂ Pk sao cho A = m và :

∆A= min{ ∆B : B ⊂ Pk , B= m}
Để giải quyết bài tốn này, thường người ta tìm một thứ tự toàn phần trên Pk
mà ta gọi là thứ tự tuyến tính và chứng minh rằng tập A phải tìm gồm m phần tử
đầu tiên của Pk trong thứ tự tuyến tính ấy. Đó là nội dung chủ yếu của định lý
Kruskal-Katona.
Và về sau, Clements – Linstrom đã mở rộng thêm định lý KK cho
poset S ( k1 , k2 ,..., kn ) các tập con của tập đa bội . Nói chung, Clements – Linstrom
đã chứng minh được rằng với thứ tự tuyến tính là thứ tự từ điển thì


S (k1 , k2 ,..., kn ) là một K-poset. Chúng ta khơng đi sâu vào việc tìm hiểu K-poset.
Nói riêng, họ đã chỉ ra rằng bóng của một đoạn đầu xác định bởi phần tử a trong

Sk theo thứ tự từ điển lại là một đoạn đầu trong Sk −1 .
Vấn đề được đặt ra là:
Những đặc trưng nào của một số các tập con của 1 poset thì cịn giữ lại được
qua bóng ?
Luận văn này nhằm giải quyết một phần rất nhỏ của vấn đề trên: Với những
điều kiện nào thì bóng của một đoạn lại là một đoạn trong multiset ?
Để giải quyết vấn đề trên, trước tiên ta hệ thống lại một vài khái niệm và đưa ra
một số ký hiệu như sau:
Cho poset S ( k1 , k2 ,..., kn ) các tập con của tập đa bội n phần tử mà phần tử
thứ i lặp ki lần.


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

Như trên đã đề cập, các tập con có thể đồng nhất với các vector nguyên

x = x1 x2 ...xn mà 0 ≤ xi ≤ ki với mỗi i .
Thứ tự bao hàm của các tập con chuyển sang các vector cho ta thứ tự tự nhiên sau:

=
x x1 x2 ...xn=
≤ y y1 y2 ... yn khi và chỉ khi xi ≤ yi với mọi i .
Khái niệm hạng, mức, bóng của một phần tử, một tập hợp được đinh nghĩa và ký
hiệu như Ví dụ 4.2.
Để giải quyết vấn đề đặt ra, ta trang bị thêm một thứ tự tuyến tính là thứ tự từ điển.

Về sau, ta chủ yếu dùng thứ tự này.
Để tiện lợi cho sư trình bày, trước hết ta cần thống nhất một số ký hiệu:
Với mỗi phần tử a ∈ S k mà tọa độ khác khơng đầu tiên là ai , ta có thể viết:

a = zai u , ở đây z = 0...0 , cịn u = ai+1...an .
Nếu tọa độ khác khơng cuối cùng của a là at thì ta viết: a = vat z .

∆ h a= max{∆ i a}
Đối với các bóng thành phần của a , ta ký hiệu: 
.
l
∆ a= min{∆ i a}
h

a zai u (at − 1) z
∆=
Dễ thấy: nếu a = zai uat z thì 
.
l

∆ a= z (ai − 1)uat z

Đối với số tự nhiên m ≤ k , ta ký hiệu:

hi (m) = max{x = zxi u : x = m, xi ≠ 0}

(m) min{
: x m, xi ≠ 0}
x vxi z=
=

li =
=
h(m) max{x : x ∈ Sm }
.
Nói riêng: 
=
l
m
x
x
∈
S
(
)
min{
:
}
m



Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

Bây giờ, ta xét bóng ∆[a; b] mà a, b có tọa độ khác 0 đầu tiên là như nhau, tức là

a = zai u và b = zai v . Ta phân tích ∆[a; b] thành hai bộ phận được ký hiệu như
sau:
l


{∆ l x : x ∈ [a; b]} =
{z ( ai − 1)u : zai u ∈ [ a; b]}
∆ [a; b] =
 h
l

∆ [a; b] = ∆[a; b] \ ∆ [a; b] = {zai u : zai u ' ∈ ∆[ a; b]}



CHƯƠNG II: BÓNG CỦA ĐOẠN TRONG MULTISET


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

Trước khi xem xét bóng của một đoạn trong multiset, ta xem xét bóng của
một đoạn trong poset các tập con của tập đơn bội, và xem đây là một trường hợp
đặc biệt của poset các tập con của tập đa bội (multiset). Đây được xem là phần
tương đối quan trọng của bài luận văn vì nó cho phép người đọc tiếp cận và làm
quen với những gì cơ bản nhất từ ký hiệu cho đến ý nghĩa của một số kiến thức
phải dùng sau này.
I. Bóng của đoạn trong poset các tập con của tập đơn bội:
1. Từ tập con của tập đơn bội cho đến vector tọa độ:

Cho tập đơn bội S = { p1 , p2 ,..., pn }

Khi đó : A ⊂ S ⇔ (∀pi ∈ A ⇒ pi ∈ S )

Gọi xi là số lần xuất hiện của các pi trong A thì rõ ràng xi ∈ {0,1}.
Từ đó, quan hệ tập con này có thể được chuyển thành quan hệ ước số như sau:
x
x
x
A ⊂ S có thể biểu
diễn thành a p=
=
p1 p2 ... pn
1 p2 ... pn | m
1

0

neáu pi ∉ A

1

neáu pi ∈ A

Với xi = 

Tương tự, lấy

2

n

B ⊂ S , ta cũng biểu diễn thành:


0
yn
y1 y2
với
=
p
p
m
p
p
p
...
|
...
b = b p=
y
=

n
n
1
2
1 2
i
1

neáu pi ∉ B
neáu pi ∈ B

Như vậy, với mỗi tập con tương ứng của S , ta chỉ cần quan tâm đến số lần xuất

hiện của các pi ,hay nói cách khác với mỗi tập con tương ứng của S ta chỉ cần
quan tâm đến mỗi bộ số tương ứng, mà thành phần của nó là số lần xuất hiện của
các pi . Chẳng hạn:
Với

A ⊂ S , ta chú ý đến vector x = x1 x2 ...xn ,

Với

B ⊂ S , ta chú ý đến vector y = y1 y2 ... yn .


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

Lúc này, thay vì dùng các tập con, ta chỉ cần dùng các vector tọa độ như trên.
Chúng ta hãy xem Ví Dụ sau đây để hình dung rõ hơn:
Ví dụ 1.1: Cho tập đơn bội S = {1,2,3,4} .
vector a = 0101 là đại diện của tập con A = {2,4} ,
vector b = 0110 là đại diện cho tập con B = {2,3} ,
vector c = 1011 là đại diện cho tập con C = {1,3,4}

) {=
x x1 x2 ...xn : xi ∈ {0;1}}
Xét vành Bool hữu hạn: B ( n=
Thứ tự bao hàm của các tập con chuyển sang các vector cho ta thứ tự tự nhiên sau:

=
x x1 x2 ...=

xn ≤ y y1 y2 ... yn ⇔ xi ≤ yi , ∀i ∈ {1,2,..., n}
Ta trang bị thêm trên B (n) một thứ tự tuyến tính – thứ tự từ điển.
Với mỗi x ∈ B (n) , hạng của x được ký hiệu và xác định là :

x = x1 + x2 + ... + xn
Hạng của một vector cho ta biết số thành phần khác không của vector đó.

=
Với mỗi phần
tử x x1 x2 ...xn ∈ B ( n) , bóng thứ i của x được ký hiệu và định
nghĩa là:

1
 x1 x2 ...( xi − 1)...xn nếu xi =
∆i x =

nếu xi =
0
∅
Bóng của phần tử x là: ∆x =  ∆ i x
Nếu A ⊂ B (n) thì bóng của A là: ∆A =

 ∆a

a∈A

Với 0 ≤ k ≤ n cho trước, mức hạng k trong B ( n) được định nghĩa là:

B(n; k ) =
{x ∈ B ( n) : x =

k}
Ví Dụ 1.2:


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

B(5;3) = {00111,01011,01101,01110,10011,
10101,10110,11001,11010,11100}
2. Các kết quả chính:

Lấy a = z1i u và
=
b z1 j v ∈ B (n, k ) . So sánh hai chỉ số

i, j xảy ra các trường

hợp sau:
i.

i= j

ii.

i= j + 1

iii.

i > j +1


Trong mỗi trường hợp, ta sẽ nghiên cứu các điều kiện cần và đủ để bóng của một
đoạn là một đoạn.
Trước hết ta cần một vài bổ đề phụ sau:
2.1. Các Bổ Đề:
2.1.1. Bổ đề 1:

IS (∆ b) với ∆ b ∈ B(n; k − 1) .
b z1i u ∈ B(n; k ) thì: ∆IS (b) =
Cho=
h

h

Hay nói cách khác, bóng của một đoạn đầu trong B (n; k ) là một đoạn đầu trong

B(n; k − 1) .
Đây là kết quả quan trọng đã được chứng minh và nó là một trong những trường
hợp đặc biệt của những kết quả tổng quát sau này và mục tiêu của chúng ta là thể
hiện và chứng minh những điều tổng quát đó.
2.1.2 Bổ đề 2:

Lấy=
a z1i u=
, b z1 j v ∈ B (n, k ) : 1 < j ≤ i . Và lấy k là số sao cho: 1 ≤ k < j .
Đặt

 x = z1k z1i u
∈ B(n, k + 1) .Thì ta có:


y
=
z
1
z
1
v
k
j


[ x, y ] ={1k + c : c ∈ [a, b]}

{d − 1k : d ∈ [ x, y ]}
[a, b] =


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

1k + a, y =
1k + b
x =
x 1k , b =−
y 1k
a =−

Lưu ý: Ta ký hiệu: 


Tức là tại vị trí thứ k của a , ta thay xk = 0 thành xk = 1 . Và ngược lại, tại vị trí
thứ k của x , ta thay xk = 1 thành xk = 0 .
Điều này có thể chứng minh một cách dễ dàng.
Chứng minh:

=
c z1t q ( j ≤ t ≤ i ) .
Lấy c ∈ [a; b] thì c có dạng:
c + 1k z1k z1t q
Suy ra: =

∈ B(n; k + 1)

Vì c ∈ [a; b] ⇒ z1i u ≤ z1t q ≤ z1 j v
Suy ra: z1k z1i u ≤ z1k z1t q ≤ z1k z1 j v hay c + 1k ∈ [ x; y ] . Và ngược lại.
Ví dụ 2.1:

=
=
b 001101.
Xét B (6;3) , lấy hai phần
tử a 000111,
Khi đó, ta có: [a; b] = {000111, 001011, 001101}

 x = 12 + a = 010111
∈ B(6;4)
y
1
b
011101

=
+
=
2


Lấy 

Khi đó, [ x; y ] = {010111, 011011, 011101}
Rõ ràng: [ x; y ] ={12 + c : c ∈ [a, b]}

2.1.3. Bổ đề 3:

=
b z1i hi +1 (k − 1) z ∈ B(n; k ) .
=
Cho a z1i zl ( k − 1) , và
∆ hb z1i hi +1 (k − 2) z ∈ B (n; k − 1)
Thì ∆[ a; b] =IS ( ∆ b) với=
h

Chứng minh:


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

=
 g zl (k − 1)

∈ B(n, k − 1)
(
1)
d
zh
k
z
=
−
i +1


Đặt 

Theo bổ đề 1.2, ta có:

∆ l [ a, b] =
A=
IS (d )
{x − 1i : x ∈ [a, b]} =
[g, d ] =
Theo bổ đề 1.1, ta có:

∆A= ∆IS (d ) = IS (∆ h d ) = IS (∆ hb − 1i )
Ta có: ∆ [a, b]= B= { y + 1i : y ∈ ∆A}
h

= [h, ∆ b] , với=
h z1i zl (k − 2) ∈ B(n, k − 1) .
Theo 1.2, ta có: B

h

Ta có: ∆[ a, b] = ∆ [ a, b] ∪ ∆ [ a, b] = A ∪ B = IS ( d ) ∪ [ h, ∆ b]
l

h

h

Mà d , h là 2 phần tử liên tiếp trong B (n, k − 1) nên ∆[ a, b] =IS ( ∆ b) .
h


2.1.4. Bổ đề 4:

=
b z1i hi +1 (k − 1) z ∈ B(n; k ) thì:
Cho a = z1i +1 u , và

∆[a, b] =IS (∆ hb) , với=
∆ hb z1i hi +1 (k − 2) z ∈ B (n; k − 1) .
Chứng minh:

=
d z1i zl (k − 1) ∈ B(n, k )
Lấy
Suy ra [d , b] ⊂ [a, b] (vì a < d < b )

⇒ ∆[d , b] ⊂ ∆[a, b]
⇒ IS (∆ hb) ⊂ ∆[a, b] (theo 1.3) (1)

Hiển nhiên:

[a, b] ⊂ IS (b)
⇒ ∆[a, b] ⊂ ∆IS (b)
hay ∆[a, b] ⊂ IS (∆ hb) (2)


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

Từ (1),(2) suy ra ∆[ a, b] =IS ( ∆ b) .
h


2.1.5. Bổ đề 5:

=
b z1i v ∈ B(n; k ) thì: ∆[a, b] =IS (∆ hb)
Cho a z1i +1 zl (k − 1) , và=
Chứng minh:
Lấy :

=
h z1i +1 hi +2 (k − 1) ∈ B (n, k )
d=
∆hh =
z1i +1 hi +2 (k − 2) ∈ B (n, k − 1)
=
g z1i zl (k − 2) ∈ B(n, k − 1)

Ta có: [ a, h] ⊂ [ a, b] ⇒ ∆[ a, h] ⊂ ∆[ a, b] ⇒ IS ( ∆ h) ⊂ ∆[ a, b]
h

(1)

Hay IS (d ) ⊂ ∆[a, b]

Ta lại có: [ g , ∆ b] ⊂ ∆[a, b]
h

(2)

Từ (1),(2) suy ra: IS (d ) ∪ [ g , ∆ b] ⊂ ∆[a, b]
h

Mà d , g là 2 phần tử liên tiếp trong B (n, k − 1) nên IS (∆ b) ⊂ ∆[ a, b]
h

Hiển nhiên: ∆[ a, b] ⊂ IS ( ∆ b) .
h

Suy ra: ∆[ a, b] =IS ( ∆ b) .
h


 Lưu ý: Các bổ đề trên rất quan trọng trong việc chứng minh các định lý sau:
2.2 Các Định Lý:
2.2.1. Định lý 1:

Cho a = z1i u , và

=
b z1 j v ∈ B (n; k ) sao cho: i > j + 1. Thì ∆[a, b] =IS (∆ b)
h

Chứng minh:


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

Chọn k = j + 1 < i

=
d z1k zl (k − 1) ∈ B(n, k )
Lấy
Ta có: [d , b] ⊂ [a, b]
Suy ra: ∆[d , b] ⊂ ∆[a, b]

IS (∆ b) theo bổ đề 1.5)
hay IS (∆ b) ⊂ ∆[ a, b] (vì ∆[d , b] =
h

h

Hiển nhiên: ∆[ a, b] ⊂ IS ( ∆ b)
h

Suy ra: ∆[ a, b] =IS ( ∆ b)
h



Như vậy, ta đã giải quyết xong trường hợp iii) đã đặt ra ban đầu, tiếp theo ta
khảo sát trường hợp i) qua định lý sau:
2.2.2 Định lý 2:

, b z1i v ∈ B (n; k ) thì
=
a z1i u=
Cho

∆[a; b] là đoạn khi và chỉ khi:

=
 a z11
i i +1 zl ( k − 2)
=
b z1i hi +1 (k − 1) z vaø 
=
 a z1i z1t q (t > i + 1)
Chứng minh:

c= a − 1i
∈ B(n, k − 1)
d
=
b
−
1
i



Lấy 

, b] [c, d ] ∪ {x + 1i : x ∈ ∆[c, d ]}
Ta có: ∆[ a=

g zl (k − 2) ∈ ∆[c, d ] sao cho
Giả sử ∆[a, b] là đoạn thì phải có: =
g=
+ 1i z1i zl (k − 2) ∈ B(n, k − 1) .
Suy ra: d , g + 1i là 2 phần tử liên tiếp trong ∆[a, b]

=
d zhi+1 (k − 1) z .
Vì thế:


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

=
Suy
ra: b z1i hi +1 (k − 1) z .
=
Giả
sử : a z1i z1t q (t ≥ i + 1) , tức là 1t là tọa độ bằng 1 tiếp theo của a sau
1i Ta xét 2 trường hợp của t :
TH 1: t = i + 1

Suy ra: a = z11
i i +1 p

g + 1i z1i zl (k − 2) ∈ ∆[a, b]=
Vì =
nên h z11
i i +1 zl ( k − 2) ∈ [ a, b] .
Suy ra: h ≥ a
Mà h ≤ a nên h = a .

=
Suy ra a z11
i i +1 zl ( k − 2) .
=
a z11
i i +1 zl ( k − 2)

Ngược lại, giả sử : 

=
b z1i hi +1 (k − 1) z

Ta chứng minh ∆[a, b] là đoạn.

] IS (h) ,h= zhi +1 (k − 2) z
Ta có: ∆[ z1i +1 zl (k − 2), zhi +1 (k − 1) z=
[a, b] [ z1i+1 zl (k − 2), zhi+1 (k − 1) z ] ∪ {x + 1i : x ∈ IS (h)}
Ta có: ∆=
Đây là hợp của hai đoạn liên tiếp nên ∆[a, b] là đoạn.
TH 2: t > i + 1


t = i + 2
t > i + 2

Suy ra: 

a = z1i z1i +2 q
- Nếu t = i + 2 , suy ra 
=
b z1i hi +1 (k − 1) z
Áp dụng bổ đề 1.4 cho [a − 1i , b − 1i ]
- Nếu t > i + 2 , áp dụng định lý 1.1 cho [a − 1i , b − 1i ]


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

IS (h)
Cả hai trường hợp này ta đều có: ∆[ a − 1i , b − 1i ] =
] [a − 1i , b − 1i ] ∪ {x + 1i : x ∈ ∆IS (h)}
Ta có: ∆[ a, b=
Là hợp của 2 đoạn liên tiếp nên ∆[a, b] là đoạn.

Như vậy, ta đã giải quyết xong 2 trường hợp i) và iii) đã đặt ra ban đầu. Bây
giờ, cuối cùng ta xét trường hợp ii) :

a = z1i +1 u
∈ B(n, k )
b

=
z
1
v
1
z
i
j


Giả sử 

Có 2 khả năng xảy ra đối với chỉ số

j:

TH 1: j =i + k − 1
Lúc đó dễ dàng thấy =
được: b z1i hi +1 (k − 1) z . Theo bổ đề 1.4, ta có ∆[a, b] là
đoạn.
TH 2: j > i + k − 1
Suy ra b < z1i hi +1 ( k − 1) z .
Trong trường hợp này, ta lưu ý 2 khả năng của a :

=
- Nếu a z1i +1 zl (k − 1) : theo bổ đề 1.5, suy ra ∆[a, b] là đoạn.
- Nếu a > z1i +1 zl (k − 1) :
Lúc này, đối với các chỉ số của vector b , ta đặt:

=

s min{t=
yi+t −1 0}
: yi+t 1,=
Tức yi + s là tọa độ bằng 1 đầu tiên của b không liên tiếp sau 1i .
Ta có thể biểu diễn b như sau:

b

z11
i i +1...1i + p z1i + s q

 Lưu ý:

( p + 1 < s)


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

1i + p là tọa độ bằng 1 cuối cùng của b trong chuỗi liên tiếp các tọa độ bằng 1 sau 1i .
Và rõ ràng, 1i + p là số 1 thứ ( p + 1) kể từ 1i .
Gọi 1l là số 1 thứ ( p + 1) trong số các tọa độ bằng 1 của a kể từ 1i+1 .
Gọi 1m là số 1 thứ ( p + 2) trong số các tọa độ bằng 1 của a kể từ 1i+1 .
Tức là 1l và 1m là 2 số 1 liên tiếp trong tất cả các thành phần bằng 1 của a sau 1i+1 .
Ta có thể biểu diễn a như sau:

a = z1i+1 u1l z1m v
Ta có định lý quan trọng sau, và tất nhiên định lý đang áp dụng với trường hợp 2
đang xét.

2.2.3. Định lý 3:

a = z1i +1 u1l z1m v
∈ B (n; k ) . Với s, m, l được định nghĩa như trên.
=
b
z
z
q
11
...1
1
i i +1
i+ p
i+s


Cho 

Nếu l > i + p + 1 thì ∆[a; b] là đoạn.
Nếu l =i + p + 1 thì ∆[a; b] là đoạn khi và chỉ khi:

a ' = z1m v
a' là trội trực tiếp của b'
∈ B(n; k − p − 1)
vớ
i

b ' ≥ a '
=

b
z
q
'
1

i+s

Và

m > i + p + 2
 m =i + p + 2, zv =zl (k − p − 2) tức a =z1 1 ...1 1
i +1 i + 2
i + p +1 i + p + 2 zl ( k − p − 2)

Chứng minh:

c= a − 1i +1
∈ B(n, k − 1) .
=
−
d
b
1
i


Đặt 



Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

=
Và h z1i +1 hi + 2 (k − 1) z ∈ B (n, k )
] [a, h] ∪ {x + 1i : x ∈ IS (d )}
Ta có: [ a, b=
∆[a, h] ∪ ∆({x + 1i : x ∈ IS (d )}) =
∆[a, h] ∪ IS (d ) ∪ X
Suy ra: ∆[ a, b] =
Với X= { y + 1i : y ∈ ∆IS (d )}
Ta có: IS ( d ), X là các đoạn

max ∆[a, h] =
zhi +1 (k − 1) z
∆hh =
là 2 phần tử liên tiếp trong
Mặt khác: 
X z1i zl (k − 2)
=
min

B(n, k − 1) .
Nên để chứng minh ∆[a, b] là đoạn, ta chứng minh ∆[a, h] ∪ IS (d ) là đoạn.
Ta xét 2 trường hợp:
TH 1: l > i + p + 1
Suy ra g z1i +1...1i + p +1 zl (k − p − 1) ∈ [a, h]
=


(*)

=

 g ' z1i + p+1 zl (k − p − 1)
Chọn 
∈ B ( n, k − p )
'
(
)
h
zh
k
p
z
=
−

i + p +1

Suy ra: ∆[ g ', h '] là đoạn đầu (theo bổ đề 1.3)
Suy

ra: Y= {x + 1i + p + 1i + p −1 + ... + 1i +1 : x ∈ ∆[ g ', h ']} là

1

B(n, k − 1) (theo bổ đề 1.2)
Theo cách đặt, ta có:


d = z1i +1...1i + p z1i + s q
Ta có: zl ( k − p − 1) ≤ z1i + s q ≤ zhi + p +1 (k − p − 1) z (vì s > p + 1 )
Suy ra : z1i + s q ∈ ∆[ g ', h '] , nên d ∈ Y .
Suy ra : IS (d ) ∪ Y là một đoạn trong B (n, k − 1) (1)

đoạn

trong


Bóng của đoạn trong Multiset

Luận văn tốt nghiệp đại học

Ta lưu ý:
Từ (*), suy ra: [a, h] = [a, g ] ∪ [ g , h] ⇒ ∆[a, h] = ∆[a, g ] ∪ ∆[ g , h]
Ta có: Y ⊂ ∆[ g , h] ⇒ Y ⊂ ∆[a, h]
Suy ra: IS (d ) ∪ Y ⊂ IS (d ) ∪ ∆[a, h] .
Ngược lại, lấy x ∈ IS (d ) ∪ ∆[a, h]

max Y
Suy ra: min IS ( d ) ≤ x ≤ max ∆[a, h] =
⇒ x ∈ IS (d ) ∪ Y ⇒ IS (d ) ∪ ∆[a, h] ⊂ IS (d ) ∪ Y
a, h] IS (d ) ∪ Y
Nên IS (d ) ∪ ∆[=

(2)

Từ (1),(2), suy ra IS (d ) ∪ ∆[a, h] là đoạn.
TH 2: l =i + p + 1

- Nếu p = 0
Suy ra l = i + 1 , ta biểu diễn lại:

a = z1i +1 z1m v

=
b z1i z1i + s q

( s ≥ 2)

h] [c, h − 1i+1 ] ∪ { y + 1i+1 : y ∈ ∆[c, h − 1i+1 ]}
Ta có: ∆[ a,=
d z1i+ s q ≤ h − 1=
zhi+2 (k − 1) z (vì s ≥ 2 )
Ta có:=
i +1
Vì thế, IS (d ) ∪ ∆[a, h] là đoạn khi và chỉ khi:

 d trước c
và ∆[a, h] là 1 đoạn.
d ≥ c

=
 a z1i +11i +2 zl (k − 2)
=
 a z1i +1 z1m v (m > i + 2)

Điều kiện thứ hai tương đương: 
- Nếu p > 0 :