Bài 2: Hoán Vị, Chỉnh Hợp, Tổ Hợp

45 lượt xem - Posted on

1. Hoán vị

a) Định nghĩa: 

   Cho tập hợp A có n (left(nge1right)) phần tử.

   Mỗi kết quả của sự sắp xếp thứ tự (n) phần tử của tập hợp (A) được một hoán vị của (n) phần tử đó.

Nhận xét: Hai hoán vị của (n) phần tử chỉ khác nhau ở thứ tự sắp xếp.

                  Chẳng hạn, hai hoán vị (abc) và (acb) của ba phần tử (a,b,c) là khác nhau.

b) Số những hoán vị:

Ví dụ 1: Có bao nhiêu cách sắp xếp 4 bạn An, Bình, Chi, Dung ngồi vào một bàn học gồm bốn chỗ ngồi?

Giải:

  Mỗi cách sắp xếp bốn bạn vào một bàn bốn chỗ là một hoán vị của 4 phần tử. Ta tính số hoán vị bằng 2 cách như sau:

– Cách 1: Liệt kê: Để cho gọn, ta viết A, B, C, D thay cho tên bốn bạn: An, Bình, Chi, Dung. Ta có tổng thể những cách sắp xếp là:

   ABCD, ABDC, ACBD, ACDB, ADBC, ADCB

   BACD, BADC, BCAD, BCDA, BDAC, BDCA

   CABD, CADB, CBAD, CBDA, CDAB, CDBA

   DABC. DACB, DBAC, DBCA, DCAB, DCBA

 Có tất cả 24 cách.

– Cách 2: Sử dụng qui tắc nhân: Để chọn được một cách sắp xếp thì ta thực hiện liên tục 4 hành vi sau:

   + Chọn người vào vị trí tiên phong của bàn: Có 4 cách chọn (A, B, C, D)

   + Sau khi chọn người vào vị trí đầu, ta chọn tiếp người vào vị trí thứ hai: có 3 cách chọn (vì không chọn người đã ngồi vị trí thứ nhất)

   + Sau khi chọn hai người vào vị trí thứ nhất và thứ hai, ta chọn tiếp ngườ vào vị trí thứ ba: Có 2 cách chọn (vì không chọn lại hai người ở vị trí thứ nhất và vị trí thứ hai)

   + Sau khi chọn ba người vào ba vị trí đầu tiên, vị trí thứ tư chỉ còn 1 lựa chọn.

Vậy số cách chọn là: (4.3.2.1=24) cách. 

Qua ví dụ trên, ta có công thức tính số hoạn vị của n thành phần như sau:

Định lí 1:

Số những hoán vị của một tập hợp có n phần tử, kí hiệu là (P_n):

           (P_n=n!=n.left(n-1right)…2.1)

Ví dụ 2: Một đoàn khách du lịch dự định thăm quan bảy địa điểm (A,B,C,D,E.G) và (H) ở thủ đô Hà Nội. Họ đi thăm quan theo một thứ tự nào đó, chẳng hạn B→A→C→E→D→G→H.

Hỏi đoàn khách có bao nhiêu cách chọn thứ tự du lịch thăm quan du lịch?

Giải:

Mỗi cách chọn thứ tự những khu vực tham quan trên là một hoán vị của tập (left{A,B,C,D,E,G,Hright}).

Do đó, đoàn khách có tất cả (7!=5040) cách chọn.

 

2. Chỉnh hợp

a) Định nghĩa:

Cho tập hợp (A) gồm (n) phần tử ((nge1)) và số nguyên (k) với (1le kle n).

Kết quả của việc lấy (k) phần tử khác nhau từ (n) phần tử của tập hợp (A) và sắp xếp chúng 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ử đã cho.

– Nhận xét: Hai chỉnh hợp khác nhau khi và chi khi có một thành phần của chỉnh hợp này mà không phải của chỉnh hợp kia, hoặc thành phần của hai chỉnh hợp giống nhau nhưng được sắp xếp theo thứ tự khác nhau.

b) Ví dụ và cách tính số những chỉnh hợp:

Ví dụ 1: Một nhóm học tập có năm bạn (A,B,C,D,E). Hãy tính số cách phân công ba bạn làm trực nhật: một bạn quét nhà, một bạn lau bảng và một bạn sắp xếp bàn ghế?

Giải:

