Luận văn Thạc sĩ Toán học: Quan hệ hai ngôi và một số bài toán liên quan

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:43

Thêm vào BST

Báo xấu

28
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nội dung chính của luận văn trình bày một số kiến thức về lý thuyết quan hệ hai ngôi, quan hệ tương đương, quan hệ thứ tự, quan hệ ánh sáng và mở đầu lý thuyết về tổ hợp. Mời các bạn tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Toán học: Quan hệ hai ngôi và một số bài toán liên quan

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- BÙI THỊ THU THỦY QUAN HỆ HAI NGÔI VÀ MỘT SỐ BÀI TOÁN LIÊN QUAN LUẬN VĂN THẠC SĨ TOÁN HỌC THÁI NGUYÊN - 2019
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC KHOA HỌC --------------------------- BÙI THỊ THU THỦY QUAN HỆ HAI NGÔI VÀ MỘT SỐ BÀI TOÁN LIÊN QUAN Chuyên ngành: Phương pháp Toán sơ cấp Mã số: 8 46 01 13 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC TS. Trần Nguyên An THÁI NGUYÊN - 2019
Möc löc Mð ¦u . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 Ch÷ìng 1. Ki¸n thùc chu©n bà . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1. Quan h» hai ngæi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2. ¤i sè tê hñp. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 Ch÷ìng 2. Quan h» hai ngæi v mët sè b i to¡n. . . . . . . . . . . . . 15 2.1. ¸m mët sè quan h» hai ngæi °c bi»t . . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.2. nh x¤ v mët sè b i to¡n li¶n quan. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 2.3. Ph¥n ho¤ch, sè Stirling lo¤i hai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.4. ¸m sè quan h» t÷ìng ÷ìng v quan h» hai ngæi bc c¦u . . . . . . 32 K¸t luªn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 T i li»u tham kh£o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 i
Mð ¦u Cho A, B l c¡c tªp hñp. Mët quan h» hai ngæi tø tªp A ¸n tªp B l mët tªp con cõa tªp t½ch · c¡c A × B . °c bi»t, mët quan h» hai ngæi tø A ¸n A ÷ñc gåi l mët quan h» hai ngæi tr¶n A. N¸u R l mët quan h» hai ngæi tr¶n tªp A v (a, b) ∈ R th¼ ta k½ hi»u aRb (åc l a câ quan h» R vîi b). Quan h» hai ngæi xu§t hi»n trong nhi·u ng nh kh¡c nhau cõa to¡n håc: ¤i sè, Sè håc, H¼nh håc, Lþ thuy¸t ç thà, Khoa håc m¡y t½nh, .... Mët tr÷íng hñp °c bi»t cõa quan h» hai ngæi. C¡c quan h» hai ngæi iºn h¼nh trong ch÷ìng tr¼nh phê thæng l "quan h» chia h¸t", "quan h» çng d÷", "quan h» lîn hìn", "quan h» song song", h m sè, .... Ta th÷íng quan t¥m ¸n c¡c t½nh ch§t sau cõa quan h» hai ngæi ph£n x¤ (reflexive), èi xùng (symmetric), bc c¦u (transitive), b§t èi xùng (asymmetric), ph£n èi xùng (antisymmetric), b§t ph£n x¤ (irreflexive). Möc ½ch ch½nh cõa luªn v«n l t¼m hiºu mët sè b i to¡n tê hñp v· quan h» hai ngæi. T i li»u ch½nh cõa luªn v«n l gi£i mët sè b i tªp trong [7], [2] v b i b¡o [6]. Luªn v«n ÷ñc chia l m hai ch÷ìng. Ch÷ìng 1 tr¼nh b y mët sè ki¸n thùc chu©n bà v· lþ thuy¸t quan h» hai ngæi, quan h» t÷ìng ÷ìng, quan h» thù tü, ¡nh x¤ v mð ¦u v· lþ thuy¸t tê hñp. Tuy l ki¸n thùc chu©n bà cho Ch÷ìng 2 nh÷ng èi vîi t¡c gi£ nhi·u ki¸n thùc cõa ch÷ìng l ki¸n thùc mîi v câ nhi·u ùng döng trong gi£i to¡n phê thæng. Ch÷ìng n y chõ y¸u tham kh£o theo c¡c t i li»u [1, 2]. Ch÷ìng 2 theo t i li»u [6, 7] l ch÷ìng ch½nh cõa luªn v«n tr¼nh b y v· mët sè b i to¡n li¶n quan ¸n quan h» hai ngæi. Bt ¦u l b i to¡n ¸m mët sè quan h» hai ngæi °c bi»t. Công c¦n ph£i nâi th¶m r¬ng quan h» hai ngæi xu§t ph¡t tø nhúng v§n · trong to¡n sì c§p nh÷ "lþ thuy¸t chia h¸t", "lþ thuy¸t çng d÷" nh÷ng v¼ khuæn khê cõa luªn v«n t¡c gi£ ch¿ khai th¡c mët sè b i to¡n sì c§p li¶n quan ¸n b i to¡n tê hñp. Mët l÷u þ cõa luªn 1
v«n l t¡c gi£ cè gng t¼m hiºu nhi·u c¡ch gi£i, c¡ch ti¸p cªn kh¡c nhau cõa mët b i to¡n, mët v§n ·. ¸m quan h» hai ngæi l ¡nh x¤ v c¡c tr÷íng hñp °c bi»t (ìn ¡nh, song ¡nh, to n ¡nh) ÷ñc tr¼nh b y trong möc thù hai cõa ch÷ìng. Vi»c nghi¶n cùu sè to n ¡nh gñi þ cho ta t¼m hiºu sè Stirling lo¤i hai v b i to¡n ¸m sè ph¥n ho¤ch mët tªp hñp. V§n · n y ÷ñc tr¼nh b y trong möc thù ba cõa ch÷ìng. Möc cuèi cõa ch÷ìng t¼m hiºu sè quan h» t÷ìng ÷ìng, sè quan h» bc c¦u (li¶n h» vîi quan h» thù tü) theo b i b¡o [6]. Chó þ r¬ng sè quan h» t÷ìng ÷ìng tr¶n tªp n ph¦n tû ch½nh l sè ph¥n ho¤ch, sè Bell thù n. Trong qu¡ tr¼nh l m luªn v«n, tæi nhªn ÷ñc sü h÷îng d¨n v gióp ï tªn t¼nh cõa TS. Tr¦n Nguy¶n An - Tr÷íng ¤i håc S÷ ph¤m - ¤i håc Th¡i Nguy¶n. Tæi xin ÷ñc b y tä láng bi¸t ìn s¥u sc ¸n th¦y. Tæi xin gûi líi c£m ìn ch¥n th nh ¸n quþ th¦y cæ gi£ng d¤y lîp Cao håc khâa Cao håc To¡n khâa 11B (2017-2019) - tr÷íng ¤i håc Khoa håc - ¤i håc Th¡i Nguy¶n, ¢ truy·n thö ¸n cho tæi nhi·u ki¸n thùc v kinh nghi»m nghi¶n cùu khoa håc. Líi cuèi còng, t¡c gi£ muèn d nh º tri ¥n bè mµ v gia ¼nh v¼ ¢ chia s´ nhúng khâ kh«n º t¡c gi£ ho n th nh cæng vi»c håc tªp cõa m¼nh. Th¡i Nguy¶n, ng y 28 th¡ng 10 n«m 2019 T¡c gi£ Bòi Thà Thu Thõy 2
Ch÷ìng 1 Ki¸n thùc chu©n bà 1.1. Quan h» hai ngæi ành ngh¾a 1.1.1. Mët quan h» hai ngæi tø tªp A ¸n tªp B l mët tªp con cõa tªp t½ch · c¡c A × B . °c bi»t, mët quan h» hai ngæi tø A ¸n A ÷ñc gåi l mët quan h» hai ngæi tr¶n A. Nâi c¡ch kh¡c, mët quan h» hai ngæi tr¶n mët tªp A l mët tªp con cõa tªp A2. Ta th÷íng k½ hi»u c¡c quan h» hai ngæi b¬ng c¡c chú c¡i R (hay S, T, U, V, . . .). N¸u R l mët quan h» hai ngæi tr¶n tªp A v (a, b) ∈ R th¼ ta k½ hi»u aRb (åc l a câ quan h» R vîi b, ho°c nâi tt l a R b). Khi / R th¼ ta vi¸t aRb (åc l a khæng câ quan h» R vîi b). Ta th÷íng (a, b) ∈ quan t¥m ¸n c¡c t½nh ch§t sau cõa quan h» hai ngæi. ành ngh¾a 1.1.2. Gi£ sû R ⊆ A × A l quan h» hai ngæi. Quan h» hai ngæi R ÷ñc gåi l (i) Ph£n x¤ (reflexive) n¸u ∀a ∈ A, ((a, a) ∈ R); (ii) èi xùng (symmetric) n¸u ∀a, b ∈ A, ((a, b) ∈ R th¼ (b, a) ∈ R); (iii) Bc c¦u (transitive) n¸u ∀a, b, c ∈ A, ((a, b) ∈ R ∧ (b, c) ∈ R th¼ (a, c) ∈ R); (iv) B§t èi xùng (asymmetric) n¸u ∀a, b ∈ A, ((a, b) ∈ R th¼ (b, a) ∈/ R); (v) Ph£n èi xùng (antisymmetric) n¸u ∀a, b ∈ A, [((a, b) ∈ R∧(b, a) ∈ R) th¼ a = b]; (vi) B§t ph£n x¤ (irreflexive) n¸u ∀a ∈ A, ((a, a) ∈/ R). V½ dö 1.1.3. Cho A = {1, 2, 3}. X²t c¡c quan h» R1 = {(1, 1), (2, 2), (3, 3)}, 3
R2 = {(1, 1), (1, 2), (1, 3)}, R3 = A × A, R4 = {(2, 2), (3, 3), (1, 2)}. Ta câ vîi T kþ hi»u True, F kþ hi»u False. R1 R2 R3 R4 Ph£n x¤ T F T F èi xùng T F T F Bc c¦u T T T T V½ dö 1.1.4. Cho A = {1, 2, 3, 4}. X²t c¡c quan h». R1 = {(1, 1), (2, 2), (3, 3), (2, 1), (4, 3), (3, 2)}, R2 = A × A, R3 = {(1, 1), (2, 2), (3, 3), (2, 1), (4, 3), (4, 1), (3, 2)}, R4 = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 2), (2, 1), (4, 3), (3, 4)}. PX X PX X BPX BC R1 F F F T F F R2 T T F F F T R4 T T F T F T R5 T T F F F T Chó þ ta vi¸t tt: PX = Ph£n x¤, X = èi xùng, PX = Ph£n èi xùng, BPX = B§t ph£n x¤, BC = Bc c¦u. ành ngh¾a 1.1.5. (i) Mët quan h» hai ngæi tr¶n tªp A ÷ñc gåi l quan h» t÷ìng ÷ìng n¸u nâ câ c¡c t½nh ch§t ph£n x¤, èi xùng v bc c¦u. Theo truy·n thèng, c¡c quan h» t÷ìng ÷ìng th÷íng ÷ñc k½ hi»u bði d§u ∼ . (ii) Cho ∼ l mët quan h» t÷ìng ÷ìng tr¶n tªp A. Vîi méi a ∈ A, ta gåi lîp t÷ìng ÷ìng cõa a èi vîi quan h» t÷ìng ÷ìng ∼, k½ hi»u bði [a]∼ (hay [a], hay a, hay C(a)), â l mët tªp con cõa A ÷ñc x¡c ành bði [a] = {b ∈ A | b ∼ a}. çng thíi, tªp hñp t§t c£ c¡c lîp t÷ìng ÷ìng cõa c¡c ph¦n tû trong A ÷ñc gåi l tªp th÷ìng cõa A theo quan h» t÷ìng ÷ìng ∼, v ÷ñc k½ hi»u l A/ ∼ . Nh÷ vªy, ta câ biºu di¹n A/ ∼ = {[a] | a ∈ A}. V½ dö 1.1.6. Cho m l mët sè tü nhi¶n lîn hìn 1. Tr¶n tªp Z c¡c sè nguy¶n ta ành ngh¾a quan h» hai ngæi R nh÷ sau: vîi måi a, b ∈ Z, ta nâi aRb ⇔ m|(a − b). 4
Quan h» n y ÷ñc gåi l quan h» çng d÷ theo mæun m (hay cán gåi l quan h» çng d÷ modulo m). Khi a çng d÷ b theo mæun m, ta th÷íng k½ hi»u l a ≡ b (mod m). Ta th§y â l mët quan h» t÷ìng ÷ìng tr¶n tªp Z. Vîi a ∈ Z, lîp t÷ìng ÷ìng cõa a ÷ñc k½ hi»u bði a, v ÷ñc gåi l mët lîp th°ng d÷ theo mæun m vîi ¤i di»n l a. Tªp th÷ìng cõa Z èi vîi quan h» çng d÷ modulo m ÷ñ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 hñp c¡c lîp th°ng d÷ modulo m). Cho a ∈ Z, khi â ta câ a = {b ∈ Z | b ≡ a (mod m)} = {b ∈ Z | b − a chia h¸t cho m}. Vîi méi a ∈ Z ¢ cho, ta luæn câ biºu di¹n a = mq+r trong â 0 ≤ r ≤ m−1 (theo ành lþ ph²p chia vîi d÷). Khi â b − a = b − mq − r, n¶n ta câ a = {b ∈ Z | b−mq−r chia h¸t cho m} = {b ∈ Z | b−r chia h¸t cho m} = r. Hìn núa, vîi måi sè tü nhi¶n i, j sao cho 0 ≤ i < j ≤ m − 1 ta luæn câ 0 < j − i < m n¶n j − i khæng chia h¸t cho m. Do â i 6≡ j (mod m), n¶n i 6= j. V¼ th¸ tªp Zm gçm m ph¦n tû æi mët kh¡c nhau nh÷ sau: Zm = {0, 1, . . . , m − 1}. Chó þ r¬ng n¸u a = mq + r th¼ a = r. V¼ th¸ vîi q1, . . . , qm l m sè nguy¶n tuý þ ta luæn câ Zm = {q1 m, q2 m + 1, . . . , qm m + m − 1}. Ch¯ng h¤n Z3 = {0, 1, 2} = {6, −2, 8}. ành lþ d÷îi ¥y cho ta þ ngh¾a cõa c¡c quan h» t÷ìng ÷ìng. Tr÷îc khi ph¡t biºu ành lþ, chóng ta c¦n kh¡i ni»m sau. ành ngh¾a 1.1.7. Cho A l mët tªp hñp. Ta gåi mët ph¥n ho¤ch (hay mët sü chia lîp) tr¶n A l mët ph²p ph¥n chia tªp A th nh mët hå c¡c tªp con kh¡c réng {Ai}i∈I tho£ m¢n c¡c i·u ki»n: (i) Ai ∩ Aj = ∅ vîi måi i, j ∈ I, i 6= j. (ii) A = Ai. S i∈I 5
ành lþ 1.1.8. Cho A l mët quan h» t÷ìng ÷ìng tr¶n tªp A. Khi â c¡c ph¡t biºu sau l óng. (i) [a] 6= ∅ vîi måi a ∈ A. (ii) A = [a]. S a∈A (iii) [a] = [b] ho°c [a] ∩ [b] = ∅ vîi måi a, b ∈ A. V¼ th¸ quan h» t÷ìng ÷ìng ∼ x¡c ành mët ph¥n ho¤ch tr¶n A. Ng÷ñc l¤i, n¸u {Ai}i∈I l mët ph¥n ho¤ch tr¶n A th¼ tçn t¤i duy nh§t mët quan h» t÷ìng ÷ìng tr¶n A sao cho méi Ai l mët lîp t÷ìng ÷ìng. ành ngh¾a 1.1.9. (i) Mët quan h» hai ngæi tr¶n mët tªp hñp ÷ñc gåi l quan h» thù tü n¸u nâ câ c¡c t½nh ch§t ph£n x¤, ph£n èi xùng, v bc c¦u. Quan h» thù tü th÷íng ÷ñc k½ hi»u bði d§u "≤" (åc l "nhä hìn ho°c b¬ng"). Khi a ≤ b th¼ ta công vi¸t b ≥ a. (ii) Khi tr¶n mët tªp hñp A câ mët quan h» thù tü ≤ th¼ ta nâi A l mët tªp hñp ÷ñc sp thù tü bði ≤. V½ dö 1. (i) Quan h» nhä hìn ho°c b¬ng ≤ thæng th÷íng (ta ¢ bi¸t ð phê thæng) l quan h» thù tü tr¶n c¡c tªp N, Z, Q, v R. (ii) Quan h» bao h m ⊆ tr¶n tªp 2A (tªp t§t c£ c¡c tªp con cõa A) l mët quan h» thù tü. (iii) Quan h» chia h¸t "|" tr¶n tªp N∗ = N \ {0} l mët quan h» thù tü. (iv) X²t A l tªp con tòy þ cõa tªp N∗. Khi â quan h» chia h¸t "|" tr¶n tªp A công l mët quan h» thù tü tr¶n A. Möc cuèi giîi thi»u lîp quan h» hai ngæi °c bi»t l ¡nh x¤. ành ngh¾a 1.1.10. Cho R l quan h» 2 ngæi tø A ¸n B . Khi â mi·n x¡c ành cõa R (domain of R), kþ hi»u D(R) ÷ñc ành ngh¾a l tªp {x|x ∈ A; ∃y ∈ A, (x, y) ∈ R}. nh cõa R (image of R), kþ hi»u im(R) ÷ñc ành ngh¾a l tªp {y|y ∈ B, ∃x ∈ A, (x, y) ∈ R}. 6
V½ dö 1.1.11. Cho A = {4, 5, 7, 8, 9} v B = {16, 18, 20, 22}, R = {(4, 16), (4, 20), (5, 20), (8, 16), (9, 18)}. Khi â R l quan h» 2 ngæi tø A ¸n B , D(R) = {4, 5, 8, 9}, im(R) = {16, 18, 20}. ành ngh¾a 1.1.12. (i) Cho A, B l c¡c tªp kh¡c réng. Mët quan h» hai ngæi f tø A ¸n B ÷ñc gåi l mët ¡nh x¤ n¸u (1) D(f ) = A (tùc l ∀a ∈ A, ∃b ∈ B, (a, b) ∈ f ), (2) Vîi måi (a, b), (a, b) ∈ f, a = a k²o theo b = b. Mët c¡ch t÷ìng ÷ìng mët ¡nh x¤ f tø tªp A ¸n tªp B l mët quy tc cho t÷ìng ùng méi ph¦n tû a ∈ A vîi mët ph¦n tû duy nh§t b ∈ B. Khi â ta vi¸t f (a) = b, ta gåi b gåi l £nh cõa ph¦n tû a bði ¡nh x¤ f ; v ta gåi a l mët t¤o £nh cõa ph¦n tû b. Tªp A ÷ñc gåi l tªp nguçn, tªp B gåi l tªp ½ch cõa ¡nh x¤ f . º di¹n t£ ¡nh x¤ f nh÷ tr¶n ng÷íi ta k½ hi»u: − B, a 7→ f (a) = b, ho°c f A→ f : A → B, a 7→ f (a) = b, ho°c f :A→B a 7−→ f (a) = b. (ii) Ta quy ÷îc r¬ng câ mët ¡nh x¤ réng tø tªp ∅ ¸n tªp B b§t k¼. (iii) Cho ¡nh x¤ f : A → B, a 7→ f (a). Ta gåi tªp hñp con G(f ) cõa A × B x¡c ành bði G(f ) = {(a, f (a)) | a ∈ A} l ç thà cõa ¡nh x¤ f . (iv) Hai ¡nh x¤ ÷ñc gåi l b¬ng nhau n¸u chóng câ chung nguçn, chung ½ch v chung ç thà. Nâi c¡ch kh¡c, cho f : A → B v g : A0 → B 0 l hai ¡nh x¤, khi â f = g n¸u A = A0, B = B 0 v f (a) = g(a) vîi måi a ∈ A. ành ngh¾a 1.1.13. Cho f : A −→ B, a 7→ b = f (a) l mët ¡nh x¤. (i) f ÷ñc gåi l ìn ¡nh n¸u f (a) = f (a0) k²o theo a = a0 vîi måi a, a0 ∈ A. (ii) f ÷ñc gåi l to n ¡nh n¸u vîi måi b ∈ B k²o theo tçn t¤i a ∈ A º f (a) = b. (iii) f ÷ñc gåi l song ¡nh n¸u nâ vøa l ìn ¡nh vøa l to n ¡nh. 7
1.2. ¤i sè tê hñp ành ngh¾a 1.2.1 (Quy tc cëng). Gi£ sû c¡c vi»c A1, A2, ..., Am câ thº l m t÷ìng ùng b¬ng n1, n2, ...nm c¡ch v gi£ sû khæng câ hai vi»c n o câ thº l m çng thíi. Khi â sè c¡ch l m mët trong m vi»c â l n1 + n2 + ... + nm. Quy tc cëng ÷ñc ph¡t biºu d÷îi d¤ng tªp hñp nh÷ sau. M»nh · 1.2.2. N¸u A1, ..., Am l c¡c tªp hñp húu h¤n æi mët ríi nhau, khi â: |A1 ∪ ... ∪ Am | = |A1 | + ... + |Am−1 | + |Am |. ành ngh¾a 1.2.3 (Quy tc nh¥n). Gi£ sû mët nhi»m vö n o â ÷ñc t¡ch ra l m hai vi»c. Vi»c thù nh§t câ thº l m b¬ng n1 c¡ch, vi»c thù hai câ thº l m b¬ng n2 c¡ch sau khi vi»c thù nh§t ¢ ÷ñc l m, khi â s³ câ n1n2 c¡ch thüc hi»n nhi»m vö n y. Quy tc nh¥n th÷íng ÷ñc ph¡t biºu têng qu¡t b¬ng ngæn ngú tªp hñp nh÷ sau: M»nh · 1.2.4. Cho n tªp hñp húu h¤n A1, A2, ..., An (n ≥ 2). Khi â |A1 × A2 × ... × An | = |A1 |.|A2 |...|An |. Sau ¥y ta nhc l¤i mët sè t½nh ch§t cì b£n cõa tê hñp theo [2]. Cho A1 , . . . , Am l c¡c tªp b§t k¼, S l tªp mët sì ç sp x¸p (câ thº l trüc quan h¼nh håc ho°c câ thº l trøu t÷ñng v ÷ñc mæ t£ d÷îi d¤ng c¡c quy tc sp x¸p), cán R1, . . . , Rn l c¡c i·u ki»n ¢ cho. C¡c i·u ki»n n y °t c¡c r ng buëc l¶n sü sp x¸p c¡c ph¦n tû cõa A1, . . . , Am, theo sì ç S . Khi â mët sp x¸p b§t ký c¡c ph¦n tû cõa A1, . . . , Am theo sì ç S thäa m¢n c¡c i·u ki»n R1, . . . , Rn ÷ñc gåi l mët c§u h¼nh tê hñp tr¶n c¡c tªp A1, . . . , Am. N¸u c¡c ph¦n tû cõa A1, . . . , Am ·u thuëc tªp A th¼ c§u h¼nh tê hñp tr¶n A1 , . . . , Am th÷íng ÷ñc gåi ngn gån l c§u h¼nh tê hñp tr¶n tªp A. V½ dö 2. Gi£ sû A1 l tªp gçm 12 håc sinh nú v A2 l tªp bao gçm 20 håc sinh nam cõa mët lîp; Sì ç sp x¸p S l "3 h ng dåc, méi h ng câ 6 và tr½"; i·u ki»n R1: 3 và tr½ ¦u cõa h ng 1 ph£i l nú, 3 và tr½ sau cõa h ng 1 ph£i l nam; 8
i·u ki»n R2: ð h ng 2, nam v núa ÷ñc x¸p v o c¡c và tr½ xen k³ nhau, nh÷ng và tr½ ¦u ti¶n ph£i l nam; i·u ki»n R2: 3 và tr½ ¦u cõa h ng 3 ph£i l nam, 3 và tr½ sau cõa h ng 3 ph£i l nú; Khi â méi c¡ch sp x¸p th nh h ng cõa c¡c håc sinh tø A1 v A2 theo sì ç S thäa m¢n c¡c i·u ki»n R1, R2, R3 l mët c§u h¼nh tê hñp. Ghi chó 1.2.5 (Ch¿nh hñp câ l°p). Gi£ sû A l mët hñp húu h¤n vîi |A| = n, cán k l mët sè nguy¶n d÷ìng. Ta công gi£ sû A1 , A2 , . . . , Ak l c¡c ph¦n tû cõa A, S l sì ç sp x¸p "bë câ thù tü gçm k th nh ph¦n (x1 , x2 , . . . , xk )", R l i·u ki»n sp x¸p "x1 ∈ A1 , x2 ∈ A2 , . . . , xk ∈ Ak ". Khi â méi c§u h¼nh tê hñp tr¶n A1, A2, . . . , Ak theo S thäa m¢n R ÷ñc gåi l mët ch¿nh hñp câ l°p chªp k cõa n ph¦n tû cõa A. D¹ th§y r¬ng méi ch¿nh hñp câ l°p chªp k cõa n ph¦n tû cõa A câ thº coi l mët ph¦n tû cõa t½ch · c¡c A1 ×. . .×Ak . Do â, n¸u ta kþ hi»u sè ch¿nh hñp câ l°p chªp k cõa n ph¦n tû cõa A b¬ng Akn, th¼ Akn = |A1 ×A2 ×. . .×Ak |. Theo quy tc nh¥n ta câ |A1 × A2 × . . . × Ak | = |A1 ||A2 | . . . |Ak | = nk . V¼ vªy k An = nk . Ghi chó 1.2.6 (Ch¿nh hñp khæng l°p). Gi£ sû A l mët tªp húu h¤n vîi |A| = n, cán k l mët sè nguy¶n d÷ìng. Ta gi£ sû A1 = A, S l sì ç sp x¸p "bë câ thù tü gçm k th nh ph¦n (x1 , x2 , . . . , xk )", R l i·u ki»n sp x¸p "x1 ∈ A1 , x2 ∈ A1 , . . . , xk ∈ A1 ". Khi â méi c§u h¼nh tê hñp tr¶n A1 theo S thäa m¢n tr¶n R ÷ñc gåi l mët ch¿nh hñp khæng l°p chªp k cõa n ph¦n tû cõa A. Ch¿nh hñp khæng l°p th÷íng ìn gi£n ÷ñc gåi l ch¿nh hñp. Kþ hi»n sè c¡c ch¿nh hñp chªp k cõa n ph¦n tû cõa A b¬ng Akn. n! Akn = , n¸u k 6 n. (n − k)! 9
Ghi chó 1.2.7 (Tê hñp khæng l°p). Gi£ sû A l mët tªp húu h¤n vîi |A| = n, cán k l mët sè nguy¶n d÷ìng. Ta gi£ sû A1 = A, S l sì ç sp x¸p "tªp câ k ph¦n tû {x1 , x2 , . . . , xk }", R l i·u ki»n sp x¸p ”x1 ∈ A1 , x2 ∈ A1 , . . . , xk ∈ A1 ”. Khi â méi c§u h¼nh tê hñp tr¶n A1 theo S thäa m¢n R ÷ñc gåi l mët tê hñp khæng l°p chªp k cõa n ph¦n tû cõa A. Tê hñp khæng l°p th÷íng ÷ñc gåi ìn gi£n l tê hñp. Nh÷ vªy, mët tê hñp chªp k cõa n ph¦n tû cõa A câ thº ÷ñc xem nh÷ l mët tªp conlücl÷ñng k cõa A. K½ hi»u sè c¡c tê hñp chªp k cõa n ph¦n tû cõa A b¬ng nk , ( n = n! k!(n−k)! , n¸u 0 6 k 6 n, = k 0, n¸u k > n. Ghi chó 1.2.8 (a tªp). Mët sü tö tªp c¡c vªt câ b£n ch§t tòy þ, trong â câ thº câ nhúng vªt khæng ph¥n bi»t ÷ñc vîi nhau (v câ thº coi nh÷ l sü l°p l¤i cõa còng mët vªt), ÷ñc gåi l a tªp hñp hay ngn gån l a tªp. C¡c vªt trong a tªp công ÷ñc gåi l c¡c ph¦n tû. Ta công dòng c¡c ph÷ìng ph¡p x¡c ành tªp hñp º x¡c ành a tªp. Nh÷ng èi vîi a tªp, ta c¦n x¡c ành sè c¡c ph¦n tû khæng ph¥n bi»t ÷ñc vîi nhau, sè l÷ñng c¡c ph¦n tû cõa mët a tªp A công ÷ñc gåi l lüc l÷ñng cõa A v ÷ñc kþ hi»u l |A|. V½ dö: A = {a, a, a, b, c, c} l mët a tªp vîi |A| = 6. Theo ành ngh¾a, hiºn nhi¶n méi tªp công l a tªp, nh÷ng ng÷ñc l¤i, mët a tªp câ thº khæng l tªp hñp. Ch¯ng h¤n, a tªp A ð tr¶n khæng l tªp hñp. N¸u c¡c ph¦n tû cõa mët a tªp A ·u l ph¦n tû cõa mët tªp B , th¼ ta s³ nâi r¬ng A l a tªp tr¶n B . Ch¯ng h¤n, a tªp A ð tr¶n l mët a tªp tr¶n tªp B = {a, b, c}. Ghi chó 1.2.9 (Tê hñp l°p). Gi£ sû A l mët tªp húu h¤n vîi |A| = n, cán k l mët sè nguy¶n d÷ìng. Ta gi£ sû A1 , A2 , . . . , Ak l c¡c ph¦n tû cõa A, S l sì ç sp x¸p "a tªp câ k ph¦n tû {x1 , x2 , . . . , xk }", 10
R l i·u ki»n sp x¸p ”x1 ∈ A1, x2 ∈ A2, . . . , xk ∈ Ak ”. Khi â, méi c§u h¼nh tê hñp tr¶n A1, A2, . . . , Ak theo S thäa m¢n R ÷ñc gåi l mët tê hñp câ l°p chªp k cõa n ph¦n tû cõa A. Nh÷ vªy, theo ành ngh¾a mët tê hñp câ l°p chªp k cõa n ph¦n tû cõa A câ thº coi l mët a tªp lüc l÷ñng k vîi c¡c ph¦n tû ·u thuëc A. K½ hi»u sè c¡c tê hñp câ l°p chªp k cõa n ph¦n tû cõa A b¬ng CRnk . Ta công nhªn x²t r¬ng n¸u A = {a1, a2, . . . , an}, th¼ mët a tªp B lüc l÷ñng k vîi c¡c ph¦n tû ·u thuëc A ho n to n ÷ñc x¡c ành n¸u sè l¦n xu§t hi»n trong B cõa méi ai, i = 1, 2, . . . , n, ÷ñc x¡c ành. Ta câ CRnk = Cn+k−1 k . Ghi chó 1.2.10 (Ho¡n và khæng l°p). Gi£ sû A l mët tªp húu h¤n vîi |A| = n. Khi â mët ch¿nh hñp chªp n cõa n ph¦n tû A ÷ñc gåi l mët ho¡n và khæng l°p cõa n ph¦n tû cõa A. Ho¡n và khæng l°p th÷íng ÷ñc gåi ìn gi£n l ho¡n và. N¸u kþ hi»u sè c¡c ho¡n và cõa n ph¦n tû cõa A l Pn th¼ theo ành ngh¾a ta câ n! n! Pn = Ann = = = n!. (n − n)! 0! Ghi chó 1.2.11 (Ho¡n và câ l°p). Gi£ sû A = {a1, a2, . . . , an} l mët tªp húu h¤n lüc l÷ñng n, cán m1, m2, . . . , mn l n sè nguy¶n khæng ¥m ¢ cho sao cho ½t nh§t câ mët mi 6= 0. Ta công gi£ sû m = m1 + m2 + . . . + mn, A1 , A2 , . . . , Am l c¡c ph¦n tû cõa A, S l sì ç sp x¸p "bë câ thù tü gçn m th nh ph¦n d¤ng (x1 , x2 , . . . , xm )," R1 l i·u ki»n "x1 ∈ A1 , x2 ∈ A2 , . . . , xm ∈ Am ", R2 l i·u ki»n"a1 xu§t hi»n ð óng m1 th nh ph¦n, a2 xu§t hi»n ð óng m2 th nh ph¦n, . . . , an xu§t hi»n ð óng mn th nh ph¦n". Khi â c§u h¼nh tê hñp A1, . . . , Am theo S thäa m¢n R1, R2 ÷ñc gåi l mët ho¡n và câ l°p cõa c¡c ph¦n tû a1, . . . , an cõa tªp A vîi tham sè l°p l m1, . . . , mn. Theo ành ngh¾a cõa ch¿nh hñp câ l°p v ho¡n và câ l°p ta th§y ngay r¬ng mët ho¡n và câ l°p cõa c¡c ph¦n tû a1, . . . , an cõa tªp A vîi tham sè l°p l m1, m2, . . . , mn ch½nh l mët ch¿nh hñp l°p chªp m cõa n ph¦n tû cõa 11
A thäa m¢n i·u ki»n R2. Công th§y ngay r¬ng mët ho¡n và câ l°p cõa c¡c ph¦n tû a1, a2, . . . , an cõa tªp A vîi tham sè l°p l m1 = m2 = . . . = mn = 1 ch½nh l mët ho¡n và khæng l°p chªp n cõa ph¦n tû A. Kþ hi»u sè c¡c ho¡n và câ l°p cõa c¡c ph¦n tû a1, a2, . . . , an vîi tham sè l°p m1, m2, . . . , mn l m ,mm,...,m . º t½nh sè n y ta coi mët ho¡n và câ 1 2 n l°p tr¶n l mët c¡ch thüc hi»n h nh ëng H "t¤o ra ho¡n và câ l°p" bao gçm n giai o¤n k¸ ti¸p nhau H1 , H2 , . . . , Hn sau ¥y: Giai o¤n H1: t¤o ra m1 th nh ph¦n a1 cho ho¡n và câ l°p. Rã r ng l méi tªp con B1 = {i ∈ {1, . . . , m} |xi = a} cõa tªp {1, 2, . . . , m} t÷ìng ùng vîi óng mët c¡ch thüc hi»n giai o¤n n y. V¼ vªy câ mm c¡ch thüc hi»n 1 H1 . Giai o¤n H2: t¤o ra m2 th nh ph¦n a2 cho ho¡n và câ l°p. V¼ ¢ chån ra m1 th nh ph¦n º l m th nh ph¦n a1 n¶n ch¿ cán l¤i m − m1 th nh ph¦n câ thº dòng º chån ra l m th nh ph¦n a2. Lªp luªn nh÷ ð giai o¤n H1 ta câ m−1 c¡ch thüc hi»n giai o¤n H2. m 2 .................................... Giai o¤n Hn: T¤o ra mn th nh ph¦n l an cho ho¡n và câ l°p. V¼ ð (n − 1) giai o¤n tr÷îc ta ¢ chån ra (m1 + . . . + mn−1 ) th nh ph¦n n¶n ch¿ cán l¤i m − (m1 + . . . + mn−1) th nh ph¦n câ thº dòng º l m th nh ph¦n an . Do â m−(m +...+m ) c¡ch thüc hi»n giai o¤n Hn. 1 n−1 m n Theo nguy¶n lþ nh¥n ta câ ! ! ! ! m m m − m1 m − (m1 + . . . + mn−1 ) = m1 , m2 , . . . , mn m1 m2 mn m! (m − m1 )! (m − m1 − . . . − mn−1 )! = . ··· m1 !(m − m1 )! m2 !(m − m1 − m2 )! m!(m − m1 − . . . − mn−1 )! Suy ra ! m m! = . m1 , m2 , . . . , mn m1 !m2 ! . . . mn ! K¸t qu£ tr¶n câ thº ph¡t biºu d÷îi d¤ng kh¡c nh÷ sau (ph¥n ho¤ch cõa mët tªp hñp). ành lþ 1.2.12. Cho c¡c sè tü nhi¶n m1, m2, . . . , mn sao cho m1 + m2 + . . . + mn = m. Khi â sè ph¥n ho¤ch mët tªp hñp A gçm m ph¦n tû kh¡c 12
nhau th nh hñp ríi r¤c cõa n tªp con B1, B2, . . . , Bn, vîi sè ph¦n tû theo thù tü m1, m2, . . . , mn, kþ hi»u m ,mm,...,m v b¬ng 1 2 n m! . m1 !m2 ! . . . mn ! Chùng minh. Ta câ thº thüc hi»n c¡c ph¥n ho¤ch ¢ mæ t£ tr¶n ¥y cõa tªp A th nh n tªp con B1 , B2 , . . . , Bn nh÷ sau: Ta l§y mët tªp con B1b§t ký chùa m1 ph¦n tû cõa tªp hñp A (i·u n y câ thº thüc hi»n theo mm c¡ch), 1 trong m − m1 ph¦n tû cánl¤i, ta l§ymët tªp con B2 chùa m2 ph¦n tû (i·u n y câ thº thüc hi»n theo m m − m1 c¡ch), . . . . Khi â, theo quy tc nh¥n, 2 sè t§t c£ c¡c c¡ch chån c¡c tªp con B1, B2, . . . , Bn l m m − m1 m − m1 − m2 − . . . − mn−1 ... m1 m2 mn m! (m − m1 )! (m − m1 − m2 )! = × × m1 !(m − m1 )! m2 !(m − m1 − m2 )! m3 !(m − m1 − m2 − m3 )! (m − m1 − m2 − . . . − mn )! × ... × mn !(m − m1 − m2 − . . . − mn )! m! = . m1 !m2 ! . . . mn ! V½ dö 1.2.13. Gi£ sû câ m chú c¡i, trong â câ m1 chú a1, m2 chú a2 . . . , mn chú an (trong â m1 + m2 + . . . + mn = m). Tø c¡c chú c¡i â câ thº lªp ÷ñc bao nhi¶u "tø" kh¡c nhau (tø câ ngh¾a ho°c tø khæng câ ngh¾a) m méi tø gçm m chú c¡i ¢ cho? Ta ¡nh sè và tr½ c¡c chú c¡i trong méi tø bði c¡c sè 1, 2, . . . , m. Méi "tø" ÷ñc x¡c ành ho n to n bði tªp hñp Bi c¡c sè hi»u cõa c¡c và tr½ t¤i â câ chú ai. Do â sè "tø" kh¡c nhau lªp n¶n tø c¡c chú c¡i ¢ cho b¬ng sè c¡ch m ta câ thº biºu di¹n tªp hñp A = {1, 2, . . . , m} d÷îi d¤ng hñp ríi r¤c cõa c¡c tªp con B1, B2, . . . , Bn. Theo ành lþ 1.2.12 th¼ sè "tø" c¦n t¼m b¬ng ! m m! = . m1 , m2 , . . . , mn m1 !m2 ! . . . mn ! Ch¯ng h¤n, x²t hai tr÷íng hñp minh håa cö thº: 13
i) Sè c¡c "tø" thu ÷ñc b¬ng c¡ch ho¡n và c¡c chú c¡i cõa tø 'nhanh' b¬ng 5! = 30. 2!2!1! ii) Sè c¡c "tø" câ thº lªp ÷ñc tø 12 chú c¡i (gçm 4 chú a, 4 chú b, 2 chú c, 2 chú d) b¬ng 4!4!2!2! 12! . Ghi chó 1.2.14 (Cæng thùc a thùc). "Cæng thùc nhà thùc Newton" l sü khai triºn cõa biºu thùc (a + b)n trong â a, b ∈ R v n ∈ N∗. "Cæng thùc a thùc" l sü khai triºn cõa biºu thùc (a1 + a2 + . . . + am)n trong â a1 , a2 , . . . , am ∈ R v n ∈ N∗ . Sü khai triºn cõa (a1 + a2 + . . . + am)n ÷ñc cho bði cæng thùc sau ¥y, gåi l cæng thùc a thùc ! X m (a1 + . . . + am )n = an1 1 . . . anmm Pm m1 , m2 , . . . , mn n1 ,...,nm ∈N, i=1 ni =n X n! = an1 1 . . . anmm . Pm n1 ! . . . nm ! n1 ,...,nm ∈N, i=1 ni =n 14
Ch÷ìng 2 Quan h» hai ngæi v mët sè b i to¡n 2.1. ¸m mët sè quan h» hai ngæi °c bi»t Möc ½ch ch½nh cõa möc n y l ¸m mët sè quan h» hai ngæi °c bi»t nh÷ sè quan h» hai ngæi ph£n x¤, sè quan h» hai ngæi èi xùng, .... Tr÷îc h¸t ta ÷a ra mët sè ki¸n thùc chu©n bà. Theo lþ thuy¸t tê hñp sè tªp con k ph¦n tû cõa tªp n l nk = . Ta ÷a ra mët chùng minh sì c§p n! k!(n − k)! kh£ng ành n y düa v o c¡c quy tc ¸m cì b£n. Bê · 2.1.1. Sè t§tc£ c¡c tªp con k ph¦n tû cõa mët tªp hñp n ph¦n tû b¬ng k!(nn!− k)! = nk . Chùng minh. Kþ hi»u sè tªp con k ph¦n tû cõa mët tªp n ph¦n tû l Unk . Muèn düng mët tªp con k ph¦n tû cõa tªp hñp A ta câ thº gh²p th¶m v o mët tªp con k − 1 ph¦n tû cõa A mët trong n − (k − 1) = n − k + 1 ph¦n tû cán l¤i. V¼ câ Unk−1 tªp con k − 1 ph¦n tû v ta câ thº bê sung tªp con §y th nh mët tªp con k ph¦n tû theo n − k + 1 c¡ch, n¶n l m nh÷ vªy ta thu ÷ñc (n − k + 1)Unk−1 tªp con k ph¦n tû cõa A. Nh÷ng khæng ph£i t§t c£ c¡c tªp con ·u kh¡c nhau, v¼ ta câ thº nhªn mët tªp con k ph¦n tû theo k c¡ch, cö thº l l§y méi mët trong k ph¦n tû cõa nâ gh²p th¶m k − 1 ph¦n tû cán l¤i. V¼ vªy sè (n − k + 1)Unk−1 vøa t¼m ÷ñc ð tr¶n g§p k l¦n sè Unk c¡c tªp con k ph¦n tû cõa A. Do â ta câ ¯ng thùc (n − k + 1)Unk−1 = kUnk . Tø â ta suy ra n − k + 1 k−1 n − k + 1 n − k + 2 k−2 Unk = Un = Un = . . . k k k−1 15
(n − k + 1) . . . (n − 1) n U1 . k(k − 1) . . . 2 U1nl sè tªp con mët ph¦n tû cõa A. Nâ b¬ng sè ph¦n tû cõa A, tùc l n. Vªy n(n − 1) . . . (n − k + 1) Ukn = 1.2 . . . k n(n − 1) . . . (n − k + 1)(n − k) . . . 3.2.1 n! = = . 1.2 . . . k.(n − k) . . . 3.2.1 k!(n − k)! Bê · 2.1.2 (Sè tªp con cõa mët tªp húu h¤n). Sè tªp con kh¡c nhau cõa mët tªp A húu h¤n ph¦n tû l 2|A|. Chùng minh. C¡ch 1: Cho A l mët tªp húu h¤n. Ta li»t k¶ c¡c ph¦n tû cõa A theo mët thù tü n o â. Giúa c¡c tªp con cõa A v c¡c d¢y nhà ph¥n câ ë d i |A| câ sü t÷ìng ùng 1-1. Cö thº l , mët tªp con cõa A ÷ñc g¡n vîi d¢y nhà ph¥n câ sè 1 ð và tr½ thù i n¸u ph¦n tû thù i trong danh s¡ch thuëc tªp con n y, v l sè 0 trong nhúng tr÷íng hñp ng÷ñc l¤i. Theo quy tc nh¥n câ 2|A| d¢y nhà ph¥n ë d i |A|. V¼ vªy |P (A)| = 2|A|. C¡ch 2: Gåi Ta l tªp hñp t§t c£ c¡c tªp con cõa tªp hñp A chùa ph¦n tû a ∈ A. Hiºn nhi¶n méi tªp con nh÷ th¸ ÷ñc ho n to n x¡c ành, n¸u ta bi¸t t§t c£ c¡c ph¦n tû cán l¤i cõa nâ (trø a). V¼ vªy câ bao nhi¶u tªp con nh÷ th¸ th¼ câ b§y nhi¶u tªp con trong tªp A0 = A \ a. Tªp hñp A0 n y câ m − 1 ph¦n tû. V¼ vªy, n¸u ta gåi sm l sè tªp con cõa mët tªp hñp câ m ph¦n tû, th¼ |Ta| = sm−1. Gåi T a l tªp hñp t§t c£ c¡c tªp con cõa tªp hìp A khæng chùa a, th¼ |T a| công b¬ng sm−1, v¼ c¡c tªp con â công l c¡c tªp con cõa tªp hñp A 0 = A \ a. V¼ 2A = Ta ∪ T a v Ta ∩ T a = ∅, n¶n theo quy tc cëng, ta câ |2A | = |T (a)| + |T a | = 2sm−1 . Tø â suy ra sm = 2sm−1. p döng li¶n ti¸p ¯ng thùc n y, ta ÷ñc sn = 2sn−1 = 22 sn−2 = . . . = 2n−1 s1 . s1 l sè tªp con cõa mët tªp hñp câ mët ph¦n tû. Nh÷ng mët tªp hñp câ 16
mët ph¦n tû ch¿ câ hai tªp con l tªp réng v ch½nh nâ. Vªy s1 = 2. Do â sn = 2n . C¡ch 3: Cho tªp A câ n ph¦n tû. X²t tªp hñp Y = {0, 1}. Vîi méi tªp con B cõa A, ta x¡c ành mët ¡nh x¤ f : A → Y nh÷ sau: Cho x ∈ A, n¸u x ∈ B th¼ ta °t f (x) = 1, cán n¸u x ∈ / B th¼ ta °t f (x) = 0. Nh÷ vªy ùng vîi méi tªp con B cõa A, câ mët ¡nh x¤ f tø A tîi Y . £o l¤i, n¸u f l mët ¡nh x¤ tø A tîi Y th¼ ùng vîi nâ câ mët tªp con B cõa A, gçm t§t c£ c¡c ph¦n tû x ∈ A sao cho f (x) = 1. Sü t÷ìng ùng §y giúa tªp hñp c¡c tªp con cõa tªp hñp A v tªp hñp c¡c ¡nh x¤ tø A tîi X rã r ng l 1 − 1. Do â sè tªp con cõa A, tùc l |2A|, b¬ng sè ¡nh x¤ tø tªp hñp A câ n ph¦n tû tîi tªp hñp Y câ hai ph¦n tû. Theo M»nh · 2.1.2 sè n y l 2m. Vªy |2A| = 2m. C¡ch 4: C¡c tªp con cõa A gçm c¡c lo¤i tªp: 0 ph¦n tû, 1 ph¦n tû, ..., n ph¦n tû. Méi k ∈ {0, 1, ..., n}, theo Bê · 2.1.1 câ nk tªp con k ph¦n tû cõa A. Vªy sè tªp con cõa A l ! ! ! n n n + + ··· + = (1 + 1)n = 2n 0 1 n theo cæng thùc khai triºn a thùc. Ta ÷a ra mët ùng döng cõa k¸t qu£ tr¶n trong gi£i to¡n sì c§p. B i to¡n 2.1.3 (VMO-2004). Cho tr÷îc c¡c sè nguy¶n d÷ìng m, n. T½nh m n X Ck n+k X Ck m+k T = m+k + n+k . k=0 2 k=0 2 H÷îng d¨n gi£i. Ta c¦n chùng minh têng c¦n t½nh b¬ng 1, tùc l : m k n k X Cn+k X Cm+k + = 1. 2n+k+1 k=0 2m+k+1 k=0 C¡c lôy thøa cõa 2 cho ta li¶n t÷ðng ¸n sè tªp con cõa mët tªp hñp Trong c¡c tªp con cõa tªp S = {1, 2, . . . , m + n + 1} d¹ th§y Cn+k k 2m−k tªp d¤ng {a1, a2, . . . , an+i} , (1 < i 6 m + 1) trong â (a1 < a2 < . . . < an+i) v an+1 = n + k + 1 vîi 0 6 k 6 m (Do câ Cn+k n c¡ch chån n ph¦n tû (a1 , a2 , . . . , an )) tø tªp {1, 2, . . . , n + k}, 1 c¡ch chån an+1 = n + k + 1 17