Chỉnh hợp lặp

Chỉnh hợp lặp giống chỉnh hợp thông thường, chỉ khác là ta cho phép các phần tử của tập hợp cơ sở M được lặp lại.

Định nghĩa và công thức

Ta bắt đầu bằng một ví dụ quen thuộc: từ các chữ cái của bảng chữ cái tiếng Anh (abc … xyz, gồm 26 chữ cái) có thể lập được bao nhiêu từ khác nhau có độ dài 6? 6 chữ cái không nhiều, nhưng số từ như vậy lại khá lớn. Ta không quan tâm đến nghĩa của từ, nên cả “weqrww” cũng được coi là một từ hợp lệ có độ dài 6.

Để tính, ta chỉ cần biết quy tắc nhân. Có tất cả 26 chữ cái khác nhau có thể dùng. Ở vị trí thứ nhất có thể đặt một trong 26 chữ cái. Ở vị trí thứ hai cũng có thể đặt một trong 26 chữ cái, vì ta không đặt điều kiện các chữ cái không được lặp lại. Như vậy ở mỗi vị trí ta chọn từ 26 chữ cái, và theo quy tắc nhân, tổng số chỉnh hợp là 26⁶ = 308.915.776. Khá nhiều, trong khi ta chỉ dùng 26 chữ cái.

Ta gọi chỉnh hợp lặp chập k của tập hợp M gồm n phần tử là mỗi bộ k phần tử có thứ tự, các phần tử thuộc tập hợp M và mỗi phần tử có thể xuất hiện trong bộ tới k lần. Chẳng hạn với tập hợp M = {1; 2; 3}, tất cả các bộ sau đều là chỉnh hợp lặp chập 4 hợp lệ: (1; 1; 1; 1), (1; 2; 3; 1), (2; 2; 3; 3). Số các chỉnh hợp lặp chập k của n phần tử bằng

$$n^k.$$

Ví dụ có lời giải

1. Từ các chữ số {2; 4; 6; 8} có thể lập được bao nhiêu số có sáu chữ số, nếu các chữ số có thể lặp lại? Ta chỉ cần thay vào công thức: tập hợp có 4 phần tử và ta chọn các bộ 6 phần tử, nên số chỉnh hợp lặp chập 6 của 4 phần tử là

   $$4^6=4096.$$

2. Máy tính thường dùng hệ nhị phân, tức là hệ đếm chỉ dùng hai chữ số 0 và 1. Ở đó người ta dùng các đơn vị riêng, chẳng hạn một bit là một ô nhớ chứa đúng một trong hai giá trị 0 hoặc 1. Đơn vị lớn hơn là byte, gồm 8 bit. Như vậy 1 là một bit, còn 01110001 là một byte. Có bao nhiêu cách khác nhau để điền 8 bit của một byte?

   Ta chọn từ tập hợp {0; 1}, tức là từ 2 phần tử. Ta chọn bộ k phần tử với k = 8, nên số tất cả các khả năng là chỉnh hợp lặp chập 8 của 2 phần tử:

   $$2^8=256.$$

3. Từ ví dụ trước ta biết rằng một byte phân biệt được tới 256 giá trị khác nhau. Có bao nhiêu cách điền 4 byte?

   4 byte gồm 4 · 8 = 32 bit, ta vẫn chọn từ tập hợp có 2 phần tử. Vậy kết quả là chỉnh hợp lặp chập 32 của 2 phần tử:

   $$2^{32}=4.294.967.296.$$

   Ta thấy chỉ 4 byte thôi đã phân biệt được hơn 4 tỉ giá trị. Để dễ hình dung: máy tính ngày nay có ổ đĩa dung lượng hàng trăm gigabyte, thậm chí hàng terabyte. Một terabyte gồm 1.000.000.000.000 byte, tức là 8.000.000.000.000 bit. Như vậy trên ổ đĩa 1 terabyte có thể lưu tới 2^{8.000.000.000.000} giá trị khác nhau.

   Chú ý: hiện nay khái niệm kilobyte (megabyte, v.v.) có phần lộn xộn. Vì lí do kĩ thuật, trước đây một kilobyte không gồm 1000 byte như thông lệ ở các đơn vị khác (một kilôgam bằng 1000 gam), mà bằng 2¹⁰ byte, tức là 1024 byte. Một megabyte khi đó bằng 2²⁰ byte, hay 2¹⁰ kilobyte.

   Vì vậy hiện nay người ta phân biệt hai cách viết: 1 kB (đọc là kilobyte) bằng 1000 byte, còn 1 KiB (đọc là kibibyte) bằng 2¹⁰ = 1024 byte.

4. Một ví dụ khác có trong bài riêng về độ an toàn của mật khẩu.