Bài giảng Toán rời rạc - Chương 4: Đếm các phần tử - Nguyễn Quỳnh Diệp

n tử lặp lại.
 Định lí 1
 Số các chỉnh hợp lặp chập r từ n phần tử bằng nr.
 Ví dụ: • Có bao nhiêu xâu gồm hai kí tự sinh ra từ tập {a, b, c}
 aa, ab, ac, 
 bb, ba, bc, 3.3 = 32 = 9
 cc, ca, cb
 Toán rời rạc Nguyễn Quỳnh Diệp 24
CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG
 • Tổ hợp lặp chập r của một tập hợp n phần tử là cách
 chọn không có thứ tự r phần tử của tập đó, cho phép
 các phần tử được lặp lại.
 Định lí 2 Có C(n+r-1,r) số tổ hợp lặp chập r từ tập n 
 phần tử.
Ví dụ: • Có bao nhiêu tổ hợp lặp chập 2 sinh ra từ tập {a, b, c}
 aa, bb, cc, 4!
 C(3+2-1,2) = C(4,2) = = 6
 ab, bc, ac, 2!(4−2)!
 Toán rời rạc Nguyễn Quỳnh Diệp 25
 CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG
 Ví dụ 1: Trong đĩa hoa quả có táo, cam, lê, mỗi loại có ít nhất 4 quả. 
 tính số cách lấy 4 quả từ đĩa này nếu thứ tự các quả được
 chọn không quan trọng.
Ví dụ 2: Có bao nhiêu cách đặt 10 viên bi giống hệt nhau vào tám
 ngăn phân biệt?
Ví dụ 3: Có bao nhiêu cách chọn năm tờ giấy bạc từ một két đựng
 tiền gồm những tờ có mệnh giá 1$, 2$, 5$, 10$, 20$, 50$ 
 và 100$. Giả sử thứ tự mà các tờ tiền được chọn ra là
 không quan trọng, các tờ tiền cùng loại là không phân biệt
 và mỗi loại có ít nhất 5 tờ. 
 Toán rời rạc Nguyễn Quỳnh Diệp 26
CHỈNH HỢP VÀ TỔ HỢP SUY RỘNG
 Tổ hợp và chỉnh hợp:
 Loại Lặp không? Công thức
Chỉnh hợp chập r Không 푛!
 푃(푛, ) =
 푛 − !
Tổ hợp chập r Không 푛!
 (푛, ) =
 ! 푛 − !
Chỉnh hợp chập r Lặp 푛 
 (푛 + − 1)!
Tổ hợp chập r Lặp (푛 + − 1, ) =
 ! 푛 − 1 !
 Toán rời rạc Nguyễn Quỳnh Diệp 27
HOÁN VỊ VỚI CÁC PHẦN TỬ KHÔNG PHÂN BIỆT
 • Trong bài toán đếm, một số phần tử có thể giống hệt
 nhau, không phân biệt Tránh đếm chúng hơn 1 lần
 Ví dụ:
 Có thể nhận được bao nhiêu xâu khác nhau bằng cách sắp
 xếp lại các chữ cái của từ SUCCESS?
 Toán rời rạc Nguyễn Quỳnh Diệp 28
HOÁN VỊ VỚI CÁC PHẦN TỬ KHÔNG PHÂN BIỆT
Định lí 3:
 Số các hoán vị khác nhau của n phần tử, trong đó có n1
 phần tử thuộc loại 1, n2 phần tử thuộc loại 2,... nk phần tử
 thuộc loại k, bằng:
 풏!
 풏 ! 풏 !  풏풌!
 Toán rời rạc Nguyễn Quỳnh Diệp 29
SỰ PHÂN PHỐI CÁC VẬT VÀO TRONG CÁC HỘP
 Định lí 4:
 Số cách phân phối n vật khác nhau vào k hộp khác 
 nhau sao cho có ni vật được đặt vào hộp thứ i, với i= 1, 2, 
 ..., k, bằng:
 풏!
 풏 ! 풏 !  풏풌!
 Ví dụ:
 • Có bao nhiêu cách chia một cỗ bài chuẩn 52 quân thành những
 tay bài gồm 5 quân cho 4 người chơi.
 Toán rời rạc Nguyễn Quỳnh Diệp 30
