Bài Tập Phép đếm - Toán Rời Rạc Có Lời Giải Chi Tiết - TTnguyen

Tổng hợp bài tập chương 2: phép đếm bao gồm những nguyên lý cơ bản: nguyên lý cộng, nguyên lý nhân, nguyên lý loại trừ, nguyên lý bù trừ, nguyên lý quy về đơn giản, hệ thức truy hồi để giải bài toán đếm toán rời rạc.

Xem thêm:

• logic mệnh đề – Bài tập toán rời rạc chương 1 có lời giải

Nội dung

Toggle

• I. Tóm tắt lý thuyết bài toán đếm toán rời rạc chương 2
• II. Một số lưu ý và phương pháp đếm khi làm bài toán đếm toán rời rạc
• III. Bài tập bài toán đếm toán rời rạc có lời giải
• IV. Tổng hợp bài tập chương 2 toán rời rạc

I. Tóm tắt lý thuyết bài toán đếm toán rời rạc chương 2

1. Các nguyên lý đếm cơ bản

• Nguyên lý cộng: Số cách thực hiện A hoặc B là n + m.
• Nguyên lý nhân: Số cách thực hiện A và sau đó B là n * m.
• Nguyên lý bù trừ: Số cách thực hiện A hoặc B là n1 + n2 – (số cách chung).
• Nguyên lý chia: Số phương án thực hiện A qua k phương án khác nhau là k = n/d.

>>> Chi tiết lý thuyết và bài tập các nguyên lý đếm cơ bản: cộng, nhân, bù trừ, chia.

2. Công thức hoán vị – tổ hợp – chỉnh hợp

• Hoán vị: Công thức: \(P_{n} = n(n – 1) = n!\)
• Chỉnh hợp: Công thức: \(A_{k}^{n} = n(n-1)…(n-k+1)=\frac{n!}{(n-k)!}\)
• Tổ hợp: \(C_{n}^{k} = \frac{n!}{k!(n-k)!}\)

>>> Chi tiết lý thuyết và bài tập hoán vị chỉnh hợp tổ hợp có lời giải

3.  Công thức tổ hợp lặp – chỉnh hợp lặp

• Chỉnh hợp lặp: \( A_n^{k} = n^k \).
• Tổ hợp lặp: \( C_n^{k} = C_{n+k-1}^{k} \)

>>> Chi tiết bài tập chỉnh hợp lặp và tổ hợp lặp có lời giải

4. Hệ thức truy hồi

Một hệ thức truy hồi thuần nhất tuyến tính bậc k với hệ số hằng là hệ thức truy hồi có dạng:

\(a_{n} = a_{1}a_{n-1} + c_{2}a_{n-2} + … + c_{k}a_{n-k}\) với \(c_{1},c_{2},…,c_{k} \)là hằng số thực khác 0.

>>> hệ thức truy hồi trong toán rời rạc

II. Một số lưu ý và phương pháp đếm khi làm bài toán đếm toán rời rạc

8.Hoán vị vòng quanh: \(Q_n=(n-1)!\)

III. Bài tập bài toán đếm toán rời rạc có lời giải

1. Bài tập nguyên lý cộng

Bài 1: Giả sử cần chọn ra 1 đại diện học sinh tham gia dự thi Olympic Tin học. Biết thể lựa chọn học sinh khối 11 và khối 12. Hỏi có bao nhiêu lựa chọn khác nhau, nếu có 300 học sinh khối 11 và 260 em học sinh khối 12.

Giải

Có 300 cách chọn 1 học sinh khối 11 Có 260 cách chọn 1 học sinh khối 12 Theo nguyên lý cộng: 300 + 260 = 560 cách

Bài 2: Một sinh viên có thể lựa chọn đề tài từ 1 trong 3 danh sách. Mỗi danh sách lần lượt chứa 10, 20 và 30 đề tài khác nhau tương ứng. Mỗi đề tài chỉ xuất hiện trong 1 danh sách. Một sinh viên có bao nhiêu cách lựa chọn đề tài?

Giải

