ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC KHOA HỌC

NGUYỄN VĂN DIỄN

PHÉP PHÂN HOẠCH TẬP HOWPJVAF MỘT SỐ ỨNG DỤNG TRONG TOÁN SƠ CẤP

THÁI NGUYÊN 2015

Môc lôc

Muc luc . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

Lêi nãi ®Çu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1 PhÐp ph©n ho¹ch tËp hîp 5

1.1 PhÐp ph©n hoach tËp hîp vµ quan hÖ t−¬ng ®−¬ng . . . . . 5

1.2 Sè Bell vµ sè Stirling lo¹i hai . . . . . . . . . . . . . . . . 10

1.3 Mét sè c«ng thøc tÝnh hµm ph©n ho¹ch tËp hîp . . . . . . 18

2 Mét sè øng dông trong to¸n s¬ cÊp 22

2.1 Ph©n ho¹ch ch½n, lÎ vµ øng dông trong to¸n s¬ cÊp . . . . 22

2.2 Mét sè øng dông gi¶i to¸n tæ hîp vµ h×nh häc s¬ cÊp . . . 27

2.3 Ph©n hoach sè vµ øng dông trong to¸n s¬ cÊp . . . . . . . 32

KÕt luËn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

1

Tµi liÖu tham kh¶o . . . . . . . . . . . . . . . . . . . . . . . . 39

2

Lêi c¶m ¬n

Tr−íc hÕt, t«i xin göi lêi biÕt ¬n ch©n thµnh vµ s©u s¾c nhÊt ®Õn PGS.TS

Lª ThÞ Thanh Nhµn ®• gióp t«i hoµn thµnh b¶n luËn v¨n nµy. Khi b¾t ®Çu

nhËn ®Ò tµi thùc sù t«i c¶m nhËn ®Ò tµi mang nhiÒu néi dung míi mÎ. H¬n

n÷a víi vèn kiÕn thøc Ýt ái cïng víi kinh nghiÖm lµm ®Ò tµi lín kh«ng

nhiÒu nªn t«i ch−a thùc sù tù tin ®Ó tiÕp cËn ®Ò tµi. MÆc dï rÊt bËn rén

trong c«ng viÖc nh−ng C« vÉn dµnh nhiÒu thêi gian vµ t©m huyÕt trong viÖc

h−íng dÉn, ®éng viªn khuyÕn khÝch t«i trong suèt thêi gian t«i thùc hiÖn

®Ò tµi. Trong qu¸ tr×nh tiÕp cËn ®Ò tµi ®Õn qu¸ tr×nh hoµn thiÖn luËn v¨n

C« lu©n tËn t×nh chØ b¶o vµ t¹o ®iÒu kiÖn tèt nhÊt cho t«i. Cho ®Õn b©y giê

luËn v¨n th¹c sÜ cña t«i ®• ®−îc hoµn thµnh, xin c¶m ¬n C« ®• ®«n ®èc

nh¾c nhë vµ gióp ®ì t«i hÕt m×nh.

T«i xin tr©n träng c¶m ¬n Ban Gi¸m hiÖu, Khoa to¸n-Tin vµ phßng §µo

t¹o cña tr−êng §¹i häc Khoa häc-§¹i häc Th¸i Nguyªn. T«i xin tr©n träng

c¶m ¬n c¸c ThÇy, C« ®• tËn t×nh truyÒn ®¹t nh÷ng kiÕn thøc quÝ b¸u còng

nh− t¹o mäi ®iÒu kiÖn thuËn lîi nhÊt ®Ó t«i hoµn thµnh luËn v¨n nµy.

Cuèi cïng, t«i xin ch©n thµnh bµy tá lßng biÕt ¬n ®Õn gia ®×nh, b¹n bÌ,

nh÷ng ng−êi ®• kh«ng ngõng ®éng viªn, hç trî t¹o mäi ®iÒu kiÖn cho t«i.

V× n¨ng lùc b¶n th©n còng nh− thêi gian cßn h¹n chÕ, luËn v¨n ch¾c ch¾n

kh«ng thÓ tr¸nh khái nh÷ng sai sãt. T¸c gi¶ rÊt mong nhËn ®−îc sù ®ãng

gãp ý kiÕn nhËn xÐt cña ThÇy, C« ®Ó b¶n luËn v¨n ®−îc hoµn thiÖn h¬n.

Nam §Þnh, ngµy 15, th¸ng 4, n¨m 2015

Häc viªn

NguyÔn V¨n DiÔn

3

Lêi nãi ®Çu

LÝ thuyÕt ph©n ho¹ch tËp hîp cã mét lÞch sö l©u dµi (®−îc quan t©m tõ

ThÕ kØ 19), cho ®Õn nay ®©y vÉn lµ mét chñ ®Ò nghiªn cøu rÊt hÊp dÉn vµ

thêi sù. LÝ thuyÕt ph©n ho¹ch tËp hîp ®ãng vai trß quan träng trong nhiÒu

lÜnh vùc kh¸c nhau cña to¸n häc nh− Tæ hîp, LÝ thuyÕt Lie, LÝ thuyÕt biÓu

diÔn, To¸n vËt lÝ, LÝ thuyÕt c¸c hµm ®Æc biÖt . . . . V× tÇm quan träng cña

nã trong nh÷ng øng dông kh¸c nhau, c¸c nhµ to¸n häc ®• nç lùc t×m c«ng

thøc tÝnh sè ph©n ho¹ch mét tËp hîp. Mét trong sè nh÷ng c«ng thøc tÝnh sè

ph©n ho¹ch ®Çu tiªn thuéc vÒ Bell trong mét bµi b¸o trªn t¹p chÝ næi tiÕng

Annals of Mathematics n¨m 1934 vµ tiÕp tôc ph¸t triÓn trong mét bµi b¸o

kh¸c trªn Annals of Mathematics c«ng bè n¨m 1938. Sè phÐp ph©n ho¹ch

trªn mét tËp hîp n phÇn tö ®−îc gäi lµ sè Bell thø n ®Ó ghi nhËn ®ãng gãp

to lín cña nhµ to¸n häc tªn tuæi Eric Temple Bell (1883-1960), sè nµy ®−îc

kÝ hiÖu lµ Bn. NhiÒu c«ng thøc kh¸c ®Ó tÝnh sè ph©n ho¹ch tËp hîp n phÇn tö nh− c«ng thøc ®−îc ®−a ra bëi G. C. Rota trong bµi b¸o “The Number

of Partitions of a Set” trªn Amer. Math. Monthly n¨m 1964, c«ng thøc

cña W. F. Lunnon, P. Pleasants, M. N. Stephens trong bµi b¸o “Arithmetic

Properties of Bell Numbers to a Composite Modulus” trªn Acta Arith. n¨m

1979, . . . . Ngµy nay viÖc nghiªn cøu sè Bell vÉn rÊt ®−îc quan t©m, thÓ

hiÖn trong c«ng tr×nh n¨m 2013 cña E. D. Knuth tæng kÕt 2000 n¨m vÒ to¸n

Tæ hîp (xem [K]), cña D. Berend vµ T. Tassa n¨m 2010 (xem [BT]), cña D.

Callan n¨m 2006 (xem [Ca]), . . ..

Môc ®Ých cña luËn v¨n lµ nghiªn cøu lÝ thuyÕt ph©n ho¹ch tËp hîp, mét

sè c«ng thøc tÝnh sè Bell Bn vµ øng dông ®Ó gi¶i mét sè d¹ng to¸n s¬ cÊp, ®Æc biÖt lµ to¸n tæ hîp.

LuËn v¨n gåm 2 ch−¬ng. Trong Ch−¬ng 1, tr−íc hÕt chóng t«i tr×nh bµy

4

kh¸i niÖm phÐp ph©n ho¹ch tËp hîp, chØ ra sù liªn quan chÆt chÏ gi÷a phÐp

ph©n ho¹ch tËp hîp vµ quan hÖ t−¬ng ®−¬ng trªn cïng mét tËp hîp. TiÕt 1.2

dµnh ®Ó chøng minh mét sè c«ng thøc tÝnh sè ph©n ho¹ch, sè Stirling lo¹i

2 vµ ®−a ra mét sè c«ng thøc truy håi ®Ó tÝnh sè Bell. Ch−¬ng nµy còng

giíi thiÖu vÒ tam gi¸c Bell, ®ã lµ thµnh qu¶ cña viÖc tÝnh to¸n dùa trªn c¸c

c«ng thøc cã ®−îc. Trong Ch−¬ng 2, chóng t«i tr×nh bµy mét sè øng dông

cña lÝ thuyÕt ph©n ho¹ch trong viÖc gi¶i mét sè d¹ng to¸n s¬ cÊp, ®Æc biÖt

lµ ®èi víi nh÷ng bµi to¸n trong ®¹i sè tæ hîp hay h×nh häc s¬ cÊp. Chóng

t«i còng ®−a ra lêi gi¶i mét sè bµi to¸n liªn quan ®Õn nghiÖm cña ph−¬ng

tr×nh, tÝnh x¸c suÊt cña biÕn cè hay bµi to¸n ph©n ho¹ch cña tËp hîp sè,

®Æc biÖt lµ nh÷ng bµi to¸n ph©n ho¹ch ®a gi¸c thµnh nh÷ng tam gi¸c trong

h×nh häc s¬ cÊp.

Ch−¬ng 1

PhÐp ph©n ho¹ch tËp hîp

Môc tiªu cña Ch−¬ng 1 lµ tr×nh bµy kh¸i niÖm ph©n ho¹ch tËp hîp, mèi

quan hÖ gi÷a ph©n ho¹ch tËp hîp vµ quan hÖ t−¬ng ®−¬ng, tÝnh chÊt c¬ së

cña sè Bell vµ chøng minh mét sè c«ng thøc tÝnh sè Bell, tøc lµ c«ng thøc

tÝnh hµm ph©n ho¹ch tËp hîp.

1.1 PhÐp ph©n hoach tËp hîp vµ quan hÖ t−¬ng ®−¬ng

Trong suèt tiÕt nµy lu«n gi¶ thiÕt X lµ mét tËp hîp kh¸c rçng. Môc tiªu

cña tiÕt nµy lµ giíi thiÖu kh¸i niÖm phÐp ph©n ho¹ch tËp hîp vµ mèi liªn

hÖ gi÷a c¸c phÐp ph©n ho¹ch cña tËp X víi c¸c quan hÖ t−¬ng ®−¬ng trªn

tËp X.

1.1.1 §Þnh nghÜa. Ta gäi mét phÐp ph©n ho¹ch tËp X (hay mét sù chia líp trªn X) lµ mét c¸ch chia X thµnh mét hä c¸c tËp con kh¸c rçng {Xi}i∈I sao cho Xi ∩ Xj = ∅ víi mäi i, j ∈ I, i 6= j vµ X = S Xi. NÕu {Xi}i∈I lµ i∈I mét ph©n ho¹ch tËp X th× mçi tËp con Xi ®−îc gäi lµ mét khèi cña ph©n ho¹ch; nÕu I gåm k phÇn tö th× ta nãi ph©n ho¹ch ®ã gåm k khèi.

1.1.2 VÝ dô. (i) NÕu X = {a} th× X cã ®óng mét ph©n ho¹ch, ®ã lµ ph©n

5

ho¹ch thµnh mét khèi X.

6

(ii) NÕu X = {a, b} th× X cã hai ph©n ho¹ch, ph©n ho¹ch thø nhÊt thµnh

mét khèi X; ph©n ho¹ch thø hai gåm hai khèi {a}, {b}.

(iii) NÕu X = {a, b, c} th× cã 5 phÐp ph©n ho¹ch tËp X, ®ã lµ

{{a}, {b}, {c}}; {{a, b}, {c}}; {{a, c}, {b}}; {{b, c}, {a}}; {{a, b, c}},

trong ®ã cã mét ph©n ho¹ch thµnh 1 khèi, ba ph©n ho¹ch thµnh 2 khèi, vµ

mét ph©n ho¹ch thµnh 3 khèi.

(iv) NÕu X = {a, b, c, d} th× cã 15 phÐp ph©n ho¹ch tËp X, ®ã lµ

{{a, d}, {b}, {c}}; {{a, b}, {c}, {d}}; {{a, c}, {b}, {d}}

{{b, c}, {a}, {d}}; {{b, d}, {a}, {c}}; {{c, d}, {a}, {b}}

{{a, b, c}, {d}}; {{a, b, d}, {c}}; {{a, c, d}, {b}}

{{b, c, d}, {a}}; {{a, b}, {c, d}}; {{a, c}, {b, d}}