BÀI TẬP
 . Bài 6: Có bao nhiêu cách chọn 12 chiếc bánh từ một cửa
 hàng có 21 loại bánh khác nhau
 . Bài 7: Có bao nhiêu cách phân phối 12 viên bi giống hệt
 nhau vào sáu ngăn phân biệt.
 . Bài 8: Có bao nhiêu cách phân phối 12 vật khác nhau vào
 6 ngăn phân biệt, mỗi ngăn 2 vật.
 31
 Toán rời rạc Nguyễn Quỳnh Diệp 31
 4.5. HỆ THỨC TRUY HỒI
Toán rời rạc Nguyễn Quỳnh Diệp 32
CÁC HỆ THỨC TRUY HỒI
 • Một số bài toán đếm không thể giải được bằng kĩ thuật
 đếm thông thường
 • Có thể giải bằng cách tìm mối quan hệ, gọi là các hệ thức
 truy hồi
 Toán rời rạc Nguyễn Quỳnh Diệp 33
CÁC HỆ THỨC TRUY HỒI
 Định nghĩa 1:
 Hệ thức truy hồi đối với dãy số {an} là phương trình biểu diễn an
 qua một hay nhiều số hạng đứng trước nó, cụ thể là a0, a1, ..., an-1
 với mọi số nguyên n n0 ,trong đó n0 là một số nguyên không âm.
 Dãy số được gọi là lời giải hay là nghiệm của hệ thức truy hồi nếu
 các số hạng của nó thỏa mãn hệ thức truy hồi này.
 Ví dụ:
 Một hệ thức truy hồi an = 2an-1 - an-2 với a0 = 1, a1 = 3 
 thì nghiệm của hệ thức truy hồi là: 
 an = 2n+1
 Toán rời rạc Nguyễn Quỳnh Diệp 34
CÁC HỆ THỨC TRUY HỒI
 Ví dụ 1:
 Cho {an} là dãy số thỏa mãn hệ thức truy hồi
 an = an-1 – an-2 với n = 2, 3, 4,... và giả sử a0 = 3, a1 = 5. 
 Tìm a2, a3.
 Ví dụ 2:
 Hãy xác định xem dãy {an} trong đó an =3n với mọi n
 nguyên không âm có phải là lời giải của hệ thức truy hồi
 an = 2an-1 – an-2 với n = 2, 3, 4... hay không?
 n
 Cũng câu hỏi như vậy đối với an = 2 và an = 5
 Toán rời rạc Nguyễn Quỳnh Diệp 35
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
Ví dụ 1:
 Lãi kép. Giả sử một người gửi 10.000$ vào tài khoản của mình tại 
 một ngân hàng với lãi suất kép 11% mỗi năm. Hỏi sau 30 năm anh ta 
 có bao nhiêu tiền trong tài khoản của mình?
 Giải:
 - Gọi Pn là tổng số tiền có trong tài khoản sau n năm
 Pn = Pn-1 + 0.11Pn-1 = 1,11Pn-1
 - Như vậy:
 - P1 = 1,11P0
 2
 - P2 = 1,11P1 = (1,11) P0
 - ...
 n
 - Pn = 1,11Pn-1 = (1,11) P0
 30
 - Thay n = 30 vào công thức P30 = (1,11) . 10000 = 228 923$
 Toán rời rạc Nguyễn Quỳnh Diệp 36
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
Ví dụ 2:
 Họ nhà thỏ và các số Fibonacci. Một cặp thỏ mới sinh được thả
 trên một hòn đảo. Giả sử rằng một cặp thỏ chưa sinh sản được trước
 khi đầy 2 tháng tuổi. Kể từ khi chúng đầy 2 tháng tuổi, mỗi tháng
 chúng đẻ được một đôi thỏ con. Tìm công thức truy hồi tính số
 cặp thỏ trên đảo sau n tháng với giả sử các con thỏ là trường thọ.
 Toán rời rạc Nguyễn Quỳnh Diệp 37
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
 Số cặp thỏ trên đảo
 số cặp đẻ thêm số cũ thêm
 Toán rời rạc Nguyễn Quỳnh Diệp 38
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
 Số cặp thỏ trên đảo
 số cặp đẻ thêm số cũ thêm
 Toán rời rạc Nguyễn Quỳnh Diệp 39
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
 Số cặp thỏ trên đảo
 số cặp đẻ thêm số cặp cũ
 Toán rời rạc Nguyễn Quỳnh Diệp 40
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
 Số cặp thỏ trên đảo
 số cặp đẻ thêm số cặp cũ
 Toán rời rạc Nguyễn Quỳnh Diệp 41
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
 Giải:
 - Giả sử fn là số cặp thỏ sau n tháng, với n = 1, 2, 3,...
 - Tháng 1 số cặp thỏ trên đảo là f1 = 1
 - Tháng 2 số cặp thỏ trên đảo là f2 = 1
 - Tháng 3 số cặp thỏ f3 = 1 + 1 = f1 + f2
 - Tháng 4 số cặp thỏ f4 = 1 + 2 = f2 + f3
 - Tháng n số cặp thỏ trên đảo là fn = fn-1 + fn-2 , fn-1 số cặp thỏ 
 tháng trước, fn-2 số cặp thỏ mới đẻ
 Toán rời rạc Nguyễn Quỳnh Diệp 42
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
Ví dụ 3:
 Tháp Hà Nội. Do Édouard Lucas đưa ra cuối thế kỉ XIX.
 Cọc 1 Cọc 2 Cọc 3
 Toán rời rạc Nguyễn Quỳnh Diệp 43
