Toán học rời rạc - Lý thuyết đếm
Trong cuộc sống hàng ngày, nhiều khi người ta cần tìm ra số lượng tất cả các kết quả có thể xảy ra cho một loạt các sự kiện. Ví dụ, trong số 50 nam và 38 nữ có thể chọn một ban giám khảo gồm 6 nam và 4 nữ bằng bao nhiêu cách? Có thể tạo ra bao nhiêu số PAN gồm 10 chữ cái khác nhau sao cho năm chữ cái đầu tiên là bảng chữ cái viết hoa, bốn chữ số tiếp theo là chữ số và chữ cái cuối cùng lại là chữ cái viết hoa. Để giải quyết những vấn đề này, lý thuyết toán học về số đếm được sử dụng.Counting chủ yếu bao gồm quy tắc đếm cơ bản, quy tắc hoán vị và quy tắc kết hợp.
Quy tắc Tổng và Sản phẩm
Các Rule of Sum và Rule of Product được sử dụng để phân rã các bài toán đếm khó thành các bài toán đơn giản.
The Rule of Sum- Nếu một chuỗi tác vụ $ T_1, T_2, \ dot, T_m $ có thể được thực hiện theo cách tương ứng $ w_1, w_2, \ dot w_m $ (điều kiện là không có tác vụ nào có thể được thực hiện đồng thời) thì số cách thực hiện thực hiện một trong những tác vụ này là $ w_1 + w_2 + \ dot + w_m $. Nếu chúng ta coi hai nhiệm vụ A và B là rời rạc (tức là $ A \ cap B = \ blankset $), thì về mặt toán học $ | A \ cup B | = | A | + | B | $
The Rule of Product- Nếu một chuỗi nhiệm vụ $ T_1, T_2, \ dot, T_m $ có thể được thực hiện theo các cách $ w_1, w_2, \ dot w_m $ tương ứng và mọi nhiệm vụ đến sau sự xuất hiện của nhiệm vụ trước đó thì sẽ có $ w_1 \ lần w_2 \ times \ dot \ times w_m $ cách để thực hiện các tác vụ. Về mặt toán học, nếu một nhiệm vụ B đến sau một nhiệm vụ A, thì $ | A \ times B | = | A | \ lần | B | $
Thí dụ
Question- Một cậu bé sống ở X và muốn đến trường ở Z. Từ nhà của cậu ấy, cậu ấy phải đến Y trước rồi đến Y đến Z. Cậu ấy có thể đi X đến Y bằng 3 tuyến xe buýt hoặc 2 tuyến tàu hỏa. Từ đó, người đó có thể chọn 4 tuyến xe buýt hoặc 5 tuyến xe lửa để đến Z. Có bao nhiêu cách đi từ X đến Z?
Solution- Từ X đến Y, anh ta có thể đi theo cách $ 3 + 2 = 5 $ (Quy tắc Tổng). Sau đó, anh ta có thể đi Y đến Z theo cách $ 4 + 5 = 9 $ (Quy tắc tổng). Do đó, từ X đến Z anh ta có thể đi theo $ 5 \ nhân lần 9 = 45 $ cách (Quy tắc sản phẩm).
Hoán vị
A permutationlà sự sắp xếp của một số yếu tố theo thứ tự quan trọng. Nói cách khác, Hoán vị là một Tổ hợp có thứ tự của các phần tử.
Ví dụ
Từ một tập S = {x, y, z} bằng cách lấy hai lần một lúc, tất cả các hoán vị là:
$ xy, yx, xz, zx, yz, zy $.
Chúng ta phải tạo một hoán vị của các số có ba chữ số từ tập hợp các số $ S = \ lbrace 1, 2, 3 \ rbrace $. Các số có ba chữ số khác nhau sẽ được tạo thành khi chúng ta sắp xếp các chữ số. Hoán vị sẽ là = 123, 132, 213, 231, 312, 321
Số lần hoán vị
Số hoán vị của 'n' vật khác nhau lấy 'r' tại một thời điểm được ký hiệu là $ n_ {P_ {r}} $
$$ n_ {P_ {r}} = \ frac {n!} {(n - r)!} $$
nơi $ n! = 1.2.3. \ dot (n - 1) .n $
Proof - Để có 'n' phần tử khác nhau.
Có n số cách điền vào vị trí thứ nhất. Sau khi điền vào vị trí đầu tiên (n-1) số phần tử còn lại. Do đó, có (n-1) cách để điền vào vị trí thứ hai. Sau khi điền vào vị trí thứ nhất và thứ hai, (n-2) số phần tử còn lại. Do đó, có (n-2) cách để điền vào vị trí thứ ba. Bây giờ chúng ta có thể tổng quát hóa số cách điền vào vị trí thứ r là [n - (r – 1)] = n – r + 1
Vì vậy, tổng số không có. các cách để điền từ vị trí đầu tiên đến vị trí thứ r -
$ n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1) $
$ = [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ dot 3.2.1] / [(nr) (nr-1) \ dot 3.2.1] $
Vì thế,
$ n_ {P_ {r}} = n! / (nr)! $
Một số công thức quan trọng của hoán vị
Nếu có n phần tử trong đó $ a_1 $ giống nhau ở một loại nào đó thì $ a_2 $ giống nhau; $ a_3 $ giống nhau thuộc loại thứ ba, v.v. và $ a_r $ thuộc loại $ r ^ {th} $, trong đó $ (a_1 + a_2 + ... a_r) = n $.
Khi đó, số hoán vị của n đối tượng này là = $ n! / [(a_1! (a_2!) \ dot (a_r!)] $.
Số hoán vị của n phần tử phân biệt lấy n phần tử tại một thời điểm = $ n_ {P_n} = n! $
Số hoán vị của n phần tử giống nhau lấy r phần tử tại một thời điểm, khi x thứ cụ thể luôn chiếm những vị trí xác định = $ n-x_ {p_ {rx}} $
Số hoán vị của n phần tử khác nhau khi r vật xác định luôn đi kèm với nhau là - $ r! (n − r + 1)! $
Số hoán vị của n phần tử khác nhau khi r thứ xác định không bao giờ kết hợp với nhau là - $ n! - [r! (n − r + 1)!] $
Số hoán vị vòng tròn của n phần tử khác nhau lấy x phần tử tại thời điểm = $ ^ np_ {x} / x $
Số hoán vị vòng tròn của n thứ khác nhau = $ ^ np_ {n} / n $
Một số vấn đề
Problem 1 - Từ một bó gồm 6 thẻ khác nhau, ta có thể hoán vị bao nhiêu cách?
Solution- Vì chúng ta đang lấy 6 quân bài cùng một lúc từ bộ bài 6 quân, hoán vị sẽ là $ ^ 6P_ {6} = 6! = 720 đô la
Problem 2 - Các chữ cái của từ 'READER' có thể được sắp xếp theo bao nhiêu cách?
Solution - Có 6 chữ cái từ (2 E, 1 A, 1D và 2R.) Trong từ 'READER'.
Hoán vị sẽ là $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $
Problem 3 - Các chữ cái của từ 'ORANGE' có thể được sắp xếp như thế nào để các phụ âm chỉ chiếm vị trí chẵn?
Solution- Có 3 nguyên âm và 3 phụ âm trong từ 'ORANGE'. Số cách sắp xếp các phụ âm trong số chúng $ = ^ 3P_ {3} = 3! = 6 $. 3 chỗ trống còn lại sẽ được lấp đầy bởi 3 nguyên âm trong $ ^ 3P_ {3} = 3! = 6 $ cách. Do đó, tổng số hoán vị là $ 6 \ nhân lần 6 = 36 $
Kết hợp
A combination là sự lựa chọn của một số phần tử nhất định mà thứ tự không quan trọng.
Số tất cả các kết hợp của n thứ, lấy r tại một thời điểm là -
$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$
Problem 1
Tìm số tập hợp con của tập hợp $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ có 3 phần tử.
Solution
Tổng số của tập hợp là 6 và chúng ta phải chọn 3 phần tử từ tập hợp. Ở đây, thứ tự không quan trọng. Do đó, số tập hợp con sẽ là $ ^ 6C_ {3} = 20 $.
Problem 2
Có 6 nam và 5 nữ trong một phòng. Trong phòng có bao nhiêu cách chọn 3 nam và 2 nữ?
Solution
Số cách chọn 3 nam trong 6 nam là $ ^ 6C_ {3} $ và số cách chọn 2 nữ trong 5 nữ là $ ^ 5C_ {2} $
Do đó, tổng số cách là - $ ^ 6C_ {3} \ lần ^ 5C_ {2} = 20 \ lần 10 = 200 $
Problem 3
Có bao nhiêu cách chọn 3 nhóm 3 học sinh khác nhau trong tổng số 9 học sinh?
Solution
Hãy để chúng tôi đánh số các nhóm là 1, 2 và 3
Để chọn 3 học sinh cho nhóm thứ nhất, số cách - $ ^ 9C_ {3} $
Số cách chọn 3 học sinh cho nhóm 2 sau khi chọn nhóm 1 - $ ^ 6C_ {3} $
Số cách để lựa chọn 3 sinh viên cho 3 thứ nhóm sau khi chọn 1 st và 2 nd nhóm - $ ^ 3C_ {3} $
Do đó, tổng số cách $ = ^ 9C_ {3} \ lần ^ 6C_ {3} \ lần ^ 3C_ {3} = 84 \ lần 20 \ lần 1 = 1680 $
Danh tính của Pascal
Bản sắc của Pascal, trước hết bắt nguồn bởi Blaise Pascal trong 17 thứ thế kỷ, tiểu bang rằng số cách để chọn các yếu tố k từ n phần tử bằng tổng của số cách để chọn các yếu tố (k-1) từ (n-1) các yếu tố và số cách chọn phần tử từ n-1 phần tử.
Về mặt toán học, với mọi số nguyên dương k và n: $ ^ nC_ {k} = ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $
Proof -
$$ ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $$
$ = \ frac {(n-1)! } {(k-1)! (nk)! } + \ frac {(n-1)! } {k! (nk-1)! } $
$ = (n-1)! (\ frac {k} {k! (nk)!} + \ frac {nk} {k! (nk)!}) $
$ = (n-1)! \ frac {n} {k! (nk)! } $
$ = \ frac {n! } {k! (nk)! } $
$ = n_ {C_ {k}} $
Nguyên tắc chuồng bồ câu
Năm 1834, nhà toán học người Đức, Peter Gustav Lejeune Dirichlet, đã phát biểu một nguyên tắc mà ông gọi là nguyên tắc ngăn kéo. Bây giờ, nó được gọi là nguyên tắc chuồng bồ câu.
Pigeonhole Principlequy định rằng nếu có ít lỗ chim bồ câu hơn tổng số chim bồ câu và mỗi con chim bồ câu được bỏ vào một lỗ chim bồ câu thì phải có ít nhất một lỗ nuôi chim bồ câu có nhiều hơn một con chim bồ câu. Nếu bỏ n con chim bồ câu vào m ổ chim bồ câu có n> m thì sẽ có một lỗ có nhiều hơn một con chim bồ câu.
Ví dụ
Mười người đàn ông ở trong một căn phòng và họ bắt tay nhau. Nếu mỗi người bắt tay ít nhất một lần và không người nào bắt tay người đó nhiều hơn một lần thì hai người bắt tay với số lượng như nhau.
Phải có ít nhất hai người trong một lớp gồm 30 người có tên bắt đầu bằng cùng một bảng chữ cái.
Nguyên tắc Bao gồm-Loại trừ
Các Inclusion-exclusion principletính toán số thứ tự của sự kết hợp của nhiều tập hợp không rời rạc. Đối với hai tập hợp A và B, nguyên tắc phát biểu:
$ | A \ cup B | = | A | + | B | - | A \ cap B | $
Đối với ba tập hợp A, B và C, nguyên tắc phát biểu:
$ | A \ cup B \ cup C | = | A | + | B | + | C | - | A \ cap B | - | A \ cap C | - | B \ cap C | + | A \ cap B \ cap C | $
Công thức tổng quát -
$ | \ bigcup_ {i = 1} ^ {n} A_i | = \ sum \ limit_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ limit_ {1 \ leq i < j <k \ leq n} | A_i \ cap A_j \ cap A_k | - \ dot + (- 1) ^ {\ pi-1} | A_1 \ cap \ dot \ cap A_2 | $
Problem 1
Có bao nhiêu số nguyên từ 1 đến 50 là bội của 2 hoặc 3 mà không phải là cả hai?
Solution
Từ 1 đến 100, có $ 50/2 = 25 $ là bội số của 2.
Có $ 50/3 = 16 $ số là bội của 3.
Có $ 50/6 = 8 $ số là bội của cả 2 và 3.
Vì vậy, $ | A | = 25 $, $ | B | = 16 $ và $ | A \ cap B | = 8 $.
$ | A \ cup B | = | A | + | B | - | A \ cap B | = 25 + 16 - 8 = 33 $
Problem 2
Trong một nhóm gồm 50 sinh viên, 24 sinh viên thích đồ uống lạnh và 36 người thích đồ uống nóng và mỗi sinh viên thích ít nhất một trong hai loại đồ uống. Có bao nhiêu người thích cả cà phê và trà?
Solution
Gọi X là tập hợp những sinh viên thích đồ uống lạnh và Y là tập hợp những người thích đồ uống nóng.
Vì vậy, $ | X \ cốc Y | = 50 $, $ | X | = 24 $, $ | Y | = 36 đô la
$ | X \ cap Y | = | X | + | Y | - | X \ cup Y | = 24 + 36 - 50 = 60 - 50 = 10 $
Do đó, có 10 sinh viên thích cả trà và cà phê.