Dùng ánh xạ trong các bài toán Tổ hợp


Để đếm số phần tử của một tập hữu hạn A, ta tìm một tập hữu hạn B có cùng số phần tử như A nhưng dễ đếm hơn.

Nguyên lý ánh xạ. Cho AB là các tập hữu hạn khác rỗng và f:A\to B là một ánh xạ. Khi đó

a)Nếu f là đơn ánh thì |A|\leq |B|;

b)Nếu f là toàn ánh thì |A|\geq |B|;

c)Nếu f là song ánh thì |A|=|B|.

Continue reading “Dùng ánh xạ trong các bài toán Tổ hợp”

Các tính chất đại số của hệ số nhị thức


Bài 5.1. Cho n là một số nguyên dương. Tìm số hạng lớn nhất của dãy \{C_n^k\}_{k=0}^n.

Bài 5.2. Chứng minh rằng nếu n,k là các số nguyên dương sao cho n>1 thì

a)kC_n^k=nC_{n-1}^{k-1};

b)kC_n^k=(n-k+1)C_n^{k-1}.

Bài 5.3. Chứng minh rằng nếu n,k là các số nguyên dương thì

a)C_n^0+C_{n+1}^1+C_{n+2}^2+\cdots+C_{n+k}^k=C_{n+k+1}^k;

b)C_n^n+C_{n+1}^n+C_{n+2}^n+\cdots+C_{n+k}^n=C_{n+k+1}^{n+1}.

Bài 5.4. Chứng minh rằng nếu n là một số nguyên dương thì

a)C_n^0+C_n^1+\cdots + C_n^n=2^n;

b)C_n^0-C_n^1+\cdots+(-1)^nC_n^n=0;

Continue reading “Các tính chất đại số của hệ số nhị thức”

Tổ hợp


Định nghĩa. Cho một tập An phần tử(n\in\mathbb{N}) và 0\leq k\leq n là một số nguyên. Một k-tổ hợp(một tổ hợp chập k) của A là một tập con k phần tử của A.

Ví dụ 4.1. Các 3-tổ hợp của A=\{a,b,c,d\}\{a,b,c\},\{b,c,d\},\{c,d,a\},\{d,a,b\}\Box.

Số tổ hợp. Cho một tập An phần tử(n\in\mathbb{N}) và 0\leq k\leq n là một số nguyên. Khi đó số k-tổ hợp của A bằng C_n^k=\dfrac{A_n^k}{k!}=\dfrac{n!}{k!(n-k)!}.

Chứng minh. Sự khác nhau giữa một k-tổ hợp và một k-hoán vị chính là một đằng không quan tâm đến thứ tự, trong khi đằng kia có quan tâm đến thứ tự. Tận dụng điều này ta có chứng minh như sau.

Continue reading “Tổ hợp”

Hoán vị tuyến tính


Định nghĩa. Cho n là một số nguyên dương, r là một số nguyên thoả mãn 0\leq r\leq nA là một tập hợp có n phần tử. Một r-hoán vị của A(hay một chỉnh hợp chập r của A) là một cách xếp r phần tử nào đó của A thành một hàng. Một n-hoán vị của A sẽ được gọi là một hoán vị của A.

Ví dụ 2.1. Cho tập A=\{a,b,c,d\}. Khi đó các 3-hoán vị của A là(có tất cả 24):

abc,acb,bac,bca,cab,cba,

abd,adb,bad,bda,dab,dba,

acd,adc,cad,cda,dac,dca,

bcd,bdc,cbd,cdb,dbc,dcb.\Box

Số hoán vị. Cho n là một số nguyên dương, r là một số nguyên thoả mãn 0\leq r\leq nA là một tập hợp có n phần tử. Khi đó số r-hoán vị của A bằng A_n^r=\dfrac{n!}{(n-r)!}. Nói riêng, số hoán vị của A bằng P_n=n!.

