Category Archives: Các bài toán đếm

Chỉnh hợp – Hoán vị – Tổ hợp

Chỉnh hợp

Mỗi cách sắp xếp $k$ phần tử (phân biệt) vào $n$ vị trí phân biệt ($n\geq k$) được gọi là một chỉnh hợp chập $k$ của $n$.

Tính chất. Số chỉnh hợp chập $k$ của $n$ là $$A_n^k = \dfrac{(n!)}{(n-k)!}$$

Hoán vị. 

Mỗi chỉnh hợp chập $n$ của $n$ được gọi là một hoán vị, hay mỗi cách sắp xếp $n$ phần tử vào $n$ vị trí được gọi là một hoán vị của $n$ phần tử. Số hoán vị của $n$ phần tử là $P_n = n!$.


Định nghĩa khác. Cho tập $A = {1, 2, \cdots, n}$. Mỗi song ánh từ $A$ vào $A$ được gọi là một hoán vị.

Ví dụ 1. Có 8 bạn nam và 2 bạn nữ được xếp thành một hàng dài. Hỏi có bao nhiêu cách xếp thỏa:

a) Xếp bất kì.
b) 8 bạn nam kề nhau,2 bạn nữ kề nhau.
c) Các bạn nam giữa hai bạn nữ.

Ví dụ 2. Có 8 bạn nam và 4 bạn nữ. Có bao nhiêu cách sắp xếp các bạn này thành một hàng sao cho không có hai bạn nữ nào đứng kề nhau.

Ví dụ 3.  Cho tập $A = {0, 1, 2, 3, 4, 5}$. Từ $A$ có thể lập được bao nhiêu số

a) Là số chẵn có 4 chữ số khác nhau.
b) Là số lẻ có 5 chữ số khác nhau và chia hết cho 3.

 

Tổ hợp. Cho tập hợp $A$ có $n$ phần tử. Một tập hợp con có $k$ phần tử của $A$ được gọi là một tổ hợp chập $k$ của $n$ phần tử.

Tính chất. Số tổ hợp có chập $k$ của $n$ là: [C_n^k = \dfrac{A_n^k}{k!} = \dfrac{n!}{(n-k)! k!}]

Ví dụ 4. Đội văn nghệ của trường gồm 4 bạn học sinh lớp 10, 5 học sinh lớp 11, 4 học sinh lớp 12.

a) Có bao nhiêu cách chọn ra hai bạn hát song ca?
b) Có bao nhiêu cách chọn ra 3 bạn hát tam ca mà mỗi khối có một học sinh?
c) Có bao nhiêu cách chọn ra một đội múa gồm 5 bạn trong đó có ít nhất 2 học sinh lớp 11.

Ví dụ 5. Cho tập $A = {1, 2, 3, 4, 5}, B = {a, b, c, d, e, }$, $C = {x, y, z}$.

a) Có bao nhiêu song ánh từ $A$ vào $B$.
b) Có bao nhiêu ánh xạ từ $A$ vào $C$? Có bao nhiêu đơn ánh từ $C$ vào $A$.
c) Có bao nhiêu đơn ánh từ $C$ và $A$ sao cho $f(x) + f(y) + f(z)$ là số chẵn.

Bài tập rèn luyện

Bài 1. Cho tập $A = {0, 1, 2, 3, 4,5,6, a, b, c, d}$

a) Có bao nhiêu hoán vị của $A$.
b) Có bao nhiêu hoán vị của $A$ mà các chữ số đứng kề nhau.
c) Có bao nhiêu hoán vị của $A$ mà không có chữ cái nào đứng kề nhau?

Bài 2. Cho tập $A = {0, 1, 2, 3, 4, 5, 6 }$

a)Từ A có thể lập được bao nhiêu số có 5 chữ số khác nhau.
b) Có bao nhiêu hoán vị của A mà hai chữ số lẻ không đứng kề nhau.
c) Từ A có thể lập được bao nhiêu số có 4 chữ số mà chữ số đứng sau lớn hơn chữ số đứng liền trước.
d) Từ A có thể lập được bao nhiêu số có 3 chữ số chia hết cho 3.