{{a, d}, {b, c}; {a, b, c, d}; {abcd}.

Cô thÓ:

TËp hîp gåm 4 phÇn tö cã 1 ph©n ho¹ch thµnh 1 khèi lµ {abcd}

TËp hîp gåm 4 phÇn tö cã 1 ph©n ho¹ch thµnh 4 khèi lµ {a, b, c, d}

TËp hîp gåm 4 phÇn tö cã 7 ph©n ho¹ch thµnh 2 khèi lµ

{{a, b, c}, {d}}; {{a, b, d}, {c}}; {{a, c, d}, {b}}; {{b, c, d}, {a}};

{{a, b}, {c, d}}; {{a, c}, {b, d}}; {{a, d}, {b, c}}

TËp hîp gåm 4 phÇn tö cã 6 ph©n ho¹ch thµnh 3 khèi lµ

{{a, d}, {b}, {c}}; {{a, b}, {c}, {d}}; {{a, c}, {b}, {d}};

{{b, c}, {a}, {d}}; {{b, d}, {a}, {c}}; {{c, d}, {a}, {b}}

1.1.3 VÝ dô. Chó ý r»ng ph©n ho¹ch kh«ng phô thuéc vµo thø tù cña c¸c

khèi. Ch¼ng h¹n, trong VÝ dô 1.1.2(iii) víi X = {a, b, c}, phÐp ph©n

ho¹ch {{a}, {b}, {c}} vµ {{b}, {a}, {c}} lµ nh− nhau; phÐp ph©n ho¹ch

{{a, c}, {b}} vµ {{b}, {a, c}} lµ nh− nhau.

7

Thùc tÕ, cã nhiÒu bµi to¸n ®−îc quy vÒ bµi to¸n ph©n ho¹ch tËp hîp nh−

c¸c bµi to¸n vÒ x¸c xuÊt thèng kª, vÒ tæ hîp ®å thÞ, . . . .

1.1.4 VÝ dô. Cho Ω lµ kh«ng gian mÉu cña mét phÐp thö nµo ®ã. Khi ®ã

hÖ biÕn cè gåm n biÕn cè A1, A2, A3, . . . , An ®−îc gäi lµ 1 ph©n ho¹ch cña kh«ng gian mÉu Ω nÕu Ai ∩ Aj = ∅, víi mäi i, j = 1, 2, 3 . . . n vµ A1 ∪ A2 ∪ A3 ∪ . . . ∪ An = Ω. HÖ biÕn cè trªn cßn ®−îc gäi lµ hÖ ®Çy ®ñ vµ ®«i mét xung kh¾c víi nhau. Khi ®ã víi B lµ mét biÕn cè bÊt k× trong

phÐp thö, ta cã c«ng thøc ®Çy ®ñ vµ c«ng thøc Bayes nh− sau:

(i) P (B) = P (A1)P (B/A1) + P (A2)P (B/A2) + . . . + P (An)P (B/An)

. (ii) P (Ai/B) = P (Ai)P (B/Ai) P (B)

TiÕp theo, chóng ta tr×nh bµy mèi quan hÖ gi÷a c¸c phÐp ph©n ho¹ch tËp

X víi c¸c quan hÖ t−¬ng ®−¬ng trªn X. Nh¾c l¹i r»ng mét tËp con kh¸c

rçng cña tÝch Descartes X × X ®−îc gäi lµ mét quan hÖ (hai ng«i) trªn X.

Ta th−êng kÝ hiÖu c¸c quan hÖ b»ng c¸c ch÷ R, S, T, Ω, . . . hoÆc c¸c kÝ hiÖu ∼, 6, ≥, . . .. Cho Ω lµ mét quan hÖ hai ng«i trªn X. NÕu (a, b) ∈ Ω th× ta viÕt lµ aΩb vµ ta nãi a quan hÖ víi b (theo quan hÖ Ω). D−íi ®©y lµ mét sè

tÝnh chÊt quan träng mµ mét quan hÖ Ω cã thÓ cã

(i) Ph¶n x¹: aΩa víi mäi a ∈ X.

(ii) §èi xøng: NÕu aΩb th× bΩa víi mäi a, b ∈ X.

(iii) Ph¶n ®èi xøng: NÕu aΩb vµ bΩa th× a = b víi mäi a, b ∈ X.

(iv) B¾c cÇu: NÕu aΩb vµ bΩc th× aΩc víi mäi a, b, c ∈ X. Ch¼ng h¹n, víi

X = {1, 2, 3, 4}, quan hÖ chia hÕt

Ω = {(a, b) ∈ X × X | a lµ −íc cña b}

cã c¸c tÝnh chÊt ph¶n x¹, ph¶n ®èi xøng vµ b¾c cÇu. Ta còng viÕt quan hÖ

chia hÕt nµy b»ng c¸ch chØ ra mét thuéc tÝnh ®Æc tr−ng nh− sau: aΩb nÕu

vµ chØ nÕu a lµ −íc cña b víi mäi a, b ∈ X. Ta còng cã thÓ viÕt quan hÖ

8

nµy b»ng c¸ch liÖt kª nh− sau

Ω = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)}.

1.1.5 §Þnh nghÜa. Mét quan hÖ trªn X ®−îc gäi lµ quan hÖ t−¬ng ®−¬ng

nÕu nã ph¶n x¹, ®èi xøng vµ b¾c cÇu.

Theo truyÒn thèng, quan hÖ t−¬ng ®−¬ng th−êng ®−îc kÝ hiÖu bëi ∼ .

Gi¶ sö ∼ lµ quan hÖ t−¬ng ®−¬ng trªn X. Víi mçi a ∈ X, ta gäi líp t−¬ng

®−¬ng cña a, kÝ hiÖu bëi cl(a) (hay a, hoÆc [a]) lµ tËp c¸c phÇn tö cña X

quan hÖ víi a, tøc lµ

cl(a) = {b ∈ X | b ∼ a}.

TËp c¸c líp t−¬ng ®−¬ng ®−îc gäi lµ tËp th−¬ng cña X theo quan hÖ t−¬ng

®−¬ng ∼ vµ ®−îc kÝ hiÖu bëi X/ ∼ . Nh− vËy

X/ ∼ = {cl(a) | a ∈ X}.

Chó ý r»ng a ∼ b khi vµ chØ khi cl(a) = cl(b) víi mäi a, b ∈ X. ThËt vËy,

gi¶ sö a ∼ b. Cho x ∈ cl(a), tøc lµ x ∼ a. Do ∼ cã tÝnh b¾c cÇu nªn x ∼ b.

V× thÕ x ∈ cl(b). Do ®ã cl(a) ⊆ cl(b). T−¬ng tù, cl(b) ⊆ cl(a). Ng−îc l¹i,

gi¶ sö cl(a) = cl(b). Do ∼ cã tÝnh ph¶n x¹ nªn a ∈ cl(a). V× thÕ a ∈ cl(b),

tøc lµ a ∼ b.

1.1.6 VÝ dô. Cho m ≥ 1 lµ mét sè tù nhiªn. Ta ®Þnh nghÜa quan hÖ ≡ (mod m) trªn Z nh− sau: víi mäi a, b ∈ Z, a ≡ b (mod m) khi vµ chØ khi a − b lµ béi cña m. Quan hÖ nµy ®−îc gäi lµ quan hÖ ®ång d− theo

m«®un m. Quan hÖ nµy lµ ph¶n x¹, ®èi xøng vµ b¾c cÇu vµ kh«ng ph¶n xøng. Do ®ã nã lµ quan hÖ t−¬ng ®−¬ng trªn Z. NÕu a ≡ b (mod m) th× ta ®äc lµ a ®ång d− víi b theo m«®un m. Víi mçi a ∈ Z, líp t−¬ng ®−¬ng cña a th−êng ®−îc kÝ hiÖu bëi a vµ gäi lµ líp thÆng d− theo m«®un m víi

9

®¹i diÖn lµ a. TËp th−¬ng cña Z theo quan hÖ nµy ®−îc kÝ hiÖu bëi Zm vµ ®−îc gäi lµ tËp c¸c líp thÆng d− theo m«®un m hay tËp c¸c sè nguyªn mo®unl« m. Cho a ∈ Z. ViÕt a = mq + r víi 0 6 r 6 m − 1. Khi ®ã a − r lµ béi cña m, tøc lµ a ≡ r (mod m). Suy ra a = r. H¬n n÷a, nÕu r 6= s lµ c¸c sè tù nhiªn sao cho r, s 6 m − 1 th× r − s kh«ng lµ béi cña m. Do ®ã r 6= s. VËy tËp th−¬ng Zm gåm ®óng m phÇn tö, ®ã lµ 0, 1, . . . , m − 1.

1.1.7 MÖnh ®Ò. Cho ∼ lµ quan hÖ t−¬ng ®−¬ng trªn X. Khi ®ã.

cl(a);

(i) cl(a) 6= ∅ víi mäi a ∈ X; (ii) X = S a∈X (iii) NÕu cl(a) 6= cl(b) th× cl(a) ∩ cl(b) = ∅ víi mäi a, b ∈ X.

cl(a).

Chøng minh. (i), (ii). Víi mçi a ∈ X, do tÝnh ph¶n x¹ nªn ta lu«n cã a ∼ a. V× thÕ a ∈ cl(a). Do ®ã cl(a) 6= ∅ vµ X = S a∈X (iii). Gi¶ sö cl(a) ∩ cl(b) 6= ∅. Chän c ∈ cl(a) ∩ cl(b). Ta cã a ∼ c vµ

c ∼ b. Gi¶ sö x ∈ cl(a). Khi ®ã x ∼ a. Do tÝnh chÊt b¾c cÇu ta cã x ∼ b.

V× thÕ x ∈ cl(b). Suy ra cl(a) ⊆ cl(b). T−¬ng tù, cl(a) ⊇ cl(b). Do ®ã

cl(a) = cl(b).

§Þnh lÝ sau ®©y lµ kÕt qu¶ chÝnh cña tiÕt nµy, cho ta mèi quan hÖ gi÷a

c¸c phÐp ph©n ho¹ch víi c¸c quan hÖ t−¬ng ®−¬ng.

1.1.8 §Þnh lý. NÕu ∼ lµ mét quan hÖ t−¬ng ®−¬ng trªn X th× tËp c¸c líp

t−¬ng ®−¬ng X/ ∼ = {cl(a) | a ∈ X} lµ mét ph©n ho¹ch cña X. Ng−îc l¹i, nÕu {Xi}i∈I lµ mét phÐp ph©n hoach tËp X th× tån t¹i duy nhÊt mét quan hÖ t−¬ng ®−¬ng trªn X sao cho mçi Xi lµ mét líp t−¬ng ®−¬ng.

Chøng minh. Gi¶ sö ∼ lµ mét quan hÖ t−¬ng ®−¬ng trªn X. Theo MÖnh

®Ò 1.1.7, tËp X/ ∼ c¸c líp t−¬ng ®−¬ng cña X theo quan hÖ t−¬ng ®−¬ng ∼ lµm thµnh mét phÐp ph©n ho¹ch trªn X. Ng−îc l¹i, gi¶ sö {Xi}i∈I lµ

10

mét ph©n ho¹ch tËp X. §Þnh nghÜa quan hÖ Ω trªn X nh− sau: víi mäi a, b ∈ X, aΩb khi vµ chØ khi tån t¹i i ∈ I ®Ó a, b ∈ Xi. DÔ thÊy Ω lµ quan hÖ t−¬ng ®−¬ng vµ mçi Xi lµ mét líp t−¬ng ®−¬ng. Gi¶ sö S lµ quan hÖ t−¬ng ®−¬ng trªn X còng cã tÝnh chÊt mçi Xi lµ mét líp t−¬ng ®−¬ng. Cho (a, b) ∈ Ω. Khi ®ã tån t¹i i ∈ I ®Ó a, b ∈ Xi. Theo gi¶ thiÕt vÒ S, tån t¹i c ∈ X sao cho Xi = cl(c)S, trong ®ã ta kÝ hiÖu cl(c)S lµ líp t−¬ng ®−¬ng cña phÇn tö c theo quan hÖ t−¬ng ®−¬ng S. Do a, b ∈ Xi = cl(c)S nªn aSc vµ bSc. Do tÝnh ®èi xøng cña S ta cã aSc vµ cSb. V× S b¾c cÇu

nªn aSb, hay (a, b) ∈ S. VËy Ω ⊆ S. Cho (a, b) ∈ S. Khi ®ã ∃i ∈ I ®Ó cl(a)S = Xi. V× aSb nªn b ∈ cl(a)S = Xi, vµ v× aSa nªn a ∈ cl(a)S = Xi. Suy ra a, b ∈ Xi. Do ®ã aΩb hay (a, b) ∈ Ω. VËy Ω = S.

1.1.9 HÖ qu¶. Gi¶ sö X lµ tËp h÷u h¹n. Khi ®ã sè ph©n ho¹ch tËp X chÝnh

lµ sè quan hÖ t−¬ng ®−¬ng trªn X.

Chøng minh. Theo §Þnh lÝ 1.1.8, ¸nh x¹ cho øng mçi quan hÖ t−¬ng ®−¬ng

Ω trªn X víi phÐp ph©n ho¹ch gåm c¸c líp t−¬ng ®−¬ng cña X theo Ω, lµ

mét song ¸nh.

1.2 Sè Bell vµ sè Stirling lo¹i hai

