Hoán vị, chuyển vị, nghịch thế và một số bài toán liên quan
Vũ Thế Khôi, email: [email protected]
Viện Toán Học, 18 Hoàng Quốc Việt, Hà Nội

Bài viết gồm ba phần, phần đầu giới thiệu ngắn gọn một số định nghĩa và tính chất cơ
bản của hoán vị. Phần thứ hai giới thiệu về số nghịch thế của hoán vị, các tính chất của
nó và một số bài toán sơ cấp liên quan. Trong phần cuối chúng tôi giới thiệu một số kết
quả về bài toán đếm số hoán vị thỏa mãn các điều kiện cho trước. Với mục đích giới thiệu
cho giáo viên THPT, chúng tôi đưa ra nhiều ví dụ và bài tập sơ cấp để minh họa. Các
kiến thức trong phần đầu và phần thứ hai được trình bày chủ yếu dựa theo tài liệu tham
khảo [3]. Phần cuối được trình bày dựa theo tài liệu [1, 4, 5]. Người đọc có thể tham khảo
các tài liệu gốc để tìm hiểu sâu thêm về các kết quả trình bày ở đây.
1. Kiến thức cơ bản về hoán vị
Khi lần đầu giới thiệu về hoán vị cho học sinh chúng ta thường định nghĩa một hoán
vị của (1, 2, · · · , n) đơn giản là một dãy (a1 , a2 , · · · , an ) chứa các số 1, · · · , n mỗi số đúng
một lần và được viết theo thứ tự bất kỳ. Định nghĩa hoán vị như một dãy số có thuận lợi
là đơn giản và thường được dùng trong phát biểu của nhiều bài toán.
Một cách nhìn khác về hoán vị là coi hoán vị (a1 , a2 , · · · , an ) như một song ánh σ :
, {1, 2, · · · , n} → {1, 2, · · · , n} cho bởi σ(i) = ai . Khi coi hoán vị như một song ánh ta có
thể lấy hợp thành của hai hoán vị. Để thuận tiện cho việc tính toán hợp thành của hai
ánh xạ, người ta thường ký hiệu hoán vị như sau:




 1 2 ···
σ=
a1 a2 · · ·

n−1
an−1

những xích chỉ chứa đúng 1 phần tử k, tức là σ(k) = k, để cho gọn người ta thường bỏ đi
không viết nếu không gây hiểu lầm gì.
Một xích chỉ chứa hai phần tử (a b) gọi là một phép chuyển vị.
Ta ký hiệu si = (i i + 1), i = 1, 2, · · · , n − 1, là các phép chuyển vị đổi chỗ hai số i và
i + 1.
Định lý 1.2 Mọi hoán vị đều là hợp thành của một số phép chuyển vị si .
Chứng minh. Về trực giác ta thấy định lý đúng vì chỉ cần đổi chỗ hai phần tử kề nhau
ta nhận được mọi hoán vị. Lý luận chặt chẽ như sau: Ở trên ta thấy mọi hoán vị đều viết
được như hợp thành của các xích. Mọi xích lại được viết thành hợp thành của các phép
chuyển vị
(x1 x2 · · · xn ) = (x1 xn )(x1 xn−1 ) · · · (x1 x2 ).


3

Hơn nữa mọi phép chuyển vị đều là hợp thành của các si :
(k l) = (k k + 1)(k + 1 k + 2) · · · (l − 1 l)(l − 2 l − 1) · · · (k k + 1).
Ta có điều cần chứng minh.
Ý tưởng coi các hoán vị như song ánh và sử dụng phép hợp thành thường có ích khi
giải những bài toán mà ta thực hiện liên tiếp nhiều phép đổi chỗ.
Bài tập 1.3. Một bộ bài gồm 2n + 1 quân bài phân biệt. Mỗi lần ta được quyền thực
hiện một trong hai cách tráo bài sau:
- Lấy một số quân bài ở trên cùng, giữ nguyên thứ tự và chuyển về cuối bộ bài;
- Lấy n quân bài ở trên cùng và lần lượt xếp chúng vào n vị trí ở giữa của n + 1 quân
bài dưới cùng.
Chứng minh rằng bằng cách thực hiện các phép tráo bài như trên ta nhận được không
quá 2n(2n + 1) hoán vị khác nhau của bộ bài ban đầu.
Gợi ý: Ta coi bộ bài ban đầu được đánh số lần lượt từ trên xuống dưới 1, 2, · · · , 2n + 1.
Có thể thấy hai phép tráo bài tương ứng với hai loại hoán vị
σk , τ : {1, 2, · · · , 2n + 1} → {1, 2, · · · , 2n + 1}

Ví dụ 2.1. Nếu σ cho bởi (1, 2, · · · , n) thì (σ) = 0. Nếu σ cho bởi (n, n − 1, · · · , 1) thì
(σ) =

n(n−1)
.
2

Ta dễ thấy phép chuyển vị si có thể biểu diễn như dãy (1, · · · i − 1, i +

1, i, i + 2, · · · n) và do đó có (si ) = 1 với mọi i.
Ta có tính chất sau của số nghịch thế.
Tính chất 2.2. (σ ◦ si ) = (σ) ± 1 và (si ◦ σ) = (σ) ± 1.
Chứng minh. Giả sử σ cho bởi (a1 , a2 , · · · , an ) thì dễ dàng tính được σ ◦ si cho bởi
(a1 , · · · , ai−1 , ai+1 , ai , ai+2 , · · · , an ). Như vậy nếu ai < ai+1 thì (σ ◦ si ) = (σ) + 1 và nếu
ai > ai+1 thì (σ ◦ si ) = (σ) − 1.

Ta tính được si ◦ σ(j) = si (aj ) =





