Rate this post

Nguyên tắc đếm là một quy tắc cơ bản của đếm; nó thường được lấy ở phần đầu của quy tắc hoán vị và quy tắc tổ hợp. Nó nói rằng nếu một công việc X có thể được thực hiện theo m cách và công việc Y có thể được thực hiện theo n cách, thì với điều kiện X và Y loại trừ lẫn nhau, số cách thực hiện cả X và Y là m x n. Ví dụ: giả sử một người (T) có thể đi chợ từ nhà bằng xe buýt, đi bộ và bằng xe đạp, tức là T = 3 nếu anh ta trở về nhà (B) bằng đi bộ và bằng ô tô, tức là B = 2. Vậy có thể thực hiện TB bằng 3 * 2 = 6 cách.

Các bài viết liên quan:

Quy tắc Tổng và Sản phẩm

Quy tắc tổng hoặc nguyên tắc cộng và quy tắc tích hoặc nguyên tắc nhân được đưa ra dưới đây.

Quy tắc Tổng (Nguyên tắc Cộng)

Nếu một số tác vụ P1, P2, P3 ………, Pm có thể được thực hiện trong K1, K2, K3…. Km Số cách tương ứng mà không có nhiệm vụ nào có thể được thực hiện đồng thời, số cách để thực hiện một trong những nhiệm vụ này được cho bởi

K1 + K2 + ………… + Km.

Giả sử hai nhiệm vụ khác nhau, P và Q, tách rời nhau, điều đó có nghĩa là P ∩Q = Ø

Về mặt toán học,

| P∪Q | = | P | + | Q |

Quy tắc sản phẩm (quy tắc nhân)

Nếu một số công việc P1, P2, P3, …………, Pm có thể thực hiện được trong K1, K2, K3, ……… ..Km Số cách tương ứng và mọi công việc đến sau lần xuất hiện của công việc trước thì cách để thực hiện một trong những nhiệm vụ này được đưa ra bởi

K1 x K2 x ………… x Km.

Về mặt toán học,

Nếu một nhiệm vụ Q đến sau một nhiệm vụ P, thì

| P x Q | = | P | x | Q |

Ví dụ 1:

Một nhân viên sống tại địa điểm K và muốn đến văn phòng tại địa điểm G. Từ nhà của anh ta, K, anh ta phải đến địa điểm B, sau đó đến B đến G. Anh ta có thể đến K đến B bằng bốn hoặc ba tuyến tàu điện ngầm. các tuyến xe buýt. Từ đó, anh ta có thể chọn sáu tuyến tàu điện ngầm hoặc bốn tuyến xe buýt để đến địa điểm G. Tìm bất kỳ cách nào để đi từ K đến G.

Đáp án:

Anh ta có thể đi theo 4 + 3 = 7 cách (Quy tắc cộng). Sau đó, anh ta có thể đi từ B đến G theo 6 + 4 (10) cách (Quy tắc cộng). Do đó, từ K đến G, anh ta có thể đi theo 7 * 10 = 70 cách (Quy tắc nhân)

Hoán vị

Hoán vị đề cập đến sự sắp xếp của các phần tử theo một cách xác định. Ví dụ

Chúng ta phải tạo thành một hoán vị của các số có hai chữ số từ tập hợp các số S = (5, 7). Các số có hai chữ số khác nhau sẽ được tạo thành khi chúng ta sắp xếp các số đã cho. Các hoán vị sẽ là = (5,7) và (7,5).

Ví dụ 1:

Từ một tập hợp S = (P, Q, R) bằng cách lấy hai lần cùng một lúc, tất cả các hoán vị là

pq, qp, pr, rp, qr, rq

Ví dụ 2:

Chúng ta phải tạo thành một hoán vị của hai đồng tiền từ tập S = (H, T). Hai mặt khác nhau sẽ được hình thành khi chúng ta sắp xếp hai mặt. Các hoán vị sẽ là

(H, T) và (T, H)

Số lần hoán vị

Số lần hoán vị của n đối tượng khác nhau thực hiện r tại một thời điểm được cho bởi

P (n, r) = n (n-1) (n-2) ……… (n-r-1) (n≥r) = n! / (n-r)!

Với

N! = 1,2.…. (N-1) .n

Lưu ý: n luôn lớn hơn hoặc bằng r, tương đương với n giai thừa chia cho n trừ r.

Chứng minh công thức hoán vị