Chứng minh. Một r-hoán vị của A sẽ được hình thành sau r bước: Đầu tiên, chọn một phần tử từ A và đặt nó vào vị trí thứ nhất; sau đó ta chọn trong các phần tử còn lại của A một phần và đặt nó vào vị trí thứ hai;…; và cuối cùng ta chọn một phần tử từ n-r+1 phần tử còn lại của A và đặt nó vào vị trí thứ r.

Vì có n cách làm bước thứ nhất, n-1 cách làm bước thứ hai;…;và n-r+1 cách làm bước thứ r nên theo nguyên lý nhân ta có A_n^r=n(n-1)\cdots (n-r+1)=\dfrac{n!}{(n-r)!}.

Ví dụ 2.2. Gọi E là tập tất cả 26 chữ cái tiếng Anh. Tìm số các từ gồm 5 chữ trong E sao cho chữ đầu tiên, chữ cuối cùng là các nguyên âm phân biệt và ba chữ còn lại là các phụ âm phân biệt.

Lời giải. Có 5 nguyên âm trong E đó là a,e,i,o,u21 chữ cái còn lại là các phụ âm.

Một từ thỏa mãn yêu cầu của đầu bài sẽ được hình thành sau hai bước: Đầu tiên, chọn một 2-hoán vị của \{a,e,i,o,u\} và đặt nguyên âm thứ nhất vào vị trí 1, nguyên âm thứ hai vào vị trí 5, sau đó chọn một 3-hoán vị của E-\{a,e,i,o,u\} và đặt phụ âm thứ nhất, hai, ba của hoán vị vào vị trí 2,3,4 tương ứng.

Bởi vì có A_5^2 cách để làm bước thứ nhất và A_{21}^3 cách để làm bước thứ hai nên theo nguyên lý nhân ta có số các từ thoả mãn là A_5^2\times A_{21}^3=159600\Box.

Ví dụ 2.3.7 bé trai và 3 bé gái trong một buổi liên hoan. Có bao nhiêu cách có thể xếp họ thành một hàng sao cho

a)3 bé gái đứng cạnh nhau?

b)Hai vị trí đầu và cuối hàng bị chiếm bởi các bé trai và không có hai bé gái nào đứng cạnh nhau?

Lời giải. a)Vì 3 bé gái đứng cạnh nhau nên ta có thể xem họ là một “bé gái”. Một cách xếp thoả mãn yêu cầu của bài toán sẽ được hình thành sau hai bước: Đầu tiên, xếp 8 người này thành một hàng, sau đó xếp vị trí cho 3 bé gái.

Vì có P_8 cách thực hiện bước đầu và P_3 cách thực hiện bước thứ hai nên theo nguyên lý nhân ta có số các cách xếp thoả mãn là P_8\times P_3\Box.

b)Theo đầu bài, vị trí của các bé trai và các bé gái chỉ có thể như sau

1\,\,\,2\,\,\,3\,\,\,4\,\,\,5\,\,\,6\,\,\,7\,\,\,8\,\,\,9\,\,\,10\,\,\,11\,\,\,12\,\,\,13.

Với vị trí của các bé trai là 1,3,5,7,9,11,13 và các vị trí của các bé gái là 2,4,6,8,10,12. Theo nguyên lý nhân, số cách xếp thoả mãn là P_7\times A_6^3\Box.

Ví dụ 2.4. Tìm số các số nguyên chẵn nằm giữa 2000070000 sao cho các chữ số của chúng đôi một khác nhau.

Lời giải. Gọi \overline{abcde} là một số thoả mãn. Ta thấy a\in\{2,3,4,5,6\}e\in\{0,2,4,6,8\}.

i)Nếu a\in\{2,4,6\}.

Một số thoả mãn sẽ được hình thành sau ba bước: Đầu tiên chọn a từ tập \{2,4,6\}; sau đó chọn e từ tập \{0,2,4,6,8\}-\{a\}; cuối cùng chọn một 3-hoán vị của tập \{0,1,2,3,4,5,6,7,8,9\}-\{a,e\} và cho b bằng số thứ nhất, c bằng số thứ hai, và d bằng số thứ ba của hoán vị.