1.2.1 §Þnh nghÜa. Sè phÐp ph©n ho¹ch tËp hîp n phÇn tö ®−îc gäi lµ sè

Bell thø n vµ ®−îc kÝ hiÖu lµ Bn.

Theo §Þnh lÝ 1.1.8, sè Bell thø n chÝnh lµ sè quan hÖ t−¬ng ®−¬ng trªn

tËp n phÇn tö. Ta quy −íc sè Bell thø 0 lµ 1, tøc lµ B0 = 1. Theo VÝ dô 1.1.2, c¸c sè Bell thø 1, 2, 3, 4 lÇn l−ît lµ B1 = 1, B2 = 2, B3 = 5, B4 = 15. Mét sè sè Bell ®Çu tiªn trong d•y c¸c sè Bell lµ

B0 = 1, B1 = 1, B2 = 2, B3 = 5, B4 = 15, B5 = 52, B6 = 203, B7 = 877,

B8 = 4140, B9 = 21147, B10 = 115975.

11

§Ó tÝnh sè Bell, tøc lµ sè ph©n ho¹ch tËp hîp X gåm n phÇn tö, chóng ta

cÇn tÝnh sè ph©n hoach tËp X thµnh k khèi víi k = 1, . . . , n. C¸c sè nµy

®−îc gäi lµ sè Stirling läai hai.

1.2.2 §Þnh nghÜa. Cho X lµ tËp cã n phÇn tö. Sè ph©n ho¹ch tËp X thµnh

k khèi ®−îc gäi lµ sè Stirling lo¹i hai vµ ®−îc kÝ hiÖu lµ S(n, k).

1.2.3 VÝ dô. B»ng ph−¬ng ph¸p liÖt kª ta t×m ®−îc sè ph©n ho¹ch tËp hîp

gåm 4 phÇn tö thµnh 3 khèi lµ S(4, 3). Sè ph©n ho¹ch tËp hîp gåm 5 phÇn

tö thµnh 4 khèi lµ S(5, 4) = 10. §Æc biÖt, sè ph©n ho¹ch cña tËp hîp rçng

thµnh 0 khèi lµ 1, sè ph©n ho¹ch tËp hîp kh¸c rçng thµnh 1 khèi lu«n b»ng

1. Sau nµy ta x©y dùng ®−îc sè ph©n ho¹ch thµnh k khèi cña tËp hîp gåm

n phÇn tö bÊt k×, ch¼ng h¹n S(10, 4) = 34105, S(10, 5) = 42525.

C¸c sè Stirling lo¹i hai xuÊt hiÖn nhiÒu trong c¸c bµi to¸n tæ hîp vµ cã

øng dông trong To¸n thèng kª. Ng−êi ta cã thÓ sö dông phÇn mÒm Maple

®Ó tÝnh c¸c sè Stirling lo¹i hai. Sè Stirling lo¹i hai d−îc ®Æt theo tªn cña

nhµ to¸n häc James Stirling (1692-1770), ng−êi ®• giíi thiÖu vµ nghiªn cøu

kh¸i niÖm nµy vµo ThÕ kØ 18. Chó ý r»ng nÕu {X1, . . . , Xk} lµ mét ph©n ho¹ch cña tËp X thµnh k khèi th× 1 6 k 6 n, trong ®ã n > 0 lµ sè phÇn tö cña X. V× thÕ ta cã c«ng thøc tÝnh sè Bell th«ng qua sè Stirling lo¹i hai

nh− sau.

1.2.4 Bæ ®Ò. Bn = S(n, 1) + . . . + S(n, n − 1) + S(n, n).

1.2.5 VÝ dô. §Ó tÝnh B5, theo Bæ ®Ò 1.2.4 ta cÇn tÝnh S(5, k) víi k = 1, 2, 3, 4, 5. Ta cã S(5, 1) = 1, S(5, 2) = 15, S(5, 3) = 25, S(5, 4) = 10,

S(5, 5) = 1. Do ®ã

B5 = S(5, 0) + S(5, 1) + S(5, 2) + S(5, 3) + S(5, 4) + S(5, 5) = 52.

12

Tõ Bæ ®Ò 1.2.4 ta thÊy r»ng c¸c sè Stirling lo¹i hai rÊt quan träng trong

viÖc tÝnh to¸n sè Bell. Do ®ã trong phÇn tiÕp theo cña tiÕt nµy chóng ta

nghiªn cøu mét sè tÝnh chÊt vÒ sè Stirling lo¹i hai.

KÕt qu¶ sau ®©y cho ta mét sè c«ng thøc tÝnh sè Stirling lo¹i hai. Víi

n =

n lµ hÖ sè nhÞ thøc thø

. Ta gäi Ck k ∈ {0, 1, . . . , n}, ta ®Æt Ck n! k!(n − k)!

k øng víi n hay sè tæ hîp chËp k cña n phÇn tö.

1.2.6 §Þnh lý. Cho n, k lµ c¸c sè tù nhiªn víi k 6 n. Khi ®ã

k P i=0

(i) S(n, k) =

. (ii) S(n, k) = (−1)k−iinCi k. 1 i1! . . . ik!

(iii) S(n + 1, k) = kn−rS(r, k − 1). 1 k! n! k! P i1+...+ik=n n P r=k−1

k P j=1

ij = n víi ik ≥ 1. Chøng minh. Gi¶ sö cã bé sè (i1, i2, . . . , ik) sao cho

Ta sÏ x¸c ®Þnh sè c¸ch ph©n ho¹ch tËp X thµnh k tËp con kh«ng rçng sao

cho sè phÇn tö cña c¸c tËp lµ ij víi j ∈ {1, 2, . . . , k}. Sè c¸ch chän i1 tõ tËp hîp n phÇn tö cña tËp X lµ Ci1 n . Víi mçi c¸ch chän i1 phÇn tö th× cã Ci2 n−i1 c¸ch chän i2 phÇn tö. Víi mçi c¸ch chän i1 phÇn tö vµ i2 phÇn tö th× cã Ci3 n−i1−i2 c¸ch chän i3 phÇn tö. Tæng qu¸t víi mçi c¸ch chän i1 phÇn tö vµ . . . ik−1 phÇn tö th× cã Cik n−i1−i2−...−ik c¸ch chän ik phÇn tö. H¬n n÷a, c¸c tËp con cña ph©n ho¹ch kh«ng ph©n biÖt thø tù, tøc lµ bé sè sau

n Ci2

n−i1−i2−...−ik hay

hay Ci1 j ∈ {1, 2, . . . , k} b»ng kh«ng ph©n biÖt thø tù (i1, i2, . . . , ik). Do ®ã sè c¸ch ph©n ho¹ch tËp hîp X thµnh k tËp con kh«ng rçng sao cho sè phÇn tö cña c¸c tËp lµ ij víi n−i1. . .Cik 1 k! 1 k! n! i1!i2!. . .ik!

. Sè c¸ch ph©n ho¹ch tËp hîp X thµnh k tËp con kh«ng rçng

i1+...+ik=n

i1+...+ik=n

. ( ) hay S(n, k) = n! 1 k! i1!i2!. . .ik! lµ S(n, k) = P n! k! n! k! P 1 i1! . . . ik! 1 i1! . . . ik!

13

1.2.7 VÝ dô. Gi¶ sö ta cÇn t×m S(5, 3). Sö dông §Þnh lÝ 1.2.6(i) ta cã

3 + (−1)215C1

3 + (−1)035C3

3 = 25.