Bài 3. Xếp $ m $ bạn nam và $ n $ bạn nữ thành 1 hàng, với $m,n\in \mathbb{N}$. Hỏi có bao nhiêu cách xếp nếu:

a) Xếp tùy ý;
b) Không có bạn nam nào đứng cạnh nhau $\left( m\le n+1 \right);$
c) $ n $ bạn nữ đứng liền kề nhau;
d) Một bạn nam A và một bạn nữ B đứng cạnh nhau.

Bài 4. Tính: $1\cdot 1!+2\cdot 2!+3\cdot 3!+\cdot \cdot \cdot +n\cdot n!,n\in \mathbb{N}.$

Bài 5. Tính: $\dfrac{1}{\left( 1+1 \right)!}+\dfrac{2}{\left( 2+1 \right)!}+\cdot \cdot \cdot +\dfrac{n}{\left( n+1 \right)!}$ với $n\in \mathbb{N}.$

Bài 6. Cho $n,r\in \mathbb{N}$ với $r\le n.$ Chứng minh rằng:

a) $A_{n}^{r}=nA_{n-1}^{r-1};$
b) $A_{n}^{r}=\left( n-r+1 \right)A_{n}^{r-1};$
c) $A_{n}^{r}=\dfrac{n}{n-r}A_{n}^{r-1},$ với $r<n;$
d) $A_{n+1}^{r}=A_{n}^{r}+rA_{n}^{r-1};$
e) $A_{n+1}^{r}=r!+r\left( A_{n}^{r-1}+A_{n-1}^{r-1}+…+A_{r}^{r-1} \right).$

Bài 7. Một nhóm có 15 hóc sinh, trong đó có 5 bạn nữ. Hỏi có bao nhiêu cách chọn 9 học sinh sao cho có đúng 3 học sinh nữ:

a) để thành lập một hội đồng.
b) để thành lập một hội đồng với 9 vị trí khác nhau.

Bài 8. Có 10 cái ghế được xếp thành một hàng. 7 học sinh được xếp vào 7 cái ghế sao cho không có 2 học sinh nào ngồi chung một cái ghế. Hỏi có bao nhiêu cách xếp sao cho không có 2 cái ghế trống nào liền nhau.

Bài 9. Có 8 cái hộp được xếp thành hàng. Hỏi có bao nhiêu cách đặt 5 viên bi khác nhau vào các hộp nếu mỗi hộp chứa nhiều nhất 1 viên bi và không có hai hộp không chứa bi nào đứng cạnh nhau?

Bài 10. Xếp một nhóm có 20 học sinh, trong đó có 3 bạn nữ là: A, B, C và 4 bạn nam: X,Y,Z,T thành 2 hàng, mỗi hàng 10 học sinh. Hỏi có bao nhiêu cách xếp sao cho 3 bạn nữ luôn ở hàng trước, còn 4 bạn nam ở hàng phía sau.

Bài 11. Hỏi có bao nhiêu cách xếp 7 bạn nam và 2 bạn nữa thành một hàng sao cho các bạn gái cách nhau bởi đúng 3 bạn nam?

Bài 12. Tìm số $(m+n)$-nhị phân là một dãy chữ số với $ m $ số 0 và $ n $ số 1 sao cho không có 2 số 1 nào đứng kề nhau, khi $n\le m+1.$

Bài 13. Lớp A có 10 bạn nữ và 15 bạn nam và lớp B có 4 nữ và 10 nam. Một hội đồng gồm 7 thành viên được chọn từ 2 lớp đó. Hỏi có bao nhiêu cách chọn các thành viên sao cho có đúng 4 bạn của lớp B và có đúng 5 bạn nam.

Bài 14. Trong mỗi trường hợp sau, tìm số tuyến đường ngắn nhất từ $ O $ đến $ P $ trong sơ đồ được cho dưới đây:
a) Tuyến đường phải đi qua $ A $.
b) Tuyến đường phải qua đoạn $AB$.
c) Tuyến đường phải đi qua $A$ và $C$.
d) Đoạn đường $AB$ bị đóng.

