Biểu tượng chim cắt của Kestrel Exams KESTREL EXAMSLUYỆN TẬP ĐỂ ĐẠT
Bản dịch này do AI thực hiện và chưa được người bản ngữ kiểm duyệt. Nếu có khác biệt, bản tiếng Anh là bản chính. Mã nguồn được giữ nguyên bằng tiếng Anh. Ứng dụng luyện tập và tài liệu cho các kỳ thi chứng chỉ của Hoa Kỳ chỉ có bằng tiếng Anh. Read in English
Discrete MathĐọc trong 7 phút

Hoán vị và chỉnh hợp: n! và P(m, n)

Có bao nhiêu cách sắp thứ tự 5 chữ cái? Có bao nhiêu từ 3 chữ cái không lặp từ một bảng chữ cái gồm 8 chữ? Cả hai đáp án đến từ một ý tưởng: điền từng vị trí một và nhân số lựa chọn. Mọi kết quả đếm trên trang này đều được kiểm tra bằng cách liệt kê ra bằng máy tính.

Luyện tập chủ đề này trong ứng dụng miễn phí →Tất cả bài hướng dẫn Discrete Math

Xếp hàng chụp ảnh#

Ba người bạn, Ana, Ben và Cai, xếp hàng chụp ảnh. Có bao nhiêu cách xếp hàng khác nhau?

Điền các chỗ từ trái sang phải. Chỗ đầu tiên có thể là bất kỳ ai trong 3 người. Khi nó đã được điền, còn 2 người cho chỗ thứ hai. Sau đó còn 1 người cho chỗ cuối. Vậy có 3 · 2 · 1 = 6 cách xếp hàng.

Viết bằng chữ cái: ABC, ACB, BAC, BCA, CAB, CBA. Sáu cách, đúng như đã nói.

Bước “điền một chỗ, nhân số lựa chọn” đó là quy tắc nhân, và nó nằm đằng sau mọi thứ trên trang này.

Hoán vị và n!#

Một hoán vị (permutation) của n đối tượng là một thứ tự của tất cả chúng, mỗi đối tượng được dùng đúng một lần. Tập hợp mọi hoán vị của n đối tượng được viết là Sn.

Theo quy tắc nhân, có n · (n − 1) · … · 2 · 1 hoán vị. Tích đó được viết là n! và đọc là “n giai thừa” (n factorial).

|Sn| = n!   Vậy 3! = 6, 4! = 24, 5! = 120.

Một hoán vị cũng là một song ánh từ một tập hợp lên chính nó: vị trí 1 đi đến một chữ cái nào đó, vị trí 2 đến chữ khác, và không chữ cái nào được dùng hai lần. Đó là mối liên hệ với các hàm.

Vì sao n! đúng: phép quy nạp từ bài giảng#

Đây là cách dựng mọi hoán vị của n + 1 chữ cái từ các hoán vị của n chữ cái, không sót cái nào và không lặp cái nào.

Lấy một hoán vị của A, B, C, ví dụ ABC. Nó có 4 khe: trước A, giữa A và B, giữa B và C, sau C. Thả chữ cái mới D vào từng khe:

DABC, ADBC, ABDC, ABCD.

Làm điều này với cả 6 hoán vị của ABC, và bạn được 6 · 4 = 24 từ.

  • Trong cùng một nhóm các từ khác nhau, vì D nằm ở vị trí khác nhau trong mỗi từ.
  • Giữa hai nhóm các từ cũng khác nhau. Xóa D khỏi cả hai và bạn được hai hoán vị khác nhau của ABC.

Vậy |S4| = 4 · |S3|, và tổng quát |Sn+1| = (n + 1) · |Sn|. Cùng với |S1| = 1, quy nạp cho |Sn| = n!.

Phép nhân có nghĩa là gì

“2 · 3” nghĩa là 2 hàng, mỗi hàng 3 đối tượng. “3 · 2” nghĩa là 3 hàng, mỗi hàng 2 đối tượng. Xoay hình chữ nhật 90° là một song ánh giữa chúng, đó là lý do 2 · 3 = 3 · 2. 24 từ ở trên thực sự là 6 hàng, mỗi hàng 4 từ.

Chỉnh hợp: sắp thứ tự chỉ một số chữ cái#

Giờ chỉ dùng một số chữ cái. Từ bảng chữ cái {A, B, C, D}, có bao nhiêu từ 2 chữ cái gồm hai chữ khác nhau? Thứ tự có ý nghĩa, nên AB và BA là hai từ khác nhau.

ABACAD
BABCBD
CACBCD
DADBDC

Có 4 lựa chọn cho chữ cái đầu và 3 cho chữ cái thứ hai: 4 · 3 = 12. Đây là một chỉnh hợp (arrangement), còn gọi là hoán vị từng phần, viết là P(4, 2).

Tổng quát, chọn có thứ tự n chữ cái từ một bảng chữ cái gồm m chữ:

P(m, n) = m · (m − 1) · (m − 2) · … · (m − n + 1)

Tích đó có đúng n thừa số: mỗi vị trí một thừa số. Dừng sau n thừa số. Ví dụ P(7, 3) = 7 · 6 · 5 = 210.