MÔ HÌNH HÓA BẰNG CÁC HỆ THỨC TRUY HỒI
Giải:
 - Gọi Hn là số bước dịch chuyển để giải câu đố tháp Hà Nội với n đĩa
 - Dịch chuyển n-1 đĩa từ cọc 1 sang cọc 3, phải dùng Hn-1 lần
 - Dịch chuyển đĩa n từ cọc 1 sang cọc 2
 - Cuối cùng, mất Hn-1 lần để dịch chuyển n-1 đĩa từ cọc 3 sang cọc 2
 - Ta có hệ thức truy hồi:
 Hn = 2.Hn-1 + 1, với H1 = 1
 2
 - Hn = 2.Hn-1 + 1 = 2.(2Hn-2 + 1) + 1 = 2 Hn-2 + 2 + 1
 2 3 2
 = 2 (2.Hn-3 + 1) + 2 + 1 = 2 Hn-3 + 2 + 2 + 1
 n-1 n-2
 ... = 2 H1 + 2 +... + 2 + 1
 = 2n-1 + 2n-2 +... + 2 + 1
 = 2n -1
 Toán rời rạc Nguyễn Quỳnh Diệp 44
 BÀI TẬP
 n n
. Bài 1: Giả sử an = 2 + 5.3 , với n = 0, 1, 2,...
 a) Tìm a1, a2 ,a3 và a4
 b) CM: a2 = 5a1 – 6a0 , a3 = 5a2 – 6a1 và a4 = 5a3 – 6a2 
 c) CMR: an = 5an-1 – 6an-2 với mọi số nguyên n 2
. Bài 2: Chứng tỏ rằng dãy {an} là nghiệm của hệ thức truy hồi 
 an=an-1 + 2an-2 + 2n – 9 nếu:
 a) an = -n + 2
 n
 b) an = 5(-1) – n + 2
 45
 Toán rời rạc Nguyễn Quỳnh Diệp 45
 BÀI TẬP
. Bài 3: Một nhân viên bắt đầu làm việc tại một công ti từ năm 1999 
 với lương khởi điểm là 50 000 đô la một năm. Hằng năm anh ta 
 được nhận thêm 1000 đô la và 5% lương của năm trước.
 a) Hãy thiết lập hệ thức truy hồi tính lương của nhân viên đó sau 
năm 1999 n năm.
b)Lương năm 2007 của anh ta là bao nhiêu?
c)Hãy tìm công thức tường minh tính lương của nhân viên này sau 
năm 1999 n năm
 46
 Toán rời rạc Nguyễn Quỳnh Diệp 46
4.6. GIẢI CÁC HỆ THỨC TRUY HỒI
 Toán rời rạc 47
HỆ THỨC TRUY HỒI TUYẾN TÍNH
 Định nghĩa 1:
 Một hệ thức truy hồi tuyến tính thuần nhất bậc k với hệ số hằng 
 số là hệ thức truy hồi có dạng:
 an = c1an-1 + c2an-2 + ... + ckan-k 
 trong đó: c1 , c2 , ck là các số thực và ck 0
 • Tuyến tính vì vế phải là tổng các tích của các số hạng trước
 của dãy
 • Thuần nhất vì mọi số hạng đều có dạng aj nhân với hệ số
 • Bậc k là vì an được biểu diễn qua k số hạng đứng trước
 Toán rời rạc Nguyễn Quỳnh Diệp 48
