Bài toán đếm và bài toán tồn tại: Bài giảng Toán ứng dụng

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

MÔN HỌC: TOÁN ỨNG DỤNG

Bài 1: CƠ SỞ LOGIC Bài 2: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI Bài 3: LÝ THUYẾT ĐỒ THỊ Bài 4: THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ Bài 5: CÂY VÀ CÁC ỨNG DỤNG

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

Bài 2: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TẬP HỢP

2. QUAN HỆ

2.1 Khái niệm quan hệ 2.2 Ma trận biểu diễn quan hệ

BÀI TOÁN ĐẾM 3.1 Nguyên lý cộng 3.2 Nguyên lý nhân 3.3 Nguyên lý bù trừ

4. GIẢI TÍCH TỔ HỢP 4.1 Hoán vị 4.2 Chỉnh hợp 4.3 Tổ hợp 4.4 Hoán vị lặp 4.5 Tổ hợp và chỉnh hợp lặp

5. BÀI TOÁN TỒN TẠI

5.1 Nguyên lý Dirichlet 5.2 Nguyên lý Dirichlet tổng quát

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

Cơ sở Logic

1. Tập hợp

1.1 Khái niệm

Tập hợp là một khái niệm cơ bản của Toán học, không được định nghĩa.

Có thể hiểu tập hợp là một nhóm đối tượng có chung một tính chất nào đó.

Ví dụ:

1) Tập hợp sinh viên một trường đại học.

2) Tập hợp các số nguyên

3) Tập hợp các bài thơ của Nguyễn Bính.

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

Cơ sở Logic

1. Tập hợp

1.1 Khái niệm

Những đối tượng tạo thành một tập hợp gọi là phần tử (hay điểm) của tập hợp.

Nếu a là một phần tử của tập hợp A, ta viết aA (đọc "a thuộc A")

Trường hợp ngược lại, ta viết a A (đọc "a không thuộc A")

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

Cơ sở Logic

1. Tập hợp

1.2 Diễn tả tập hợp

Cách 1: Bằng lời

"A là tập hợp bốn số nguyên dương đầu tiên"

"B là tập hợp các màu trên quốc kỳ Pháp"

Cách 2: Liệt kê các phần tử, đặt giữa cặp { }

X = {4, 2, 1, 3}

Y= {đỏ, trắng, xanh}

Cách 3: Đưa ra tính chất đặc trưng

A={ n N | n chia hết cho 3}

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Tập hợp

1.3 Lực lượng của tập hợp

Số phần tử của tập hợp A được gọi là lực

lượng của tập hợp, kí hiệu |A|.

Nếu tập hợp A có hữu hạn phần tử, ta nói A

hữu hạn. Ngược lại, ta nói A vô hạn.

Tập hợp không có phần tử nào gọi là tập hợp

rỗng, kí hiệu là Ø

Ví dụ

Tập hợp số N, Z, R, là các tập vô hạn Tập hợp X={1,3,4,5} là tập hữu hạn, Ta có: |X|=4

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Tập hợp

1.4 Tập hợp con

Nếu mọi phần tử của tập hợp B đều là phần tử

của tập hợp A thì ta nói B là tập hợp con của A (hay B được bao hàm trong A).

Kí kiệu: B  A hay A  B B  A  (x | x B  x A) P(A)-là kí hiệu tập hợp tất cả tập con của A

Ví dụ

A={1,2}, B={1} - là tập con của A P(A)={Ø,{1},{2},{1,2}} Ø: là tập con của mọi tập hợp

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Tập hợp

1.5 Biểu đồ Venn

Biểu diễn tập hợp bởi một đường cong kín Mỗi phần tử của tập hợp được đặc trưng bởi

điểm nằm trong đường cong ấy

Ví dụ

A  B

C ≠ D

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Tập hợp

1.6 Các phép toán trên tập hợp

Phép hợp:

Hợp của tập hợp A và B là một tập hợp tạo bởi tất cả các phần tử thuộc A hoặc thuộc B.

Ký hiệu: A  B

A  B= {x  xA  xB}

Ví dụ

B

A

A= {a,b,c,d} B= {c,d,e,f} A  B = {a,b,c,d,e,f}

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Tập hợp

1.6 Các phép toán trên tập hợp

Phép giao:

Giao của tập hợp A và B là một tập hợp tạo bởi các phần tử thuộc A và thuộc B.

Ký hiệu: A  B

A  B ={x  xA  xB}

Ví dụ

B

A

A= {a,b,c,d} B= {c,d,e,f} A  B = {c,d}

A

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Tập hợp

1.6 Các phép toán trên tập hợp

Hiệu của hai tập hợp:

Hiệu của tập hợp A với B là một tập hợp tạo bởi tất cả các phần tử thuộc tập A mà không thuộc tập B. Kí hiệu: A\B A\B= { x  xA  xB}

Phần bù:

Cho B  A, A\B gọi là bù của B trong A

A

Ví dụ

BB

AA\B

A= {a,b,c,d} B= {c,d,e,f} A\B = {a,b}

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Tập hợp

1.7 Tính chất của phép toán trên tập hợp a/. Tính giao hoán: A  B = B  A A  B = B  A.

