duongthang_2004

New Member

Download miễn phí Giáo trình Toán rời rạc - Bài toán đếm





Sinh các hoán vị:
Có nhiều thuật toán đã được phát triển để sinh ra n! hoán vị của tập {1,2,.,n}. Ta
sẽ mô tả một trong các phương pháp đó, phương pháp liệt kê các hoán vị của tập
{1,2,.,n} theo thứ tự từ điển. Khi đó, hoán vị a1a2.anđược gọi là đi trước hoán vị
b1b2.bnnếu tồn tại k (1 k n), a1= b1, a2= b2,., ak-1= bk-1và ak< bk.
Thuật toán sinh các hoán vị của tập {1,2,.,n} dựa trên thủ tục xây dựng hoán vị
kế tiếp, theo thứ tự từ điển, từ hoán vị cho trước a1a2.an. Đầu tiên nếu an-1< anthì rõ
ràng đổi chỗ an-1và ancho nhau thì sẽ nhận được hoán vị mới đi liền sau hoán vị đã cho.
Nếu tồn tại các số nguyên ajvà aj+1sao cho aj< aj+1và aj+1> aj+2 > . > an, tức là tìm cặp
số nguyên liền kề đầu tiên tính từ bên phải sang bên trái của hoán vị mà số đầu nhỏ hơn
số sau. Sau đó, để nhận được hoán vị liền sau ta đặt vào vị trí thứ j số nguyên nhỏ nhất
trong các số lớn hơn a
jcủa tập aj+1, aj+2, ., an, rồi liệt kê theo thứ tự tăng dần của các số
còn lại của aj, aj+1, aj+2, ., anvào các vị trí j+1, ., n. Dễ thấy không có hoán vị nào đi
sau hoán vị xuất phát và đi trước hoán vị vừa tạo ra.



Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

i tập thành phần. Ta biết rằng việc chọn một phần tử của
tích Descartes A1 x A2 x...x Ak được tiến hành bằng cách chọn lần lượt một phần tử của
A1, một phần tử của A2, ..., một phần tử của Ak. Theo quy tắc nhân ta có:
|A1 x A2 x ... x Ak| = |A1|.|A2|...|Ak|.
2.1.2. Nguyên lý bù trừ:
Khi hai công việc có thể được làm đồng thời, ta không thể dùng quy tắc cộng để
tính số cách thực hiện nhiệm vụ gồm cả hai việc. Để tính đúng số cách thực hiện nhiệm
vụ này ta cộng số cách làm mỗi một trong hai việc rồi trừ đi số cách làm đồng thời cả
hai việc. Ta có thể phát biểu nguyên lý đếm này bằng ngôn ngữ tập hợp. Cho A1, A2 là
hai tập hữu hạn, khi đó
|A1  A2| = |A1| + |A2|  |A1  A2|.
Từ đó với ba tập hợp hữu hạn A1, A2, A3, ta có:
|A1  A2  A3| = |A1| + |A2| + |A3|  |A1  A2|  |A2  A3|  |A3  A1| + |A1  A2  A3|,
và bằng quy nạp, với k tập hữu hạn A1, A2, ..., Ak ta có:
| A1  A2  ...  Ak| = N1  N2 + N3  ... + (1)
k-1Nk,
trong đó Nm (1  m  k) là tổng phần tử của tất cả các giao m tập lấy từ k tập đã cho,
nghĩa là
Nm = |...|
...1 21
21 m
m
i
kiii
ii AAA 