HỆ THỨC TRUY HỒI TUYẾN TÍNH
Ví dụ:
 - Hệ thức truy hồi Pn = (1.11)Pn-1 là hệ thức truy hồi tuyến tính 
 thuần nhất bậc nhất
 2
 - Hệ thức truy hồi an = an-1 + (an-1) không là tuyến tính
 - Hệ thức truy hồi Hn = 2Hn-1 + 1 không là thuần nhất
 - Hệ thức truy hồi Bn =nBn-1 không có hệ số hằng
 Toán rời rạc Nguyễn Quỳnh Diệp 49
GIẢI HỆ THỨC TRUY HỒI TUYẾN TÍNH
 Phương pháp cơ bản: 
 n
 • Tìm nghiệm dạng an = r , trong đó r là hằng số
 n
 • an = r là nghiệm của HTTH: an=c1an-1+ c2an-2 +... +ckan-k
 n n-1 n-2 n-k 
 nếu và chỉ nếu r = c1r + c2r +... +ckr (*)
 • Chia cả 2 vế cho rn-k . Khi đó (*) tương đương phương trình: 
 k k-1 k-2
 r - c1r - c2r - ... +ck-1r – ck = 0 (1)
 n
 • Do đó, an = r là nghiệm nếu và chỉ nếu r là nghiệm phương trình
 (1)
 • Phương trình (1) gọi là phương trình đặc trưng
 • Nghiệm của phương trình (1) gọi là nghiệm đặc trưng của hệ
 thức truy hồi
 Toán rời rạc Nguyễn Quỳnh Diệp 50
GIẢI HTTH TUYẾN TÍNH BẬC 2
 Định lí 1:
 Cho hệ thức truy hồi an = c1an-1 + c2an-2 với c1 , c2 là hai số
 thực. 
 2
 Giả sử phương trình đặc trưng r – c1r – c2 = 0 có hai nghiệm
 phân biệt là r1, r2. 
 Khi đó {an} là nghiệm của HTTH nếu và chỉ nếu
 n n
 an = 1r1 + 2r2
 với n = 0, 1, 2,... trong đó 1, 2 là các hằng số.
 Ví dụ 1: Tìm nghiệm của hệ thức truy hồi
 an = an-1 + 2an-2 với a0 = 2, a1 = 7
 Toán rời rạc Nguyễn Quỳnh Diệp 51
GIẢI HTTH TUYẾN TÍNH BẬC 2
 Định lí 2:
 Cho hệ thức truy hồi an = c1an-1 + c2an-2 với c1 , c2 là hai số 
 thực, c2 0. 
 2
 Giả sử phương trình đặc trưng r – c1r – c2 = 0 có nghiệm kép r0
 Khi đó {an} là nghiệm của hệ thức truy hồi nếu và chỉ nếu
 n n
 an = 1r0 + 2nr0
 với n = 0, 1, 2 ,... trong đó 1, 2 là các hằng số.
 Ví dụ 2: Tìm nghiệm của hệ thức truy hồi
 an = 6an-1 - 9an-2 với a0 = 1, a1 = 6
 Toán rời rạc Nguyễn Quỳnh Diệp 52
GIẢI HTTH TUYẾN TÍNH TỔNG QUÁT
 Định lí 3:
 Cho hệ thức truy hồi an = c1an-1 + c2an-2 + ckan-k với c1 , c2 ,..., 
 ck là các số thực.
 k k-1 
 Giả sử phương trình đặc trưng r – c1r – ... – ck =0
 có k nghiệm phân biệt r1, r2, ..., rk. 
 Khi đó, dãy {an} là nghiệm của hệ thức truy hồi nếu và chỉ nếu
 n n n
 an = 1r1 + 2r2 + ... + krk ,
 với n = 0, 1, 2 ,... trong đó 1, 2 ,..., k là các hằng số.
 Ví dụ 3: Tìm nghiệm của hệ thức truy hồi
 an = 6an-1 - 11an-2 + 6an-3 với a0 = 2, a1 = 5, a2 = 15
 Toán rời rạc Nguyễn Quỳnh Diệp 53
 BÀI TẬP