Bài 15. Tìm số cách chọn một nhóm gồm $ 2k $ người từ $n$ cặp đôi, với $k,n\in \mathbb{N}$ và $2k\le n,$ trong mỗi trường hợp sau đây:

a) Có $k$ cặp đôi trong nhóm đó.
b) Không có cặp đôi nào trong nhóm đó.
c) Có ít nhất một cặp đôi được chọn trong nhóm.

d) Có đúng 2 cặp đôi được chọn trong nhóm đó.

Bài 16. Cho một đa giác có 10 đỉnh.

a) Có bao nhiêu đường chéo.
b) Có bao nhiêu tam giác có 3 đỉnh là 3 đỉnh thuộc đa giác.
c) Có bao nhiêu tam giác có đúng 1 cạnh trùng với cạnh của đa giác.
d) Có bao nhiêu tam giác không có cạnh nào trùng với cạnh của đa giác.
e) Biết rằng không có 3 đường chéo nào đồng quy. Tìm số giao điểm của các đường chéo.

Bài 17. Cho đa giác đều có 100 cạnh. Hỏi có bao nhiêu hình chữ nhật tạo ra từ các đỉnh của đa giác trên.

Bài 18. Cho A là tập hợp các số nguyên dương từ 1 đến 100. Hỏi có bao nhiêu tập con có 3 phần tử của A thỏa:

a) Tổng các số chia hết cho 3
b) Tổng các số chia hết cho 4.

Bài 19. Chung kết cuộc thi tiếng hát học đường có 3 bạn vào chung kết, mỗi bạn hát 2 bài khác nhau. Hỏi có bao nhiêu cách sắp xếp chương trình sao cho không có ai hát liên tiếp.

Bài 20. Có bao nhiêu cách chọn ra 3 số từ tập $A = {1, 2, \cdots, 100}$ sao cho một số là trung bình cộng của hai số còn lại.

Tổ hợp lặp và bài toán chia kẹo Euler

Leave a reply

Trong các bài toán đếm ta gặp bài toán sau: Một người vào cửa hang mua dụng cụ học tập để làm thành một món quà gồm viết, sách và tập, người đó chỉ mua tổng cộng 5 món đồ. Biết rằng trong cửa hàng có 5 cây viết giống nhau, 6 sách giống nhau và 10 cuốn tập giống nhau, hỏi có bao nhiêu cách chọn viết, sách tập để làm quà?

Ta thấy rằng số lượng các viết sách và tập đều lớn hơn số cần mua, do đó bài toán chỉ quay lại việc đếm là có bao nhiêu bộ sách viết tập mà tổng số là 5 cái, trong đó mỗi cái có hoặc không có.

Có ba đối tượng là viết, sách và tập, tạ kí hiệu là $A = \{ V, S, T \}$. Một món quà gồm 5 cái, do đó quà có thể là $X = \{ V, V, V, S, T \}$, gồm 3 cây viết và 1 sách, 1 tập, hoặc là tập $Y = \{ V, V, S, T, T \}$, ta thấy các đối tượng $V, T$ là lập lại. Khi đó ta nói tổ hợp $X, Y$ là tổ hợp lặp.

Để định nghĩa rõ hơn ta có định nghĩa sau:

Định nghĩa.  Cho tập $A = \{ a_1, a_2, \cdots, a_k \}$. Một ánh xạ từ $p: A \mapsto \mathbb{N} $, khi đó $P$ được gọi là một multiset của A.

Ví dụ 1. Cho $A = \{ a, b, c \}$. Ánh xạ $p: A \mapsto \mathbb{N}$ như sau: $p(a) = 2, p(b) = 1, p(c) = 1$. Khi đó ta có thể kí hiệu $p$ là $(aabc)$, hay $(baac)$,.., không tính đến thứ tự của các phần tử $a, b, c$.

Đặt $n = p(a_1) + p(a_2)+\cdots +p(a_k)$, bài toán đặt ra là có bao nhiêu ánh xạ $p: A \mapsto \mathbb{N}$ mà $n = p(a_1) + p(a_2)+\cdots +p(a_k)$.