Bởi vì có 3 cách để làm bước thứ nhất, 4 cách để làm bước thứ hai, và A_8^3 cách để làm bước thứ ba nên theo nguyên lý nhân ta có số các số thoả mãn trong trường hợp này là 3\times 4\times A_8^3.

ii)Nếu a\in\{3,5\}. Tương tự ta có số các số thoả mãn trong trường hợp này là 2\times 5\times A_8^3.

Theo nguyên lý cộng, số các số thoả mãn là 7392.\Box

Ví dụ 2.5. Gọi S là tập các số nguyên có các chữ số lấy từ \{1,3,5,7\} và các chữ số của chúng đôi một khác nhau. Tính

a)|S|;

b)\sum_{n\in S}n.

Lời giải. a)Gọi S_i\subset S với i=1,2,3,4 là tập các số trong Si chữ số, dễ thấy |S|=|S_1|+|S_2|+|S_3|+|S_4|=A_4^1+A_4^2+A_4^3+A_4^4=4+12+24+24=64.

b)Gọi n_1,n_2,n_3,n_4 tương ứng là tổng các chữ số hàng đơn vị, hàng chục, hàng trăm, hàng nghìn của các số trong S. Khi đó tổng cần tính bằng

n_1+10n_2+100n_3+1000n_4.

i)Tính n_1.

Tổng các chữ số hàng đơn vị của các số trong S_1 bằng 1+3+5+7=16. Đê tính tổng các chữ số hàng đơn vị của các số trong S_2, ta cần tìm xem có bao nhiêu số trong S_2 có chữ số hàng đơn vị bằng 1,3,5,7 tương ứng? Suy ra tổng các chữ số hàng đơn vị của các số trong S_2 bằng A_3^1\times (1+3+5+7)=3\times 16=48. Tương tự, tổng các chữ số hàng đơn vị của các số trong S_3 bằng 96, và trong S_4 bằng 96. Suy ra n_1=256.

ii)Tính n_2.

Tương tự n_2=240.

iii)Tính n_3.

Tương tự n_3=192.

iv)Tính n_4.

Tương tự n_4=96.

Vậy tổng cần tính bằng 117856\Box.

Sau đây là một số bài tập tự luyện.

Bài 2.1. Có bao nhiêu cách xếp 26 chữ cái trong bảng chữ cái tiếng Anh thành một hàng nếu các nguyên âm không đứng cạnh nhau?

Hướng dẫn. Làm như Ví dụ 2.3, đáp số của bài toán là P_{21}\times A_{22}^5\Box.

Bài 2.2. Có bao nhiêu số nguyên dương có 7 chữ số sao cho các chữ số đôi một khác nhau thuộc tập \{1,2,3,4,5,6,7,8,9\} và các chữ số 5,6 không đứng cạnh nhau?

Hướng dẫn. Chia các số cần đếm thành 4 loại

Loại 1:Không có 56 trong biểu diễn thập phân. Loại này có P_7 số.

Loại 2:Có 5 nhưng không có 6 trong biểu diễn thập phân. Loại này có 7\times A_7^6.

Loại 3:Có 6 nhưng không có 5 trong biểu diễn thập phân. Loại này có 7\times A_7^6.

Loại 4:Có cả 56 trong biểu diễn thập phân. Ta lại chia các số loại này thành 3 loại:

i)5 xuất hiện ở đầu. Loại này có 5\times A_7^5 số.

ii)5 xuất hiện ở cuối. Loại này cũng có 5\times A_7^5 số.

iii)5 không xuất hiện ở đầu cũng không xuất hiện ở cuối. Loại này có 5\times 4\times A_7^5.

Như vậy số các số thoả mãn là 151200\Box.

Ta có thể làm cách khác bằng cách dùng nguyên lý sau:

Nguyên lý trừ. Nếu A\subset B là các tập hữu hạn thì |B-A|=|B|-|A|.

