[Thuật Toán] Nhắc lại 1 số kiến thức về đại số tổ hợp

trong bài đầu tiên này, chúng ta sẽ cùng ôn lại 1 số kiến thức về đại số tổ hợp mà các bạn đã từng học ở cấp 3 nhé, mình chỉ nhắc lại thôi :D
có 4 khái niệm các bạn cần phân biệt được, đó là chỉnh hợp lặp, chỉnh hợp không lặp, hoán vị & tổ hợp.

1. Chỉnh Hợp Lặp

 để định nghĩa chỉnh hợp lặp này theo góc độ ánh xạ thì có vẻ là khá là khó hiểu nên mình sẽ nói về nó dưới 1 góc độ khác.

* ĐN : cho 1 tập X gồm n phần tử. 
   mỗi bộ ( hoặc nhóm ) có thứ tự gồm k phần tử lấy ra từ n phần tử đã cho ta được 1 chỉnh hợp    lặp chập k của n.
   các phần tử trong bộ ( nhóm trên ) có thể lặp lại 1,2,3,....,k lần.

ví dụ : tập X gồm các phần tử : {1,2,3,4,5}
thì (1,2,1,3) là 1 chỉnh hợp lặp chập 4 của X.
bằng phép quy nạp toán học ta có thể dễ dàng chứng minh được kết quả sau :

* số các chỉnh hợp lặp chập k của n phần tử là n^k

2. Chỉnh Hợp Không Lặp

* ĐN : cho 1 tập X gồm n phần tử. 
   lấy ra k phần tử trong n phần tử và có sự sắp xếp ( thứ tự nhất định ) ta được 1 chỉnh hợp          không lặp chập k của n

ví dụ : tập X gồm các phần tử : {1,2,3,4,5}
thì (1,2,3) là 1 chỉnh hợp không lặp chập 3 của X.

* số các chỉnh hợp không lặp chập k của X được tính theo công thức : 

3. Hoán Vị

* khi k = n thì 1 chỉnh hợp không lặp chập n của X được gọi là 1 hoán vị của X

* số các hoán vị của tập X gồm n phần tử ( hay số chỉnh hơp không lặp chập n của X ) là n!

4. Tổ Hợp
* ĐN : cho 1 tập X gồm n phần tử. 
   lấy ra k phần tử trong n phần tử ta được 1 tổ hợp chập k của n.

ví dụ : tập X gồm các phần tử : {1,2,3,4,5}
thì (1,2,3) là 1 tổ hợp chập 3 của X.

* số các tổ hợp chập k của X được tính theo công thức : 

5. Mối quan hệ giữa tổ hợp & chỉnh hợp

* các bạn có hể dễ dàng nhận ra mối quan hệ đầu tiên giữa tổ hợp & chỉnh hợp không lặp thông qua 2 công thức tính , có nghĩa là :

* vậy điều khác biệt giữa chỉnh hợp không lặp và tổ hợp là gì ? 
nhiều bạn đọc không kĩ sẽ thắc mắc rằng cái định nghĩa và ví dụ của chỉnh hợp không lặp và tổ hợp na ná nhau. đúng là chúng có hơi giống nhau, điều khác nhau duy nhất giữa chúng đó là cụm từ "có sự sắp xếp ( thứ tự nhất định )".

vì thế, các bạn chỉ cần hiểu nôm na nó khác nhau như sau :

∎ chỉnh hợp không lặp là lấy ra và có sự sắp xếp thứ tự các phần tử .
∎ tổ hợp là chỉ lấy ra mà không có sự sắp xếp thứ tự các phần tử .
∎ tổ hợp "nằm trong" chỉnh hợp không lặp.

như vậy là mình đã trình bày xong với các bạn toàn bộ kiến thức cơ bản về 4 nội dung : chỉnh hợp lặp, chỉnh hợp không lặp, hoán vị & tổ hợp.
bài viết chắc chắn còn nhiều thiếu sót rất mong bạn đọc góp ý qua email : trieuhiepptit@gmail.com
Thanks for reading !