Các quy tắc đếm cơ bản

  1. Tác giả: LTTK CTV27
    Đánh giá: ✪ ✪ ✪ ✪ ✪

    Trong chủ đề này, ta sẽ bàn về những bài toán tổ hợp thú vị và nâng cao có thể giải bằng các quy tắc đếm cơ bản như quy tắc cộng, quy tắc nhân, quy tắc bù trừ.
    $\boxed{\text{Ví dụ 1}}$Câu lạc bộ văn nghệ của trường A có 20 thành viên. Câu lạc bộ này muốn chọn một số thành viên tham dự hội diễn văn nghệ bao gồm hai thể loại múa và hát. Có bao nhiêu cách chọn thành viên tham gia hội diễn văn nghệ sao cho
    a)Thành viên nào của câu lạc bộ cũng đăng kí một trong hai thể loại biểu diễn?
    b)Thể loại biểu diễn nào cũng có thành viên tham gia?
    a) Mỗi thành viên sẽ có 3 lựa chọn: chỉ múa, chỉ hát, múa và hát. Do đó, có $3^{20}$ cách chọn.
    b) Ta có số cách chọn thành viên sao cho thể loại múa không được ai đăng kí là $2^{20}$. Số cách chọn thành viên sao cho thể loại hát không được ai đăng kí là $2^{20}$. Số cách chọn thành viên sao cho không có thể loại nào được đăng kí là $1.$ Theo nguyên lí bù trừ, số cách chọn thành viên sao cho có ít nhất 1 thể loại không có ai đăng kí là
    \begin{align*}
    2^{20}+2^{20}-1.
    \end{align*}
    Do đó, số cách chọn thành viên sao cho thể loại nào cũng có người đăng kí là
    \begin{align*}
    4^{20}-2.2^{20}+1=(2^{20}-1)^2.
    \end{align*}
    $\boxed{\text{Ví dụ 2}}$Có bao nhiêu số tự nhiên có 5 chữ số được lấy trong tập hợp $A=\left\{1,2,3,4,5,6\right\}$ thỏa mãn
    a) Chia hết cho 3.
    b) Tổng của 2 chữ số liền kề chia hết cho 3.
    a) Chọn 4 chữ số đầu ngẫu nhiên. Chữ số cuối cùng có 2 cách chọn. Do đó số cách chọn là $6^4.2$
    b) Chữ số đầu có 6 cách chọn. Các chữ số sau có 2 cách chọn. Do đó số cách chọn là $6.4^4.$
    $\boxed{\text{Ví dụ 3}}$ Có 10 học sinh có độ tuổi phân biệt từ $9$ đến $18$ tuổi và 10 túi kẹo có số lượng phân biêt từ $11$ đến $20$ viên. Hỏi có bao nhiêu cách chia các túi kẹo cho các học sinh sao cho
    a) Số kẹo cùng tính chẵn lẻ với số tuổi?
    b) Số kẹo lớn hơn hoặc bằng số tuổi?
    a) Ta có $5$ học sinh có số tuổi chẵn, $5$ học sinh có số tuổi lẻ, $5$ túi kẹo có số kẹo chẵn, $5$ túi kẹo có số kẹo lẻ. Chia cho $5$ học sinh có số tuổi lẻ các túi kẹo có số kẹo lẻ, ta có $5!$ trường hợp. Tương tự với trường hợp chẵn. Do đó, có tổng cộng $(5!)^2$ cách chia
    b) Chia cho học sinh $18$ tuổi, ta có $3$ cách chia. Tương tự đối với các học sinh $17,16,\ldots,11$ tuổi. Khi đó, học sinh $10$ tuổi có 2 cách chia túi kẹo và học sinh $9$ tuổi có 1 cách chia túi kẹo. Vậy tổng cộng có $3^8.2$ cách chia các túi kẹo.
    $\boxed{\text{Ví dụ 4}}$ Có bao nhiêu cách sắp xếp $20$ số $1,2,\ldots,20$ thành một hàng sao cho hiệu của một số với số liền trước nó luôn không vượt quá 1?
    Ta đếm bằng truy hồi. Gọi $a_n$ là số cách sắp xếp các số $1,2,\ldots,n$ thành một hàng ngang sao cho hiệu của một số với số liền trước nó luôn không vượt quá 1. Ta có nhận xét rằng trước số $n$ phải là $n-1$, theo đó trở về trước là $n-2,n-3,\ldots$. Chia trường hợp theo vị trí của $n$, ta có công thức truy hồi
    $$\begin{cases}
    a_1&=1,\\
    a_n&=\displaystyle{\sum_{i=1}^{n-1}a_i+1.}
    \end{cases}$$
    Bằng qui nạp, ta chứng minh được $a_n=2^{n-1}$. Vậy số cách xếp là $2^{19}.$
    Ta nhận thấy rằng, đối với dãy $n$ số từ $1$ đến $n$ thỏa mãn hiệu của một số với số liền trước nó luôn không vượt quá 1 thì, nếu ta muốn thêm số $n+1$ vào dãy mà vẫn thỏa mãn tính chất này thì ta chỉ có thể thêm $n+1$ vào đầu dãy hoặc ngay sau vị trí của $n$. Do đó, ta có $a_n=2a_{n-1}.$ Từ đó, ta tính được $a_{20}=2^{19}.$
    $\boxed{\text{Ví dụ 5}}$ Cho tập hợp $A=\left\{1,2,3,4,5,6,7,8,9,10\right\}.$ Có bao nhiêu lớp $6$ tập hợp $A_1,A_2,A_3,A_4,A_5,A_6$ thỏa mãn
    \begin{equation}\label{daytaphop}
    A_1\subset A_2\subset A_3\subset A_4\subset A_5\subset A_6\subset A?
    \end{equation}
    Ta thấy rằng nếu $1$ xuất hiện ở tập hợp $A_i$ thì sẽ xuất hiện ở các tập hợp $A_n,n\ge i$. Gọi $x_1$ là vị trí đầu tiên mà $1$ xuất hiện trong dãy tập hợp trên, ta có $7$ cách chọn cho $x_1$. Do đó, số lớp tập hợp thỏa mãn là $7^{10}.$
    $\boxed{\text{Ví dụ 6}}$ Có bao nhiêu cặp số $(a,b)$ thỏa mãn hai điều kiện
    i) $a,\ b$ là ước của $210^7$?
    ii)$a,\ b$ có cùng tập ước nguyên tố?
    Ta có $$210^7=2^7.3^7.5^7.7^7.$$
    $a,b$ là ước của $210^7$ nên $a=2^{x_1}3^{x_2}5^{x_3}7^{x_4},\ b=2^{y_1}3^{y_2}5^{y_3}7^{y_4}$ với $x_i\le 7,y_i\le 7,\ i=\ 1\ldots 4.$ Nếu $x_1=0$ thì $y_1=0$. Nếu $x_1\ne 0,$ ta có $7$ cách chọn cho $x_1$ và $7$ cách chọn cho $y_1$. Vậy, tổng số cách chọn cho $(x_1,y_1)$ là $1+7.7=50$. Vậy, số cặp $a,b$ thỏa đề là $50^4.$
    $\boxed{\text{Ví dụ 7}}$ Điền các số $1,-1$ vào bảng ô vuông $6\times 6$. Hỏi có bao nhiêu cách điền sao cho
    a) Mỗi hàng, mỗi cột đều có tích bằng 1.
    b) Tổng 4 số thuộc một bảng $2\times 2$ bất kì đều bằng $0.$
    a) Ta điền các số vào các ô ở bảng $5\times 5$ ở góc trái, phía trên ngẫu nhiên. Các ô ở cột cuối cùng được điền bởi tích của các số trong các ô cùng hàng với ô đó, các ô ở hàng cuối cùng được điền bởi tích của các số trong các ô cùng cột với ô đó. Vậy, tổng cộng có $2^{25}$ cách điền.
    b) Nếu cột 1 được điền bởi các số 1 và -1 xen kẽ thì các cột sau cũng được điền xen kẽ. Mà có hai cách điền xen kẽ cho mỗi cột nên có $2^6$ cách điền. Nếu cột 1 tồn tại hai số đứng cạnh nhau giống nhau thì các số còn lại trong bảng là cố định. Có $2^6-2$ cách điền cho cột đầu tiên không xen kẽ nên trong trường hợp này, ta có $2^6-2$ cách điền. Vậy tổng cộng có $2^7-2$ cách điền.
     
    Chỉnh sửa cuối: 25/5/19