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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s