Tài liệu 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 . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2. nh x¤ v  mët sè b i to¡n li¶n quan. . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3. Ph¥n ho¤ch, sè Stirling lo¤i hai . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4. ¸m sè quan h» t÷ìng ÷ìng v  quan h» hai ngæi b­c c¦u . . . . . . 15 23 27 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), b­c 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. B­t ¦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è g­ng 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» b­c 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 s­c ¸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 t­t l  a R b). Khi (a, b) ∈ / R th¼ ta vi¸t aRb (åc l  a khæng câ quan h» R vîi b). Ta th÷íng 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) B­c 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 R1 R2 R3 R4 Ph£n x¤ T F T F èi xùng T F T F B­c c¦u T T T T câ vîi T kþ hi»u True, F kþ hi»u False. 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 R2 R4 R5 F T T T F T T T F F F F T F T F F F F F F T T T Chó þ ta vi¸t t­t: PX = Ph£n x¤, X = èi xùng, PX = Ph£n èi xùng, BPX = B§t ph£n x¤, BC = B­c 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  b­c 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. S (ii) A = Ai. 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. S (ii) A = [a]. 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  b­c 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 s­p 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 t­c 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: f A→ − B, a 7→ f (a) = b, ho°c 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 t­c 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 t­c 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 t­c 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 t­c 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 nh­c 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ì ç s­p 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 t­c s­p 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ü s­p x¸p c¡c ph¦n tû cõa A1, . . . , Am, theo sì ç S . Khi â mët s­p 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 ng­n 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ì ç s­p 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 s­p 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ì ç s­p x¸p "bë câ thù tü gçm k th nh ph¦n (x1 , x2 , . . . , xk )", R l  i·u ki»n s­p 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 t­c 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ì ç s­p x¸p "bë câ thù tü gçm k th nh ph¦n (x1 , x2 , . . . , xk )", R l  i·u ki»n s­p 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. Akn = n! , 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ì ç s­p x¸p "tªp câ k ph¦n tû {x1 , x2 , . . . , xk }", R l  i·u ki»n s­p 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¸u 0 6 k 6 n, 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 ng­n 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ì ç s­p x¸p "a tªp câ k ph¦n tû {x1 , x2 , . . . , xk }",   ( = n = k 0, n! k!(n−k)! , 10 l  i·u ki»n s­p 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â R k CRnk = Cn+k−1 . 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â Pn = Ann = n! n! = = 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ì ç s­p 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 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â 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 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 A 1 2 n 1 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. m Theo nguy¶n lþ nh¥n ta câ 1 n−1 n m m1 , m2 , . . . , mn = ! = m m1 ! m − m1 m2 ! ! m − (m1 + . . . + mn−1 ) mn (m − m1 )! (m − m1 − . . . − mn−1 )! m! . ··· m1 !(m − m1 )! m2 !(m − m1 − m2 )! m!(m − m1 − . . . − mn−1 )! Suy ra m m1 , m2 , . . . , mn ! = m! . 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 − m1 n y câ thº thüc hi»n theo m m c¡ch), . . . . Khi â, theo quy t­c nh¥n, 2 sè t§t c£ c¡c c¡ch chån c¡c tªp con B1, B2, . . . , Bn l      m − m1 m − m1 − m2 − . . . − mn−1 ... 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 ! m m1  V½ dö 1.2.13. Gi£ sû câ m chú c¡i, trong â câ m1 chú a1, m2 chú a2 . . . , 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 mn m m1 , m2 , . . . , mn ! = m! . 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, 12! 2 chú d) b¬ng 4!4!2!2! . 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 (a1 + . . . + am )n = X n1 ,...,nm ∈N, = Pm i=1 ni =n X n1 ,...,nm ∈N, Pm i=1 ni =n 14 m m1 , m2 , . . . , mn ! an1 1 . . . anmm n! an1 1 . . . anmm . n1 ! . . . nm ! 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
n! k ph¦n tû cõa tªp n l  nk = . Ta ÷a ra mët chùng minh sì c§p k!(n − k)! kh£ng ành n y düa v o c¡c quy t­c ¸m cì b£n. Bê · 2.1.1. Sè t§t
c£ 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 Unk = n − k + 1 k−1 n − k + 1 n − k + 2 k−2 Un = Un = . . . k k k−1 15 (n − k + 1) . . . (n − 1) n U1 . k(k − 1) . . . 2 l  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 U1n n(n − 1) . . . (n − k + 1) 1.2 . . . k n! n(n − 1) . . . (n − k + 1)(n − k) . . . 3.2.1 = . = 1.2 . . . k.(n − k) . . . 3.2.1 k!(n − k)! Ukn = 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 t­c 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 t­c 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 T = m X Ck k=0 n+k m+k 2 + n X Ck k=0 m+k . n+k 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 n k k X X Cn+k Cm+k + = 1. 2n+k+1 2m+k+1 k=0 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 k Trong c¡c tªp con cõa tªp S = {1, 2, . . . , m + n + 1} d¹ th§y Cn+k 2m−k tªp d¤ng {a1, a2, . . . , an+i} , (1 < i 6 m + 1) trong â (a1 < a2 < . . . < an+i) n v  an+1 = n + k + 1 vîi 0 6 k 6 m (Do câ Cn+k 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