S(5, 3) = [(−1)305C0 1 3!

Gi¶ sö ta cÇn t×m S(6, 4). Sö dông §Þnh lÝ 1.2.6(i) ta cã

S(6, 4) = [(−1)406C0 4 1 4!

4 + (−1)226C2

4 + (−1)36C3

4 + (−1)046C4

4 ] = 65.

+ (−1)316C1

Chóng ta còng cã thÓ sö dông §Þnh lÝ 1.2.6 (ii) ®Ó tÝnh S(6, 4). B»ng c¸ch

5

sö dông §Þnh lÝ 1.2.6 (iii) ta ®−îc

S(6, 4) = 45−rS(r, 3) = 42S(3, 3) + 4S(4, 3) + S(5, 3)

X r=3

= 16 + 24 + 25 = 60

6

hoÆc

46−rS(r, 3) = 43S(3, 3) + 42S(4, 3) + 4S(5, 3) + S(6, 3) S(7, 4) =

X r=3

(1.1) = 64 + 96 + 100 + 90 = 350.

(1.2)

C«ng thøc tÝnh sè Sirling lo¹i 2 b»ng c¸ch trùc tiÕp nh− trong §Þnh lÝ 1.2.6(i)

víi sè n gÆp kh¸ nhiÒu khã kh¨n khi sè tù nhiªn n lín dÇn lªn. MÖnh ®Ò

sau ®©y sÏ gióp ta kh¾c phôc ®−îc mét phÇn nh÷ng khã kh¨n ®ã.

1.2.8 MÖnh ®Ò. Cho n, k lµ c¸c sè tù nhiªn víi 2 6 k 6 n. Khi ®ã

S(n + 1, k) = kS(n, k) + S(n, k − 1).

Chøng minh. XÐt tËp hîp bÊt k× cã n + 1 phÇn tö, ch¼ng h¹n

A = {x1, x2, x3, . . . , xn+1}.

14

Theo ®Þnh nghÜa S(n + 1, k) lµ sè ph©n ho¹ch tËp hîp A thµnh k khèi.

MÆt kh¸c ta cã thÓ chia tËp B tÊt c¶ c¸c ph©n ho¹ch trªn thµnh 2 tËp con

rêi nhau nh− sau: B1 gåm tÊt c¶ c¸c ph©n ho¹ch cña tËp hîp A thµnh k khèi trong ®ã cã mét khèi lµ {xn+1}, cßn B2 gåm tÊt c¶ c¸c ph©n ho¹ch cña tËp hîp A thµnh k khèi trong ®ã kh«ng cã khèi nµo lµ {xn+1}. Khi ®ã mçi ph©n ho¹ch thuéc B1 sÏ chia tËp hîp {x1, x2, x3, . . . , xn} thµnh k − 1 khèi vµ cã S(n, k − 1) c¸ch chia nh− thÕ. Do ®ã lùc l−îng cña B1 lµ S(n, k − 1). NÕu {xn+1} kh«ng lµ mét khèi th× xn+1 sÏ n»m trong mét khèi víi Ýt nhÊt mét phÇn tö kh¸c cña A. V× cã S(n, k) c¸ch ph©n ho¹ch tËp hîp {x1, x2, x3, . . . , xn} thµnh k khèi nªn ta cã tÊt c¶ kS(n, k) c¸ch ph©n ho¹ch cña tËp hîp A thµnh k khèi, trong ®ã kh«ng cã khèi nµo lµ xn+1. Do ®ã lùc l−îng cña B2 lµ kS(n, k). Theo qui t¾c céng, ta cã:

S(n + 1, k) = kS(n, k) + S(n, k − 1).

1.2.9 VÝ dô. Ch¼ng h¹n khi ®• biÕt S(5, 3) = 25, S(5, 4) = 10 th× cã thÓ

tÝnh ®−îc S(6, 4) b»ng c«ng thøc sau ®©y S(6, 4) = 4S(5, 4) + S(5, 3) =

40 + 25 = 65. Nh− vËy, víi c«ng thøc truy håi trªn cã −u ®iÓm rÊt lín so

víi c«ng thøc tÝnh sè Sirling lo¹i 2 b»ng c¸ch trùc tiÕp nh− trong §Þnh lÝ

1.2.6(i) víi sè n lín.

PhÇn cuèi cña tiÕt nµy tr×nh bµy mét c«ng thøc tæng qu¸t ®Ó tÝnh sè

Stirling lo¹i hai cña mét tËp hîp gåm n phÇn tö víi ph©n ho¹ch thµnh k

khèi, ch¼ng h¹n k = 2, 3, 4, 5, n − 1, n − 2.

1.2.10 MÖnh ®Ò. Ta cã c¸c ®¼ng thøc sau

(i) S(n, 2) = 2n−1 − 1, n ≥ 2;

(ii) S(n, 3) = , n ≥ 3; 3n − 3.2n + 3 6

15

(iii) S(n, 4) = 4n − 4.3n + 6.2n − 4 24

, n ≥ 5; , n ≥ 4; 5n−1 − 4n + 2.3n − 2n+1 + 1 24

n, n ≥ 2; n + 3C4

n, n ≥ 4.

(iv) S(n, 5) = (v) S(n, n − 1) = C2 (vi) S(n, n − 2) = C3

Chøng minh. Ta sÏ chøng minh c¸c ®¼ng thøc trªn b»ng ph−¬ng ph¸p qui

n¹p ®ång thêi kÕt hîp víi c«ng thøc truy håi

S(n + 1, k) = kS(n, k) + S(n, k − 1).

(i) Khi n = 2, ta cã S(n, 2)=S(2, 2) = 1 vµ 2n−1 − 1 = 2 − 1 = 1, do ®ã ®¼ng thøc ®óng víi n = 2. Gi¶ sö ®¼ng thøc ®óng víi n = k ≥ 2, tøc lµ S(k, 2) = 2k−1 − 1. Ta cÇn chøng minh ®¼ng thøc ®óng víi n = k + 1. Ta cã

S(k + 1, 2) = 2S(k, 2) + S(k, 1) = 2S(k, 2) + 1

= (2k−1 − 1)2 + 1 = 2k − 1.

Ngoµi ra c«ng thøc trªn cßn cã thÓ lÝ gi¶i nh− sau: Mçi c¸ch ph©n ho¹ch

cÆp nªn sè cÆp kh«ng cã thø tù lµ = 2n−1 − 1. tËp hîp X gåm n phÇn tö thµnh 2 tËp con A vµ B th× 2 tËp con ®ã lµ bï cña nhau, tøc lµ A = X B. Mµ cã 2n cÆp (A, B) cã thø tù, bao gåm c¶ hai cÆp (A, ∅), (∅, B). Nh− vËy, nÕu kh«ng tÝnh hai cÆp nµy th× cã 2n − 2 cÆp bï nhau cã thø tù. V× trong ph©n ho¹ch ta kh«ng xÐt thø tù cña c¸c 2n − 2 2 (ii) Khi n = 3, ta cã S(n, 3) = S(3, 3) = 1 vµ

= = 1. 3n − 3.2n + 3 6 33 − 3.23 + 3 6

Do ®ã ®¼ng thøc ®óng víi n = 3. Gi¶ sö ®¼ng thøc ®óng víi n = k ≥ 3,

. Ta cÇn chøng minh ®¼ng thøc ®óng víi tøc lµ S(k, 3) = 3k − 3.2k + 3 6

16

n = k + 1. ThËt vËy, ta cã

S(k + 1, 3) = 3S(k, 3) + S(k, 2) = 3 + 2k−1 − 1

. = 3k − 3.2k + 3 6 3k − 2.2k + 1 2

(iii) Khi n = 4, ta cã S(n, 4) = S(4, 4) = 1 vµ

= = 1. 4n − 4.3n + 6.2n − 4 24 44 − 4.34 + 6.24 − 4 24

Do ®ã ®¼ng thøc ®óng víi n = 4. Gi¶ sö ®¼ng thøc ®óng víi n = k ≥ 4,

. Ta cÇn chøng minh ®¼ng thøc ®óng tøc lµ S(k, 4) = 4k − 4.3k + 6.2k − 4 24

. Suy ra qu¶ (ii) ë trªn ta cã S(k, 3) =

S(k + 1, 4) = 4 + víi n = k + 1. ThËt vËy, ta cã S(k + 1, 4) = 4S(k, 4) + S(k, 3). Theo kÕt 3k − 3.2k + 3 6 4k − 4.3k + 6.2k − 4 24 3k − 3.2k + 3 6

. = 4k+1 − 4.3k+1 + 6.2k+1 − 4 24

(iv) Khi n = 5, ta cã: S(n, 5) = S(5, 5) = 1 vµ

= = 1. 5n−1 − 4n + 2.3n − 2n+1 + 1 24 54 − 45 + 2.35 − 26 + 1 24

V× thÕ ®¼ng thøc ®óng víi n = 5. Gi¶ sö ®¼ng thøc ®óng víi n = k ≥ 5,

tøc lµ

. S(k, 5) = 5k−1 − 4k + 2.3k − 2k+1 + 1 24

Ta cÇn chøng minh ®¼ng thøc ®óng víi n = k + 1. ThËt vËy, ta cã S(k +

1, 5) = 5S(k, 5) + S(k, 4). Theo kÕt qu¶ (iii) ë trªn ta cã

. S(k, 4) = 4k − 4.3k + 6.2k − 4 24

17

V× thÕ

S(k + 1, 5) = 5 + 4k − 4.3k + 62k − 4 24

2 = 1, do ®ã ®¼ng thøc ®óng víi n = 2. k, k ≥ 2, k ∈ N .

. = 5k−1 − 4k + 2.3k − 2k+1 + 1 24 5k − 4k+1 + 2.3k+1 − 2k+2 + 1 24

(v) Khi n = 2, ta cã S(2, 1) = C2 Gi¶ sö ®¼ng thøc ®óng víi n = k, tøc lµ S(k, k − 1) = C2 Ta cÇn chøng minh ®¼ng thøc ®óng víi n = k + 1. ThËt vËy, ta cã

k = C2

k+1.

4 + 3C4

k + 3C4

S(k + 1, k) = kS(k, k) + S(k, k − 1) = k + C2

(vi) Khi n = 4, ta cã S(4, 2) = 7, C3 4 = 7 nªn ®¼ng thøc ®• cho ®óng víi n = 4. Gi¶ sö ®¼ng thøc ®• cho ®óng víi n = k, tøc lµ S(k, k − 2) = C3 k, k ≥ 4, k ∈ N . Ta cÇn chøng minh ®¼ng thøc ®óng víi n = k + 1. ThËt vËy, ta cã

S(k + 1, k − 1) = (k − 1)S(k, k − 1) + S(k, k − 2)

k + C3

k + 3C4

k = C3

k+1 + 3C4

k+1.

= (k − 1)C2

1.2.11 VÝ dô. Theo c«ng thøc trong mÖnh ®Ò trªn ta cã

S(8, 3) = = 966; 38 − 3.28 + 3 6

S(10, 4) = = 34105. 410 − 4.310 + 6.210 − 4 24

Nh− vËy c¸c c«ng thøc trong mÖnh ®Ò trªn mang hiÖu øng kh¸ m¹nh gióp

ta cã thÓ tra cøu sè ph©n ho¹ch cña tËp hîp gåm n phÇn tö thµnh k khèi

víi nh÷ng gi¸ trÞ cña k ®Æc biÖt ë trªn.

18

1.3 Mét sè c«ng thøc tÝnh hµm ph©n ho¹ch tËp hîp

Hµm ph©n ho¹ch tËp hîp lµ hµm biÕn nguyªn víi gi¸ trÞ nguyªn ®−îc cho bëi c«ng thøc f (n) = Bn víi mäi n ∈ N. Môc tiªu cña tiÕt nµy lµ chøng minh chi tiÕt mét sè c«ng thøc tÝnh hµm ph©n ho¹ch tËp hîp, tøc lµ tÝnh sè

Bell Bn, ®ång thêi ®−a ra tam gi¸c Pascal tÝnh hµm ph©n ho¹ch tËp hîp.

n

1.3.1 MÖnh ®Ò. Ta cã c«ng thøc truy håi sau ®©y.

nBk = C0

nB0 + C1

nB1 + C2

nB2 + . . . + Ck

nBk + . . . + Cn

n Bn.

Ck Bn+1 =

X k=0

x = x(x − 1) . . . (x − k + 1) → L((x)k) = 1 víi x. Do ®ã

n P k=0

Chøng minh. Ta x©y dùng phiÕm hµm tuyÕn tÝnh L : R[x] → R x¸c ®Þnh bëi (x)k = Ak mäi k = 0, 1, 2 . . .. Ta chøng minh ®−îc xn = S(n, k)Ak

n P r=0

n P k=0

L(xn) = S(n, k)L((x)k) = S(n, k) = Bn. Ta cã

(x)n+1 = x(x − 1) . . . (x − n) = x(x − 1)n.

Suy ra L((x)n+1) = L((x)n) = L(x(x − 1)n). Do ®ã L(p(x)) = L((x)n) = L(xP (x − 1)) víi mäi P (x). B©y giê ta cho P (x) = (x + 1)n, ta ®−îc L((x + 1)n) = L(xn+1), hay n

nL(xk) = Bn+1.

Ck

X k=0

nBk = Bn+1.

4 B0 + C1

4 B1 + C2

4 B2 + C3

4 B3 + C4

4 B4 = 1 + 4 + 12 +

9 B1 + C2

9 B2 + C3

9 B3 + C4

9 B4 + C5

9 B5 + C6

9 B6 + C7

9 B7 +

Nh− vËy, Ck

n P k=0 1.3.2 VÝ dô. B5 = C0 20 + 15 = 52 B10 = C0 9 B8 + C9 C8

9 B0 + C1 9 B9=

1 + 9 + 72 + 420 + 1890 + 6552 + 17052 + 31572 + 37260 + 21147 = 115975

19

Sau ®©y ta sÏ ®−a ra tam gi¸c Bell ®Ó tÝnh sè ph©n ho¹ch cña tËp hîp

gåm n phÇn tö víi n nhËn nh÷ng gi¸ trÞ ®Çu tiªn lµ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

§©y lµ kÕt qu¶ tæng hîp cña nh÷ng ®Þnh lÝ, mÖnh ®Ò ë trªn. Tr−íc hÕt ta

m« t¶ c¸ch x©y dùng tam gi¸c Bell qua chó ý sau ®©y.

1.3.3 Chó ý. C¸c sè Bell cã thÓ tÝnh dÔ dµng b»ng c¸ch x©y dùng tam gi¸c

Bell, cßn ®−îc gäi lµ d•y Aitken hoÆc tam gi¸c Pierce. Ta cã thÓ m« t¶

c¸ch x©y dùng tam gi¸c Bell nh− sau: B¾t ®Çu víi sè 1 vµ ®Æt sè nµy trªn

dßng thø nhÊt. T¹o mét dßng míi b»ng c¸ch lÊy phÇn tö bªn ph¶i cña dßng

ngay trªn nã lµm phÇn tö ®Çu tiªn bªn tr¸i cña dßng míi. LÇn l−ît c¸c sè

tiÕp theo cña dßng míi b»ng c¸ch lÊy tæng phÇn tö bªn tr¸i nã víi phÇn tö

®øng cïng cét phÇn tö Êy ë dßng tr−íc nã. TiÕp tôc b−íc ba cho ®Õn khi

sè phÇn tö cña dßng míi nhiÒu h¬n sè phÇn tö cña dßng trªn mét phÇn tö.

Sè n»m phÝa ph¶i mçi dßng lµ sè Bell cho mçi dßng.

Cô thÓ tam gi¸c Bell còng cã qui luËt thiÕt lËp cô thÓ, cã nÐt t−¬ng tù

nh− qui luËt thiÕt lËp tam gi¸c Pascal cña c¸c sè tæ hîp. Hµng ®Çu tiªn lµ

ch÷ sè 1, ®©y lµ sè Bell ®Çu tiªn. Víi mäi i ≥ 1 hµng thø i + 1 ®−îc ®iÒn

theo nguyªn t¾c sau ®©y: Ch÷ sè cuèi cïng cña hµng thø i ®−îc ®Æt lªn ®Çu

hµng thø i + 1. Víi mäi j > 1 sè thø j cña hµng i + 1 lµ tæng cña sè thø

j − 1 cña hµng i + 1 vµ sè thø j − 1 cña hµng i. Sè cuèi cïng cña hµng

i + 1 lµ sè Bell cña hµng ®ã.

20

Tr−íc hÕt ta cã b¶ng tÝnh c¸c sè S(n, k), tøc lµ c¸c sè Stirling lo¹i 2.

4 3 9 8 7 6 5 10 Bn

1 1 1 1 1 3 1 6 1 7 10 25 1 15 65 90 1 31 350 1 63 301 1701 1 127 966 1 255 3025 7770 1 15 140 1050 6951 1 21 266 2646 1 28 462 1 36 1

S(n, k) 1 2 n = 1 n = 2 n = 3 n = 4 n = 5 n = 6 n = 7 n = 8 n = 9 n = 10 1 511 9330 34105 42525 22827 5880 750 45 1 1 2 5 15 52 203 877 4140 21147 115975

TiÕp theo, chóng ta ®−a ra b¶ng t¸m gi¸c tÝnh sè Bell Bn, tøc lµ sè ph©n ho¹ch tËp hîp n phÇn tö. Trong b¶ng nµy, dßng ®Çu tiªn lµ sè Bell øng víi

n = 1, cuèi dßng thø 2 lµ sè Bell øng víi n = 2. Cø tiÕp tôc nh− thÕ, sè

cuèi n»m trong mçi dßng lµ sè Bell øng víi sè n cña dßng ®ã. Ch¼ng h¹n ë dßng thø 9 th× sè Bell lµ B9 = 21147.

5 10 27 87 322 52 151 523

2 3 15 7 37 20 203 114 67 255 674 409 1080 1335 1657 2066 2589 877 3263 4140

n = 1 1 n = 2 1 n = 3 2 n = 4 5 n = 5 15 n = 6 52 n = 7 203 n = 8 877 n = 9 4140 5017 6097 7432 9089 11155 13744 17007 21147

1.3.4 Chó ý. (i) Chóng ta hoµn toµn cã thÓ ph¸t triÓn tam gi¸c Bell víi sè

tù nhiªn n lín h¬n n÷a, ®©y lµ mét −u ®iÓm rÊt lín ®Ó tÝnh sè ph©n ho¹ch

cña tËp hîp cã nhiÒu ph©n tö.

21

(ii) Mét sè nguyªn tè Bell lµ mét sè Bell ®ång thêi lµ mét sè nguyªn tè.

C¸c sè nguyªn tè Bell ®Çu tiªn lµ

2, 5, 27644437, 35742549198872617291353508656626642567,

3593340855968622831041960188598043661065388726959079837.

C¸c sè nguyªn tè Bell ë trªn t−¬ng øng lµ c¸c sè Bell thø 2, 3, 7, 13, 42, 55. Sè nguyªn tè Bell tiÕp theo lµ B2841 xÊp xØ víi 93074106538. §Õn n¨m 2005, sè nguyªn tè Bell lín nhÊt ®• biÕt lµ B2841. N¨m 2002, PhilCarmody ph¸t biÓu r»ng B2841 lµ sè nguyªn tè. GÇn hai n¨m sau, Ignacio Larrosa Canestro ®• chøng minh ®−îc B2841 lµ sè nguyªn tè.

Ch−¬ng 2

Mét sè øng dông trong to¸n s¬ cÊp

Trong ch−¬ng nµy, ta xem xÐt mét sè øng dông cña lý thuyÕt ph©n ho¹ch

trªn mét sè lÜnh vùc cña to¸n häc, ch¼ng h¹n nh− ®¹i sè tæ hîp hay x¸c

suÊt thèng kª, ®Æc biÖt thÊy ®−îc øng dông cña phÐp ph©n ho¹ch tËp hîp

trong h×nh häc s¬ cÊp.

2.1 Ph©n ho¹ch ch½n, lÎ vµ øng dông trong to¸n s¬ cÊp

Cho X là tËp cã n phÇn tö. Mét ph©n ho¹ch tËp hîp X ®−îc gäi lµ ph©n

ho¹ch cã ®iÒu kiÖn nÕu ta g¾n mét ®iÒu kiÖn nµo ®ã trªn c¸c tËp con trong

ph©n ho¹ch. Sau ®©y ta sÏ xÐt hai lo¹i ph©n ho¹ch ®Æc biÖt, ®ã lµ ph©n

ho¹ch ch½n vµ ph©n ho¹ch lÎ.

2.1.1 §Þnh nghÜa. Mét ph©n ho¹ch tËp hîp X ®−îc gäi lµ ph©n ho¹ch ch½n

nÕu mçi tËp con trong ph©n ho¹ch cã sè phÇn tö lµ sè ch½n. Mét ph©n

ho¹ch tËp hîp X ®−îc gäi lµ ph©n ho¹ch lÎ nÕu mçi tËp con trong ph©n

ho¹ch cã sè lÎ phÇn tö.

2.1.2 KÝ hiÖu. Víi tËp X cã n phÇn tö ta kÝ hiÖu:

(i) E(n, k) lµ sè ph©n ho¹ch tËp X thµnh k tËp con sao cho mçi tËp con cã

ch½n phÇn tö.

22

(ii) O(n, k) lµ sè ph©n ho¹ch tËp X thµnh k tËp con sao cho mçi tËp con

23

cã mét sè lÎ phÇn tö.

(iii) En lµ sè ph©n ho¹ch tËp X thµnh c¸c tËp con gåm ch½n phÇn tö. (iv) On lµ sè ph©n ho¹ch tËp X thµnh c¸c tËp con gåm lÎ phÇn tö.

n P k=0

n P k=0

O(n, k). 2.1.3 Chó ý. Ta cã En = E(n, k) vµ On =

2.1.4 MÖnh ®Ò. Víi m, n lµ c¸c sè nguyªn d−¬ng, ta cã c¸c ®¼ng thøc sau:

(i) E(2m, 2) = 22m−2 − 1;

(2m)! (ii) E(2m, m) = m!2m ; (iii) O(2n, 2) = 22n−2;

n =

, n ≥ 4. (iv) O(n, n − 2) = C3

n(n − 1)(n − 2) 6 Chøng minh. (i) Gäi A lµ tËp c¸c ph©n ho¹ch mét tËp X gåm 2m phÇn tö

thµnh c¸c tËp con cã sè ch½n phÇn tö. §Ó t¹o ra mét ph©n ho¹ch trong A, ®Çu tiªn lµ chän 2j phÇn tö tõ 2m phÇn tö cho tËp con thø nhÊt, cã C2j 2m c¸ch chän 2j nh− thÕ. Sau ®ã chän 2m − 2j phÇn tö cßn l¹i cho tËp con thø

hai, cã ®óng 1 c¸ch chän. Do j cã thÓ nhËn c¸c gi¸ trÞ 1, 2, 3, . . . , m − 1

m−1

vµ sè c¸ch chän øng víi mçi j tÝnh 2 lÇn nªn ta cã c«ng thøc

2m + C4

2m + . . . + C2m−2

2m =

2m ).