i + 1 nếu aj = i




i



hoặc luôn lẻ phụ thuộc vào tính chẵn, lẻ của (σ).
Tương tự ta có τ = sj1 ◦ sj2 ◦ · · · ◦ sjl và (τ ) ≡ l mod 2.
Như vậy σ ◦ τ = si1 ◦ si2 ◦ · · · ◦ sik ◦ sj1 ◦ sj2 ◦ · · · ◦ sjl . Cũng lý luận tương tự trên ta có
(σ ◦ τ ) ≡ k + l

mod 2.

Ta có đẳng thức cần chứng minh.
Ví dụ 2.4. Ví dụ này giới thiệu trò chơi 15 gồm 1 bảng cỡ 4 × 4 trong đó có 15 ô đánh số
từ 1 đến 15 và một ô trống. Ta có thể đẩy các ô bên cạnh vào ô trống để thay đổi trạng
thái của bảng. Vào năm 1880, Sam Loyd, một nhà sáng chế trò chơi, câu đố nổi tiếng
người Mỹ đã đưa ra thách đố: hãy đưa bảng ở trạng thái ban đầu như hình bên tay trái
về hình bên tay phải.

Hình 1. Câu đố của Sam Loyd
Sam Loyd đã treo thưởng 1000 Đô la cho lời giải, nhưng không ai nhận được giải thưởng
vì thách đố này không thể làm được. Ta coi một trạng thái của bảng như một hoán vị
của các số 1, 2, · · · , 15 nhận được khi viết các số lần lượt từ trái qua phải từ trên xuống


6

dưới. Như vậy thách đố tương đương với việc đưa hoán vị (1, 2, · · · , 14, 15) về thành hoán
vị (1, 2, · · · , 15, 14).
Ta nhận xét :
- Khi trượt một ô cùng hàng vào ô trống thì hoán vị không thay đổi.
- Khi trượt một ô cùng cột vào ô trống thì số đó được chuyển về phía trước hoặc phái
sau cách 3 vị trí. Tức là ta thực hiện 3 lần đổi chỗ hai ô đứng cạnh nhau, như vậy số
nghịch thế sẽ thay đổi tính chẵn, lẻ.
Do đó nếu ta đánh số các hàng lần lượt là 1, 2, 3, 4 thì đại lượng:

Ban đầu đại lượng này bằng n − 1, cuối cùng bằng 0. Dễ thấy mỗi lần đổi chỗ hai khối thì
đại lượng này giảm nhiều nhất là 2, riêng lần đầu và lần cuối chỉ có thể giảm đi 1. như
vậy số lần ít nhất sẽ lớn hơn hoặc bằng
Ta có thể chỉ ra cách dùng đúng

n+1
2

n+1
2

.

lần đổi chỗ 2 khối có thể thực hiện được. Ví dụ

n = 9 ta sẽ làm như sau:
9, 8, 7, 6, 5, 4 , 3, 2, 1 → 5, 4, 9, 8, 7, 6, 3 , 2, 1 → 5, 6, 3, 4, 9, 8, 7, 2 , 1 →
5, 6, 7, 2, 3, 4, 9, 8, 1 → 5, 6, 7, 8, 1, 2, 3, 4, 9 → 1, 2, 3, 4, 5, 6, 7, 8, 9.
Bài tập 2.8.[3] Chứng minh rằng nếu τ = σ −1 là ánh xạ ngược của σ thì (τ ) = (σ).
3. Bài toán đếm số các hoán vị thỏa mãn điều kiện cho trước
Trong mục này chúng ta xét một số bài toán tìm số các hoán vị với các điều kiện ràng
buộc về số các nghịch thế hay điều kiện về các dãy con ba phần tử.
Bài tập 3.1. Có bao nhiêu hoán vị của 1, 2, · · · , n có đúng 1 nghịch thế.
Gợi ý: Chỉ có hai trường hợp an = n hoặc an−1 = n, an = n − 1. Từ đó dùng truy hồi
ta được đáp số n − 1.
Bài tập 3.2. Chứng minh rằng có đúng

n
2


Chứng minh. Đặt an := |Sn (132)|, dễ thấy a1 = 1, a2 = 2. Ta xét trường hợp ai = n,
khi đó
(a1 , a2 , · · · , an ) ∈ Sn (132) ⇐⇒ (a1 , a2 , · · · , ai−1 ) ∈ Si−1 (132) và (ai+1 , ai+2 , · · · , an ) ∈
Sn−i (132).
n
1 ai−1 an−i ,

Từ đó ta có công thức truy hồi: an =

( quy ước a0 = 1).

Đây chính là công thức truy hồi cho số Catalan nổi tiếng, với cùng giá trị ban đầu. Từ
đó ta nhận được an chính là số Catalan

2n
1
n+1 n

.

Định lý 3.5.[1, 5] Hai tập Sn (123) và Sn (132) có cùng số phần tử.
Chứng minh. Bạn đọc có thể tham khảo trong tài liệu [1].
Các kết quả sau đây có thể chứng minh đơn giản bằng truy hồi, thích hợp dùng làm
bài tập cho học sinh
Bài tập 3.6[5] Chứng minh rằng |Sn (123)∩Sn (132)| = 2n−1 và |Sn (132)∩Sn (213)| = 2n−1
Bài tập 3.7[4] Chứng minh rằng có đúng (n − 2)2n−3 hoán vị trong Sn (132) mà nó chứa
đúng một dãy con tăng dần có 3 phần tử.
Tài liệu
[1] Bóna, Miklós. Combinatorics of permutations. CRC Press, 2012.
[2] Eriksson, Henrik, et al. "Sorting a bridge hand." Discrete Mathematics 241.1-3 (2001):