Giả sử có ba ô trống và bạn cần tô chúng bằng ba màu khác nhau. Có n số cách điền vào ô thứ nhất. Sau khi điền vào ô thứ nhất (n-1) thì số ô còn lại là bao nhiêu. Do đó, có (n-1) cách để tô màu ở vị trí thứ hai. Sau khi điền vào vị trí thứ nhất và thứ hai, còn lại (n-2) số hộp. Do đó, có (n-2) cách để điền vào vị trí thứ ba với các màu khác nhau. Bây giờ, chúng ta có thể khái quát tổng số cách điền vào ô thứ r là

[n – (r-1)] = n-r + 1

Vì vậy, tổng số cách tô màu vào ô từ vị trí đầu tiên đến vị trí thứ r là

npr = n (n-1) (n-2) …. (n-r + 1)

npr = [n (n-1) (n-2)… (n-r + 1)] [(n-r) (n-r-1)… 3.2.1] / [(n-r) (n-r-1)… 3.2.1]

Vì thế,

= n! / (n-r)!

Các điểm cần nhớ trong hoán vị

Nếu có ‘n’ phần tử khác nhau, trong đó x1 là loại alike nào đó, x2 giống loại khác, X3 giống loại thứ ba và Xr thuộc loại thứ r, trong đó

(x1 + x2 + x3 + …………. xr) = n

Khi đó, số hoán vị của n đối tượng này là