Muốn dùng nguyên lý này vào giải bài toán trên, ta gọi B là tập các số có 7 chữ số khác nhau lấy từ \{1,2,3,4,5,6,7,8,9\}A là tập các số trong B mà trong biểu diễn thập phân có 56 đứng cạnh nhau. Dễ thấy |B|=A_9^7|A|=2\times 6\times A_7^5\Box.

Bài 2.3. Có bao nhiêu từ gồm 5 chữ cái lấy trong các chữ cái A,B,C,D,E,F, G,H,I,J nếu

a)Các chữ cái trong các từ đôi một khác nhau?

b)Nếu các chữ cái trong các từ đôi một khác nhau và A,B,C,D,E,F chỉ có thể ở các vị trí thứ nhất, ba và năm; trong khi các chữ còn lại chỉ có thể ở các vị trí thứ hai và thứ tư?

Đáp số. a)A_{10}^5;

b)A_6^3\times A_4^2\Box.

Bài 2.4. Có bao nhiêu cách xếp 26 chữ cái trong bảng chữ cái tiếng Anh thành một hàng nếu có đúng 5 chữ cái giữa XY?

Đáp số. 2\times A_{24}^5\times P_{20}\Box.

Bài 2.5. Có bao nhiêu số nguyên lẻ giữa 30008000 nếu các chữ số của nó đôi một khác nhau?

Đáp số. 1232\Box.

Hai nguyên lý đếm cơ bản


Nguyên lý cộng. Giả sử có n_1 cách thực hiện việc E_1, n_2 cách thực hiện việc E_2,…,n_k cách thực hiện việc E_k. Nếu k việc này không thể làm đồng thời thì sẽ có n_1+n_2+\cdots+n_k cách thực hiện một trong các việc E_1,E_2,\cdots,E_k.

Theo ngôn ngữ của lý thuyết tập hợp, nguyên lý này có thể phát biểu như sau: Nếu A_1,A_2,\cdots,A_k là các tập hữu hạn và đôi một rời nhau thì |\cup_{i=1}^kA_i|=\sum_{i=1}^k|A_i|.

Ví dụ 1.1. Người ta có thể đi từ Hải Phòng đến Đà Nẵng bằng một trong ba phương tiện: tàu hoả, tàu thuỷ và máy bay. Nếu có hai cách đi bằng tàu hoả, ba cách đi bằng tàu thuỷ, và 1 cách đi bằng máy bay thì sẽ có 2+3+1=6 cách đi từ Hải Phòng đến Đà Nẵng \Box.

Ví dụ 1.2. Tìm số các cặp có thứ tự (x;y) các số nguyên thoả mãn x^2+y^2\leq 5.

Lời giải. Mỗi i=0,1,2,3,4,5 ta đặt S_i=\{(x,y)|x,y\in\mathbb{Z},x^2+y^2=i\}, khi đó tập cần tính số phần tử sẽ là hợp rời rạc của các S_i. Ta tính số phần tử của các S_i bằng phương pháp liệt kê và cuối cùng được đáp số của bài toán là 21\Box.

Nguyên lý nhân. Giả sử rằng việc E có thể được làm bằng cách thực hiện liên tiếp các việc E_1,E_2,\cdots,E_k; và có n_1 cách thực hiện việc E_1, n_2 cách thực hiện việc E_2,…,n_k cách thực hiện việc E_k. Khi đó số cách làm việc En_1\times n_2\times\cdots\times n_k.

Theo ngôn ngữ của lý thuyết tập hợp, nguyên lý này có thể phát biểu như sau: Nếu A_1,A_2,\cdots,A_k là các tập hữu hạn thì |\prod_{i=1}^kA_i|=\prod_{i=1}^k|A_i|.

Ví dụ 1.3. Đề đi từ thành phố A đến thành phố D người ta phải đi lần lượt qua hai thành phố BC. Nếu có hai cách đi từ A đến B, ba cách đi từ B đến C và một cách đi từ C đến D thì sẽ có 2\times 3\times 1=6 cách đi từ A đến B\Box.