Sinh viên có thể chọn đề tài từ 1 trong 3 danh sách và không bị lặp lại. Nên theo nguyên lý cộng có 10 + 20 + 30 = 60 cách

Bài 3: Giá trị k là bao nhiêu sau khi thực hiện đoạn mã sau:

k: = 0; for i: = 1 to 5 do k: = k + 1;

Giải

Giá trị khởi tạo k=0 Lệnh thực hiện vòng lặp 5 lần, mỗi lần k tăng thêm 1 => theo nguyên lý cộng k=5

Bài 4: Một mật khẩu có độ dài từ 7 đến 8 kí tự. Trong đó có 1 chữ cái hoa tiếng anh hoặc 1 chữ số. Mỗi mật khẩu phải chứa ít nhất 1 chữ số. Có bao nhiêu mật khẩu có thể có?

Giải

Số lượng mật khẩu chứa kí tự là \(36^7\) Số lượng mật khẩu chỉ chứa chữ cái hoa là \(26^7\) Số lượng mật khẩu chứa kí tự là \(36^8\) Số lượng mật khẩu chỉ chứa chữ cái hoa là \(26^8\) Vậy số lượng mật khẩu chứa ít nhất 1 chữ số là: \(36^7+36^8-26^7-26^8\)

>>>Xem thêm: Bài tập đồ thị Euler

2. Bài tập nguyên lý nhân

Bài 1: Để tạo số báo danh cho học sinh bao gồm 1 chữ cái hoa tiếng anh và 1 chữ số không vượt quá 100. Hỏi số lượng lớn nhất số báo danh có thể có là bao nhiêu?

Giải

Số lượng số báo danh lớn nhất là : 26*100 =  2600

Bài 2: Có bao nhiêu chuỗi bit có độ dài là 7?

Giải

Mỗi bít có 2 cách lựa chọn do đó: \(2^7\)

Bài 3: Có bao nhiêu ham từ tập m phần tử đến tập n phần tử? \(n^m\)

3. Bài tập nguyên lý bù trừ

Bài 1: Có bao nhiêu chuỗi bit có độ dài 8 hoặc bắt đầu bằng 1 hoặc bắt đầu bằng 00

Giải

Chuỗi bit bắt đầu bằng 1 là: \(2^7\) Chuỗi bit bắt đầu bằng 00 là:\(2^6\) Chuỗi bit trùng nhau bắt đầu bằng 1 và 00 là: \(2^5\)

Theo nguyên lý trừ ta có: \(2^7+2^6-2^5\)

5. Bài tập hoán vị chỉnh hợp tổ hợp

Bài 1: Người ta sắp xếp ngẫu nhiên 5 lá phiếu có ghi số thứ tự từ 1 đến 5

a.Có bao nhiêu cách sắp xếp số chẵn ở cạnh nhau? Coi hai số chẵn là 1 => có 2!.4! =48 cách b.Có bao nhiêu cách sắp xếp hai thành 2 nhóm chẵn lẻ riêng biệt (2!.3!.2=24)

Bài 2: Một lớp học có 10 môn, mỗi ngày học 2 môn. Hỏi có bao nhiêu cách sắp xếp thời khoá biểu trong 1 ngày?

Giải

Cách sắp xếp thời khoá biểu là \( A_2^{10} = 90\)

Bài 3: Một tổ gồm 8 nam và 6 nữ. Có bao nhiêu cách chọn 1 nhóm 5 người mà trong đó có đúng 2 nữ?

Giải

Cách chọn 2 nữ trong 6 nữ là: \( C_6^{2} = 15\) Cách chọn 4 nam trong 8 nam là:  \( C_8^{4} = 56\) Số cách chọn theo yêu cầu là: 15.56=840 cách

6. Bài tập chỉnh hợp lặp và tổ hợp lặp

Bài 1: Tìm chuỗi nhị phân có độ dài 6 là (26)

Bài 2: Có 4 loại bút bi: xanh, đỏ, vàng, cam và mỗi loại có ít nhất 6 cây bút.Có bao nhiêu cách khác nhau để mua 6 cây?

Giải