Bây giờ ta đồng nhất tập Am (1  m  k) với tính chất Am cho trên tập vũ trụ hữu
hạn U nào đó và đếm xem có bao nhiêu phần tử của U sao cho không thỏa mãn bất kỳ
một tính chất Am nào. Gọi N là số cần đếm, N là số phần tử của U. Ta có:
N = N  | A1  A2  ...  Ak| = N  N1 + N2  ... + (1)
kNk,
trong đó Nm là tổng các phần tử của U thỏa mãn m tính chất lấy từ k tính chất đã cho.
Công thức này được gọi là nguyên lý bù trừ. Nó cho phép tính N qua các Nm trong
trường hợp các số này dễ tính toán hơn.
25
Thí dụ 3: Có n lá thư và n phong bì ghi sẵn địa chỉ. Bỏ ngẫu nhiên các lá thư vào các
phong bì. Hỏi xác suất để xảy ra không một lá thư nào đúng địa chỉ.
Mỗi phong bì có n cách bỏ thư vào, nên có tất cả n! cách bỏ thư. Vấn đề còn lại
là đếm số cách bỏ thư sao cho không lá thư nào đúng địa chỉ. Gọi U là tập hợp các cách
bỏ thư và Am là tính chất lá thư thứ m bỏ đúng địa chỉ. Khi đó theo công thức về nguyên
lý bù trừ ta có:
N = n!  N1 + N2  ... + (1)
nNn,
trong đó Nm (1  m  n) là số tất cả các cách bỏ thư sao cho có m lá thư đúng địa chỉ.
Nhận xét rằng, Nm là tổng theo mọi cách lấy m lá thư từ n lá, với mỗi cách lấy m lá thư,
có (n-m)! cách bỏ để m lá thư này đúng địa chỉ, ta nhận được:
Nm =
m
nC (n - m)! =
n
k
!
!
và N = n!(1 
1
1!
+
1
2!
 ... + (1)n
1
n!
),
trong đó mnC =
)!(!
!
mnm
n

là tổ hợp chập m của tập n phần tử (số cách chọn m đối
tượng trong n đối tượng được cho). Từ đó xác suất cần tìm là: 1 
1
1!
+
1
2!
 ... + (1)n
1
n!
. Một điều lý thú là xác suất này dần đến e
-1 (nghĩa là còn >
1
3
) khi n khá lớn.
Số N trong bài toán này được gọi là số mất thứ tự và được ký hiệu là Dn. Dưới
đây là một vài giá trị của Dn, cho ta thấy Dn tăng nhanh như thế nào so với n:
n 2 3 4 5 6 7 8 9 10 11
Dn 1 2 9 44 265 1854 14833 133496 1334961 14684570
2.2. NGUYÊN LÝ DIRICHLET.
2.2.1. Mở đầu:
Giả sử có một đàn chim bồ câu bay vào chuồng. Nếu số chim nhiều hơn số ngăn
chuồng thì ít nhất trong một ngăn có nhiều hơn một con chim. Nguyên lý này dĩ nhiên là
có thể áp dụng cho các đối tượng không phải là chim bồ câu và chuồng chim.
Mệnh đề (Nguyên lý): Nếu có k+1 (hay nhiều hơn) đồ vật được đặt vào trong k hộp
thì tồn tại một hộp có ít nhất hai đồ vật.
Chứng minh: Giả sử không có hộp nào trong k hộp chứa nhiều hơn một đồ vật. Khi đó
tổng số vật được chứa trong các hộp nhiều nhất là bằng k. Điều này trái giả thiết là có ít
nhất k + 1 vật.
Nguyên lý này thường được gọi là nguyên lý Dirichlet, mang tên nhà toán học
người Đức ở thế kỷ 19. Ông thường xuyên sử dụng nguyên lý này trong công việc của
mình.
Thí dụ 4: 1) Trong bất kỳ một nhóm 367 người thế nào cũng có ít nhất hai người có
ngày sinh nhật giống nhau bởi vì chỉ có tất cả 366 ngày sinh nhật khác nhau.
26
2) Trong kỳ thi học sinh giỏi, điểm bài thi được đánh giá bởi một số nguyên trong
khoảng từ 0 đến 100. Hỏi rằng ít nhất 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?
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.
3) Trong số những người có mặt trên trái đất, phải tìm được hai người có hàm răng
giống nhau. Nếu xem mỗi hàm răng gồm 32 cái như là một xâu nhị phân có chiều dài
32, trong đó răng còn ứng với bit 1 và răng mất ứng với bit 0, thì có tất cả 232 =
4.294.967.296 hàm răng khác nhau. Trong khi đó số người trên hành tinh này là vượt
quá 5 tỉ, nên theo nguyên lý Dirichlet ta có điều cần tìm.
2.2.2. Nguyên lý Dirichlet tổng quát:
Mệnh đề: Nếu có N đồ vật được đặt vào trong k hộp thì sẽ tồn tại một hộp chứa ít nhất
]N/k[ đồ vật.
(Ở đây, ]x[ là giá trị của hàm trần tại số thực x, đó là số nguyên nhỏ nhất có giá trị lớn
hơn hay bằng x. Khái niệm này đối ngẫu với [x] – giá trị của hàm sàn hay hàm phần
nguyên tại x – là số nguyên lớn nhất có giá trị nhỏ hơn hay bằng x.)
Chứng minh: Giả sử mọi hộp đều chứa ít hơn ]N/k[ vật. Khi đó tổng số đồ vật là
 k (]
N
k
[  1) < k
N
k
= N.
Điều này mâu thuẩn với giả thiết là có N đồ vật cần xếp.
Thí dụ 5: 1) Trong 100 người, có ít nhất 9 người sinh cùng một tháng.
Xếp những người sinh cùng tháng vào một nhóm. Có 12 tháng tất cả. Vậy theo
nguyên lý Dirichlet, tồn tại một nhóm có ít nhất ]100/12[= 9 người.
2) Có năm loại học bổng khác nhau. Hỏi rằng phải có ít nhất bao nhiêu sinh viên để
chắc chắn rằng có ít ra là 6 người cùng nhận học bổng như nhau.
Gọi N là số sinh viên, khi đó ]N/5[ = 6 khi và chỉ khi 5 < N/5  6 hay 25 < N 
30. Vậy số N cần tìm là 26.
3) Số mã vùng cần thiết nhỏ nhất phải là bao nhiêu để đảm bảo 25 triệu máy điện thoại
trong nước có số điện thoại khác nhau, mỗi số có 9 chữ số (giả sử số điện thoại có dạng
0XX - 8XXXXX với X nhận các giá trị từ 0 đến 9).
Có 107 = 10.000.000 số điện thoại khác nhau có dạng 0XX - 8XXXXX. Vì vậy
theo nguyên lý Dirichlet tổng quát, trong số 25 triệu máy điện thoại ít nhất có
]25.000.000/10.000.000[ = 3 có cùng một số. Để đảm bảo mỗi máy có một số cần có ít
nhất 3 mã vùng.
2.2.3. Một số ứng dụng của nguyên lý Dirichlet.
Trong nhiều ứng dụng thú vị của nguyên lý Dirichlet, khái niệm đồ vật và hộp
cần được lựa chọn một cách khôn khéo. Trong phần nay có vài thí dụ như vậy.
27
Thí dụ 6: 1) Trong một phòng họp có n người, bao giờ cũng tìm được 2 người có số
người quen trong số những người dự họp là như nhau.
Số người quen của mỗi người trong phòng họp 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) 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. Vậy theo nguyên lý
...
 

Các chủ đề có liên quan khác

Top