Ví dụ 1.4. Cho kn là các số nguyên dương. Một dãy k-phân độ dài n là một dãy (a_1,a_2,\cdots,a_n) với a_1,a_2,\cdots,a_n\in\{0,1,\cdots,k-1\}. Hỏi có bao nhiêu dãy này?

Lời giải. Đặt A=\{0,1,\cdots,k-1\}. Để hình thành một dãy k-phân, đầu tiên chúng ta cần chọn a_1 từ B, sau đó chọn a_2 từ B, và cứ như thế cho đến cuối cùng cần chọn a_n từ B. Bởi vì có k cách để làm mỗi bước nên theo nguyên lý nhân, số các dãy như vậy bằng k^n\Box.

Ví dụ 1.5. Tìm số các ước dương của 600.

Lời giải. Ta có 600=2^3\times 3^1\times 5^2 nên một số nguyên dương m là một ước dương của 600 khi và chỉ khi nó có dạng m=2^a\times 3^b\times 3^c với a,b,c là các số nguyên thoả mãn 0\leq a\leq 3,0\leq b\leq 1,0\leq c\leq 2. Như vậy số các ước dương của 600 bằng số các bộ ba (a,b,c) thoả mãn a\in\{0,1,2,3\},b\in\{0,1\},c\in\{0,1,2\}, theo nguyên lý nhân, số ước dương của 600 bằng 4\times 2\times 3=24\Box.

Tổng quát hơn ta có: Nếu số nguyên dương n có phân tích tiêu chuẩn n=\prod p_i^{k_i} thì số các ước dương của n bằng \prod (k_i+1).

Ví dụ 1.6. Cho X=\{1,2,\cdots,100\}S=\{(a,b,c)|a,b,c\in X,a<b,a<c\}.

Tính |S|.

Lời giải. Với mỗi k=1,2,\cdots,99 ta đặt S_k=\{(k,b,c)|b,c\in X, b>k,c>k\}. Khi đó S là hợp rời rạc của các S_k, mà theo nguyên lý nhân ta có |S_k|=(100-k)^2 nên suy ra |S|=\sum S_k=328350\Box.

Để ý đến lời giải ví dụ thứ hai và thứ sáu, ta thấy chúng có một điểm chung là chia bài toán đã cho thành các bài toán con đơn giản hơn và giải chúng. Đây là cách cơ bản nhất để giải các bài toán đếm, có thể sẽ có cách khác ngắn gọn hơn, nhưng việc chia một bài toán thành các bài toán con mà chúng ta đã biết cách giải sẽ giúp ta ít gặp phải các sai lầm hơn.

Ví dụ 1.7. Có bao nhiêu số tự nhiên có ba chữ số được lấy từ tập \{1,2,3,4,5,6\} nếu

a)Các chữ số không cần phải khác nhau?

b)Các chữ số phải khác nhau?

c)Các chữ số phải khác nhau và chứa số 3?

d)Các chữ số không cần phải khác nhau và chứa số 3?

Lời giải. a)6^3, b)6\times 5\times 4.

c)Đầu tiên ta chọn vị trí cho số 3, sau đó chọn hai số còn lại lần lượt. Đáp số là 3\times 5\times 4.

d)Nếu tiếp tục làm như trên ta sẽ được kết quả là 3\times 6\times 6, đây là một kết quả không chính xác! Vì làm như vậy những số như 323 sẽ được đếm hai lần. Vấn đề ở chỗ ta đã dùng sai nguyên lý nhân, mỗi hai tổ hợp khác nhau cách thực hiện các công việc E_i phải cho hai kết quả khác nhau thì ta mới áp dụng được nguyên lý nhân. Bài này ta lại phải chia thành các bài toán con và giải chúng lần lượt.