Tiếp theo ví dụ trên, nếu $ p(a) + p(b) + p(c) = 2$ thì có các multiset sau: $(ab), (ac), (bc), (aa), (bb), (cc)$, 6 multiset.

Tính chất. Cho tập $A = \{ a_1, a_2, \cdots, a_k \}$, số ánh xạ $p: A \mapsto \mathbb{N}$ thỏa $p(a_1) + \cdots + p(a_k) = n$ là $C^n_{n+k-1}$

Chứng minh

Mỗi ánh xạ $p$ ta cho tương ứng với một dãy nhị phân độ dài $n+k-1$, trong đó $p(a_1)$ chữ số đầu là 0, tiếp theo là số 1, rồi $p(a_2)$ chữ số $0$,…cuối cùng là $p(a_k)$ chữ số $0$. Ví dụ bộ $VVSTT$ ứng với dãy $0010100$.

Rõ ràng đây là tương ứng 1 – 1, do đó số ánh xạ $p$ bằng số dãy nhị phân, do đó ta chỉ cần đếm số dãy nhị phân.

Ta thấy dãy có $n+k-1$ chữ số trong đó có $k-1$ chữ số $1$, do đó số dãy nhị phân chỉ là số cách chọn vị trí cho $k-1$ chữ số $1$ nên số dãy nhị phân là $C^{k-1}_{n+k-1}$.

Do đó số ánh xạ $p$ là $C^{k-1}_{n+k-1} $

Trở lại bài toán trên, ta thấy số món quà có 5 cái là một tổ hợp lặp chập 5 của sách, viết, tập, do đó số món quà có thể là $C^{2}_{5+2-1} = C^2_6 = 15$.

(Chú ý trong bài toán trên, đảm bảo số mỗi loại sản phẩm có không ít hơn 5 cái).

Bài toán 1. (Chia kẹo Euler). Cho $n$ viên kẹo giống nhau đem chia cho $k$ người, hỏi có bao nhiều cách chia.

Giải

Ta gọi $k$ người là $a_1, a_2, \cdots a_k$, với mỗi cách chia kẹo là một multiset của $A$ mà $p(a_1) + p(a_2)+\cdots +p(a_k) = n$.

Do đó số cách chia kẹo là $C^n_{n+k-1}$.

Bài toán 2. Giải bài toán trên với cách chia sao cho mỗi người có ít nhất một viên.

Giải

Trước hết phát cho mỗi người một viên, thì còn $n-k$ viên kẹo, tiếp tục áp dụng bài toán trên với $n-k$. Khi đó số cách chia là

$C^{k-1}_{n-1}$

Ta có thể giải bài toán trên mà không cần sử dụng bài toán 1 bằng cách xây dựng dãy nhị phân thỏa: $a_1$ chữ số đầu là 0, tiếp theo là số 1, tiếp là $a_2$ chữ số 0, …., cuối cùng là $a_k$ chữ số 0. Dãy này có $k-1$ chữ số 1 đứng giữa $n$ chữ số 0 và không có hai chữ số $1$ nào đứng kề nhau. Khi đó số dãy nhị phân là: $C^{k-1}_{n-1}$.

Phần kế tiếp ta cùng tìm hiểu và giải một số bài toán có thể đưa về bài toán tổ hợp lặp hay bài toán chia kẹo Euler. Các bạn chờ nhé.

Bài toán 1 và 2 có thể phát biểu dưới dạng sau.

Bài toán 3. Cho phương trình $x_1 + x_2 + \cdots + x_k = n$ trong đó $k, n$ là các số nguyên dương.

a. Tìm số nghiệm tự nhiên của phương trình.

b. Tìm số nghiệm nguyên dương của phương trình.

Như bài toán trên ta đã biết, số nghiệm tự nhiên của phương trình là  $C^{k-1}_{n+k-1}$.

Số nghiệm nguyên dương của phương trình là $C^{k-1}_{n-1}$.

(Phần 2)

Trong phần trước ta đã biết, số nghiệm nguyên không âm của phương trình $x_1 +x_2+\cdots + x_k = n$ là $C_{n+k-1}^{k-1}$, và số nghiệm nguyên dương là $C^{k-1}_{n-1}$.

