Các nguyên lý đếm cơ bản là những quy tắc và phương pháp căn bản được áp dụng trong lý thuyết đếm môn toán rời rạc. Sau đây, hãy cùng TTnguyen tìm hiểu các nguyên lý đếm cơ bản: cộng, nhân, bù trừ, chia kèm theo một số dạng bài tập có lời giải nhé!
Xem thêm:
- logic mệnh đề – Bài tập toán rời rạc chương 1 có lời giải
- bài tập toán rời rạc chương 2 có lời giải
I. Các nguyên lý đếm cơ bản
1. Nguyên lý cộng (quy tắc cộng)
Giả sử một công việc được thực hiện theo một trong hai phương án (hướng, trường hợp, khả năng) A hoặc B.
- Phương án A có thể thực hiện theo n cách.
- Phương án B có thể thực hiện theo m cách.
Khi đó, để hoàn thành công việc có thể thực hiện theo n+m cách.
2. Nguyên lý nhân (quy tắc nhân)
Giả sử một công việc bao gồm hai công đoạn (giai đoạn, bước) 1 và 2.
- Công đoạn 1: có thể thực hiện theo n cách.
- Công đoạn 2: có thể thực hiện theo m cách.
Khi đó, để hoàn thành được công việc có thể thực hiện theo n.m cách.
3. Nguyên lý bù trừ
Nếu một công việc có thể được thực hiện bằng một trong hai phương án, phương án một (A1) có \(n_{1}\) cách thực hiện và phương án hai (A2) có \(n_{2}\) cách thực hiện, thì số cách thực hiện công việc là \(n_{1} + n_{2}\), trừ đi số cách thực hiện hiện chung cho hai phương án.
Biểu diễn dưới dạng tập
Giả sử rằng A1 và A2 là các tập.
có |A1| cách chọn một phần tử từ tập A1
có |A2| cách chọn một phần tử từ tập A2.
=> Số cách chọn một phần tử từ tập A1 hoặc A2, là
|A₁ U A₂| = |A₁| + |A₂| – |A₁ ∩ A₂l.
>>Xem thêm:
4. Nguyên lý chia
Biết một công việc A có n cách để thực hiện, đồng thời nó cũng được thực hiện theo k phương án khác nhau (k là giá trị chưa biết), và mỗi phương án có đúng d cách thực hiện. Thì số phương án khác nhau để thực hiện A là k = n/d.
Phát biểu nguyên lý chia theo nghĩa tập:
Nếu một tập hữu hạn A là hợp của k tập con rời nhau từng đôi một, mỗi tập có d phần tử thì số tập con k = |A|/d.
Phát biểu nguyên lý chia theo nghĩa hàm:
Nếu f là một hàm từ A đến B trong đó A và B là các các tập tập hữu hạn, và rằng với mỗi giá trị y ∈ B có đúng d giá trị x ∈ A sao cho f (x) = y, thì |B| = |A|/d.
Bài tập nguyên lý cộng có lời giải
Bài 1: Giả sử cần chọn hoặc một cán bộ hoặc một sinh viên tham gia một hội đồng của
một trường đại học. Hỏi có bao nhiêu cách chọn vị đại biểu này nếu như có 37 cán bộ và 63
sinh viên.
Giải:
Gọi việc thứ nhất là chọn một cán bộ từ tập cán bộ ta có 37 cách.
Gọi việc thứ hai là chọn một sinh viên từ tập sinh viên ta có 63 cách.
Vì tập cán bộ và tập sinh viên là rời nhau, theo nguyên lý cộng ta có tổng số cách chọn vị đại biểu này là 37 + 63 = 100 cách chọn.
Mở rộng nguyên lý cộng
Giả sử rằng một công việc có thể được thực hiện theo m phương án khác nhau:
- theo phương án một có \(n_{1}\) cách.
- theo phương án hai có \(n_{2}\) cách.
- theo phương án thứ m có \(n_{m}\) cách.
Trong đó không có cách thực hiện nào theo phương án thứ i giống với bất kỳ cách
thực hiện nào trong phương án thứ j, với mọi cặp áp giá trị i và j).
Thì số cách thực hiện công việc là \(n_{1} + n_{2} + … + n_{m}\).
Bài 2: Một sinh viên có thể chọn một project từ một trong ba danh sách. Ba danh sách chứ 23, 15 và 19 project khác nhau, tương ứng. Mỗi project chỉ xuất hiện trong một danh sách. Một sinh viên có bao nhiêu cách lựa chọn một project?
Lời giải
Sinh viên có thể chọn một project bằng cách chọn một project từ danh sách thứ nhất, thứ hai hoặc thứ 3.
Bởi không có project nào bị lặp lại trong ba danh sách, theo nguyên lý công có 23 + 15 + 19 = 57 cách chọn một project.
Bài 3: Giá trị của biến k sẽ bằng bao nhiêu sau khi thực hiện đoạn chương trình sau:
k := 0
for i1 to n1
k = k + 1
for i2 to
k = k + 1
...
...
for im to nm:
k = k + 1
Giải
Coi mỗi vòng for là một công việc, do đó ta có m công việc \(T_{1}, T_{2}, … , T_{m}\). Trong đó \(T_{i}\) thực hiện bởi \(n_{i}\) cách (i= 1, 2,.., m).
Vì các vòng for không lồng nhau hay các công việc không thực hiện đồng thời nên theo nguyên lý cộng tổng tất cả các cách để hoàn thành \(T_{1}, T_{2}, … , T_{m}\) là \( = n_{1} + n_{2}+ … + n_{m}\).
Bài 4: Trong một phiên bản của ngôn ngữ lập trình, tên của một biến là một chuỗi gồm một hoặc hai kí tự là chữ cái hoặc chữ số, không phân biệt chữ cái hoa và thường. Tuy nhiên, một tên biến phải bắt đầu bằng một chữ cái và phải khác với năm chuỗi hai kí tự được dự trữ cho việc việc lập trình. Có bao ba nhiêu tên biến khác nhau trong ngôn ngữ lập trình trên?
Lời giải
Gọi A là số lượng tên biến khác nhau , trong nhiên bản bản của ngôn ngữ lập trình.
A1 là số lượng tên biến có độ dài một kí tự.
A2 là số lượng các tên biến có độ dài hai kí tự.
Theo nguyên lý cộng: A = A1 + A2.
A1 = 26, tên biến phải là chữ cái.
Theo nguyên lý nhân: A2 = 26.36 – 5 = 931. (Có 26 cách chọn cho chữ cái đầu tiên và 36 cách chọn cho chữ cái thứ hai và loại bỏ năm chuỗi hai kí tự)
=> A= A1 + A2 = 26 + 931 = 957.
Bài 5: Mỗi người sử dụng trên một hệ thống máy tính có một mật khẩu, nó có độ dài sáu đến tám kí tự, trong đó mỗi kí tự là một chữ cái hoa (tiếng anh) hoặc một chữ số. Mỗi mật khẩu phải chứa ít nhất một chữ số. Có bao nhiêu mật khẩu có thể có?
Lời giải
Gọi P là tổng số mật khẩu có thể \(P_{6}, P_{7}, P_{8}\) là số lượng mật khẩu khả thi có độ dài 6, 7, 8 một cách tương ứng.
Theo nguyên lý cộng: \(P = P_{6} + P_{7} + P_{8}\).
Số lượng chuỗi có độ dài sáu kí tự là \(36^6\).
Số lượng chuỗi không có chữ số là \(26^6\).
Vì vậy \(P_{6} = 36^6 – 26^6\).
Tương tự, \(P_{7} = 36^7 – 26^7\) và \(P_{8} = 36^8 – 26^8\).
=> \(P = P_{6} + P_{7} + P_{8}\)
Bài tập nguyên lý nhân có lời giải
Bài 1: Một công ty mới chỉ có hai nhân viên, An và Ba, thuê một tầng của một tòa nhà có 12 phòng. Hỏi có bao nhiêu cách để phân phòng cho hai nhân viên này, biết mỗi nhân viên một phòng?
Lời giải:
Công việc phân phòng cho hai nhân viên:
1. Giao phòng cho Ân: có 12 cách thực hiện.
2. Giao phòng cho Ba: có 11 cách giao phòng.
Theo nguyên lý nhân, có 12.11 = 132 cách giao phòng cho 2 nhân viên này.
Bài 2: Các ghế trong một rạp hát được dán nhãn với một chữ cái hoa tiếng Anh sau đó là một số nguyên dương không vượt quá 100. Hỏi số lượng ghế lớn nhất có thể được dán nhãn khác nhau là bao nhiêu?
Lời giải
Công việc dán nhãn một ghế gồm 2 công việc thành phần:
- Gán cho ghế một trong 26 chữ cái hoa tiếng Anh.
- Gán cho ghế một trong 100 số nguyên.
=> có 26.100 cách mà một ghế được dán nhãn. Vậy số lượng ghế lớn nhất có thể được dán nhãn khác nhau là 2600.
Mở rộng nguyên lý nhân
Giả sử một công việc A được thực hiện bằng các công việc thành phần \(A_{1}, A_{2},…,A_{m}\) theo thứ tự.
Nếu công việc thành phần \(A_{i}\), i =1,2,…,m, được thực hiện theo \(n_{i}\) cách thì số cách thực hiện công việc A là \(n_{1}.n_{2}. … .n_{m}\) cách.
Bài 4: Có bao nhiêu xâu nhị phân có độ dài 7.
Lời giải
Một xâu nhị phân có độ dài 7 gồm 7 bít, mỗi bít có hai cách chọn (hoặc giá trị 0 hoặc
giá trị 1), theo qui tắc nhân ta có 2.2.2.2.2.2.2 = 128 xâu bít nhị phân độ dài 7.
Bài 5: Có bao nhiêu biển số xe khác khác nhau có có thể được tạo ra nếu mỗi biển số gồm có một chuỗi ba chữ cái hoa tiếng Anh tiếp theo là ba chữ số (không có dãy chữ cái nào bị cấm ngay cả nó vô nghĩa)?
Lời giải
Mỗi chữ cái có 26 lựa chọn
Mỗi chữ số có 10 lựa chọn
→ Theo nguyên lý nhân có tất cả \(26^{3}.10^{3}= 17.576.000 \) biển số khả thi.
Bài 6: Có bao nhiêu hàm từ một tập có m phần tử đến một tập có n phần tử?
Lời giải
Hàm f: A→B, f(a) = b, |A| = m, |B| = n.
Với mỗi a ∈ A có n cách lựa chọn b ∈ B.
Có \(n^{m}\) hàm từ một tập A có m phần tử đến một tập B có n phần tử.
Bài 7: Có bao nhiêu hàm đơn ánh xác định từ một tập A có m phần tử nhận giá trị trên tập B có n phần tử?
Lời giải
Hàm f: A→B, f(a) = b, |A| = m, |B| = n.
TH1: m>n sẽ không có hàm đơn ánh f: A→B
Th2: m<n, m=n
Giả sử \( A = a_{1}, a_{2}, … , a_{m} \)
\(a_{1}\) có n cách chọn \(b_{1}\)
\(a_{2}\) có n -1 cách chọn \(b_{2}\)
\(a_{k}\) có n-k+1 cách chọn \(b_{k}\)
Theo nguyên lý nhân có n(n-1)(n-2)…(n-m+1) đơn ánh f: A→B
Bài tập nguyên lý bù trừ toán rời rạc
Bài 1: Có bao nhiêu chuỗi bit có độ dài 8 hoặc bắt đầu bằng chữ số 1 hoặc kết thúc bằng 00?
Lời giải
Cách xây dựng một chuỗi bit có độ dài 8 hoặc bắt đầu bằng 1 hoặc kết thúc bằng 00:
1. Chuỗi bit có dạng: \(1b_{2}b_{3}b_{4}b_{5}b_{6}b_{7}b_{8}\), có 2^7 = 128 cách.
2. Chuỗi bit có dạng: \(b_{1}b_{2}b_{3}b_{4}b_{5}b_{6}00\), có 2^6 = 64 cách
3. Chuỗi bit có dạng: \(1b_{2}b_{3}b_{4}b_{5}b_{6}00\), có 2^5 = 32 cách.
=> Theo nguyên lý trừ: có 128 + 64 – 32 = 160 chuỗi bit bắt đầu là 1 hoặc kết thúc là 00.
Bài 2: Một công ty máy tính nhận 350 đơn xin việc từ các ứng viên cho một công việc lên kế hoạch cho một web server mới. Giả sử rằng có 220 ứng viên ngành khoa học máy tính, 17 ngành kinh doanh và 51 ứng viên có cả ngành khoa học máy tính và kinh doanh. Có bao nhiêu ứng viên không có ngành khoa học máy tính hoặc không có ngành kinh doanh?
Lời giải
Gọi A1 là tập ứng viên ngành khoa học máy tính
A2 là tập ứng viên ngành kinh doanh.
→ A1 U A2 là tập ứng viên ngành khoa học máy tính hoặc kinh doanh (hoặc cả hai),
A1 ∩ A2 là tập ứng viên học cả hai ngành khoa học máy tính và kinh doanh.
Theo nguyên lý trừ:
|A₁ U A₂| = |A₁| + |A₂|-|A₁∩ A₂l = 220 + 147 – 51 = 316.
Kết luận: có 350 – 316 = 34 ứng viên không thuộc nhành khoa học máy tính hoặc kinh doanh.
>>> Xem thêm các bài tập và minh học hình học về nguyên lý bù trừ tại bài viết: bài tập biểu đồ venn
Bài tập nguyên lý chia có lời giải
Bài 1: Có bao nhiêu phương án khác nhau để sắp xếp chỗ cho bốn người xung quanh bàn tròn, trong đó hai phương án sắp xếp được gọi là như nhau nếu mỗi người có cùng người bên trái và bên phải giống nhau?
Lời giải
Ghế số 1: có 4 cách chọn, Ghế số 2: có 3 cách chọn,
Ghế số 3: có 2 cách chọn, Ghế số 4: có 1 cách chọn.
→ có 4! = 24 cách sắp thứ tự bốn người vào bốn ghế.
Mặt khác, mỗi 1 phương án sắp xếp chỗ ngồi có 4 cách chọn vị trí ghế ngồi.
Theo nguyên lý chia:
có 24/4 = 6 phương án sắp xếp chỗ ngồi khác nhau cho 4 người quanh bàn tròn.
>> Xem thêm: hệ thức truy hồi trong toán rời rạc
Trên đây là lý thuyết và bài tập vận dụng các nguyên lý đếm cơ bản toán rời rạc. Cảm ơn các bạn đã tham khảo trên ttnguyen.net
