Tìm số nghiệm nguyên không âm của phương trình x1+x2+x3+x4=16

Bài này có thể đưa về dạng toán đã biết trước là đếm số nghiệm nguyên không âm của phương trình x1+x2+x3+x4=30 với x1>=a,x2>=b,x3>=c x+y+z+t=30-a-b-c=m với x=x1-a,y=x2-b,z=x3-c

thì số nghiệm là C[m+3,3] { C là tổ hợp } [1]

đặt F[a,b,c] tương ứng là kết quả của bài toán trên. Thì kết của của bài toán đề ra F[0,0,0]-F[18,0,0]-F[0,11,0]-F[0,0,9]+F[18,11,0]+F[18,0,9]+F[0,11,9]-F[18,11,9]

tính kết quả dựa trên công thức [1] thì kết quả bài toán = C[33,3]-C[33-18,3]-C[33-11,3]-C[33-9,3]+C[33-18-11,3]+C[33-18-9,3]+C[33-11-9,3] =1747

NGUYÊN LÝ BÙ TRỪBÀI 6 TRANG 44_1Có bao nhiêu hoán vị của các số tự nhiên 1, 2…10 màtrong đó 3 số 1, 2, 3 không đứng cạnh nhau theo thứtự tăng dần.GIẢI: Gọi |A| là tập các hoán vị của các số tự nhiên từ 1…10=> |A| =10!Gọi |A1| là tập các số tự nhiên gồm 3 số 1, 2, 3 gomthành một nhóm và theo thứ tự tăng dần, và các sốcòn lại 4…10. Như vậy |A1| là tập hoán vị của 8 số => |A1|=8!NGUYÊN LÝ BÙ TRỪBÀI 6 TRANG 44_2Gọi |A2| là tập các số tự nhiên trong đó 3 số 1,2, 3 không đứng cạnh nhau theo thứ tự tăngdần Theo nguyên lý bù trừ, ta thu được|A2| = 10! - 8! = 3588480 [ hoán vị ]BÀI 7 TRANG 44, 45Hỏi phương trình x1 + x2 + x3 + x4 = 29 có bao nhiêu nghiệmnguyên không âm thỏa mãn x1 ≤ 3, x2 ≤ 12, x3 ≤ 5, x4 ≤ 10GIẢI: Theo giả thiết ta có x1 + x2 + x3 + x4 = 29[3 − x1 ] + [12 − x2 ] + [5 − x3 ] + [10 − x4 ] = 1 Đặt t1 = 3 − x1 , t2 = 12 − x2 , t3 = 5 − x3 , t4 = 10 − x4→¬=> t1 ≥ 0, t 2 ≥ 0, t3 ≥ 0, t4 ≥ 0 và t1 ≤ 3, t2 ≤ 12, t3 ≤ 5, t4 ≤ 10Điều kiện sau là hiển nhiên vớI các nghiệm của pt t1 + t2 + t3 + t4 = 1Bài toán trở về trường hợp bài toán chia tiềnSố nghiệm của phương trình tương ứng với số cách chia tiềnÁp dụng vào bai toán => số nghiệm là :cnk+−1k −1c14+−41−1= 4 [ nghiệm]BÀI 8 TRANG 45_1Một lớp có 50 học sinh làm bài kiểm tra gồm 3 câu hỏi.Biết rằng mỗi học sinh làm được ít nhất một câu, và sốhọc sinh làm được câu 1 là 40, câu 2 là 35, câu 3 là30. Chứng minh rằng số học sinh làm được 3 câukhông vượt quá 27.GIẢI: Gọi tập hợp số học sinh làm được số câu hỏi 1 là :|X1| Gọi tập hợp số học sinh làm được số câu hỏi 2 là :|X2| Gọi tập hợp số học sinh làm được số câu hỏi 3 là :|X3| Theo giả thiết ta có : |X1|=40 , |X2|=35,|X3|=30 vàBÀI 8 TRANG 45_2Theo nguyên lý của tập hợp ta có| X 1 ∪ X 2 ∪ X 3|= | X 1| + | X 2 | + | X 3| − | X 1 ∩ X 2 | − | X 2 ∩ X 3|− | X 1 ∩ X 3| + | X 1 ∩ X 2 ∩ X 3|Đặt | X 1 ∩X 2 ∩X 3 |=K=> 50 =105- | X 1 ∩ X 2 | − | X 1 ∩ X 3 | − | X 3 ∩ X 1| + KĐặt K1 =| X 1 ∩ X 2 | − | X 1 ∩ X 2 ∩ X 3 |≥ 0K 2 =| X 2 ∩ X 3 | − | X 1 ∩ X 2 ∩ X 3 |≥ 0K 3 =| X 3 ∩ X 1| − | X 1 ∩ X 2 ∩ X 3 |≥ 0BÀI 8 TRANG 45_3Do đó ta có : 50 = 105 - [3K+K1+K2+K3] + K=>2K ≤ 55 [ do K1+K2+K3 ≥ 0 ] => K ≤ 27Vậy số học sinh làm không quá được cả 3 câukhông quá 27[ đpcm]