Ta kí hiệu (ABC) là một phân công trực nhật: (A) – quét nhà, (B) – lau bảng, (C) – sắp xếp bàn ghế.

Và như vậy: (BAC) là một phân công: (B) – quét nhà, (A) – lau bảng, (C) – sắp xếp bàn ghế.

Ta thấy (ABC) và (BAC) tuy cùng là ba bạn (A,B,C) nhưng đó là hai cách phân công khác nhau (vì khác nhau ở chỗ nhiệm vụ mỗi người khác nhau).

Như vậy mỗi một cách phân công là một chỉnh chập 3 của 5 phần tử.

Ta tính số cách phân công (hay số chỉnh hợp chập 3 của 5 phần tử) bằng hai cách sau:

– Cách 1: Liệt kê:

    (ABC), (ABD), (ABE), (ACB), (ACD), (ACE), (ADB), (ADC), (ADE), (AEB), (AEC), (AED), (BAC), ….

   Số cách là: 60 cách

– Cách 2: Sử dụng qui tắc nhân:

Mỗi cách phân công trực nhật là việc chọn liên tục 3 vị trí: quét nhà, lau bảng, sắp xếp bàn ghế.

  + Có 5 cách chọn người quét nhà

  + Khi đã chọn người quét nhà, có 4 cách chọn người lau bảng (phải trừ người quét nhà)

  + Khi đã chọn được người quét nhà và người lau bảng, có 3 cách chọn người sắp xếp bàn và ghế (vì còn 3 bạn sau khi không tính hai người quét nhà và lau bảng)

Như vậy số cách phân công trực nhật là: 5 x 4 x 3 = 60 cách.

Qua ví dụ trên ta có cách tính số chỉnh hợp chập k của n thành phần như sau:

Định lí 2: 

 Số những chỉnh hợp chập k của một tập hợp có n phần tử, kí hiệu (A_n^k) (left(1le kle nright)) 
       (A_n^k=n.left(n-1right)left(n-2right)…left(n-k+1right))     (1)

Chú ý: Với  (0< k< n) , với quy ước (0!=1) thì ta hoàn toàn hoàn toàn có thể viết công thức (1) dưới dạng:

                                   (A_n^k=dfrac{n!}{left(n-kright)!})            (2)        

Khi đó công thức (2) đúng cho cả (k=0) và (k=n). Vậy công thức (2) đúng với mọi số nguyên (k) thỏa mãn  (0le kle n).

Nhận xét: Một chỉnh hợp chập n của n thành phần chính là một hoán vị của n phần tử.

                 Do vậy: (A^n_n=P_n=n!)

Ví dụ 2: Trong mặt phẳng cho một tập hợp gồm 6 điểm phân biệt. Có bao nhiêu vectơ khác vectơ có điểm đầu và điểm cuối thuộc tập hợp điểm này? 

Giải:  

Mỗi cặp sắp xếp thứ tự gồm hai điểm (left(A,Bright)) cho ta một vectơ có điểm đầu (A), điểm cuối (B). Như vậy, mỗi vectơ có thể xem là một chỉnh hợp chập 2 của tập hợp 6 điểm đã cho. Vậy  số vectơ cần tìm là: 

        (A^2_6=6.5=30) (vectơ)

Hay (A^2_6=dfrac{6!}{left(6-2right)!}=dfrac{6!}{4!}=dfrac{720}{24}=30) (vectơ)

3. Tổ hợp

a) Định nghĩa:
Cho tập (A) có (n) phần tử (left(nge1right)) và số nguyên (k). Một tập con của (A) có (k) phần tử được gọi là một tổ hợp chập (k) của (n) phần tử của (A) (gọi tắt là một tổ hợp chập (k) của (A)).

Như vậy lập một tổng hợp chập (k) của (A) chính là lấy ra (k) phần tử của (A) (không chăm sóc đến thứ tự).

Chú ý: Số (k) trong định nghĩa cần thoả mãn điều kiện (1le kle n). Tuy nhiên tập hợp không có thành phần nào là tập rỗng nên 1a quy ước gọi tổng hợp chập 0 của (n) phần tử là tập rỗng.

b) Ví dụ và cách tính số những tổ hợp:

Ví dụ 1: Trên mặt  phẳn cho 4 điểm phân biệt (A,B,C,D) sao cho không có ba điểm nào thẳng hàng. Hỏi có thể tạo được bao nhiêu tam giác mà những đỉnh thuộc tập 4 điểm đã cho?