Ta chia trường hợp theo vị trí của số 3 nằm bên trái nhất. Nếu số 3 này nằm ở vị trí hàng trăm thì số có ba chữ số phải có dạng \overline{3ab}, nếu nó nàm ở vị trí hàng chục thì số có ba chữ số phải có dạng \overline{a3b} với a\not=3, và cuối cùng, nếu số 3 này nằm ở vị trí hàng đơn vị thì số ba chữ số phải có dạng \overline{ab3} với a,b\not=3. Giải các bài toán con ta được đáp số của bài toán là 6\times 6+5\times 6+5\times 5\Box.

Như vậy nếu chia được bài toán cần giải về các bài toán đếm đã biết cách giải thì mọi việc còn lại là đơn giản. Không may, trong đa số các bài toán đếm việc tìm ra một cấu trúc để chia bài toán thành các bài toán nhỏ hơn là việc làm khó khăn nhất. Hay nói khác đi, khó khăn nằm ở lúc bắt đầu. Sau khi chọn được cấu trúc rồi, bạn phải kiểm chia xem việc chia như vậy có đảm bảo đầu ra là các mô hình khác nhau hay không.

Hầu hết các bài toán đếm đều yêu cầu bạn phải thực sự hiểu mô hình mà mình cần đếm, hay cái mà bạn cần đếm. Biết lời giải một bài toán đếm sẽ giúp ích bạn một chút khi giải bài toán đếm khác, nhưng muốn thực sự giỏi thì bạn phải làm nhiều bài tập, việc đọc các ví dụ là không bao giờ đủ!

Ví dụ 1.8. Một rổ bóng chứa 5 quả bóng xanh giống nhau và 8 quả bóng đỏ giống nhau. Hỏi có bao nhiêu cách bốc ít nhất 1 quả bóng ra khỏi rổ?

Lời giải. Rõ ràng là có thể giải bài toán bằng cách chia thành các trường hợp: Bốc 1, bốc 2,…,bốc 13 quả bóng. Nhưng như thế hơi dài. Ở trên chia theo số bóng bốc ra, rõ ràng là số bóng khác nhau thì ta có hai lần bốc khác nhau. Liệu còn có cách khác phân biệt hai lần bốc? Ta thấy hai lần bốc cho hai kết quả giống nhau nếu và chỉ nếu số bóng xanh và số bóng đỏ như nhau, vậy hai lần bốc khác nhau nếu và chỉ nếu số bóng xanh hoặc số bóng đỏ khác nhau. Như vậy ta có lời giải sau.

Số cách bốc bằng số cặp (a,b) trừ đi 1, ở đây 0\leq a\leq 5 là số quả bóng xanh và 0\leq b\leq 8 là số quả bóng đỏ. Như vậy ta có đáp số của bài toán là 6\times 9-1=53\Box.

Sau đây là một số bài tập tự luyện.

Bài 1.1. Cho bảng ô vuông 10\times 10. Hỏi có bao nhiêu hình vuông có các đỉnh nằm ở tâm của các ô vuông của bảng vuông này?

Lời giải. Chia các hình vuông làm hai loại, loại có các cạnh song song với cạnh của bảng và loại có các cạnh không song song với các cạnh của bảng. Mỗi hình vuông ở loại thứ hai sẽ nội tiếp trong một hình vuông của loại thứ nhất, và mỗi hình vuông ở loại thứ nhất có cạnh k sẽ ngoại tiếp đúng k-1 hình vuông ở loại thứ hai. Như thế ta chỉ cần đếm số các hình vuông thuộc loại thứ nhất, dễ thấy với mỗi k, số hình vuông cạnh k thuộc loại thứ nhất bằng (10-k)^2. Do đó đáp số của bài toán là \sum_{k=1}^9(10-k)^2k=825\Box.

Bài 1.2. Cho số nguyên dương n. Hỏi có bao nhiêu tam giác có độ dài các cạnh là các số khác nhau trong tập [n]=\{1,2,\cdots,n\}?