Từ bài toán này ta có thể giải các bài toán sau:

Ví dụ 1. Tìm số nghiệm nguyên của phương trình $x_1 + x_2 + x_3 + x_4 + x_5 = 30$ nếu:

a) $x_i \geq 2 \forall i = \overline{1,5}$.

b) $ 3 < x_1, x_2 $ và $x_3, x_4, x_5 > 5$.

c) $x_1, x_2, x_3, x_4 \geq 4$ và $ 0 < x_5 < 3$.

Giải

a) $x_1 + x_2 + x_3 + x_4 + x_5 = 30$, $x_i \geq 2 \forall i = \overline{1,5}$. (1). Ta đi tìm số nghiệm của hệ (1).

Để đưa về bài toán gốc, ta đặt ẩn phụ như sau: $y_i = x_i – 1 \geq 1$ với mọi $i = \overline{1,5}$.

Khi đó ta có $y_1 +1 + y_2+1 + y_3 + 1 + y_4 + 1 + y_5 + 1 = 30 \Leftrightarrow y_1+y_2+y_3+y_4+y_5 = 25$ với $y_i \geq 1$. (2)

Một bộ nghiệm của (2) cho tương ứng một bộ nghiệm thỏa (1), mà số nghiệm của $(2)$ là $C_{24}^{4}$ (Theo bài toán chia kẹo Euler), do đó số nghiệm của (1) là $C_{24}^{4}$.

b) Tương tự câu a, đặt $y_1 = x_1 – 3, y_2 = x_2 – 3, y_3 = x_3 – 5, y_4= x_4-5, y_5 = x_5 – 5$, từ (1) ta có phương trình $y_1+y_2+y_3+y_4+y_5 = 9$ và $y_i \geq 1$. Số nghiệm là $C_8^4$.

c) Xét $x_5 = 1, 2$ và đặt ẩn phụ $y_i = x_i-3$ ta có đáp số là: $C_{16}^3 + C_{15}^3$.

Ví dụ 2. Có bao nhiêu bộ $(x_1, x_2, ..., x_{10})$ các số nguyên dương thỏa $x_1 + x_2 + \cdots x_{10} < 2020$.

Giải

Đặt $x_{11} = 2020 – (x_1+x_2+\cdots + x_{10}) $ thì $x_{11} \geq 1$.

Khi đó ta có phương trình $x_1 + \cdots + x_{11} = 2020$ và $x_i \geq 1$.

Do đó số nghiệm là $C_{2019}^{10}$.

Ví dụ 3.  Có bao nhiêu bộ $(x_1, x_2, ..., x_{10})$ các số tự nhiên thỏa $x_1 \leq x_2 \leq x_3 \leq \cdots \leq x_{10} \leq 2020$.

Giải

Đặt $y_1 = x_1, y_2 = x_2 – x_1 \geq 0$, $y_2 = x_3-x_2 \geq 0$, …, $y_{11} = 2020 -x_{10} \geq 0$.

Khi đó $y_1 + y_2 + \cdots +y_{11} = 2020$ với $y_i \geq 0$. (2)

Với một bộ nghiệm của (2) sẽ tương ứng duy nhất một bộ $(x_1, x_2, …, x_{10})$  thỏa đề bài.

Số nghiệm của (2) là $C_{2030}^{10}$, đó cũng chính là số bộ $(x_1, x_2, …, x_{10})$ thỏa đề bài.

Ví dụ 4. (VMO 2012) Cho một nhóm gồm 5 cô gái, kí hiệu là $G_1, G_2, G_3, G_4, G_5$ và 12 chàng trai. Có 17 chiếc ghế được xếp thành một hàng ngang. Người ta xếp nhóm người đã cho vào các chiếc ghế sao đó sao cho các điều kiện sau được đồng thời thỏa mãn :
1) Mỗi chiếc ghế có đúng một người ngồi;
2) Thứ tự ngồi của các cô gái, xét từ trái qua phải, là $G_1, G_2, G_3, G_4, G_5$ ;
3) Giữa $G_1$ và $G_2$ có ít nhất 3 chàng trai;
4) Giữa $G_4$ và $G_5$ có ít nhất 1 chàng trai và nhiều nhất 4 chàng trai.
Hỏi có tất cả bao nhiêu cách xếp như vậy?