C2j E(2m, 2) = (C2 1 2 1 2 X j=1

Khai triÓn nhÞ thøc (1 + x)2m sau ®ã cho x = 1, x = −1 ta nhËn ®−îc

2m + C1 2m − C1

2m + C2 2m + C2

2m + C3 2m − C3

2m + C4 2m + C4

2m + . . . + C2m−1 2m + . . . − C2m−1

2m + C2m 2m; 2m + C2m 2m.

22m = (1 + 1)2m = C0 02m = (1 − 1)2m = C0

Céng tõng vÕ c¸c ®¼ng thøc trªn ta nhËn ®−îc

m + 2(C2

2m + C4

2m + . . . + C2m−2

2m ) + 2C2m 2m .

22m = 2C0

Khi ®ã E(2m, 2) = 22m−2 − 1. (ii) Khi ph©n ho¹ch tËp hîp gåm 2m thµnh m tËp con kh«ng rçng mµ mçi

24

tËp con gåm sè ch½n phÇn tö th× sè phÇn tö trong mçi tËp con lµ 2. §Çu tiªn ta chän 2 phÇn tö cho tËp hîp con thø nhÊt th× cã C2 2m c¸ch chän, sau ®ã chän tiÕp 2 phÇn tö cho tËp con thø 2 tõ 2m − 2 phÇn tö cßn l¹i th× cã C2 2m−2 c¸ch chän. Cø nh− thÕ ®Õn khi ta chän 2 phÇn tö cßn l¹i cho tËp con cuèi cïng th× cã C2 2 c¸ch chän. Theo qui t¾c nh©n vµ ph©n ho¹ch kh«ng cã tÝnh thø tù c¸c tËp hîp con trong ph©n ho¹ch nªn ta cã

2mC2

2m−2 . . . C2

4 C2 2 ;

C2 E(2m, m) = 1 m!

. . . E(2m, m) = = 1 m! (2m)! 2!(2m − 2)! (2m − 2)! 2!(2m − 4)! 4! 2!2! 2! 2! (2m)! m!2m .

(iii) Mçi c¸ch ph©n ho¹ch tËp hîp gåm 2n phÇn tö thµnh 2 tËp con kh«ng

2n

c¸ch. Sau ®ã chän 2n + 1 − 2j phÇn tö cßn l¹i

rçng gåm hai b−íc sau: §Çu tiªn lµ chän 2j − 1 phÇn tö tõ 2n phÇn tö cho tËp hîp thø nhÊt cã C2j−1 cho tËp hîp thø hai cã 1 c¸ch. Do j cã thÓ nhËn c¸c gi¸ trÞ 1, 2, 3, . . . , n

n

vµ sè c¸ch chän øng víi mçi j tÝnh 2 lÇn nªn ta cã c«ng thøc

2n + C3

2m + . . . + C2n−1

2n =

2n

C2j−1 . O(2n, 2) = (C1 1 2 1 2 X j=1

Khai triÓn nhÞ thøc (1 + x)2n sau ®ã cho x = 1, x = −1 ta nhËn ®−îc

2n + C1 2n − C1

2n + C2 2n + C2

2n + C3 2n − C3

2n + C4 2n + C4

2n + C5 2n − C5

2n + . . . + C2n−1 2n + . . . − C2n−1

2n + C2n 2n ; 2n + C2n 2n .

22n = (1 + 1)2n = C0 02n = (1 − 1)2n = C0

Céng tõng vÕ c¸c ®¼ng thøc trªn ta nhËn ®−îc O(2n, 2) = 22n−2. (iv) Khi ph©n ho¹ch tËp hîp gåm n phÇn tö thµnh n − 2 tËp con kh«ng rçng

mµ mçi tËp con gåm mét sè lÎ phÇn tö th× sÏ cã mét tËp cã 3 phÇn tö vµ n − 3 tËp cßn l¹i mçi tËp cã mét phÇn tö. Cã C3 n c¸ch chän 3 phÇn tö ®Ó t¹o thµnh mét tËp cã 3 phÇn tö. Cã duy nhÊt mét c¸ch ph©n ho¹ch n − 3

phÇn tö ®Ó t¹o thµnh n − 3 tËp kh«ng rçng, mçi tËp cã mét phÇn tö. Do ®ã

25

theo qui t¾c nh©n, ta cã

n =

O(n, n − 2) = C3 n(n − 1)(n − 2) 6

víi n ≥ 4.

Tõ MÖnh ®Ò 2.1.4, ta cã b¶ng sau ®Ó tÝnh c¸c sè E(n, k) vµ O(n, k) víi

nh÷ng n nhá.

O(n, k) k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 On n = 1 1 n = 2 1 n = 3 2 n = 4 5 n = 5 12 n = 6 37 n = 7 128 n = 8 457 1 0 20 0 366 1 0 0 0 16 0 64 1 0 10 0 91 0 1 0 1 4 1 1 1 0 1 0 35 0 1 0 56 1 0 1

E(n, k) k = 1 k = 2 k = 3 k = 4 k = 5 k = 6 k = 7 k = 8 En n = 1 0 n = 2 1 n = 3 0 n = 4 4 n = 5 0 n = 6 31 n = 7 0 n = 8 379 0 0 0 15 0 210 0 0 0 0 105 0 0 3 0 15 0 63 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0

2.1.5 VÝ dô. Cã 20 vËn ®éng viªn trong mét cuéc thi ®Êu cÇu l«ng. Ban tæ

chøc cÇn chia c¸c vËn ®éng viªn thµnh 10 cÆp thi ®Êu. Sè c¸ch chia lµ sè

ph©n ho¹ch tËp hîp 20 phÇn tö thµnh 10 tËp con mµ mçi tËp con gåm ®óng

2 phÇn tö. Sè c¸ch lµ E(20, 10) = 654729685.

26

2.1.6 VÝ dô. T¹i vßng chung kÕt Worldcup thÕ giíi diÔn ra t¹i Brazil n¨m

2014, Ban tæ chøc chän ®−îc 16 ®éi bãng vµo ®Êu lo¹i trùc tiÕp. C¸c ®éi

bãng sÏ tham gia bèc th¨m ®Ó chia thµnh 8 cÆp ®Êu. Hai ®éi thuéc 1 cÆp sÏ

thi ®Êu ®Ó chän ra ®éi th¾ng vµo tø kÕt. Khi ®ã, sè kh¶ n¨ng ph©n chia cÆp

®Êu lµ sè ph©n ho¹ch tËp hîp gåm 16 phÇn tö thµnh 8 tËp con kh«ng rçng mµ

mçi tËp con gåm ®óng 2 phÇn tö. Sè ®ã lµ E(16, 8) = 2027025. T−¬ng tù

sè c¸ch chia 8 ®éi th¾ng thµnh 4 cÆp ®Êu cho vßng tø kÕt lµ E(8, 4) = 105,

vµ sè c¸ch chia 4 ®éi th¾ng cho vßng b¸n kÕt lµ E(4, 2) = 3.

B©y giê ta sö dông c¸c c«ng thøc trªn ®Ó gi¶i mét sè bµi to¸n s¬ cÊp.

2.1.7 Bµi to¸n. Ph©n phèi n qu¶ cÇu ph©n biÖt vµo m hép gièng nhau. Cã

bao nhiªu c¸ch ph©n phèi sao cho mçi hép cã ch½n qu¶ cÇu vµ bao nhiªu

c¸ch ph©n phèi sao cho mçi hép cã lÎ qu¶ cÇu.

Lêi gi¶i. V× c¸c qu¶ cÇu lµ ph©n biÖt nhau vµ c¸c hép lµ gièng nhau nªn sè

c¸ch ph©n phèi ®Ó mçi hép cã mét sè ch½n (lÎ) phÇn tö b»ng sè c¸ch ph©n

ho¹ch tËp hîp gåm n phÇn tö thµnh m tËp con sao cho mçi tËp cã sè ch½n

(lÎ) qu¶ cÇu.

Do ®ã sè c¸ch ph©n phèi sao cho mçi hép cã chøa mét sè ch½n qu¶ cÇu

b»ng E(n, m) c¸ch vµ sè c¸ch ph©n phèi sao cho mçi hép cã chøa sè mét

sè lÎ qu¶ cÇu b»ng O(n, m) c¸ch.

2.1.8 Bµi to¸n. Cã bao nhiªu c¸ch ph©n phèi 5 ®å vËt kh¸c nhau vµo 3

hép gièng nhau sao cho mçi hép chøa mét sè ch½n ®å vËt. Cã bao nhiªu

c¸ch ph©n phèi 5 ®å vËt kh¸c nhau vµo 3 hép gièng nhau sao cho mçi hép

chøa mét sè lÎ ®å vËt.

Lêi gi¶i. V× c¸c ®å vËt lµ kh¸c nhau vµ c¸c hép lµ gièng nhau nªn sè c¸ch

ph©n phèi 5 ®å vËt kh¸c nhau vµo 3 hép gièng nhau sao cho mçi hép cã mét

sè ch½n ®å vËt b»ng sè ph©n ho¹ch tËp hîp5 phÇn tö ph©n biÖt thµnh 3 tËp

27

con sao cho mçi tËp con cã chøa mét sè ch½n phÇn tö vµ b»ng E(5, 3) = 0.

T−¬ng tù sè c¸ch ph©n phèi 5 ®å vËt kh¸c nhau vµo 3 hép gièng nhau sao

cho mçi hép cã mét sè lÎ ®å vËt b»ng O(5, 3) = 10.

2.2 Mét sè øng dông gi¶i to¸n tæ hîp vµ h×nh häc s¬ cÊp

Nh− trong §Þnh nghÜa 1.2.2, sè ph©n ho¹ch tËp X gåm n phÇn tö thµnh

k khèi ®−îc kÝ hiÖu lµ S(n, k) vµ ®−îc gäi lµ sè Stirling lo¹i 2. Nh− vËy

S(n, k) chÝnh lµ sè c¸ch ph©n phèi n qu¶ cÇu ph©n biÖt vµo k hép gièng nhau

mµ kh«ng cã hép nµo rçng. Ch¼ng h¹n, sè c¸ch ph©n phèi 10 qu¶ cÇu ph©n

biÖt vµo 5 hép gièng nhau mµ kh«ng cã hép nµo rçng lµ S(10, 5) = 52525.

2.2.1 Bµi to¸n. Cã bao nhiªu c¸ch ph©n phèi 2015 qu¶ cÇu ph©n biÖt vµo

100 hép ph©n biÖt.

Lêi gi¶i. Gi¶ sö c¸c hép gièng nhau. Khi ®ã ph©n phèi 2015 qu¶ cÇu ph©n

biÖt vµo 100 hép gièng nhau chÝnh lµ sè ph©n ho¹ch mét tËp hîp gåm 2015

phÇn tö thµnh 100 khèi, ®ã lµ S(2015, 100). Víi mçi c¸ch ph©n phèi 2015

qu¶ cÇu vµo 100 hép gièng nhau, b»ng c¸ch ho¸n vÞ 100 hép ta sÏ ®−îc 100!

ph©n phèi 2015 qu¶ cÇu vµo 100 hép ph©n biÖt. Do ®ã sè c¸ch ph©n phèi

2015 qu¶ cÇu ph©n biÖt vµo 100 hép ph©n biÖt lµ 100! x S(2015, 100).

2.2.2 Bµi to¸n. Ph©n phèi n qu¶ cÇu ph©n biÖt vµo k hép ph©n biÖt. Cã

bao nhiªu c¸ch ph©n phèi sao cho mçi hép chøa mét sè ch½n qu¶ cÇu vµ

cã bao nhiªu c¸ch ph©n phèi sao cho mçi hép chøa mét sè lÎ qu¶ cÇu.

Lêi gi¶i. Gi¶ sö c¸c hép gièng nhau. Sè c¸ch ph©n phèi sao cho mçi hép

chøa mét sè ch½n qu¶ cÇu lµ E(n, k) vµ sè c¸ch ph©n phèi sao cho mçi

hép chøa mét sè lÎ qu¶ cÇu lµ O(n, k). Víi mçi c¸ch ph©n phèi vµo k hép

gièng nhau, b»ng c¸ch ho¸n vÞ k hép, ta ®−îc mét ph©n phèi vµo k hép

28

kh¸c nhau. Do ®ã sè c¸ch ph©n phèi n qu¶ cÇu ph©n biÖt vµo k hép ph©n

biÖt sao cho mçi hép chøa mét sè ch½n qu¶ cÇu lµ k! x E(n, k) vµ sè c¸ch

ph©n phèi n qu¶ cÇu ph©n biÖt vµo k hép ph©n biÖt sao cho mçi hép chøa

mét sè lÎ qu¶ cÇu lµ k! x O(n, k).

2.2.3 Bµi to¸n. TÝnh sè nghiÖm nguyªn kh«ng ©m cña ph−¬ng tr×nh

x1 + x2 + x3 + . . . + xk = n.

Lêi gi¶i. XÐt d•y cã ®é dµi lµ n + k − 1 bao gåm n phÇn tö x vµ k − 1 sè

0 nh− sau

x . . . x | {z }x1 0 x . . . x | {z }x2 , 0 . . . x . . . x | {z }xk

trong ®ã x1 + x2 + x3 + . . . + xk = n vµ xi > 0 víi mäi i ∈ {1, 2, 3, . . . , k}. NhËn xÐt r»ng cã 1 song ¸nh tõ tËp c¸c nghiÖm nguyªn d−¬ng cña ph−¬ng

tr×nh ®• cho vµo tËp c¸c d•y d¹ng x1, . . . , xk tháa m•n ®iÒu kiÖn trªn. MÆt kh¸c, sè c¸c d•y cã d¹ng trªn t−¬ng øng víi sè c¸ch chän k −1 vÞ trÝ cho sè

0, lµ tËp con gåm k−1 phÇn tö cña tËp hîp gåm n−1 phÇn tö. Do ®ã sè c¸c d•y d¹ng tháa m•n ®iÒu kiÖn trªn lµ Ck−1 n−1. V× thÕ sè nghiÖm nguyªn d−¬ng cña ph−¬ng tr×nh lµ Ck−1 n−1. NhËn xÐt r»ng nÕu x1 + x2 + x3 + . . . + xk = n vµ xi ≥ 0 víi i ∈ {1, 2, 3, . . . k} th×

(x1 + 1) + (x2 + 1) + . . . + (xk + 1) = n + k

víi xi+1 > 0 vµ i ∈ {1, 2, 3, . . . k}. §¶o l¹i, nÕu y1+y2+y3+. . .+yk = n+k vµ yi > 0 víi mäi i ∈ {1, 2, 3, . . . k} th×

(y1 − 1) + (y2 − 1) + . . . + (yk − 1) = n

n+k−1.

n+k−1 = Cn

víi yi ≥ 0 vµ i ∈ {1, 2, 3, . . . k}. Do ®ã sè nghiÖm nguyªn kh«ng ©m cña ph−¬ng tr×nh lµ Ck−1

29

2.2.4 Bµi to¸n. Chän ngÉu nhiªn mét sè tù nhiªn cã 3 ch÷ sè. TÝnh x¸c

suÊt ®Ó chän ®−îc mét sè cã tæng c¸c ch÷ sè chia hÕt cho 10.

Lêi gi¶i. Gäi sè cÇn lËp cã d¹ng abc tháa m•n a 6= 0 vµ

a, b, c ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

Sè cã 3 ch÷ sè tïy ý lµ 9 x 102 = 900 sè. NhËn xÐt r»ng sè nghiÖm kh«ng ©m cña ph−¬ng tr×nh a + b + c = n lµ C2 n+2. Theo gi¶ thiÕt, ta cã 2 tr−êng hîp sau ®©y.

Tr−êng hîp 1: a + b + c = 10. Khi ®ã sè nghiÖm nguyªn kh«ng ©m víi a, b, c tïy ý lµ C2 12. Sè nghiÖm a, b, c tháa m•n a = 0, 0 6 b, c 6 9 vµ b, c ∈ N lµ C1 11. Sè nghiÖm a, b, c tháa m•n a = 10, b = c = 0 lµ 1. KÕt hîp l¹i, tr−êng hîp nµy cã

12 − C1

11 − 1 = C2

11 − 1

C2

sè tháa m•n yªu cÇu bµi to¸n.

Tr−êng hîp 2: a + b + c = 20. §Æt a = 9 − x, b = 9 − y, c = 9 − z. Khi

®ã, ta cã

9 vµ c¸c sè tháa

x, y, z ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

vµ x + y + z = 7, x 6= 9. Sè nghiÖm x, y, z tháa m•n lµ C2 m•n tr−êng hîp nµy lµ C2 9 .

11 + C2

9 − 1 = 90. V×

Tãm l¹i sè c¸c sè tháa m•n yªu cÇu bµi to¸n lµ C2

. vËy, x¸c suÊt cÇn t×m lµ P = = 90 900

1 10 2.2.5 Bµi to¸n. Chän ngÉu nhiªn mét sè tù nhiªn cã 3 ch÷ sè. TÝnh x¸c

suÊt ®Ó chän ®−îc mét sè cã tæng c¸c ch÷ sè chia hÕt cho 9.

Lêi gi¶i. Gäi sè cÇn lËp cã d¹ng abc tháa m•n a 6= 0 vµ

a, b, c ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.

30

10. KÕt hîp l¹i, tr−êng hîp nµy cã C2

10 = C2

Sè cã 3 ch÷ sè tïy ý lµ 9 x 102 = 900 sè. NhËn xÐt r»ng sè nghiÖm kh«ng ©m cña ph−¬ng tr×nh a + b + c = n lµ C2 n+2. Theo gi¶ thiÕt ta cã 3 tr−êng hîp sau ®©y.

Tr−êng hîp 1: a + b + c = 9, khi ®ã sè nghiÖm nguyªn kh«ng ©m víi a, b, c 11. Sè nghiÖm a, b, c tháa m•n a = 0, 0 6 b, c 6 9 vµ b, c ∈ N lµ tïy ý lµ C2 11 − C1 C1 10 sè tháa m•n yªu cÇu bµi to¸n.

Tr−êng hîp 2: a + b + c = 18. §Æt a = 9 − x, b = 9 − y, c = 9 − z. Khi

®ã, ta cã

11 − 1,

11 − 1.

x, y, z ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

vµ x + y + z = 9, x kh¸c 9. V× thÕ sè nghiÖm x, y, z tháa m•n lµ C2 do ®ã sè c¸c sè tháa m•n tr−êng hîp nµy lµ C2 Tr−êng hîp 3: a + b + c = 27, khi ®ã a = 9, b = 9, c = 9 nªn cã 1 sè tháa

10 + C2

11 − 1 + 1 = 100.

m•n tr−êng hîp nµy.

. X¸c suÊt cÇn t×m lµ P = = Tãm l¹i sè c¸c sè tháa m•n yªu cÇu bµi to¸n lµ C2 90 900 1 10

2.2.6 Bµi to¸n. Trong mét hép cã 50 viªn bi ®−îc ®¸nh sè tõ 1 ®Õn 50,

chän ngÉu nhiªn 3 viªn bi. TÝnh x¸c suÊt ®Ó tæng ba sè trªn 3 viªn bi ®−îc

chän lµ mét sè chia hÕt cho 3.

Lêi gi¶i. Chän ngÉu nhiªn 3 viªn bi cã C3 50 c¸ch. Nªn sè phÇn tö cña kh«ng gian mÉu lµ n(Ω) = C3 50 = 19600. Gäi A lµ biÕn cè ®Ó tæng ba sè trªn ba viªn bi ®−îc chän lµ mét sè chia hÕt cho 3. Trong mét tËp hîp X gåm 50 viªn bi øng víi 50 sè ban ®Çu cã thÓ ph©n ho¹ch thµnh 3 tËp hîp X1, X2, X3, trong ®ã X1 gåm 16 viªn bi trªn ®ã ®¸nh c¸c sè cã chung mét tÝnh chÊt lµ chia hÕt cho 3, X2 gåm 17 viªn bi trªn ®ã ®¸nh c¸c sè cã chung mét tÝnh chÊt lµ chia cho 3 d− 1 vµ X3 gåm 17 viªn bi trªn ®ã ®¸nh c¸c sè cã chung mét tÝnh chÊt lµ chia cho 3 d− 2. §Ó t×m sè c¸ch chän 3 viªn bi cã tæng ba

31

sè trªn 3 viªn bi lµ mét sè chia hÕt cho 3, ta xÐt 2 tr−êng hîp sau ®©y

16 + C3

17 + C3

17 + C1

16 + C1

Tr−êng hîp 1: 3 viªn bi ®−îc chän thuéc cïng 1 lo¹i, tøc lµ cïng thuéc

tËp hîp X1 hoÆc tËp hîp X2 hoÆc tËp hîp X3. Khi ®ã sè c¸ch chän trong tr−êng hîp nµy lµ C3 17 = 1920. Tr−êng hîp 2: 3 viªn bi ®−îc chän, mçi viªn thuéc 1 lo¹i, tøc lµ viªn thø nhÊt thuéc tËp hîp X1, viªn thø hai thuéc tËp hîp X2, viªn thø ba thuéc tËp hîp X3. Khi ®ã sè c¸ch chän trong tr−êng hîp nµy lµ C1 17 = 4624. Theo qui t¾c céng cã n(A) = 1920 + 4624 = 6544. X¸c suÊt cÇn t×m lµ

. P (A) = = = n(A) n(Ω) 6544 19600 409 1225

Trong h×nh häc, ngoµi c¸c bµi to¸n truyÒn thèng dùa trªn c¸c ®Æc tr−ng

c¬ b¶n cña h×nh häc ®−îc ph¸t triÓn thµnh c¸c ®Þnh lÝ h×nh häc, cßn nh÷ng

bµi to¸n kiÓu ghÐp h×nh, chia h×nh mang néi dung kh¸c. Ph−¬ng ph¸p kh¶o

s¸t häc to¸n nµy dùa vµo mét vµi ®Æc tÝnh riªng biÖt ®−îc gäi lµ sù suy

luËn logic h×nh thøc t−¬ng tù kh«ng liªn quan ®Õn h×nh häc nh− nguyªn lÝ

Dirichle. C¸c bµi to¸n kiÓu ghÐp h×nh häc, chia h×nh cã thÓ xem nh− nh÷ng

bµi to¸n s¬ ®¼ng cña h×nh häc tæ hîp. Trong phÇn nµy chóng ta xem xÐt

mét sè tÝnh chÊt ®¬n gi¶n cu¶ h×nh häc tæ hîp. Bµi to¸n ph©n ho¹ch ®a

gi¸c låi, ph¼ng thµnh c¸c tam gi¸c b»ng mét hÖ thèng ®iÓm cho tr−íc trong

®a gi¸c ®ã.

2.2.7 VÝ dô. Cho tø gi¸c ABCD vµ 1 ®iÓm M tïy ý n»m trong tø gi¸c ®ã.

XÐt 4 tr−êng hîp sau ®©y.

(i) §iÓm M kh«ng n»m trªn 2 ®−êng chÐo AC vµ BD;

(ii) §iÓm M n»m trªn ®−êng chÐo AC vµ n»m ngoµi ®−êng chÐo BD;

(iii) §iÓm M n»m trªn ®−êng chÐo BD vµ n»m ngoµi ®−êng chÐo AC;

(iv) §iÓm M n»m trªn 2 ®−êng chÐo AC vµ BD.

32

Khi ®ã, c¶ 4 tr−êng hîp nµy ®Òu cã 4 tam gi¸c n»m trong ph©n ho¹ch

nãi trªn.

2.3 Ph©n hoach sè vµ øng dông trong to¸n s¬ cÊp

2.3.1 Bµi to¸n. Chøng minh r»ng kh«ng thÓ chia tËp hîp {1, 2, 3, . . . , 1997}

thµnh mét sè tËp con rêi nhau sao cho sè lín nhÊt trong mçi tËp con b»ng

tæng c¸c sè cßn l¹i.

Chøng minh. Gi¶ sö ph¶n chøng r»ng ph©n ho¹ch nh− thÕ tån t¹i. Khi ®ã

tæng tÊt c¶ c¸c sè cña mçi tËp con b»ng hai lÇn sè lín nhÊt. Suy ra tæng tÊt

c¶ c¸c sè cña tËp hîp {1, 2, 3, . . . , 1997} lµ mét sè ch½n. MÆt kh¸c, ta cã

d•y c¸c sè 1, 2, 3, . . . , 1997 lËp thµnh 1 cÊp sè céng cã 1997 sè h¹ng víi sè h¹ng ®Çu tiªn lµ u1 = 1 vµ c«ng sai lµ d = 1. Suy ra

1 + 2 + 3 + . . . + 1997 = = 1997999, 1997.1998 2

®©y lµ mét sè lÎ, m©u thuÉn. Tõ ®©y ta suy ra ph©n ho¹ch nh− thÕ kh«ng

tån t¹i.

2.3.2 Bµi to¸n. Chøng minh r»ng víi ph©n ho¹ch bÊt k× tËp hîp X =

{1, 2, 3, . . . , 100} thµnh 7 tËp con, lu«n tån t¹i Ýt nhÊt 1 tËp con chøa 4

phÇn tö ph©n biÖt a, b, c, d sao cho a + b = c + d hoÆc chøa 3 sè ph©n biÖt

e, f, g sao cho e + f = 2g.

Chøng minh. V× 14.7 = 98 < 100 nªn tån t¹i Ýt nhÊt 1 tËp con T cña X cã

Ýt nhÊt 15 phÇn tö. Chóng ta xÐt tÊt c¶ c¸c hiÖu a − b víi a, b thuéc T vµ a > b. Ta cã C2 15 = 105 hiÖu nh− vËy. C¸c hiÖu nh− thÕ nhËn gi¸ trÞ thuéc tËp hîp {1, 2, 3, . . . , 99}. Do ®ã tån t¹i Ýt nhÊt 2 cÆp (x, y), (u, v) ph©n biÖt

tháa m•n x − y = u − v > 0. NÕu x, y, u, v lµ 4 sè ph©n biÖt th× ta cã

x + v = u + y, suy ra ®iÒu ph¶i chøng minh. NÕu x = v th× y + u = 2x

hoÆc nÕu y = u, do ®ã ta cã x + v = 2y.

33

2.3.3 Bµi to¸n. Gi¶ sö tæng cña 2 sè nguyªn a, b kh«ng chia hÕt cho 3. Chøng minh r»ng kh«ng thÓ chia tËp sè nguyªn Z thµnh 3 líp ®«i mét rêi nhau sao cho mçi t ∈ Z th× 3 sè sau t, t + a, t + b thuéc 3 líp ph©n biÖt.

Chøng minh. : Gi¶ sö ph¶n chøng cã ph©n ho¹ch Z = T1 ∪ T2 ∪ T3 tháa m•n yªu cÇu cña bµi to¸n. Ta kÝ hiÖu xΩy nÕu x, y thuéc cïng 1 líp ph©n

ho¹ch. Bé 3 sè nguyªn (a, b, c) ®−îc gäi lµ bé tèt nÕu a, b, c thuéc 3 líp

ph©n ho¹ch.

Tõ gi¶ thiÕt (x, x + a, x + b) lµ bé tèt v× x, x + a, x + b thuéc 3 líp ph©n

ho¹ch. T−¬ng tù cho t = x + a, t = x + b ta cã c¸c bé tèt

(x + a, x + 2a, x + a + b), x + b, x + 2b, x + a + b). Khi ®ã

xΩ(x+a+b), cho x = 0 th× 0Ω(a+b) vµ cho x = a+b suy ra (a+b)Ω2(a+b)

TiÕp tôc, ta cã 0Ωp(a + b) víi mäi p ∈ Z (∗). MÆt kh¸c, (x + a, x + 2a, x + a + b) lµ bé tèt vµ (x + a + b)Ωx nªn

(x, x + a, x + 2a) lµ bét tèt, cho x = 0 suy ra (0, a, 2a) lµ bé tèt vµ cho

x = a suy ra (a, 2a, 3a) lµ bé tèt, tõ ®ã 0Ω3a.

MÆt kh¸c (3a, 4a, 5a), (4a, 5a, 6a) lµ bé tèt nªn 3aΩ6a vµ 0Ωqa khi vµ

chØ khi q chia hÕt cho 3 (∗∗). KÕt hîp (∗) víi (∗∗), ta cã tæng sè a + b

ph¶i chia hÕt cho 3, ®iÒu nµy m©u thuÉn víi gi¶ thiÕt.

2.3.4 Bµi to¸n. T×m sè m nhá nhÊt sao cho ph©n ho¹ch bÊt k× tËp hîp {1, 2, 3, . . . , m} thµnh 2 líp T1, T2 th× lu«n tån t¹i 1 líp cã chøa 3 sè ph©n biÖt x < y < z sao cho x + z = 2y

Chøng minh. : Víi m = 4, ta cã: {1, 2, 3, 4} = {2} ∪ {1, 3, 4}. C¶

hai líp nµy ®Òu kh«ng tháa m•n yªu cÇu cña bµi to¸n. XÐt m = 5,

ta cã {1, 2, 3, 4, 5} = {2, 3} ∪ {1, 4, 5} kh«ng tháa m•n yªu cÇu cña bµi

to¸n. XÐt m = 6, ta cã {1, 2, 3, 4, 5, 6} = {2, 5, 6} ∪ {1, 3, 4} kh«ng

tháa m•n yªu cÇu cña bµi to¸n. XÐt m = 7, ta cã {1, 2, 3, 4, 5, 6, 7} =

{1, 2, 4, 5} ∪ {3, 6, 7} kh«ng tháa m•n yªu cÇu cña bµi to¸n. XÐt m = 8, ta

34

cã {1, 2, 3, 4, 5, 6, 7, 8} = {1, 4, 5, 8} ∪ {2, 3, 6, 7} kh«ng tháa m•n yªu cÇu

cña bµi to¸n.

XÐt m = 9, ta gi¶ sö ph¶n chøng lµ tån t¹i ph©n ho¹ch {1, 2, 3, 4, 5, 6, 7, 8, 9} =

T1 ∪ T2 mµ c¶ 2 líp T1, T2 kh«ng tháa m•n yªu cÇu cña bµi to¸n (gi¶ sö ph¶n chøng m = 9 kh«ng tháa m•n yªu cÇu cña bµi to¸n). Do vai trß cña 2 líp T1, T2 nh− nhau nªn ta chØ xÐt 2 tr−êng hîp sau ®©y:

Tr−êng hîp 1: (1, 9) ⊆ T1 suy ra 1 + 9 2

= 5 kh«ng thuéc T1 nªn 5 thuéc T2. Tõ ®ã 3, 7 kh«ng ®ång thêi thuéc T2 (nÕu ng−îc l¹i 3+7=2.5) suy ra ph¶i Ýt nhÊt cã 1 sè thuéc T1. Gi¶ sö 3 ∈ T1 suy ra

= 2 ∈ T2, = 6 ∈ T2, = 4 ∈ T1, (5, 6) ⊆ T2, 3 + 9 2 6 + 2 2 3 + 1 2

suy ra 7 ∈ T1 vµ (1, 4, 7) ∈ T1 (m©u thuÉn). Gi¶ sö 7 ∈ T1 suy ra

= 8 ∈ T2, = 4 ∈ T2, = 6 ∈ T1, (6, 7) ⊆ T1, 7 + 1 2 4 + 8 2 7 + 9 2

suy ra 5 ∈ T2, (5, 4) ∈ T2, 3 ∈ T1 vµ (3, 6, 9) ∈ T1 (m©u thuÉn).

= 8 ∈ T1. Ta cã (3, 4) ∈ T2 suy ra 2 ∈ T1 vµ (2, 5, 8) ∈ T1 (m©u

Tr−êng hîp 2: 1 ∈ T1, 9 ∈ T2, gi¶ sö 5 ∈ T1 suy ra (1, 5) ⊆ T1 vµ 3 ∈ T2, 9 ∈ T2 vµ (1, 3, 5), (1, 5, 9) lËp thµnh mét cÊp sè céng nªn 9 + 3 = 6 ∈ T1, (5, 6) ∈ T1 suy ra 4 ∈ T2, 7 ∈ T2 mµ 7, 9 ∈ T2 nªn 2 7 + 9 2 thuÉn).

= 2 ∈ T2, (6, 7) ∈ T1, suy ra 8 ∈ T2 vµ (2, 5, 8) ∈ T2 (m©u thuÉn) Gi¶ sö 5 ∈ T2 ta suy ra (9, 5) ∈ T2 vµ (3, 6) ∈ T1 mµ 1, 3 ∈ T1 suy ra 1 + 3 2 nªn sè m nhá nhÊt cÇn t×m lµ 9.

2.3.5 Bµi to¸n. Ph©n ho¹ch T1, T2, T3, . . . , Tn cña tËp hîp X ®−îc gäi lµ c©n b»ng theo sè phÇn tö nÕu mçi líp cã sè phÇn tö b»ng nhau. Ph©n

ho¹ch ®−îc gäi lµ c©n b»ng tæng nÕu tæng c¸c phÇn tö cña mçi líp lµ b»ng

35

nhau. Hái cã tån t¹i 1 ph©n ho¹ch tËp hîp {1, 2, 3, . . . , nk} thµnh k líp

võa c©n b»ng sè phÇn tö võa c©n b»ng tæng. NÕu tån t¹i th× ta gäi gi¶ thiÕt

H(n, k) ®óng.

Chøng minh. Ta sÏ chøng minh gi¶ thiÕt H(n, k) ®óng khi n lµ sè ch½n.

ThËt vËy gi¶ sö H(2, k), n = 2 ®óng v× ta cã ph©n ho¹ch

{1, 2, 3, . . . , 2k} = {1, 2k} ∪ {2, 2k − 1} ∪ {3, 2k − 2} ∪ . . . ∪ {k, k + 1}

lµ ph©n ho¹ch c©n b»ng v× c©n b»ng theo sè phÇn tö vµ c©n b»ng theo tæng.

Ta xÐt H(2m, k) ®óng v×

{1, 2, 3 . . . , 2mk} = {1, 2mk} ∪ {2, 2mk − 1} ∪ . . . ∪ {mk, mk + 1}.

Ta kÝ hiÖu c¸c líp sau ®©y:

T1 = {1, 2mk} ∪ {2, 2mk − 1} ∪ . . . ∪ {m, 2mk − m + 1} T2 = {m+1, 2mk −m}∪{m+2, 2mk −m−1}∪. . . ∪{2m, 2mk −2m+1} Tk = {m(k − 1) + 1, 2mk − m(k − 1)} ∪ . . . ∪ {mk, mk + 1} ta thu ®−îc {1, 2, 3 . . . , 2mk} = T1 ∪ T2 ∪ T3 ∪ . . . ∪ Tk. Khi ®ã c¸c Ti ®Òu cã 2m phÇn tö vµ tæng c¸c sè cña mçi Ti ®Òu b»ng m(2mk + 1) vµ gi¶ thiÕt H(2m, k) ®óng.

Víi mäi n > 3 lÎ th× gi¶ thiÕt H(3, k) ®óng suy ra H(n, k) ®óng. ThËt

vËy, gi¶ sö ta cã T1, T2, . . . , Tn lµ ph©n ho¹ch c©n b»ng theo tæng vµ theo sè phÇn tö. NÕu n > 3 lµ sè lÎ th× n−3 lµ sè ch½n. Khi ®ã ta cã mét ph©n ho¹ch

c©n b»ng theo tæng vµ theo sè phÇn tö cña tËp hîp {1, 2, 3, . . . (n−3)k} thµnh k líp X1, X2, . . . , Xk. B©y giê ta thªm vµo c¸c líp Xi ®Ó nhËn ®−îc mét ph©n ho¹ch {1, 2, 3, . . . , nk} tõ {(n−3)k+1, (n−3)k+2, . . . , nk}. TËp hîp

sau gåm 3k sè {(n−3)k+1, (n−3)k +2, . . . , nk} nªn theo gi¶ thiÕt qui n¹p

cã thÓ ph©n ho¹ch thµnh k líp, mçi líp cã 3 phÇn tö cã tæng c¸c phÇn tö cña mçi líp b»ng nhau {(n − 3)k + 1, (n − 3)k + 2, . . . , nk} = Y1 ∪ Y2 ∪ . . . ∪ Yk.

36

Khi ®ã tËp hîp sau cã thÓ ph©n ho¹ch thµnh k líp sau ®©y

{1, 2, 3 . . . , nk} = {X1 ∪ Y1} ∪ {X2 ∪ Y2} ∪ . . . ∪ {Xk ∪ Yk}

(®iÒu ph¶i chøng minh).

2.3.6 Bµi to¸n. Chøng minh r»ng víi ph©n ho¹ch bÊt k× tËp hîp {1, 2, 3, . . . , 3n}

thµnh 3 líp, mçi líp cã n phÇn tö th× chóng ta cã thÓ chän tõ mçi líp 1 sè

sao cho 1 trong 3 sè b»ng tæng 2 sè cßn l¹i.

Chøng minh. : Ta xÐt 1 ph©n ho¹ch A, B, C. Ta cã sè phÇn tö cña mçi líp

A, B, C b»ng nhau vµ b»ng n. Kh«ng gi¶m tÝnh tæng qu¸t ta cã thÓ m« t¶

ph©n ho¹ch nh− sau: 1 ∈ A vµ {1, 2, 3, . . . , k − 1} ⊆ A, k ∈ B. C¸c phÇn

tö cßn l¹i cña A, B, C sÏ ®−îc ph©n bè tiÕp tïy theo c¸c ph©n ho¹ch kh¸c

nhau. Ta gäi (a, b, c) ∈ (A, B, C) lµ bé tèt nÕu cã 1 sè b»ng tæng cña 2 sè

cßn l¹i.

Ta gi¶ thiÕt ph¶n chøng lµ kh«ng tån t¹i bé tèt vµ ta chøng minh kh¼ng

®Þnh lµ víi mäi c ∈ C ta cã c − 1 ∈ A, víi môc ®Ých lµ chØ ra sè phÇn tö

cña C nhá h¬n sè phÇn tö cña A ®Ó suy ra m©u thuÉn v× sè phÇn tö cña C

vµ cña A b»ng nhau vµ b»ng n. Ta gi¶ sö c − 1 kh«ng thuéc A, ta chän gi¸

trÞ c nhá nhÊt trong c¸c gi¸ trÞ mµ c − 1 kh«ng thuéc A. NÕu c − 1 ∈ B

th× (1, c − 1, c) lµ bé tèt tháa m•n gi¶ thiÕt, suy ra c − 1 kh«ng thuéc B.

V× c − 1 kh«ng thuéc A vµ c − 1 kh«ng thuéc B nªn c − 1 ∈ C. NÕu

c − k ∈ A th× (c − k, k, c) lµ bé tèt (m©u thuÉn) nªn c − k kh«ng thuéc A.

NÕu c − k ∈ B th× (k − 1, c − k, c − 1) lµ bé tèt (m©u thuÉn) nªn c − k

kh«ng thuéc B, suy ra c − k ∈ C. H¬n n÷a c nhá nhÊt ®Ó c − 1 kh«ng

thuéc A suy ra c − k − 1 thuéc A vµ (c − k − 1, k, c − 1) lµ bé tèt.

Tõ ®ã kh¼ng ®Þnh trªn lµ ®óng, ¸p dông kh¼ng ®Þnh trªn ta cã sè phÇn tö

cña C nhá h¬n hoÆc b»ng sè phÇn tö cña A. MÆt kh¸c theo qui t¾c t−¬ng

øng, ta cã 2 kh«ng thuéc C mµ 2 − 1 = 1 ∈ A nªn sè phÇn tö cña C nhá

h¬n sè phÇn tö cña A (m©u thuÉn) nªn suy ra ®iÒu ph¶i chøng minh.

37

2.3.7 Bµi to¸n. Trong tËp hîp n sè nguyªn d−¬ng ph©n biÖt. XÐt tÊt c¶ c¸c

tæng cña c¸c phÇn tö trong mçi tËp con kh«ng rçng cña nã. Chøng minh 2n − 1 sè nµy cã thÓ chia thµnh n líp sao cho trong mçi líp nµy tû sè gi÷a sè lín nhÊt vµ sè nhá nhÊt lu«n nhá h¬n hoÆc b»ng 2.

Chøng minh. : Tr−íc hÕt, ta ®• biÕt sè tËp con kh«ng rçng cña mét tËp hîp gåm n phÇn tö lµ 2n − 1. Mçi tËp con th× cho ta mét tæng c¸c phÇn tö cña tËp con ®ã. Do ®ã chóng ta cã tÊt c¶ 2n − 1sè lµ c¸c tæng trªn.

B©y giê, ta kÝ hiÖu c¸c sè ®• cho lµ x1, x2, x3, . . . , xn tháa m•n ®iÒu kiÖn

mk = (x1 + x2 + x3 + . . . + xk), x1 < x2 < x3 < . . . < xn vµ kÝ hiÖu c¸c tæng sau ®©y 1 2

Mk = x1 + x2 + x3 + . . . + xk, 1 6 k 6 n.

Víi mçi k ta gäi c¸c líp Tk gåm nh÷ng tæng S (cña cac sè cña tËp con nµo ®ã) tháa m•n bÊt ®¼ng thøc mk < S < Mk (∗)

6 Gäi S1, S2 lÇn l−ît lµ tæng nhá nhÊt vµ tæng lín nhÊt cña c¸c phÇn tö = 2. trong mçi tËp con. NÕu mk 6 S1 6 S2 6 Mk th× ta cã tû sè Mk mk S2 S1

Suy ra trong mçi líp Tk tû sè gi÷a sè gi÷a sè lín nhÊt vµ sè nhá nhÊt lu«n nhá h¬n hoÆc b»ng 2. §èi víi nh÷ng tæng S tháa m•n ®iÒu kiÖn (∗)

víi nhiÒu chØ sè k ta chän 1 chØ sè k duy nhÊt. VËy ta cã Ti ∩ Tk = ∅, mäi i 6= k. Ta chøng minh mäi tæng S sÏ r¬i vµo 1 trong c¸c líp Tk ë trªn, 1 6 k 6 n.

ThËt vËy, ta gi¶ sö ph¶n chøng lµ tån t¹i 1 tæng S mµ S kh«ng thuéc Tk, 1 6 k 6 n. Ta cã Mk ∈ Tk suy ra S kh¸c Mk, 1 6 k 6 n. Ta l¹i cã M1 < S < Mn nªn tån t¹i k tháa m•n Mk < S < Mk+1. V× S > Mk nªn S = (x1 + x2 + . . . + xk) + xk+1 + . . . + xi. Tõ ®ã S > xi, i > k. Suy ra 2S > xi + Mk ≥ xk+1 + Mk = Mk+1. Khi ®ã 2S > Mk+1 = 2mk+1 suy ra S > mk+1 vµ mk+1 < S < Mk+1 suy ra S ∈ Tk+1. §iÒu nµy m©u thuÉn víi gi¶ thiÕt ph¶n chøng.

38

KÕt luËn

LuËn v¨n tr×nh bµy mét c¸ch hÖ thèng nh÷ng kÕt qu¶ c¬ b¶n cña lÝ thuyÕt

ph©n ho¹ch tËp hîp vµ øng dông gi¶i c¸c bµi s¬ cÊp trong ®¹i sè tæ hîp,

x¸c xuÊt thèng kª, trong h×nh häc s¬ cÊp, v.v.

C¸c kÕt qu¶ ®¹t ®−îc trong luËn v¨n nµy nh− sau.

- Tr×nh bµy c¸c kh¸i niÖm vµ tÝnh chÊt c¬ b¶n cña phÐp ph©n ho¹ch tËp

hîp, chØ râ mèi quan hÖ gi÷a phÐp ph©n ho¹ch tËp hîp vµ quan hÖ t−¬ng

®−¬ng.

- Tr×nh bµy c«ng thøc tÝnh sè ph©n ho¹ch mét tËp hîp gåm n phÇn tö

(kÝ hiÖu lµ sè Bell Bn), c«ng thøc tÝnh sè Stirling lo¹i 2 (kÝ hiÖu lµ S(n, k)) xuÊt hiÖn nhiÒu trong c¸c bµi to¸n tæ hîp, x¸c suÊt thèng kª.

- Tr×nh bµy mét sè øng dông cña lý thuyÕt phÐp ph©n ho¹ch tËp hîp

trong to¸n s¬ cÊp. Cô thÓ lµ gi¶i mét sè bµi to¸n liªn quan ®Õn ph©n ho¹ch

ch½n, ph©n ho¹ch lÎ, ph©n ho¹ch tËp hîp sè, ®¹i sè tæ hîp, x¸c suÊt thèng

kª hay h×nh häc s¬ cÊp.

Dùa vµo sù ph¸t triÓn cña c«ng nghÖ th«ng tin, m¸y tÝnh hay phÇn mÒm

Maple ®Ó cã thÓ tÝnh xÊp xØ hoÆc ®¸nh gi¸ cËn cña c¸c sè Bell cña tËp hîp

víi sè phÇn tö lín. Trong t−¬ng lai ch¾c ch¾n sÏ cßn nhiÒu kÕt qu¶ cô thÓ

h¬n vÒ sè Stirling lo¹i 2 hay sè Bell còng nh− thÊy ®−îc nhiÒu øng dông

s©u s¾c cña phÐp ph©n ho¹ch tËp hîp trong to¸n häc nãi chung vµ to¸n s¬

cÊp nãi riªng.

Tµi liÖu tham kh¶o

[An] G. E. Andrews, The theory of partitions, Cambridge University Press,

1998.

[B1] E. T. Bell, Exponential polynomials, Annals of Mathematics 35 (1934),

258-277.

[B2] E. T. Bell, The iterated exponential integer, Annals of Mathematics 39

(1938), 539-557.

[BT] D. Berend and T. Tassa, Improved bounds on Bell numbers and on moments of sums of random variables, Probability and Mathematical Statistics 30 (2010), 185-205.

[Ca] D. Callan, A combinatorial interpretation of the eigensequence for

composition, Journal of Integer Sequences 9 (2006), 06-14.

[Ha] R. Hankin, Set partitions in R, Journal of Statistical Software, Code

Snippets, 23 (2007).

[K] E. D. Knuth, ”Two thousand years of combinatorics”, Oxford Univer-

sity Press 2013, pp. 7-37.

39

[TBM] Hamzeh Torabi, J. Behboodian and S. M. Mirhosseini, On the num- ber of partitions of sets and natural numbers, Appl. Math. Sci. 33 (2009), 1635 - 1646.