b/. Tính kết hợp:

(A  B)  C = A  (B  C) (A  B)  C = A  (B  C)

c/. Tính phân phối:

A  (B  C) = (A  B)  (A  C) A  (B  C) = (A  B)  (A  C)

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Tập hợp

1.7 Tính chất của phép toán trên tập hợp d/. Công thức De Morgan:

Avaø

AB 

AB 

e/. Tính lũy đẳng:

A  A = A

A  A = A

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Tập hợp

1.8 Tích Descartes của các tập hợp

Tích Descartes của tập hợp A với tập hợp B là tập hợp gồm tất cả các cặp thứ tự (x,y) với xA và xB

Ký hiệu là A B hoặc A.B

A B = {(x,y)| xA, yB}

Tích của 2 tập hợp không có tính chất giao hoán.

|A x B| = |A| x |B|

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

1. Tập hợp

1.8 Tích Descartes của các tập hợp

I , x



i  



I 

 (x ) i



Tích Đề các của n tập hợp A1, A2,..., An là tập mọi dãy có thứ tự (x1,x2,...,xn), trong đó xi  Ai (i=1,...,n) Kí hiệu A1. A2... An A1. A2...An = {(x1,x2,...,xn)  xiAi (i=1,...,n) } Cách viết khác:

 i I 

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Quan hệ

2.1 Khái niệm

Một quan hệ hai ngôi giữa tập hợp A và tập hợp B là tập con R của AxB. Kí hiệu: R  A x B.

Viết a R b thay cho (a, b)  R Quan hệ từ A đến A được gọi là

quan hệ trên A

R = { (a1, b1), (a1, b3), (a3, b3) }

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Quan hệ

2.1 Khái niệm Ví dụ: Cho A = {1, 2, 3, 4}, R = {(a, b) | (a A, b A, a là ước của b} R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4,4)}

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Quan hệ

2.1 Khái niệm

Một quan hệ n-ngôi giữa các tập hợp A1, A2,..., An là

tập con R của A1x A2x...xAn. Ví dụ: Xét quan hệ 4-ngôi có tên là Sinh viên biểu diễn trong bảng sau:

Mã SV

Họ tên

Ngày sinh

Khóa học

99051110

Tran Anh

20-10-1990

99051111

Hoang Xuan

02-07-1990

99051112

Nguyen Viet

16-11-1990

...

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Quan hệ

2.2 Ma trận biểu diễn quan hệ

Cho R là quan hệ từ A = {a1,a2,…,am} đến B = {b1,b2,…,bn}. Ma trận biểu diễn của R là ma trận cấp m × n MR = [mij] xác định bởi

0 nếu (ai , bj)  R

mij =

1 nếu (ai , bj)  R

1 2



Ví dụ: Nếu R là quan hệ từ A = {1, 2, 3} đến B = {1, 2} với a R b khi a > b. Ma trận biểu diễn của R là MR

  01   11 

    

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

2. Quan hệ

2.2 Ma trận biểu diễn quan hệ Ví dụ: Cho R là quan hệ từ A = {a1, a2, a3} đến B = {b1, b2, b3, b4, b5} R xác định gồm các cặp:

{(a1, b2),(a2, b1), (a2, b3), (a2, b4), (a3, b1), (a3, b3), (a3, b5)}

00010



b1 b2 b3 b4 b5

  01101   10101 

    

a1 a2 a3

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

3. Bài toán đếm

3.1 Nguyên lý cộng Giả sử để thực hiện công việc A có n-phương pháp

- Phương pháp 1 có m1 cách làm - Phương pháp 2 có m2 cách làm - Phương pháp n có mn cách làm

Khi đó số cách chọn thực hiện công việc là m1 + m2 +...+mn

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

3. Bài toán đếm

3.1 Nguyên lý cộng Ví dụ

Cho tập hợp A={1,2,3}. Hỏi có bao nhiêu cách chọn 1 tập con B của A.

Giải:

- t/hợp 1: chọn tập B là tập hợp rỗng- 1 cách chọn

- t/hợp 2: chọn tập B chứa 1 phần tử của A - 3 cách chọn

- t/hợp 3: chọn tập B chứa 2 phần tử của A - 3 cách chọn

- t/hợp 4: chọn tập B chứa 3 phần tử của A - 1 cách chọn

Áp dụng nguyên lý cộng, số cách chọn tính được là 8 cách.

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

3. Bài toán đếm

3.2 Nguyên lý nhân Giả sử một công việc A cần được thực hiện qua n- bước liên tiếp.

- bước 1 có t1 cách làm - bước 2 có t2 cách làm - bước n có tn cách làm

Khi đó số cách chọn thực hiện công việc là t1 x t2 x ... x tn

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

3. Bài toán đếm

3.2 Nguyên lý nhân Ví dụ

Có 3x2 =6 cách đi từ A đến C

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

3. Bài toán đếm

Ví dụ: Cho tập X ={1,2,3,4,5,0} Hỏi có bao nhiêu số tự nhiên có 3 chữ số khác nhau (lấy từ tập X) mà chia hết cho 2 Giải. Gọi số có 3 chữ số là a b c TH1: c=0. Khi đó