Hai sự thật hữu ích. P(n, n) = n!, vì dùng cả n chữ cái là một hoán vị đầy đủ. Và P(m, n) = m!/(m − n)!, vì các thừa số dưới m − n + 1 được giản ước.

Thêm một chữ cái vào bảng chữ cái#

Phép quy nạp theo m trong bài giảng so sánh P(m + 1, n) với P(m, n). Hãy viết chúng cạnh nhau cho m = 7, n = 3:

P(7, 3) = 7 · 6 · 5 = 210    và    P(8, 3) = 8 · 7 · 6 = 336.

Số mới được thêm thừa số 8 ở trên cùng và mất thừa số 5 ở dưới cùng. Tổng quát:

P(m + 1, n) = (m + 1)/(m − n + 1) · P(m, n).

Kiểm tra: 210 · 8/5 = 336. Trường hợp có lời giải trong bài giảng, đi từ 4 chữ cái lên 5 với n = 4, là phiên bản dễ: thừa số dưới cùng ở đó là 1, nên P(5, 4) = 5 · 4! = 120.

Đếm các hàm#

Chỉnh hợp cũng đếm các hàm. Có bao nhiêu hàm từ {a, b, c} đến {1, 2, 3, 4}?

  • Hàm bất kỳ: mỗi trong 3 đầu vào chọn bất kỳ trong 4 đầu ra. 4 · 4 · 4 = 43 = 64.
  • Hàm đơn ánh (một-một): các đầu ra không được lặp. 4 · 3 · 2 = P(4, 3) = 24.

Sự khác nhau giữa hai con số đó là sự khác nhau giữa “cho phép lặp” (lũy thừa) và “không lặp” (chỉnh hợp).

n! tăng nhanh đến mức nào#

Giai thừa cuối cùng vượt mọi hàm mũ, vì mỗi thừa số mới đều lớn dần trong khi cơ số của hàm mũ cố định.

n2n3nn!
1231
38276
532243120
71282,1875,040
101,02459,0493,628,800

Tại n = 10, n! đã gấp khoảng 60 lần 310. Đó là lý do một máy tính không thể đơn giản thử mọi thứ tự của vài chục đối tượng.

Một câu để mang vào phòng thi

Điền từng vị trí một và nhân số lựa chọn: dùng cả n vị trí cho n!, và chỉ n vị trí trong m chữ cái cho P(m, n), có đúng n thừa số.

Sai ở chỗ nào#

  • Quá nhiều thừa số. P(7, 3) là 7 · 6 · 5. Viết 7 · 6 · 5 · 4 là đếm các từ 4 chữ cái.
  • Dùng mn khi cấm lặp. mn cho phép AA. Chỉnh hợp thì không.
  • Chia cho n! khi thứ tự có ý nghĩa. m!/(n!(m − n)!) đếm các cách chọn không thứ tự, tức các tập con có kích thước n. Đó là một câu hỏi khác.
  • Viết m!/n! cho P(m, n). Mẫu số là (m − n)!. Hai công thức trùng nhau một cách tình cờ khi m = 2n, điều này che giấu lỗi trong các ví dụ nhỏ như P(4, 2).

Tự kiểm tra trong ứng dụng Kestrel Exams miễn phí

Luyện tập Discrete Math theo chủ đề: dùng được khi không có mạng, không quảng cáo, không cần tài khoản.

Luyện tập hoán vị và chỉnh hợp →

Câu hỏi thường gặp#

Công thức của hoán vị là gì?

Số cách sắp thứ tự n đối tượng phân biệt là n! = n · (n − 1) ⋯ 2 · 1. Với việc chọn có thứ tự n đối tượng từ m đối tượng, số cách là P(m, n) = m(m − 1)⋯(m − n + 1), có n thừa số và bằng m!/(m − n)!.

Hoán vị và chỉnh hợp khác nhau thế nào?

Một hoán vị sắp thứ tự tất cả các đối tượng. Một chỉnh hợp (hoán vị từng phần) chỉ sắp thứ tự một số trong chúng, n đối tượng được chọn từ m. Vậy P(n, n) = n! là trường hợp hoán vị.

Vì sao n! đếm các hoán vị?

Có n lựa chọn cho vị trí đầu tiên, n − 1 cho vị trí thứ hai, và cứ thế xuống đến 1. Bài giảng chứng minh bằng quy nạp: chèn một chữ cái mới vào từng khe trong n + 1 khe của mỗi hoán vị của n chữ cái sẽ tạo ra mọi hoán vị của n + 1 chữ cái đúng một lần.

Có bao nhiêu hàm một-một từ một tập 3 phần tử vào một tập 4 phần tử?

24. Đầu vào thứ nhất có 4 đầu ra khả dĩ, đầu vào thứ hai còn 3, đầu vào thứ ba còn 2: 4 · 3 · 2 = P(4, 3) = 24. Nếu không có điều kiện một-một thì có 4³ = 64 hàm.

Đề xuất chỉnh sửa

Có chỗ nào chưa rõ? Có chủ đề nào bạn muốn chúng tôi viết? Hãy cho chúng tôi biết. Chúng tôi đọc mọi tin nhắn, và một lời đề nghị là cách nhanh nhất để có bài hướng dẫn mới: một số bài ở đây ra đời vì có người hỏi.