Giải

Đánh số thứ tự các ghế từ trái sang phải là $1,2, \ldots, 17$.

Gọi $x_{1}$ là số chàng trai được xếp bên trái $G_{1}, x_{2}$ là số chàng trai ở giũa $G_{1}$ và $G_{2}, x_{3}$ là số chàng trai ở giữa $G_{2}$ và $G_{3}, x_{4}$ là số chàng trai ở giữa $G_{3}$ và $G_{4}, x_{5}$ là số chàng trai ở giữa $G_{4}$ và $G_{5}, x_{6}$ là số chàng trai được xếp ở bên phải $G_5$. Khi đó bộ số $\left(x_{1}, x_{2}, \ldots, x_{6}\right)$ hoàn toàn xác định vị trí các cô gái và ta có:
1) $x_{1}+x_{2}+\cdots+x_{6}=12$
2) $3 \leq x_{2}$.
3) $1 \leq x_{5} \leq 4$
Đổi biến $y_{2}=x_{2}-3$ và $y_{5}=x_{5}-1$ ta được $x_{1}+y_{2}+x_{3}+x_{4}+y_{5}+x_{6}=8$ với các $\hat{\text {ẩn}}$ không âm và có thêm điều kiện $y_{5} \leq 3$. Tiếp theo, sử dụng bài toán chia kẹo của Euler ở dạng $x_{1}+y_{2}+x_{3}+x_{4}+x_{6}=8-y_{5}$ ta được đáp số (phần phân ghế cho các cô gái) là $C_{12}^{4}+C_{11}^{4}+C_{10}^{4}+C_{9}^{4}=1161$.
Vì còn có 12 chàng trai có thể hoán đổi vị trí ở 12 chiếc ghế dành cho họ nên số cách xếp thỏa mãn yêu cầu bài toán là $1161 \cdot 12 !$

Ví dụ 5. Có bao nhiêu bộ số nguyên dương $(a, b, c, d)$ thỏa $d = max\{a,b,c,d\}, d \leq 2015$ và

$(ad+bc)(bd+ac)(cd+ab) = (d-a)^2(d-b)^2(d-c)^2$.

Giải
  • Trước hết ta chứng minh $d = a+b+c$ bằng phản chứng.
  • Khi dó $ 3 \leq d \leq 2015$, với mỗi $d$ thì số bộ $(a,b,c)$ là $C_{d-1}^2$.
  • Do đó số bộ thỏa đề bài là $C_2^2 + C_3^2 + \cdots + C_{2014}^2$.

Trên đây là một số bài toán liên quan đến bài toán chia kẹo Euler, các bạn hãy đọc và tìm hiểu thêm trong các tài liệu khác.

Bài tập rèn luyện.

Bài 1. Tìm số nghiệm nguyên dương của phương trình: $x_1 + x_2 + ...+ x_5 = 100$
Bài 2. Tìm số nghiệm không âm của phương trình $x_1 + x_2 + x_3 + x_4 = 20$.
Bài 3. Có bao nhiêu số tự nhiên có 3 chữ số mà tổng các chữ số bằng 11 ?
Bài 4. Tìm số nghiệm nguyên của phương trình $x_1 + x_2 + x_3 + x_4 = 30$ nếu:
a) $x_i \geq 0 \forall i$.
b) $2 \leq x_1 \leq 7$, $x_i \geq 0, i = 2, 3, 4$.
c) $x_1 \geq -3, x_2 \geq -1, x_3, x_4 \geq 1$.
Bài 5. Tìm số nghiệm nguyên dương của phương trình $4x_1 + x_2 + x_3 +x_4 = 15$.
Bài 6. Có 4 viên bi vàng và 10 viên bi xanh. Hỏi có bao nhiêu cách sắp xếp các viên bi thỏa:
a) Không có bi vàng nào kề nhau.
b) Giữa hai bi vàng có ít nhất 2 bi xanh.