. Bài 4: Trong các hệ thức truy hồi sau đây, hệ thức nào là tuyến tính
 thuần nhất với hệ số hằng số. Bậc của các hệ thức đó là bao nhiêu?
 a) an =3an-1 +4an-2 + 5an-3
 b) an = 2nan-1 + an-2 c)an = an-1 + an-4 
 2
 d) an = an-1 + 2 e) an = an-1 + an-2
. Bài 5: Giải các hệ thức truy hồi cùng các điều kiện đầu sau:
 a) an = 2an-1 , với n 1, a0 = 3
 b) an = 5an-1 - 6an-2 , với n 2, a0 = 1, a1 = 0
 c) an = 4an-1 - 4an-2 , với n 2, a0 = 6, a1 = 8
 Toán rời rạc Nguyễn Quỳnh Diệp 54
 4.7. NGUYÊN LÍ BÙ TRỪ
Toán rời rạc Nguyễn Quỳnh Diệp 55
NGUYÊN LÍ BÙ TRỪ
 • Có bao nhiêu phần tử trong hợp của hai tập hợp hữu hạn phần tử?
 | A  B | = | A | + | B | - | A  B |
Ví dụ 1:
 Lớp toán rời rạc có 25 sinh viên chuyên ngành tin học, 13 sinh viên
 chuyên ngành toán và tám sinh viên theo học cả ngành toán lẫn tin
 học. Hỏi trong lớp này có bao nhiêu sinh viên, nếu mỗi sinh viên
 theo ngành toán hoặc ngành tin hoặc theo học cả toán và tin?
 Ví dụ 2:
 Giả sử trong trường có 1807 sinh viên năm thứ nhất. Trong số này có
 453 người chọn môn tin học, 547 người chọn môn toán và 299 người
 học cả hai môn toán và tin. Hỏi có bao nhiêu sinh viên không theo
 học toán cũng không học tin?
 Toán rời rạc Nguyễn Quỳnh Diệp 56
NGUYÊN LÍ BÙ TRỪ
 • Trường hợp 3 tập hợp:
 | A  B  C | = | A | + | B | + | C | - | A  B | - | A  C | - | C  B |
 + | A  B  C |
 Toán rời rạc Nguyễn Quỳnh Diệp 57
NGUYÊN LÍ BÙ TRỪ
Ví dụ 1:
 Biết rằng có 1232 sinh viên học tiếng Tây Ban Nha, 879 sinh viên
 học tiếng Pháp và 114 sinh viên học tiếng Nga. Ngoài ra còn biết
 rằng 103 sinh viên học cả tiếng Tây Ban Nha và tiếng Pháp, 23 sinh
 viên học cả tiếng Tây Ban Nha và tiếng Nga, 14 sinh viên học cả
 tiếng Pháp và tiếng Nga. Nếu tất cả 2092 sinh viên đều theo học ít
 nhất một ngoại ngữ, thì có bao nhiêu sinh viên học cả ba thứ tiếng?
 Toán rời rạc Nguyễn Quỳnh Diệp 58
NGUYÊN LÍ BÙ TRỪ
 Định lí 1:
 NGUYÊN LÍ BÙ TRỪ. Cho A1 , A2,A3 là các tập hữu hạn. Khi đó:
 ∪ ∪ ⋯ ∪ 풏 = 풊 − | 풊 ∩ 풋|
 ≤풊≤풏 ≤풊<풋≤풏
 풏+ 
 + | 풊 ∩ 풋∩ 풌 | −  + − | ∩ ∩ ⋯ ∩ 풏|
 ≤풊<풋<풌≤풏
 Toán rời rạc Nguyễn Quỳnh Diệp 59
NGUYÊN LÍ BÙ TRỪ
 Ví dụ:
 Có bao nhiêu phần tử trong hợp của bốn tập hợp, nếu mỗi
 tập có 100 phần tử, mỗi cặp tập hợp có chung 50 phần tử,
 mỗi bộ ba tập hợp có 25 phần tử chung và có năm phần tử
 thuộc cả 4 tập hợp.
 Toán rời rạc Nguyễn Quỳnh Diệp 60
