Chỉnh Hợp Lặp Chập K Của N Phần Tử C

Có thể bạn quan tâm

Chỉnh hợp lặp chập k của n phần tử C 2 năms trước Trả lời: 0 Lượt xem: 79

Share Like

“Chỉnh hợp lặp và không lặp” gồm có 3 phần chính: Phần I – Chỉnh hợp không lặp, Phần II – Chỉnh hợp lặp, Phần III – Bài tập củng cố kiến thức về chỉnh hợp lặp và không lặp.
“Chỉnh hợp lặp và không lặp” bao gôm tất cả kiến thức (định nghĩa, công thức) về chỉnh hợp lặp và không lặp. Thêm vào đó là một số bài tập củng cố kiến thức về chỉnh hợp lặp và không lặp. Như vậy, để có thể làm được các bài về chỉnh hợp, ta cần có một kiến thức chính xác và rõ ràng về chỉnh hợp lặp và không lặp.

PHỤ HUYNH VÀ HỌC SINH CÓ THỂ TÌM HIỂU THÊM

Tổ hợp xác suất – Những điều cần biết

Chuyên đề tổ hợp xác suất lớp 11

Công thức tổ hợp xác suất lớp 11

I.Chỉnh hợp (không lặp):

– Cho tập hợp A gồm n phần tử. Mỗi cách sắp xếp k phần tử của A (1≤k≤n) theo một thứ tự nào đó được gọi là một chỉnh hợp chập k của n phần tử của tập A.

– Số chỉnh hợp chập k của n phần tử:

-Công thức trên cũng đúng trong trường hợp k = 0 hoặc k = n

– Khi k = n thì Ann = Pn = n!

II. Chỉnh hợp lặp:

– Cho tập A gồm n phần tử. Mỗi dãy gồm k phần tử của A, trong đó mỗi phần tử có thể được lặp lại nhiều lần, được sắp xếp theo 1 thứ tự nhất định được gọi là một chỉnh hợp lặp chập k của n phần tử của tập A.

– Số chỉnh hợp lặp chập k của n phần tử :

III. Bài tập củng cố kiến thức:

Định nghĩa: Chỉnh hợp lặp chập k của n phần tử là một bộ (nhóm) có thứ tự gồm k phần tử được chọn từ n phần tử đã cho, trong đó các phần tử trong nhóm có thể lặp lại 2,3,4,.., k lần. Gọi số chỉnh hợp lặp chập k của n phần tử là , khi đó: = nk