Lời giải. Ba số dương a<b<c là độ dài ba cạnh của một tam giác khi và chỉ khi a+b>c. Như vậy số các tam giác trong đầu bài bằng giá trị của tổng |A_1|+|A_2|+\cdots+|A_n|, ở đây A_k=\{(a,b,k)\in [n]^3|a<b<k,a+b>k\} với k=1,2,\cdots,n. Do đó bài toán sẽ được giải nếu ta tính được |A_k| với mỗi k. Không khó khăn ta thấy |A_1|=|A_2|=|A_3|=0. Bây giờ ta sẽ tính |A_k| với k\geq 4.

a)Nếu k chẵn, k=2m với m>1 là số nguyên dương. Trong trường hợp này ta có |A_k|=(m-1)^2.

b)Nếu k lẻ, k=2m+1 với m>1 là số nguyên dương. Trong trường hợp này ta có |A_k|=m(m-1).

Như vậy đáp số của bài toán là \dfrac{p(p-1)(4p+1)}{6} nếu n=2p+1, \dfrac{p(p-1)(4p-5)}{6} nếu n=2p\Box.

Bài 1.3. Xác định số cặp có thứ tự các số nguyên dương (a,b) sao cho bội chung nhỏ nhất của ab bằng 2^35^711^{13}.

Lời giải.a,b là các ước của 2^35^711^{13} nên ta có thể viết a=2^x5^y11^z,b=2^s5^t11^u, từ đây ta phải có \max\{x,s\}=3,\max\{y,t\}=7,\max\{z,u\}=13. Bằng phương pháp liệt kê ta sẽ đếm được số các cặp (x,s),(y,t),(z,u) và đáp số của bài toán là 7\times 15\times 27\Box.

Tổng quát hơn ta có nếu n=\prod p_i^{a_i} thì số các cặp có thứ tự các số nguyên dương (a;b) sao cho bội chung nhỏ nhất của ab bằng n bằng \prod (2a_i+1).

Bài 1.4. Tìm số các số nguyên dương bé hơn 1000 mà trong biểu diễn thập phân của chúng có chứa ít nhất một chữ số 1.

Hướng dẫn. Ta đếm phần bù, đáp số của bài toán là 271\Box.

Bài 1.5. Tìm số các ánh xạ f:\{1,2,\cdots,2008\}\to\{2009,2010,2011,2012\} thoả mãn f(1)+f(2)+\cdots+f(2008) là số chẵn.

Đáp số. 4^{2007}\Box.

Bài 1.6. Có bao nhiêu tập con có ba phần tử của tập \{2^1,2^2,\cdots,2^{2010}\} sao cho ba phần tử đó có thể xếp thành một cấp số nhân tăng?

Hướng dẫn. Ta cần đếm số các cấp số cộng tăng gồm ba số hạng trong tập \{1,2,\cdots,2010\}. Để làm điều này ta hãy chọn phần tử ở giữa của cấp số cộng đó \Box.

Bài 1.7. Tìm số bộ ba có thứ tự các tập (A,B,C) sao cho A\cap B\cap C=\emptysetA\cup B\cup C=\{1,2,\cdots,2010\}.

Lời giải. Mỗi một số 1,2,\cdots,2010 chỉ có thể nằm trong một trong sáu tập A,B,C,A\cap B,B\cap CC\cap A. Như vậy đáp số của bài toán là 6^{2010}\Box.

Bài 1.8. Tìm số các tập con của một tập có n phần tử, ở đây n là một số nguyên dương.

Hướng dẫn. Mỗi một phần tử của tập nói đến trong đầu bài, nó có thể thuộc hay không thuộc vào tập con. Như vậy ta có đáp số của bài toán là 2^n\Box.

Bổ đề Burnside và áp dụng của nó vào bài toán đếm


Cho X là một tập hợp và G là một nhóm. Ta nói G tác động trên X, hay X là một G-tập, nếu có hàm G\times X\to X, (g,x)\mapsto gx thoả mãn ex=x\forall x\in Xg_1(g_2x)=(g_1g_2)x\forall x\in X\forall g_1,g_2\in G, ở đây e là phần tử đơn vị của G.