Bài 7. Để bảo vệ máy tính của minh khỏi su tấn công của hacker, một lâp trinh viên muốn thiết lập một mât khẩu cho máy tính của mình. Mât khẩu này bao gồm tất cả các chữ cái trong bảng chữ cái tiêng Anh, mỗi chữ cái một lần xuất hiện và các chữ nguyên âm không đứng cạnh nhau. Hỏi lâp trình viên đó có bao nhiêu cách cài đăt mât khẩu?

Bài 8. Bốn anh em An, Bình, Cừng, Danh rất thích ăn keo. Nhân dip Tết, me của các câu đực thửng rất nhiều quà, trong đó có một phần quà là một bịch keo bao gồm 125 viên keo. Vì quá thich ăn kẹo nên bốn anh em đã xin mẹ thêm một vài bịch keo khác giống nhu vậy nữa, nhưng me nhất quyết không cho vì sơ ăn nhiều keo sẽ bi sâu răng, do đó mẹ chỉ cho các câu ăn số kẹo trong bịch kia thôi. Thế là họ ngay lâp tức chia nhau số keo nói trên. Hỏi họ có tông công bao nhiêu cách chia keo ? (cho rằng 125 viên keo là giống hệt nhau, và anh em họ có quyền không ăn môt số viên keo trong số 125 viên keo ban đầu, đồng thời cũng có thể xảy ra trường họ có một nguròi không durọc chia viên keo nào).

Tài liệu tham khảo. 

  1. Jiri-herman-radan-kucera-jaromir-simsa, Counting-and-configurations-problems-in-combinatorics-arithmetic-and-geometry
  2. Chuyên đề toán học 11 - Tập san của học sinh Trường Phổ thông Năng khiếu.

Quy tắc cộng – Quy tắc nhân

Leave a reply

Quy tắc cộng – Quy tắc nhân

 

Quy tắc cộng. Để thực hiện một công việc có thể sử một trong $k$ phương án $A_1, A_2, …, A_k$. Nếu phương án $A_1$ có $a_1$ cách thực hiện, $A_2$ có $a_2$ cách thực hiện…$A_k$ có $a_k$ cách thực hiện. Khi đó số cách thực hiện công việc là: $a_1 + a_2 + …+ a_k$.

Quy tắc cộng. (Dạng khác) Tập $A_1$ có $a_1$ phần tử, $A_2$ có $a_2$ phần tử, …, $A_k$ có $a_k$ phần tử, $A_i \cap A_j = \emptyset \forall i, j = 1, 2, …, k, i \neq j$. Khi đó số phần tử của tập ${A_1} \cup {A_2} \cup … \cup {A_k}$ là $a_1 + a_2 + …+ a_k$.

Nguyên lý bù trừ. Cho hai tập hợp A và B. Khi đó [|A \cup B| = |A| + |B| – |A \cap B| ]
Khi $A \subset X$ thì $|\overline{A}| = |X| – |A|$.

Quy tắc nhân. Để thực hiện một công việc, ta cần thực hiện lần lượt qua các giai đoạn $A_1, A_2, …, A_k$. Nếu $A_1$ có $a_1$ cách thực hiện, $A_2$ có $a_2$ cách thực hiện, …, $A_k$ có $a_k$ cách thực hiện. Khi đó số cách thực hiện công việc là $a_1 \times a_2 \times …\times a_k$.

Quy tắc nhân (Dạng khác) Cho tập $A_1$ có $a_1$ phần tử, $A_2$ có $a_2$ phần tử, …, $A_k$ có $a_k$ phần tử. Khi đó số phần tử của tích Decarters $A_1 \times A_2 \times … \times A_k = {(x_1, x_2, …x_k)| x_i \in A_i \forall i = 1, 2, …, k }$ là $a_1 \times a_2 \times a_3 \times … \times a_k$.

Các ví dụ

Ví dụ 1. Cho tập $A = {0, 1, 2, 3, 4, 5, 6}$. Từ tập $A$ có thể lập được bao nhiêu số tự nhiên

a) Có 5 chữ số khác nhau.
b) Không lớn hơn 4000.
c) Có bao nhiêu số lẻ có các chữ số khác nhau.
d) Có bao nhiêu số có 4 chữ số, mà các chữ số không nhất thiết phải khác nhau.
e) Có bao nhiêu số có 5 chữ số không có số 1 hoặc không có số 2.