Tổ hợp lặp chập 6 của 4 phần tử: \( C_{4+6-1}^{6} =84 \)

IV. Tổng hợp bài tập chương 2 toán rời rạc

Bài toán tú lơ khơ

Bài 1: Có bao nhiêu cách chia bộ bài tú lơ khơ 52 quân, thành 4 phần tương ứng với số quân là 10, 12, 14, 16

Giải

Vì số quân của các phần khác nhau nên:

\( C_{52}(10,12,14,16) = \frac{52!}{10!.12!.14!.16!} \)

Bài 2: Có bao nhiêu cách chia bộ bài tú lơ khơ 52 quân thành 4 phần bằng nhau?

Giải

Vì số quân của các phần bằng nhau nên:

\( C_{52}(13,13,13,13) = \frac{52!}{13!.13!.13!.13!.4!} \)

Bài toán chia kẹo toán rời rạc

Bài 1: Có bao nhiêu cách chia 10 chiếc kẹo cho 5 em bé trong các trường hợp sau:

a/ Chia 1 cách tuỳ ý

\( R_{5}^{10}=C_{5+10-1}^{10} =1001 \)

b/ Em nào cũng được chia kẹo

Chia cho mỗi em 1 kẹo để đảm bảo ai cũng được kẹo rồi tiếp tục chia 1 cách tuỳ ý :

\( R_{5}^{5}=C_{5+5-1}^{5} = 126 \)

c/ Có 1 em có số kẹo ít hơn 4

\( C_{10}^{0} + C_{10}^{1} + C_{10}^{2} + C_{10}^{3}\)

Bài 2: Một phiếu trắc nghiệm có 10 câu hỏi, mỗi câu hỏi có 4 phương án trả lời.

a) Có bao nhiêu cách điền vào phiếu, nếu câu hỏi nào cũng đều được trả lời? \(4^{10}\) b) Có bao nhiêu cách điền vào phiếu, nếu có thể có câu hỏi bỏ trống không trả lời? \(5^{10}\)

Bài toán xếp bộ quần áo kích thước khác nhau

Bài 1. Có 5 bộ quần áo có kích thước khác nhau. Chủ cửa hàng xếp ngẫu nhiên quần này với áo khác. Hỏi có bao nhiêu cách xếp để cho:

a) Chỉ có 3 bộ quần áo là đúng kích thước với nhau? b) Tất cả 5 bộ quần áo đều sai kích thước? c) Ít nhất có 2 bộ có cùng kích thước.

Giải

a)

– Chọn ra 3 bộ có cùng kích thước với nhau: \( C_{5}^{3} = 10 \) – 3 bộ có đúng 1 cách xếp – Còn lại 2 bộ quần áo có kích thước khác nhau:

\(D_n= (n-1).(D_n-1+D_n-2) với D_1=0, D_2=1\)

=> Số cách sắp xếp 2 bộ quần áo có kích thước khác nhau là \(D_2=1\)

=>Chỉ có 3 bộ quần áo là đúng kích thước với nhau: 10.1

b)

Số cách sắp xếp 5 bộ quần áo có kích thước khác nhau là \(D_5\)

\(D_1\) = 0

\(D_2\) = 1 \(D_3\) = 2.( 1 + 0 ) = 2 \(D_4\) = 3 ( 2 + 1) =9 \(D_5\) = 4( 9+ 2) = 44

c)

Chỉ có 2 bộ quần áo là đúng kích thước với nhau: \( C_5^2.D_3 \)

Chỉ có 3 bộ quần áo là đúng kích thước với nhau: \( C_5^3.D_2 \)

Chỉ có 4 bộ quần áo là đúng kích thước với nhau: \( C_5^4.D_1 \)

Ít nhất có 2 bộ có cùng kích thước:

\( C_5^2.D_3+C_5^3.D_2+C_5^4.D_1 \)

Như vậy, vừa rồi TTnguyen đã gửi tới bạn một số bài tập toán rời rạc có lời giải về bài toán đếm giúp các bạn ôn tập hơn. Cảm ơn các bạn đã tham khảo trên ttnguyen.net. Chúc các bạn học tập tốt!