Gìơ ta xét một G-tập X, với mỗi x\in X, ta gọi quỹ đạo của x là tập \{gx|g\in G\}. Các quỹ đạo khác nhau của các phần tử trong X làm thành một phân hoạch của X, thật vậy, quan hệ xRy nếu có g\in G để x=gy là một quan hệ tương đương trên X. Khi XG là các tập hữu hạn thì ta có thể tính số khối của phân hoạch này theo bổ đề sau đây.

Bổ đề Burnside. Nếu X là một G-tập hữu hạn (nghĩa là XG là các tập hữu hạn và X là một G-tập) và N là số các quỹ đạo khác nhau của các phần tử trong X thì N=\dfrac{1}{|G|}\sum_{g\in G}F(g), trong đó với mỗi g\in G, F(g) là số phần tử của tập \{x\in X|gx=x\}.

Tôi sẽ không đưa ra chứng minh nào của bổ đề này ở  đây, các bạn có thể tìm một chứng minh  trong sách Tổ hợp của Ngô Đắc Tân hay sách về lý thuyết nhóm của Rotman. Gìơ ta đi xét các áp dụng của bổ đề này vào giải các bài toán đếm, các bài tập này đều có trong sách của Rotman.

Bài 1. Cho nq là các số nguyên dương. Hỏi có bao nhiêu lá cờ gồm n mảnh sao cho mỗi mảnh mang một trong q màu cho trước?(Ví dụ một lá cờ như vậy là cờ của Pháp gồm 3 mảnh).

Lời giải. Vì khi ta tô màu một mặt của lá cờ thì mặt sau sẽ được xác định hoàn toàn màu. Nên số lá cờ bằng số cách tô bảng 1\times n bởi q màu, hai cách tô là như nhau nếu nó ở dạng như hình dưới đây.

(Trong hình trên các c_i là các màu.)

Gọi X là tập các bộ (c_1,c_2,\cdots,c_n) với c_i là một trong q màu đã cho với mỗi i. Ký hiệu S_n là nhóm các hoán vị trên \{1,2,\cdots,n\}, G là nhóm con cyclic sinh bởi hoán vị f của S_n, ở đây f(i)=n+1-i\forall i. Ta cho G tác động trên X theo luật f(c_1,c_2,\cdots,c_n)=(c_n,c_{n-1},\cdots,c_1). Như trên đã phân tích, ta chỉ cần đếm số N các quỹ đạo của các phần tử của x theo tác động này là xong. Theo bổ đề Burnside, ta chỉ cần tính F(id)F(f). Dễ thấy F(id)=|X|=q^n theo quy tắc nhân. Để tính F(f), ta chú ý rằng (c_1,c_2,\cdots,c_n)\in X không thay đổi khi tác động f nếu và chỉ nếu c_1=c_n,c_2=c_{n-1},\cdots, vậy cùng theo quy tắc nhân ta có F(f)=q^{[\dfrac{n+1}{2}]}. Như thế đáp số của bài toán là \dfrac{1}{2}(q^n+q^{[\dfrac{n+1}{2}]}).

Bài 2. Cho nq là các số nguyên dương. Chứng minh rằng có

\dfrac{1}{4}(q^{n^2}+2q^{[\dfrac{n^2+3}{4}]}+q^{[\dfrac{n^2+1}{2}]}) cách tô màu bảng vuông n\times n bởi q màu.

Lời giải sơ lược. Lời giải y hệt như trường hợp trên. Ta đánh số các ô của bảng theo kiểu xoáy ốc, chia hai trường hợp n chẵn, lẻ cho dễ đánh số. Tập X bây giờ là tập tất cả các bộ (c_1,c_2,\cdots,c_{n^2}), nhóm G bây giờ là nhóm con cyclic cấp 4 sinh bởi phép quay +90^0 của S_{n^2}.

Chú ý.  Khi n=3,q=n ta có bài số 5 trong VMO 2010.