Ví dụ 2.  Có thể tạo ra được bao nhiêu hình vuông từ bảng các điểm đã cho như hình sau ($8 \times 8$). Biết rằng:

a) Cạnh hình vuông song song với cạnh hình vuông lớn.
b) Bất kì.

Ví dụ 3.  Cho $n$ có phân tích thành thừa số nguyên tố như sau $$n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$$
Tính số ước nguyên dương của $n$.

Ví dụ 4. bao nhiêu số tự nhiên không lớn hơn 1000

a) Có ít nhất một chữ số 1. (\textbf{272})
b) Không chia hết cho 2 hoặc 3 hoặc 5.

Bài tập rèn luyện

Bài 1. Đội tình nguyện viên của trường PTNK gồm 6 bạn lớp 10, 3 bạn lớp 11 và 5 bạn lớp 12. Cần chọn ra 3 bạn làm ban chỉ huy trong đó có 1 đội trưởng, một đội phó và 1 ủy viên. Hỏi có bao nhiêu cách chọn thỏa:

a) Chọn tùy ý.
b) Bạn tổ trưởng lớp 11.

Bài 2. Thầy dạy toán có một số bài tập gồm: 6 bài toán khó, 5 bài toán trung bình và 7 bài toán dễ và 4 bài siêu dễ. Thầy muốn lập một đề thi gồm 1 câu hỏi khó, 1 câu hỏi trung bình, 1 câu hỏi dễ và 1 câu siêu dễ. Hỏi có bao nhiêu cách chọn bài.

Bài 3.
a) Có bao nhiêu dãy nhị phân có độ dài $n$.
b) Có bao nhiêu tập con của tập có $n$ phần tử.

Bài 4. Có bao nhiêu số nguyên dương có 5 chữ số:

a) Có các chữ số chẵn lẻ xen kẽ.
b) Có chữ số 1 và 2 nhưng không đứng cạnh nhau.
c) Có các chữ số khác nhau và có chữ số 1.
d) Có 4 chữ số không có chữ số 1 hoặc không có chữ số 0.
e) Số chẵn có 5 chữ số khác nhau và chữ số 3 và 0 không đồng thời có mặt.
f) Có 5 chữ số có chữ số 1 hoặc có chữ số 2.
Bài 5.  Cho $A = {1, 2, 3, 4, 5, 6, 7}$ và $B = {a, b, c}$. Có bao nhiêu ánh xạ $f$ từ $A$ vào $B$.

Bài 6. Có bao nhiêu cặp số $(a,b)$ mà bội chung nhỏ nhất của $a, b$ là $2017^3 2018^5 2019^4$

Bài 7. Lớp 10 Toán có 6 bạn nữ và 6 bạn nam được xếp ngồi trên hai dãy ghế đối diện nhau, mỗi dãy có 6 ghế. Có bao nhiêu cách xếp thỏa:

a) Xếp bất kì.
b) Mỗi bạn nam ngồi đối diện với một bạn nữ.

Bài 8. Có 5 bạn vào rạp xem phim, trong rạp chỉ còn một dãy ghế gồm 8 ghế. Hỏi có bao nhiêu cách để các bạn ngồi, biết rằng mỗi người đều được ngồi vị trí bất kì.

Bài 9. Cho tập $A = {1, 2, 3,4,5,6}$. Có bao nhiêu số mà các chữ số thuộc $A$ thỏa:

a) Số chẵn có 5 chữ số khác nhau.
b) Số có 3 chữ số khác nhau và chia hết cho 9. (Số chia hết cho 9 khi và chỉ khi tổng các số chia hết cho 9)
c) Số có 4 chữ số khác nhau và chia hết cho 25.
d) Số có 5 chữ số có dạng $\overline{abcba}$ ($a, b,c$ đôi một khác nhau).
e) Số có 6 chữ số có dạng$\overline{12abab}$ và chia hết cho 5.

Bài giảng quy tắc cộng – Quy tắc nhân.