Giải:

Mỗi một tam giác ứng với tập có 3 đỉnh lấy ra từ tập 5 điểm đã cho (thứ tự những đỉnh không quan trọng, ví dụ các tam giác (ABC), (ACB), (BAC), (BCA), (CAB), (CBA) đều là một tam giác và chỉ đếm 1 lần). Hay nói cách mỗi tam giác là một tổng hợp chập 3 của 4 thành phần (A,B,C,D).

Ta tính số tổng hợp chập 3 của 4 thành phần bằng 2 cách sau:

– Cách 1: Liệt kê:

   (ABC), (ABD), (BCD)

   Như vậy có 3 tam giác.

– Cách 2: Tính theo số chỉnh hợp chập (k) của (n) phần tử:

   Số chỉnh hợp chập (k) của (n) phần tử là: (A_n^k=dfrac{n!}{left(n-kright)!})

   Tuy nhiên trong các chỉnh hợp chập (k), thứ tự các thành phần là quan trọng. Nếu thứ tự là không quan trong, thì số thành phần sẽ giảm đi ((k!)) lần.

   Hay nói cách khác, so với số chỉnh hợp chập (k) thì số tổng hợp chập (k) chỉ tính mỗi tập con là 1 lần còn số chỉnh hợp phải tính (k!) lần tương ứng với số hoán vị của (k) phần tử.

Vậy số tổng hợp chập (k) của (n) phần từ bằng số chỉnh hợp chập (k) của (n) phần tử chia cho (k!).

Kí hiệu số tổng hợp chập (k) của (n) phần tử là (C^k_n)  hoặc (left(dfrac{n}{k}right))thì ta có:

    (C_n^k=dfrac{A^k_n}{k!}=dfrac{n!}{k!left(n-kright)!})

Số các tổng hợp chập (k) của một tập hợp có n phần tử  là  

     (C_n^k=dfrac{A_n^k}{k!}=dfrac{nleft(n-1right)left(n-2right)……left(n-k+1right)}{k!})

Ví dụ 2:  Một tổ có 10 người gồm 6 nam và 4 nữ. Cần lập một đoàn đại biểu gồm 5 người. Hỏi

   a) Có tất cả bao nhiêu cách lập?

   b) Có bao nhiêu cách lập trong đó có 3 nam và 2 nữ?

Giải:

a) Mỗi cách lập là một tổng hợp chập 5 của 10 thành phần (vì 10 người). Số cách lập là:

       (C^5_{10}=dfrac{10!}{5!left(10-5right)!}=252) cách

b) Số cách lập đoàn 5 người trong đó có 3 nam và 2 nữ:

   – Số cách chọn 3 nam từ 6 nam là: (C^3_6)

   – Số cách chọn 2 nam từ 4 nữ là: (C^2_4)

  Theo qui tắc nhân, số cách chọn 5 người trong đó có 3 nam và 2 nữ là:

               

(C^3_6.C^2_4=20.6=120)

 cách.

4. Hai đặc thù cơ bản của số 

(C^k_n)

a) Tính chất 1:

 Cho số nguyên dương (n) và số nguyên (k) với (0le kle n). Khi đó:

          (C^k_n=C^{n-k}_n)

Chẳng hạn: (C^3_7=C^4_7=35).

b) Tính chất 2 (hằng đẳng thức Pa-xcan):

Cho các số nguyên (n) và (k) với (1le kle n). Khi đó :

          (C^{k-1}_{n-1}+C^k_{n-1}=C^k_n)

Chẳng hạn: (C^3_7+C^4_7=C^4_8=70)

Chú ý: Để phân biệt sự khác nhau giữa số chỉnh hợp với số tổ hợp, ta chỉ cần chú ý chăm sóc đển nhận xét sau :

-Tổ hợp là cách chọn k thành phần trong n thành phần mà “không quan tâm” đến thứ tự sắp xếp

– Chỉnh hợp là cách chọn k thành phần trong n phần  tử và “có quan tâm” đến thứ tự sắp xếp. Việc phân biệt khi nào sử dụng số chỉnh hợp, lúc nào sử dụng số tổng hợp là rất quan trọng. 

5. Vài tính chất quan trọng của số chỉnh hợp, số tổ hợp

Cho (0le kle n) với (k,n) là các số tự nhiên (trong đó (n>0)). Khi đó ta có :

