Permutations

Cho $n$ là một số nguyên dương, $r$ là một số nguyên thoả mãn $0\leq r\leq n$ và $A$ 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ụ 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$

Định lí 1. Cho $n$ là một số nguyên dương, $r$ là một số nguyên thoả mãn $0\leq r\leq n$ và $A$ 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 quy tắc nhân, ta có $A_n^r=n(n-1)\cdots (n-r+1)=\dfrac{n!}{(n-r)!}.$ $\Box$

Ví dụ 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,u$ và $21$ 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\setminus \{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 quy tắc nhân ta có số các từ thoả mãn là $A_5^2\times A_{21}^3=159600.$ $\Box$

Continue reading →

Basic counting principles

Nguyên lý thứ nhất (Quy tắc 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,\ldots,E_k$ .

Ví dụ 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ụ 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ý thứ hai (Quy tắc 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,\ldots,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 $E$ là $n_1\times n_2\times\cdots\times n_k$ .

Ví dụ 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ố $B$ và $C$ . 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 $D.$ $\Box$

Ví dụ 4. Cho $k$ và $n$ 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,\ldots,a_n)$ với $a_1,a_2,\ldots,a_n\in\{0,1,\ldots,k-1\}$ . Hỏi có bao nhiêu dãy này?

Lời giải. Đặt $A=\{0,1,\ldots,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 quy tắc nhân, số các dãy như vậy bằng $k^n.$ $\Box$

Ví dụ 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 5^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 quy tắc 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ụ 6. Cho $X=\{1,2,\ldots,100\}$ và

$S=\{(a,b,c)\mid 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 quy tắc 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ụ 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?

(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$ .

(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 quy tắc 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 quy tắc 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$

Continue reading →

Burnside’s lemma

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 X$ và $g_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 $X$ và $G$ 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à $X$ và $G$ 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 $n$ và $q$ 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)$ và $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 $n$ và $q$ 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}$ .