Ví dụ 8: Xếp ngẫu nhiên 5 quyển sách vào 3 ngăn kéo. Hỏi có bao nhiêu cách xếp? Mỗi cách xếp 5 quyển sách vào 3 ngăn kéo xem như một chỉnh hợp lặp chập 3 của 5 (mỗi lần xếp một quyển sách vào một ngăn, ta có thể xem như chọn một trong 3 ngăn nên có 3 cách chọn. Do có 5 quyển sách nên số cách chọn là n = 35 = 243 cách.

Ví dụ 9: Có bao nhiêu số tự nhiên gồm 4 chữ số từ các số: 1,2,3,4,5? Có = 54 = 625 số.

Ví dụ 10: Có bao nhiêu cách sắp xếp 10 người lên một tàu hỏa có 3 toa? Số cách sắp xếp 10 người lên 3 toa tàu là số các chỉnh hợp lặp chập 10 của 3 phần tử. Số cách sắp xếp:

Ví dụ 11: Mỗi vé số của mỗi tỉnh gồm có 6 chữ số. Hỏi mỗi tỉnh khi phát hành mỗi đợt sẽ phát hành được bao nhiêu vé số khác nhau? Ta có mỗi vé số gồm có 6 chữ số, nên ta có thể xem việc phát hành ra một vé số là việc chọn ra 6 số bất kỳ có thứ tự có thể trùng nhau từ 10 số từ 0 đến 9. Do đó mỗi vé số được phát hành có thể được xem là một chỉnh hợp lặp chập 6 của 10. Vậy số vé số có thể phát hành mỗi đợt của mỗi tỉnh là số chỉnh hợp lặp chập 6 của 10:

(vé số)

Lưu ý: Trong chỉnh hợp không lặp thì còn trong chỉnh hợp lặp thì có thể có k > n.

Để hiểu được như thế nào là một chỉnh hợp lặp, thì ta xét ví dụ sau:

Ví dụ: Hãy lập ra các số gồm 2 chữ số từ bốn chữ số sau: 1, 2, 3, 4.

Giải

Các số đó là:

11, 12, 13, 14
21, 22, 23, 24
31, 32, 33, 34
41, 42, 43, 44

Mỗi số trong các số nói trên chính là một cách sắp xếp có thứ tự gồm hai chữ số, mỗi chữ số có thể có mặt đến hai lần lấy từ bốn số đã cho. Và mỗi cách sắp xếp như vậy cũng chính là một chỉnh hợp lặp chập 2 của 4 phần tử đã cho.

Để có một khái niệm tổng quát về chỉnh hợp lặp, ta xem 2 phần tử để tạo thành số có 2 chữ số là k và 4 số đã cho là n.

Định nghĩa chỉnh hợp lặp

Chỉnh hợp lặp chập k của n phần tử là một cách sắp xếp có thứ tự của k phần tử, mà mỗi phần tử lấy từ n phần tử đã cho có thể có mặt nhiều lần.

Cách tính số chỉnh hợp lặp

Số các chỉnh hợp lặp chập k của n phần tử được kí hiệu là Ânk. Ta sẽ đi xây dựng để tính Ânk

Để tạo ra một chỉnh hợp lặp chập k của n phần tử ta phải thực hiện một dãy liên tiếp k hành động:

Hành động thứ nhất: Chọn 1 trong n phần tử xếp đầu, có n cách chọn
Hành động thứ hai: Chọn 1 trong n phần tử xếp thứ 2, có n cách chọn
...
Hành động thứ k: Chọn 1 trong n phần tử xếp thứ k có n cách chọn

Theo quy tắc nhân ta có:

Ânk = n.n... = nk

Home » Thuật Toán » [Thuật Toán] Sinh các chỉnh hợp lặp chập k của n

THUẬT TOÁN SINH CÁC CHỈNH HỢP LẶP CHẬP K CỦA N

Xét về bản chất thì thuật toán sinh các chuỗi nhị phân có độ dài là k thực chất là liệt kê các chỉnh hợp lặp chập k của 2 (vì tập nguồn của chúng ta có 2 phần tử là 0 và 1).

Vậy thì nếu tập nguồn của chúng ta không phải là 2 phần tử nữa, mà là n phần tử thì sao ?

Khi đó, bài toán mới của chúng ta sẽ là :

Cho tập X có n phần tử {1,2,…,n}. hãy liệt kê các chỉnh hợp lặp chập k của n.

Ví dụ : với n = 2 và k = 3 nhập từ bàn phím thì các cấu hình của bài toán là :

(111) ; (112) ; (121) ; (122) ; (211) ; (212) ; (221) ; (222).

Theo công thức của chỉnh hợp lặp thì số các cấu hình = n^k= 2^3 = 8.

Và nhìn vào ví dụ trên, chúng ta cũng sẽ thấy cấu hình đầu là toàn số 1 và cấu hình cuối toàn số n. và ta dễ dàng tìm ra thuật toán như sau :

Xét từ cuối dãy về đầu, gặp chữ số có giá trị chưa bằng n :

· * Tăng chữ số đó lên 1 đơn vị

· * Gán tất cả phần tử sau vị trí đó = 1.

Thuật toán dừng lại khi sinh được cấu hình cuối gồm các phần tử có giá trị đều = n.

Source code tham khảo :

#include<iostream> using namespace std; int n, k, a[10]; bool check = false; void display(){ for (int i = 1; i <= k; i++){ cout << a[i]; } cout << endl; } void nextString(){ int i = k; while (a[i]==n&&i>0){ // nếu a[i] = n và i > 0 thì giảm i i--; } if (i == 0) check = true; // nếu i = 0 thì đã đến cấu hình cuối cùng else { a[i]++; // tăng a[i] lên 1 đơn vị for (int j = i + 1; j <= k; j++){ a[j] = 1; // đặt tất cả phần tử phía sau a[i] = 1 } } } void main(){ cout << " nhap n = "; cin >> n; cout << " nhap k = "; cin >> k; for (int i = 1; i <= k; i++){ a[i] = 1; } while (!check){ display(); nextString(); } system("pause"); } 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 : Thanks for reading !