c có 1 cách chọn a có 5 cách chọn ( aX\{0} ) b có 4 cách chọn ( bX\{a, 0} )

TH2 . c≠0. Khi đó

TH1 có 1x4x5 =20

c có 2 cách chọn a có 4 cách chọn ( aX\{c, 0} ) b có 4 cách chọn ( bX\{a, c} )

TH2 có 2x4x4 =32

Tổng cộng có 20+32 =52 (số có 3 chữ số thỏa mãn bài toán)

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

3. Bài toán đếm

3.3 Nguyên lý bù trừ Với hai tập hợp A và B thì: |AB| = |A|+|B|-|AB|

A  B

A

B

Ví dụ: Trong một cơ quan có 180 người. Có 55 người biết sử dụng MS-Word, 45 người biết sử dụng MS-Excel và 15 người vừa thạo MS-Word, vừa thạo MS-Excel. Hỏi có bao nhiêu người không sử dụng được cả hai tiện ích? (95)

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

3. Bài toán đếm

3.3 Nguyên lý bù trừ Với ba tập hợp A, B và C thì: |ABC| = |A|+|B|+|C|-|AB|-|BC|-|CA|+|ABC|

BC

A  C

A  B  C

A  B

A B

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

4. Giải tích tổ hợp

4.1 Hoán vị Cho tập hợp A gồm n phần tử. Mỗi cách sắp đặt có thứ tự n phần tử của A được gọi là một hoán vị của n phần tử.

- Số các hoán vị của n phần tử ký hiệu là Pn Pn = n! = 1.2.3... (n-1).n Quy ước 0! =1

Ví dụ Cho A ={a,b,c}. Khi đó A có các hoán vị sau

abc,acb, bac,bca, cab,cba

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

4. Giải tích tổ hợp

4.2 Chỉnh hợp Cho A là tập hợp gồm n phần tử. Mỗi bộ gồm k phần tử (1 k n) sắp thứ tự của tập hợp A được gọi là một

chỉnh hợp chập k của n phần tử

Số các chỉnh hợp chập k của n ký hiệu là



k A n

n !  n k

- Công thức





Ví dụ. Cho X ={abc}. Khi đó X có các chỉnh hợp chập 2 của 3 là: ab, ba, ac, ca, bc, cb.

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

4. Giải tích tổ hợp

4.3 Tổ hợp Cho A là tập hợp gồm n phần tử. Mỗi tập con gồm k phần tử (1 k n) của A (không phân biệt thứ tự) được gọi là một

tổ hợp chập k của n phần tử

Số các tổ hợp chập k của n ký hiệu là



k n

- Công thức



n !   k n k ! Ví dụ. Một lớp có 30 học sinh. Hỏi có bao nhiêu cách chọn 10 bạn?

30C

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

4. Giải tích tổ hợp

4.4 Hoán vị lặp Cho n đối tượng trong đó có ni đối tượng loại i giống hệt nhau (i =1,2,…,k ; n1+ n2,…+ nk= n). Mỗi cách sắp xếp có thứ tự n đối tượng đã cho gọi là một hoán vị lặp của n. Số hoán vị của n đối tượng, trong đó có

n1 đối tượng giống nhau thuộc loại 1, n2 đối tượng giống nhau thuộc loại 2,

...

n ! n !... !k

n n ! 1 2

nk đối tượng giống nhau thuộc loại k, là

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

4. Giải tích tổ hợp

4.4 Hoán vị lặp Ví dụ. Có bao nhiêu chuỗi kí tự khác nhau bằng cách sắp

xếp các chữ cái của từ SUCCESS?

Giải. Trong từ SUCCESS có 3 chữ S, 1 chữ U, 2 chữ C và 1



4 2 0

7 ! 3 !1! 2 !1!

chữ E. Vậy tổng số chuỗi tạo được là

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

4. Giải tích tổ hợp

4.5 Tổ hợp và chỉnh hợp lặp a/. Một chỉnh hợp lặp chập k từ n phần tử là một bộ có thứ tự gồm k phần tử lấy từ n phần tử đã cho, trong đó mỗi phần tử có thể lấy lặp lại. Cách tính:

b/. Một tổ hợp lặp chập k từ n phần tử là một bộ gồm k phần tử (không phân biệt thứ tự), mỗi phần tử có thể lấy lặp lại từ n phần tử đã cho Cách tính:

BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: http://www.ispace.edu.vn

4. Giải tích tổ hợp

4.5 Tổ hợp và chỉnh hợp lặp Ví dụ Có 3 loại nón A, B, C. An mua 2 cái nón. Hỏi An có bao nhiêu cách chọn?



2 3

2   3 2 1

2 4

Ta có mỗi cách chọn là mỗi tổ hợp lặp chập 2 của 3. Cụ thể là AA, AB, AC, BB, BC, CC Ví dụ Để đăng ký một loại hàng hóa mới, người ta dùng 3 chữ số trong 9 chữ số từ 1 đến 9. Hỏi có thể đánh số theo cách này được cho bao nhiêu loại hàng hóa? Kết quả là: 93 = 729