Toán rời rạc 2 counting

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây [842.19 KB, 81 trang ]

Học viện Công nghệ Bưu chính Viễn thông
Khoa Công nghệ thông tin 1

Toán rời rạc 1

Bài toán đếm
Ngô Xuân Bách


Nội dung


Giới thiệu bài toán



Các nguyên lý đếm cơ bản



Quy về bài toán con



Hệ thức truy hồi



Phương pháp hàm sinh



Bài tập

2

//www.ptit.edu.vn


Giới thiệu bài toán đếm
Bài toán đếm



o
o

Là bài toán đếm xem có bao nhiêu cấu hình tổ hợp có thể được
tạo ra với những quy tắc đã nêu?
Lời giải thường phụ thuộc vào một số tham số ban đầu và người
ta cố gắng biều diễn những phụ thuộc này bằng những công thức
toán học

Nguyên tắc chung giải bài toán đếm



o

Để đếm các cấu hình đã cho, người ta tìm cách đưa về các cấu
hình quen thuộc bằng cách thiếp lập một quan hệ 1-1 giữa chúng

Ứng dụng của bài toán đếm trong khoa học máy tính



o
o

3

Ước lượng số phép toán thực hiện trong một giải thuật, chương
trình máy tính
Ước lượng độ phức tạp thời gian và không gian của giải thuật
//www.ptit.edu.vn


Các phương pháp giải quyết bài toán đếm
Sử dụng các nguyên lý đếm cơ bản: nguyên lý cộng,
nguyên lý nhân, nguyên lý bù trừ
Qui về các bài toán con: Phân tích lời giải bài toán
đếm phức tạp thành những bài toán con. Trong đó, mỗi
bài toán con có thể giải được bằng các nguyên lý đếm cơ
bản
Sử dụng hệ thức truy hồi: Xây dựng công thức tính số
nghiệm tổng quát bất kỳ dựa vào biểu diễn các số hạng
biết trước
Phương pháp hàm sinh: Sử dụng hàm sinh của một
dãy số để đếm các cấu hình tổ hợp









4

//www.ptit.edu.vn


Nội dung


Giới thiệu bài toán



Các nguyên lý đếm cơ bản



Quy về bài toán con



Hệ thức truy hồi



Phương pháp hàm sinh



Bài tập

5

//www.ptit.edu.vn


Nguyên lý cộng [nhắc lại]
Nếu 𝐴 và 𝐵 là hai tập rời nhau thì
𝐴∪𝐵 = 𝐴 + 𝐵
Nếu *𝐴1 , 𝐴2 , … , 𝐴𝑘 + là một phân hoạch của tập hợp 𝑋 thì
𝑋 = 𝐴1 + 𝐴2 + ⋯ + 𝐴𝑘





Nếu có 𝐾 việc, việc thứ 𝑖 thực hiện bằng 𝑛𝑖 cách và thực
hiện một cách tuần tự. Khi đó sẽ có 𝑛1 + 𝑛2 +. . + 𝑛𝐾 cách
thực hiện một trong 𝐾 việc nêu trên.



6

//www.ptit.edu.vn


Ví dụ 1
Bài toán: Giả sử 𝑁, 𝑀 là hai số tự nhiên đã xác định giá
trị. Hãy cho biết giá trị của 𝑆 sau khi thực hiện đoạn
chương trình.



𝑆 = 0;
for [𝑖 = 1; 𝑖