BÀI TẬP
. Bài 5: Giả sử trong một sọt táo chứa 100 quả có 20 quả bị 
 sâu và 15 quả bị giập nát. Chỉ những quả táo không có sâu 
 hoặc không giập nát mới có thể bán được. Hỏi nếu có 10 
 quả táo vừa bị sâu vừa bị giập nát thì có bao nhiêu quả táo 
 trong sọt có thể bán?
 61
 Toán rời rạc Nguyễn Quỳnh Diệp 61
DẠNG KHÁC CỦA NGUYÊN LÍ BÙ TRỪ
 • Giả sử Ai là tập con chứa các phần tử có tính chất P1 , P2,
 ,Pn kí hiệu N(P1P2...Pn)
 | A1  A2  ...  An | = N(P1P2...Pk)
 • Nếu số các phần tử không có tính chất nào trong số n
 ’ ’ ’
 tính chất P1P2...Pn được kí hiệu N(P1 P2 ...Pn )
 ’ ’ ’
 N(P1 P2 ...Pk ) = N - | A1  A2  ...  An | 
 Toán rời rạc Nguyễn Quỳnh Diệp 62
ỨNG DỤNG NGUYÊN LÍ BÙ TRỪ
 Ví dụ 1:
 Phương trình x1 + x2 + x3 = 11 có bao nhiêu nghiệm, trong
 đó x1, x2, x3 là các số nguyên không âm với x1 3, x2 4 và
 x3 6.
 Ví dụ 2:
 Tìm số các số nguyên tố không vượt quá 100?
 Toán rời rạc Nguyễn Quỳnh Diệp 63
 4.4. CÁC HỆ SỐ NHỊ THỨC
Toán rời rạc Nguyễn Quỳnh Diệp 64
CÁC HỆ SỐ NHỊ THỨC
 • Nhị thức là tổng của hai số hạng
 Định lí nhị thức
 Cho x và y là hai biến và n là một số nguyên dương. Khi đó:
 풏
 (풙 + 풚)풏= 푪 풏, 풋 풙풏−풋풚풋
 풋= 
 = 푪 풏, 풙풏 + 푪 풏, 풙풏− 풚 + ⋯ + 푪 풏, 풏 − 풙풚풏− + 푪(풏, 풏)풚풏
 Toán rời rạc Nguyễn Quỳnh Diệp 65
CÁC HỆ SỐ NHỊ THỨC
 Ví dụ 1: Tìm khai triển biểu thức (x+y)4
 4
 ( + )4= 4, 푗 4−푗 푗
 푗=0
 = 4,0 4 + 4,1 3 + 4,2 2 2 + 4,3 3 + 4,4 4
 = 풙ퟒ + ퟒ풙 풚 + 풙 풚 + ퟒ풙풚 + 풚ퟒ
 Ví dụ 2: Tìm hệ số của x12y13 khai triển biểu thức (2x-3y)25
 Toán rời rạc Nguyễn Quỳnh Diệp 66
CÁC HỆ SỐ NHỊ THỨC
 Nếu n là số nguyên không âm, thì:
 풏
 Hệ quả 1
 푪 풏, 풌 = 풏
 풌= 
 Nếu n là số nguyên dương, khi đó:
 풏
 Hệ quả 2 (− )풌푪 풏, 풌 = 
 풌= 
 Nếu n là số nguyên không âm, thì:
 풏
 Hệ quả 3 풌푪 풏, 풌 = 풏
 풌= 
 Toán rời rạc Nguyễn Quỳnh Diệp 67
HẰNG ĐẲNG THỨC PASCAL VÀ TAM GIÁC PASCAL
 Định lí 1
 HẰNG ĐẲNG THỨC PASCAL. Cho n và k là các số nguyên 
 dương, với n k. Khi đó:
 푪 풏 + , 풌 = 푪 풏, 풌 − + 푪(풏, 풌)
 푛 + 1 푛 푛
 = +
 − 1 
 Toán rời rạc Nguyễn Quỳnh Diệp 68
HẰNG ĐẲNG THỨC PASCAL VÀ TAM GIÁC PASCAL
 푛 + 1 푛 푛
 = +
 − 1 
 Toán rời rạc Nguyễn Quỳnh Diệp 69
BÀI TẬP
. Bài 7: Tìm khai triển (x + y)7
. Bài 8: Tìm hệ số của x101y99 trong khai triển của (2x-3y)200
 70
 Toán rời rạc Nguyễn Quỳnh Diệp 70
 84
Nguyễn Quỳnh Diệp