1) (C_n^k=dfrac{A_n^k}{P_k})

2) (C_n^k=C_n^n=1;A_n^0=1)

3) (C_n^k=C_n^{n-k})

4) (C_n^k=C_{n-1}^k+C_{n-1}^{k-1}), (đúng với mọi (nge kge1))

Ví dụ 1 : Tính giá trị biểu thức : 

     (M=dfrac{A_{n+1}^4+3A^3_n}{left(n+1right)!})

Nếu (C_{n+1}^2+2C_{n+2}^2+2C_{n+3}^2+C_{n+4}^2=149)

Giải:

Xét phương trình :

(C_{n+1}^2+2C_{n+2}^2+2C_{n+3}^2+C_{n+4}^2=149left(1right))

Chú ý : khi (n+1ge2) thì rõ ràng (n+2>2;n+3>3;n+4>4), vì thế điều kiện kèm theo kèm theo để (1) có nghĩa là (nin N)*

Ta có :

(1) (Leftrightarrowdfrac{left(n+1right)!}{left(n-1right)!2!}+2dfrac{left(n+2right)!}{n!2!}+2dfrac{left(n+3right)!}{left(n+1right)!2!}+dfrac{left(n+4right)!}{left(n+2right)!2!}=149)

     (Leftrightarrowdfrac{nleft(n+1right)}{2}+left(n+1right)left(n+2right)+left(n+2right)left(n+3right)+dfrac{left(n+3right)left(n+4right)}{2}=149)

     (Leftrightarrow n^2+4n+6+2n^2+8n+8=149)

     (Leftrightarrow3n^2+12n-135=0)

     (Leftrightarrow n^2+4n-45=0)

     (Leftrightarrow n=5) hoặc (n=-9) (loại do (nge1))

Vậy (M=dfrac{A_6^4+3A_5^3}{6}=dfrac{dfrac{6!}{2!}+3dfrac{5!}{2!}}{6!}=dfrac{3}{4})

Ví dụ 2 : Cho tập hợp (A) gồm (n) phần tử ((nge4)). Biết rằng số tập hợp con gồm 4 thành phần bằng 20 lần số tập hợp con gồm 2 thành phần của A. Tìm (n) ?

Giải:

Số tập hợp con có 4 thành phần của A là (C^4_n)

Số tập hợp con có 4 thành phần của A là (C^2_n)

Theo bài ra ta có phương trình : (C^4_n=20C^2_nleft(nge4right))

(Leftrightarrowdfrac{n!}{left(n-4right)!4!}=20dfrac{n!}{left(n-2right)!2!})

(Leftrightarrowdfrac{nleft(n-1right)left(n-2right)left(n-3right)}{3.4}=20nleft(n-1right))

(Leftrightarrowleft(n-2right)left(n-3right)=240)

(Leftrightarrow n^2-5n-234=0)

(Leftrightarrow n=18) hoặc (n=-13) (loại do (nge4))

Vậy tập hợp (A) có 18 phần tử

Ví dụ 3 : Cho đa giác đều (A_1A_2….A_{2n};nge2), (n là nguyên dương) nội tiếp đường tròn (O). Biết rằng số tam giác có 3 đỉnh trong 2n điểm (A_1,A_2,….,A_{2n}) gấp 20 lần số hình chữ nhật có 4 đỉnh trong 2n điểm (A_1,A_2,….,A_{2n}). Tìm (n) ?

Giải:

Số tam giác là (C^3_{2n}). Một đa giác đều (2n) đỉnh thì có (n) đường chéo xuyên tâm. Cứ hai đường chéo xuyên tâm có 1 chữ nhật theo yêu cầu. Vậy số hình chữ nhật là  (C^2_{2n}).

Theo bài ta có phương trình :

(C_{2n}^3=20C_n^2left(nge2right))

(Leftrightarrowdfrac{left(2nright)!}{left(2n-3right)!3!}=20dfrac{n!}{left(n-2right)!2!})

(Leftrightarrowdfrac{left(2n-2right)left(2n-1right)2n}{3}=20left(n-1right)n)

(Leftrightarrow2left(n-1right)left(2n-1right)2n=60left(n-1right)n)

(Leftrightarrow2n-1=15) (do (nge2))

(Leftrightarrow n=8)

Vậy đa giác đều có 16 cạnh (thập lục giác đều).

Đánh giá post này

Trả lời

Email của bạn sẽ không được hiển thị công khai.