Bài giảng Toán rời rạc - Chương 2: Tổ hợp - Nguyễn Đức Nghĩa

. Từ
 đó suy ra tổng số đối tượng xếp trong n cái hộp là không
 vượt quá n, trái với giả thiết là có nhiều hơn n đối tượng
 được xếp trong chúng.
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-121 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-122
 2.6.1 . Phát biểu nguyên lý 2.6.1 . Phát biểu nguyên lý
 • Lập luận trên đã được nhà toán học người Đức là Dirichlet vận dụng l Trong tài liệu tiếng Anh lập luận đó lại được trình bày
 thành công vào việc giải quyết rất nhiều bài toán tồn tại tổ hợp . trong ngôn ngữ của các con chim bồ câu: “Nếu đem
 • Trong lập luận của Dirichlet, các đối tượng được xét là các quả táo còn nhốt nhiều hơn n con chim bồ câu vào n cái lồng thì bao
 các cái hộp được thay bởi các cái giỏ : “Nếu đem bỏ nhiều hơn n quả táo
 giờ cũng tìm được ít nhất 1 cái lồng chứa ít ra là 2 con
 vào n cái giỏ thì bao giờ cũng tìm được ít nhất một cái giỏ chứa ít ra là 2
 quả táo ”. chim bồ câu ”. Vì thế nguyên lý còn có tên gọi là
 “Nguyên lý về các lồng chim bồ câu ”.
 l Trong ngôn ngữ của lý thuyết tập hợp, nguyên lý có thể
 phát biểu như sau: “Nếu tập X gồm nhiều hơn n phần tử
 được phân hoạch thành n tập con, thì bao giờ cũng tìm
 Johann Peter Gustav Lejeune Dirichlet
 Born: 13 Feb 1805 được một tập con trong phân hoạch đó có lực lượng ít
 Died: 5 May 1859 ra là 2”
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-123 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-124
 Ví dụ Ví dụ
 • Ví dụ 1. Trong số 367 người bao giờ cũng tìm được hai • Ví dụ 3. Trong số những người có mặt trên trái đất luôn tìm 
 người có ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 được hai người có hàm răng giống nhau.
 ngày sinh nhật khác nhau. • Giải: Tất cả chỉ có
 232 = 4 294 967 296
 • Ví dụ 2. Trong kỳ thi học sinh giỏi điểm bài thi được đánh hàm răng khác nhau mà số người trên hành tinh chúng ta 
 giá bởi một số nguyên trong khoảng từ 0 đến 100. Hỏi rằng hiện nay đã vượt quá 5 tỷ.
 ít nhất phải có bao nhiêu học sinh dự thi để cho chắc chắn 
 tìm được hai học sinh có kết quả thi như nhau? 
 • Giải. Theo nguyên lý Dirichlet, số học sinh cần tìm là 102, 
 vì ta có 101 kết quả điểm thi khác nhau.
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-125 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-126
 NguyênNguyêu ênê lýý DirichletDiDiriricr chlechletleet tổngổ g quátátá NguyênNguyêu ênê lýý DirichletDiriDiricr chlechletleet tổngổ g quátátá
 Generalized Pigeonhole Principle Generalized Pigeonhole Principle
 • Khi số lượng quả táo bỏ vào k cái giỏ vượt quá số lượng cái • Chứng minh nguyên lý tổng quát: 
 giỏ nhiều lần thì rõ ràng khẳng định trong nguyên lý về sự • Giả sử khẳng định của nguyên lý là không đúng. 
 tồn tại cái giỏ chứa ít ra là 2 quả táo là quá ít. Trong trường Khi đó mỗi cái giỏ chứa không quá én/k ù - 1 quả 
 hợp như vậy ta sử dụng nguyên lý Dirichlet tổng quát sau táo. Từ đó suy ra tổng số quả táo bỏ trong k cái giỏ 
 đây: không vượt quá 
 • “Nếu đem bỏ n quả táo vào k cái giỏ thì bao giờ cũng tìm k(én/k ù - 1) < k((n/k+ 1) - 1)) = n. 
 được ít nhất một cái giỏ chứa ít ra là én/k ù quả táo”. Mâu thuẫn thu được đã chứng minh nguyên lý.
 • Ở đây ký hiệu éaù gọi là phần nguyên già của số thực a, 
 theo định nghĩa, là số nguyên nhỏ nhất còn lớn hơn hoặc 
 bằng a.
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-127 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-128
 Ví dụ Ví dụ
 • Ví dụ 4. Trong 100 người có ít nhất 9 người sinh cùng một • Ví dụ 6. Hỏi ít nhất phải có bao nhiêu người có mặt trên 
 tháng.
 • Giải: Xếp những người cùng sinh một tháng vào một nhóm. Có trái đất để luôn tìm được ba người có hàm răng giống nhau?
 12 tháng tất cả. Vậy theo nguyên lý Dirichlet, tồn tại ít nhất một • Giải: Tất cả chỉ có
 nhóm có không ít hơn é100/12 ù = 9 người.
 • Ví dụ 5. Có năm loại học bổng khác nhau. Hỏi rằng phải có ít 232 = 4 294 967 296
 nhất bao nhiêu sinh viên để chắc chắn rằng có ít ra là sáu người 
 hàm răng khác nhau. Ta cần tìm số n nhỏ nhất để
 cùng nhận học bổng như nhau?
 • Giải: Số sinh viên ít nhất cần có để đảm bảo chắc chắn có 6 sinh én/ 232 ù = 3. 
 viên cùng nhận học bổng như nhau là số nguyên nhỏ nhất n sao 
 cho én/ 5ù = 6. Số nguyên nhỏ nhất đó là n = 5´5+1 = 26 . Vậy • Từ đó số người cần tìm là 
 26 là số lượng sinh viên nhỏ nhất đảm bảo chắc chắn là có sáu 2´232 + 1 = 8 589 934 593.
 sinh viên cùng hưởng một loại học bổng.
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-129 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-130
 2.6.2 . Các ví dụ ứng dụng Ví dụ 1
 • Trong các ví dụ ứng dụng phức tạp hơn của nguyên lý • Ví dụ 1. Trong một phòng họp bao giờ cũng tìm được 
 hai người có số người quen trong số những người dự 
 Dirichlet, cái giỏ và quả táo cần phải được lựa chọn khôn họp là bằng nhau .
 khéo hơn rất nhiều. • Gi¶i : Gäi sè ngêi dù häp lµ n, khi ®ã sè ngêi quen cña mét
 • Trong phần này ta sẽ xét một số ví dụ như vậy. ngêi nµo ®ã trong phßng häp chØ cã thÓ nhËn c¸c gi¸ trÞ tõ 0
 ®Õn n-1. Râ rµng trong phßng kh«ng thÓ ®ång thêi cã ngêi
 cã sè ngêi quen lµ 0 (tøc lµ kh«ng quen ai c¶) vµ cã ngêi cã
 sè ngêi quen lµ n-1 (tøc lµ quen tÊt c¶). V× vËy, theo sè lîng
 ngêi quen ta chØ cã thÓ ph©n n ngêi ra thµnh n-1 nhãm.
 Theo nguyªn lý Dirichlet suy ra cã Ýt nhÊt mét nhãm ph¶i
 cã kh«ng Ýt h¬n hai ngêi, tøc lµ lu«n t×m ®îc Ýt ra lµ hai ngêi
 cã sè ngêi quen lµ b»ng nhau.
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-131 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-132
 Ví dụ 2 Ví dụ 2
 • Ví dụ 2. Trong một tháng gồm 30 ngày một đội bóng • Tất cả có 60 số nguyên dương 
 chuyền thi đấu mỗi ngày ít nhất một trận, nhưng
 a , a , ..., a , a +14 , a +14, ... , a +14, 
 không chơi quá 45 trận .Chứng minh rằng phải tìm 1 2 30 1 2 30
 được một giai đoạn gồm một số ngày liên tục nào đó trong đó tất cả đều nhỏ hơn hoặc bằng 59. 
 trong tháng sao cho trong giai đoạn đó đội chơi đúng • Vì vậy theo nguyên lý Dirichlet, hai trong số các số nguyên
 14 trận .
 này phải là bằng nhau. Vì các số a , ..., a là đôi một khác
 • Gi¶i : Gi¶ sö a lµ tæng sè trËn thi ®Êu cho ®Õn hÕt ngµy thø 1 30
 j nhau và các số a +14, ..., a +14 cũng là đôi một khác
 j cña ®éi. Khi ®ã 1 30
 nhau, nên suy ra phải tìm được chỉ số i và j sao cho
 a1, a2, ..., a 30
 j<i và ai = aj+14.
 lµ d·y t¨ng c¸c sè nguyªn d¬ng vµ ®ång thêi 1 £ aj £ 45. 
 Suy ra d·y • Điều đó có nghĩa là có đúng 14 trận đấu trong giai đoạn từ
 a1+14 , a2+14 , ..., a30 +14 ngày j+1 đến hết ngày i.
 còng lµ d·y t¨ng c¸c sè nguyªn d¬ng vµ 15 £ aj +14 £ 59 .
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-133 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-134
 Ví dụ 3 Ví dụ 3
 • Ví dụ 3. Chứng minh rằng, trong số n+1 số • Các số q1, q2, ..., qn+ 1 là các số nguyên lẻ, mỗi số
 nguyên dương, mỗi số không lớn hơn 2n, bao không lớn hơn 2n.
 giờ cũng tìm được hai số sao cho số này chia • Do trong đoạn từ 1 đến 2n chỉ có n số lẻ, nên từ
 hết cho số kia.
 nguyên lý Dirichlet suy ra là hai trong số các số q1,
 •
 Gi¶i : Gäi c¸c sè ®· cho lµ q2, ..., qn+1 là bằng nhau, tức là tìm được hai chỉ số
 a1, a2, . . . , an+ 1 . i và j sao cho qi = qj = q.
 •
 ViÕt mçi mét sè aj trong n+ 1 sè trªn díi d¹ng: • Khi đó
 k(j) k(i) k(j)
 aj = 2 qj , j = 1, 2, ..., n+1 ai = 2 q, aj = 2 q.
 trong ®ã k(j) lµ nguyªn kh«ng ©m, qj lµ sè lÎ. • Suy ra nếu k(i) < k(j) thì aj chia hết cho ai, còn
 nếu k(i) ³ k(j) thì ai chia hết cho aj.
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-135 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-136
 Ví dụ 4 Ví dụ 4
 • Từ đó theo nguyên lý Dirichlet phải tìm được một nhóm
 • Ví dụ 4. Trên mặt phẳng cho 5 điểm có toạ độ nguyên
 chứa ít ra là 2 điểm, chẳng hạn đó là Mi,Mj. Khi đó
 M (x , y ), i=1, 2, ..., 5. Chứng minh rằng luôn tìm được 2
 i i i điểm giữa Gij của đoạn thẳng nối Mi và Mi có toạ độ
 điểm sao cho đoạn thẳng nối chúng, ngoài hai đầu mút, còn
 Gij = (( xi+x j)/2, (yi+y j)/2).
 đi qua một điểm có toạ độ nguyên khác nữa .
 • Do xi và xj cũng như yi và yj có cùng tính chẵn lẻ nên các
 • Giải . Ta sẽ chứng minh: Luôn tìm được 2 điểm sao cho
 toạ độ của Gij là các số nguyên. Khẳng định của ví dụ
 điểm giữa của đoạn thẳng nối chúng có toạ độ nguyên. được chứng minh.
 Theo tính chẵn lẻ của hai toạ độ, 5 điểm đã cho có thể phân • Khẳng định của ví dụ có thể tổng quát cho không gian n-
 vào nhiều nhất là 4 nhóm: chiều : “Trong không gian n-chiều cho 2n + 1 điểm có toạ
 (Chẵn, Chẵn), (Chẵn, Lẻ), (Lẻ, Chẵn), (Lẻ, Lẻ) . độ nguyên. Khi đó luôn tìm được 2 điểm sao cho đoạn
 thẳng nối chúng, ngoài hai đầu mút, còn đi qua một
 điểm có toạ độ nguyên khác nữa”.
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-137 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-138
 Ví dụ 5 Ví dụ 5
 Trước hết ta cần một số khái niệm. • Định lý: Mỗi dãy gồm n2+1 số phân biệt (nghĩa là các
 • Cho a1, a2,  an là dãy số thực. phần tử là khác nhau từng đôi) luôn chứa hoặc dãy con
 • n được gọi là độ dài của dãy số đã cho. tăng ngặt độ dài n+1 hoặc dãy con giảm ngặt độ dài
 n+1.
 • Ta gọi dãy con của dãy đã cho là dãy có dạng ai1, ai2, , aim, trong đó 
 1 £ i1 < i2 < . . . < im £ n • Ví dụ: Dãy
 • Dãy số được gọi là tăng ngặt nếu mỗi số hạng đứng sau luôn lớn hơn 8, 11, 9, 1, 4, 6, 12, 10, 5, 7 
 số hạng đứng trước. Dãy số được gọi là giảm ngặt nếu mỗi số hạng gồm 10 = 32+1 số hạng phải chứa hoặc dãy con tăng ngặt 
 đứng sau luôn nhỏ hơn số hạng đứng trước.. độ dài 4 phần tử hoặc dãy con giảm ngặt độ dài 4 phần tử.
 ΏVí dụ: Cho dãy số 1, 4, 6, 12
 1, 5, 6, 2, 3, 9. 1, 4, 6, 7
 • 5, 6, 9 là dãy con tăng ngặt của dãy đã cho
 11, 9, 6, 5
 • 6, 3 là dãy con giảm ngặt của dãy đã cho
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-139 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-140
 Ví dụ 5 Ví dụ 5
 2 2
 • Chứng minh: Giả sử a1, a2, , an2+1 là dãy gồm n +1 số • Do 1 £ ik, dk £ n, nên theo qui tắc nhân có tất cả n cặp có
 phân biệt . Gán cho mỗi số hạng a của dãy số cặp có thứ tự
 k thứ tự dạng (ik,d k) khác nhau.
 (i ,d ), trong đó i là độ dài của dãy con tăng dài nhất bắt
 k k k • Do ta có tất cả n2 + 1 cặp (i ,d ), nên theo nguyên lý
 đầu từ a còn d là độ dài của dãy con giảm dài nhất bắt đầu k k
 k k Dirichlet, hai trong số chúng là trùng nhau. Tức là tồn tại
 từ a .
 k hai số hạng a và a trong dãy đã cho với s < t sao cho i = i
 • Ví dụ: 8, 11 , 9, 1, 4, 6, 12, 10, 5, 7 s t s t
 và ds = dt.
 a = 11 , ( i ,d ) = (2,4) 
 2 2 2 • Ta sẽ chỉ ra điều này là không thể xảy ra. 
 a4 = 1 , (i4,d4) =(4,1) 
 • Do các số hạng của dãy là phân biệt, nên 
 • Bây giờ giả sử không tồn tại dãy tăng cũng như dãy giảm 
 hoặc là a a . 
 có độ dài n+1. Khi đó ik và dk là các số nguyên dương £ n, s t s t
 với k = 1, 2, ..., n2+1.
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-141 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-142
 Ví dụ 5
 • Nếu as < at, khi đó do is = i t , ta có thể xây dựng dãy con 
 tăng độ dài it+1 bắt đầu từ as, bằng cách nối đuôi nó bởi 
 dãy con tăng độ dài it, bắt đầu từ at.
 ... , as , ..., at , ....
 • Suy ra dãy con tăng dài nhất bắt đầu từ as có độ dài ít ra là 
 it + 1, nghĩa là is > it. Mâu thuẫn với giả thiết is= it.
 • Tương tự như vậy, nếu as > at, ta có thể chỉ ra ds phải lớn 
 hơn dt, và cũng đi đến mâu thuẫn.
 • Định lý được chứng minh. Hết chương 2
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-143 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-144
 2.4.1 . Xây dựng công thức đệ qui
 • Định nghĩa. Công thức đệ qui (recurence relation) cho dãy số 
 {an} là công thức cho phép tính an thông qua một hoặc một vài 
 số hạng đi trước nó trong dãy số (đó là các số hạng a0, a1,..., an-1) 
 với mọi n ³ n0, trong đó n0 là số nguyên không âm. Một dãy số 
 được gọi là nghiệm của công thức đệ qui nếu như các số hạng 
 của nó thỏa mãn của công thức này.
 • Ví dụ: Xét công thức đệ qui an= 2an– 1 – an– 2 với n = 2,3,4,...
 ΏDãy số { an} với an = 3n là nghiệm của công thức này, vì ta có 
 an= 2an– 1 – an– 2 = 2[3(n–1)] – 3(n–2) = 3n, với n ³ 2.
 ΏDãy số { an = 5} cũng là nghiệm, vì an= 2an – 1 – an – 2 =2*5–
 5=5, với mọi n ³ 2.
 n
 ΏDãy số { an = 2 } không là nghiệm, vì ta có a0= 1, a1=2, a2 = 
 4, nhưng a2 = 4 ¹ 2a1 – a0 = 2*2 – 1 = 3.
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-145 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-146
 Cây nhị phân
 • A binary tree is often defined recursively as either (a) being empty, or 
 (b) consisting of a root node together with left and right subtrees, both 
 of which are binary trees. It is this definition that is most useful from 
 the point of view of data structures in computer science. From the 
 mathematical point of view these objects are not trees. Changing (a) 
 from "empty" to "a single vertex" gives a definition equivalent to that 
 of ordered trees in which every node is either a leaf (no children) or has 
 two children. These are sometimes called extended binary trees . In 
 either case, they are usually parameterized by n, the number of 
 applications of rule (b) that are used. 
 • In the extended binary tree illustrated above there are 5 internal nodes
 (the brown circles, which correspond to applications of rule (b)) and 6 
 leaves (the blue squares, which correspond to applications of rule (a)). 
 By removing the blue edges and the leaves you obtain the 
 corresponding binary tree. 
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-147 Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-148
 • Ordered Trees
 • An ordered tree is a rooted tree in which the relative order of subtrees 
 matters. An ordered forest is an ordered collection of ordered trees. 
 There is a one-to-one correspondence between ordered forests with n
 nodes and binary trees with n nodes. This correspondence is best 
 explained using the well-formed parentheses strings with n left and n
 right parentheses. If the n left parentheses and n right parentheses are 
 labelled 1 through n from left to right in the string, then there are n pairs 
 of matching left/right pairs of parentheses. These pairs correspond to 
 the nodes of the corresponding ordered forest. Listing the pairs in 
 increasing order of the left parentheses corresponds to a preorder listing 
 of the nodes of the forest and listing the pairs in increasing order of the 
 right parentheses corresponds to a postorder listing of the nodes of the 
 forest. 
Toán rời rạc – NGUYỄN ĐỨC NGHĨA – Bộ môn KHMT – ĐHBK Hà nội Chap02-149