N! / [(x1! (x2!)… (xr!)]

Số hoán vị của n phần tử khác nhau lấy “n” phần tử tại một thời điểm

npn = n!

Số hoán vị của n phần tử khác nhau lấy r phần tử tại một thời điểm, khi m vật cụ thể luôn chiếm những vị trí xác định

n-mpr-m

Số hoán vị của n vật khác nhau khi r vật xác định luôn đi cùng nhau được cho bởi

r! (n-r + 1)!

Số hoán vị của n vật khác nhau khi r vật xác định không bao giờ kết hợp với nhau được cho bởi

N! – [r! (n-r + 1)!]

Số hoán vị đường tròn của n vật phân biệt lấy x phần tử tại thời điểm

npx / x

Số hoán vị vòng của n thứ khác nhau

npn / n

Hãy hiểu khái niệm này với sự trợ giúp của các ví dụ

Ví dụ 1:

Các chữ cái của từ “SCISSORS” có thể được sắp xếp theo bao nhiêu cách?

Giải pháp

Có tám chữ cái từ (4 S, 1 C, 1 I, 1 O 1 R) trong từ SCISSORS

Hoán vị sẽ là =

số 8! / [(4!) (1!) (1!) (1!)] = 1680

Ví dụ 2:

Các chữ cái của từ “TỐT” có thể được sắp xếp theo bao nhiêu cách?

Giải pháp

Có 4 chữ cái từ (1 G, 2 O, 1 D) trong từ TỐT

Hoán vị sẽ là =

4! / [(1!) (2!) (1!)] = 12

Ví dụ 3:

Từ một chùm 4 thẻ khác nhau, chúng ta có thể hoán vị nó bằng bao nhiêu cách?

Giải pháp: Vì chúng ta đang lấy 4 lá một lúc từ bộ bài 4 lá. Hoán vị sẽ là

4p4 = 4! = 24

Ví dụ 4:

Các chữ cái của từ ‘READER’ có thể được sắp xếp như thế nào để các phụ âm chỉ chiếm vị trí chẵn?

Giải pháp

Có 3 nguyên âm và 3 phụ âm trong từ ‘READER’. Một số cách sắp xếp các phụ âm trong số chúng 3p3 = 3! = 6. 3 nguyên âm sẽ điền vào 3 chỗ trống còn lại trong 3p3 = 3! = 6 cách. Do đó, tổng số hoán vị là 6 × 6 = 36

Kết hợp

Sự kết hợp đề cập đến việc chọn các phần tử từ một tập hợp sao cho thứ tự lựa chọn không quan trọng, không giống như hoán vị.

Nhìn chung, trong sự kết hợp, chúng tôi chỉ thích lựa chọn. Thứ tự của các phần tử đã chọn không quan trọng. Nói chung, số lượng các hoán vị vượt quá số lượng các tổ hợp. Mỗi tổ hợp tương ứng với nhiều hoán vị.

Sự kết hợp của n thứ khác nhau lấy r tại một thời điểm được cho bởi

nCr = n! / r! (n-r)!

ví dụ 1

Tìm số tập con của tập hợp {1,2,3,4,5,6,7} có 4 phần tử.

Giải pháp

Tổng số của tập hợp là 7, và chúng ta phải chọn 4 phần tử từ tập hợp.

Ở đây, thứ tự của số lượng không quan trọng. Do đó số lượng tập hợp con sẽ là

nCr = n! / r! (n-r)!

7C4 = 7! / 4! (7-4)!

= 7 * 6 * 5/3 * 2 = 35

Ví dụ 2

Có 8 chàng trai và 6 cô gái đã tham gia vào một cuộc thi. Có bao nhiêu cách chọn được 4 nam và 3 nữ từ cuộc thi?

Giải pháp

Số cách chọn 4 nam từ 8 nam là 8C4 và số cách chọn 3 nữ từ 6 nữ là 6C.

Do đó, tổng số cách là

8C4 6Cs = 8! / 4! (8-4)! 6! / 3! (6-3)!

= 8 × 7 × 6 × 5/4 × 3 × 2 × 6 × 5 × 4/3 × 2

= 70 × 20 = 1400

Ví dụ 3

Có bao nhiêu cách chọn 4 nhóm gồm 2 học sinh khác nhau trong tổng số 8 học sinh?

Giải pháp

Giả sử số nhóm là 1, 2, 3 và 4

Để chọn 2 học sinh cho nhóm 1 thì số cách chọn là = 8C2

Số cách chọn 2 học sinh cho tổ 2 sau khi chọn tổ 1 = 6C2

Số cách chọn 2 học sinh cho tổ 3 sau khi chọn tổ 1 và tổ 2 = 4C2

Số cách chọn 2 học sinh cho tổ 4 sau khi chọn tổ 1, tổ 2, tổ 3 = 2C2

Do đó, tổng số cách

8C2 × 6C2 × 4C2 × 2C2 = 28 × 15 × 6 × 1 = 2520

Nguyên tắc Bao gồm-Loại trừ

Nguyên tắc Bao gồm-Loại trừ đề cập đến một định lý rất cơ bản về phép đếm, và các bài toán khác nhau trong các cuộc thi lập trình khác nhau dựa trên đó; một ví dụ cơ bản về nguyên tắc bao gồm-loại trừ được đưa ra dưới đây.

Coi A là tập hợp các phần tử và | A | là số phần tử trong A và giống như đối với B. Tính tổng số của tập hợp các phần tử của cả hai tập A và B (khi cả A và B là rời rạc) có thể được phát biểu là (đối với 2 tập hợp hữu hạn):

| AUB | = | A | + | B |

Hãy xem xét trường hợp đó nếu các bộ rời rạc.

Chúng ta phải trừ các phần tử chung được đếm hai lần trong khi tính tổng số của cả A và B, và một dạng mới sẽ trở thành:

| AUB | = | A | + | B | – | A∩B |

Công thức tổng quát:

Nguyên tắc đếm

Ví dụ dựa trên Nguyên tắc Bao gồm-Loại trừ

ví dụ 1

Có bao nhiêu số nguyên từ 1 đến 100 là bội của 5,6 mà không phải là cả hai?

Giải pháp

Từ 1 đến 100, có 100/5 = 20 số là bội của 5

Và, có 100/6 = 16 số là bội của 6.

Và, có 100/30 = 3 số là bội của cả 5 và 6

Vì vậy,

| A | = 20, | B | = 16 và | A∩B | = 3

Chúng ta biết rằng,

| AUB | = | A | + | B | – | A∩B |

= 20 + 16 -3 = 33

Ví dụ 2

Trong một nhóm gồm 60 nhân viên, 32 người thích pizza và 38 người thích bánh mì kẹp thịt, và mỗi nhân viên thích ít nhất một trong hai món ăn nhẹ. Tìm bao nhiêu nhân viên thích cả bánh pizza và bánh mì kẹp thịt?

Giải pháp

Gọi P là tập hợp những nhân viên thích ăn pizza và Q là những nhân viên thích một chiếc bánh mì kẹp thịt.

Vì vậy,

| P | = 32, | Q | = 38 và | PUQ | = 60

Chúng ta biết rằng,

| AUB | = | A | + | B | – | A∩B |

Cho nên,

| P∩Q | = | P | + | Q | – | PUQ |

= 32 + 38 – 60 = 70 – 60 = 10

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Contact Me on Zalo
Call now