Bổ túc về Giải tích Tổ hợp

1. TẬP HỢP:

Tập hợp là một nhóm các đối tượng có chung một số các tính chất nhất định nào đó. Mỗi đối tượng thuộc tập hợp được gọi là phần tử của tập hợp.

Các ví dụ về tập hợp:

– Tập hợp sinh viên trong trường đại học nào đó.

– Tập hợp N mọi số tự nhiên.

– Tập hợp R mọi số thực.

Muốn xác định một tãp hợp, có thể dùng một trong hai cách:

a) Liệt kê mọi phần tử của nó, chẳng hạn: A = {a, b, c, d} là tập hợp bốn chữ cái đầu tiên của bảng chữ cái tiếng Việt.

b) Chỉ ra một đặc tính đặc trưng cho các phần tử của tập hợp.

Thí dụ: B = \{x \in \Re : |x| \le 2 \} là tập hợp số thực thỏa mãn tính chất -2 \le x \le 2 .

Tập hợp có số phần tử hữu hạn được gọi là tập hợp hữu hạn. Còn tập hợp có số phần tử là vô hạn được gọi là tập hợp vô hạn.

Tập hợp vô hạn được chia làm hai loại:

Tập hợp vô hạn đếm được. Thí dụ: tập hợp tất cả các số nguyên dương: 1, 2, 3, …

Tập hợp vô hạn không đếm được. Thí dụ: tập hợp tất cả các điểm của một đường thẳng, tập hợp tất cả các số thực trong khoảng (0, 2) là những tập hợp không đếm được.

2. QUY TẮC NHÂN:

Quy tắc nhân được phát biểu như sau:

Một công việc nào đó được chia làm hai giai đoạn, có n1 cách hoàn thành giai đoạn I và có n2 cách hoàn thành giai đoạn II. Khi đó sẽ có tất cả: n = n1.n2 cách hoàn thành công việc.

Thí dụ: Ta muốn đi từ vị trí A đến vị trí B. Trên đường đi ta muốn ghé qua vị trí C. Có 2 cách đi từ A đến C và có 3 cách đi từ C tới B. Ki đó ta có tất cả n = 2.3 = 6 cách đi khác nhau từ A đến B.

Một cách tổng quát, ta phát biểu quy tắc nhân:

Giả sử một công việc nào đó được chia làm k giai đoạn. có n1 cách hoàn thành giai đoạn thứ I, có n2 cách hoàn thành giai đoạn thứ II,…, có nk cách hoàn thành giai đoạn cuối cùng. Khi đó sẽ có tất cả: n = n_1n_2...n_k = \prod\limits_{i=1}^k n_i cách hoàn thành công việc.

3. CHỈNH HỢP:

3.1. Định nghĩa:

Chỉnh hợp chập k của n phần tử (k \le n ) là một nhóm có thứ tự gồm k phần tử khác nhau được chọn từ n phần tử đã cho.

Thí dụ: cho ba phần tử 2,3,5. Các chỉnh hợp chập 2 của 3 phần tử đó là: 23, 25, 32, 35, 52, 53.

Như vậy từ n phần tử ta có thể tạo nên nhiều chỉnh hợp chập k khác nhau. Chỉnh hợp này khác chỉnh hợp kia hoặc bởi có ít nhất một phần tử khác nhau hoặc chỉ do thứ tự  sắp xếp.

Số chỉnh hợp chập k của n phần tử được ký hiệu là: A_n^k

3.22. Công thức tính:

A_n^k = \dfrac{n!}{(n-k)!} (1.1)

Trong đó: n! = n(n -1)(n -2) … 2.1 ; 0! = 1

3.3 Thí dụ: Mỗi lớp phải học 6 môn, mỗi ngày học 2 môn. Hỏi có bao nhiêu cách xếp thời khóa biểu trong mỗi ngày.

Giải: Vì mỗi cách xếp thời khóa biểu trong một ngày là việc ghép 2 môn trong số 6 môn học. Các cách này do ít nhất 1 môn khác nhau hoặc chỉ do thứ tự sắp xếp trước sau giữa hai môn. Vì thế mỗi cách sắp xếp ứng với một chỉnh hợp chập 2 từ 6 phần tử.

Do đó có tất cả: A_6^2 = \dfrac{6!}{(6-2)!} = 30 cách

4. CHỈNH HỢP LẶP:

4.1 – Định nghĩa:

Chỉnh hợp lặp chập k của n phần tử là một nhóm có thứ tự gồm k phần tử lấy từ n phần tử đã cho, trong đó mỗi phần tử có thể có mặt 1, 2, …, k lần trong nhóm tạo thành.

Vì mỗi phần tử có thể xuất hiện nhiều lần trong một chỉnh hợp lặp, nên k có thể lớn hơn n. Chẳng hạn cho ba phần tử 2, 3, 5. Các chỉnh hợp lặp chập 2 của ba phần tử sẽ là:

22 23 25

32 33 35

52 53 55

Số chỉnh lặp chập k của n phần tử được ký hiệu là: \overline{A}_n^k

4.2 – Công thức tính:

Ta thành lập công thức tổng quát để tính \overline{A}_n^k . Muốn vậy ta lập luận như sau: để có một chỉnh hợp lặp chập k ta có thể chọn phần tử thứ nhất theo n cách. Phần tử thứ hai cũng có n cách chọn … phần tử thứ k cũng có n cách chọn ( vì mỗi phần tử có thể chọn lại nhiều lần). Vì vậy theo quy tắc nhân ta có: n . n … n = cách thành lập một chỉnh hợp lặp chập h khác nhau từ n phần tử đã cho.

Do đó: \overline{A}_n^k = n^k (1.3)

4.3 Thí dụ: Để đăng ký mỗi loại máy mới người ta dùng 3 con số trong 9 con số 1 … 2 … 9. Hỏi có thể đánh số được bao nhiêu máy.

Giải: Ở đây mỗi số của máy là một chỉnh hợp lặp chập 3 từ 9 phần tử đã cho. Vậy có thể đánh số được: \overline{A}_9^3 = 9^3 = 729 máy.

5. HOÁN VỊ:

5.1 – Định nghĩa:

Hoán vị của n phần tử là một nhóm có thứ tự gồm đủ mặt n phần tử đã cho.

Số hoán vị của n phần tử được ký hiệu là P_n

5.2 – Công thức tính:

Theo định nghĩa ta thấy các hoán vị của n phần tử chỉ khác nhau bởi thứ tự sắp xếp giữa các phần tử mà thôi. Một hoán vị của n phần tử cũng chính là một chỉnh hợp chập n của n phần tử. Do đó:
P_n = A_n^n = \dfrac{n!}{(n-n)!}= \dfrac{n!}{0!} = n!

Vậy P_n = n! (1.4)

5.3 Thí dụ: Một bàn có 4 học sinh ngồi. Hỏi có bao nhiêu cách xếp chỗ ngồi?

Ta thấy mỗi cách xếp chỗ cho 4 học sinh là một hoán vị của 4 phần tử. Do đó số cách sắp xếp là: P_4 = 4! = 24 cách

6. TỔ HỢP:

6.1 – Định nghĩa:

Tổ chập k của n phần tử (k \le n ) là một nhóm không phân biệt thứ tự gồm k phần tử khác nhau chọn từ n phần tử  đã cho.

Số tổ hợp chập k của n phần tử được ký hiệu là C_n^k

6.2 – Công thức tính:

Từ  định nghĩa tổ hợp ta thấy tổ hợp cũng chính là một chỉnh hợp (không lặp). Nhưng các chỉnh hợp nếu chỉ khác nhau về thứ tự  sắp xếp của các phần tử được coi như cùng một tổ hợp mà thôi.

Giả sử từ n phần tử ta có thể thành lập C_n^k tổ hợp chập k khác nhau. Ta đem hoán vị các phần tử trong các tổ hợp này thì mỗi tổ hợp sẽ tạo ra k! chỉnh hợp, mà ta có tất cả C_n^k tổ hợp. Vậy ta có đẳng thức:

C_n^kk! = A_n^k \Rightarrow C_n^k = \dfrac{A_n^k}{k!}= \dfrac{n!}{k!(n-k)!}

6.3 Thí dụ: Có mười đội bóng đá thi đấu với nhau theo thể thức vòng tròn một lượt (tức hai đội bất kỳ trong mười đội bóng này phải thi đấu với nhau một trận). Hỏi phải tổ chức bao nhiêu trận đấu.

Giải: Ta thấy mỗi trận đấu giữa hai đội bóng là một tổ hợp chập 2 của 10 phần tử (vì hai đội thi đấu với nhau thì không cần phân biệt thứ tự). Do đó số trận đấu cần tổ chức là: C_{10}^2 = \dfrac{10!}{2!(10-2)!} = \dfrac{10!}{2!8!} = \dfrac{9.10}{2} = 45

6.4 – Các tính chất của tổ hợp:

1) C_n^k = C_n^{n-k}
Chứng minh: C_n^{n-k} = \dfrac{n!}{(n-k)![n-(n-k)]!} = \dfrac{n!}{(n-k)!k!} = C_n^k
2) C_n^k = C_{n-1}^k + C_{n-1}^{k-1}
3) C_n^0 = 1 ; C_n^n = 1 ; C_n^1 = n

7. CÔNG THỨC NHỊ THỨC NEWTON:

Nhị thức Newton là lũy thừa bậc nguyên dương của tổng hai số hạng (a+b)^n trong đó a, b là hằng số thực tùy ý, n = 1, 2, 3, …

(a+b)^n = C_n^0a^n + C_n^1a^{n-1}b + ... + C_n^{n-1}ab^{n-1} + C_n^nb^n

\Rightarrow (a+b)^n = \sum\limits_{k=0}^nC_n^ka^{n-k}b^k

57 responses to “Bổ túc về Giải tích Tổ hợp

  1. thay oi cho em hoi cach giai bai toan nay voi ah.!
    Một thùng chứa 10 quả bóng màu xanh và 10 quả bóng màu đỏ. Phải lấy ngẫu nhiên ít nhất bao nhiêu quả bóng để bảo đảm có 3 quả bóng cùng màu ?
    em van chua hieu ro theo nguyenly dirichlet thi cai nao la chuong cai nao la chim ah.mong thay giup em

    • Giả sử lần đầu em lấy là màu xanh, lần thứ 2 em lấy cũng màu xanh; lần 3 em lấy màu xanh thì tốt, nhưng lần 3 em lấy màu đỏ thì chưa được. Vậy lần thứ 3 cũng chưa chắc chắn. Lần 4 em cũng lấy màu đỏ thì cũng chưa được. Vậy lần thứ 4 cũng chưa chắc chắn. Nhưng sau lần 4, em đã có 2 bóng màu xanh, 2 bóng màu đỏ. Do đó, chắc chắn lấy 1 lần nữa, bất kể là màu gì, em cũng sẽ có 3 quả bóng cùng màu. Vậy lần thứ 5 là chắc chắn.
      Vậy màu là chuồng và bóng là chim.
      Bài toán tổng quát: có 2 loại đũa, cần lấy ít nhất bao nhiêu chiếc để được n đôi đũa.

  2. Cho em hỏi cách giải bài toán này:
    1, cho n là số nguyên dương . CMR ∑C(k,n)=2^n
    2, cho n là số nguyên dương . CMR ∑(-1)^k.C(k,n)=0

    • Thường những dạng toán này em sẽ sử dụng công thức khai triển của (1+x)^n
      1. Ứng với x = 1.
      2. Ứng với x = -1
      Trường hợp tổng quát: (a+x)^n ; (1+ax)^n và các phép toán lấy đạo hàm, tích phân của công thức khai triển.

  3. Cho em hỏi công thức của bài này
    1.Bài toán xếp khách (Lucas)
    Bài toán: Một bàn tròn có 2n ghế. Cần sắp xếp n cặp vợ chồng vào bàn tròn sao cho đàn ông ngồi xen kẽ với đàn bà và không có cặp vợ chồng nào ngồi cạnh nhau (có tính đến vị trí ghế và thứ tự chỗ ngồi). Hỏi có bao nhiêu cách xếp?
    2. Hoán vị có lặp
    3. Tổ hợp lặp chập k

  4. giai thich cho em bai nay voi a!

    Cho các chữ số 0,2,3,4,6,7,9. Có bao nhiêu số có 5 chữ số thỏa mãn.
    a, các chữ số khác nhau
    b, số đó là chẵn và các chữ số khác nhau
    c, số đó là lẻ và các số khác nhau
    d, số đó là một số đối xứng
    mong giúp em càng sớm càng tốt ạ! cau d em k hieu gi a

    • Gọi số có 5 chữ số là: \overline{a_1a_2a_3a_4a_5} (a_1 \ne 0 )
      Bây giờ, ta chọn các số a_i thỏa các điều kiện đã cho, với quy tắc, chữ số nào có điều kiện thì chọn trước.
      a. Các chữ số khác nhau.
      a_1 \ne 0 : 6 cách , a_2 \ne a_1: 6 cách (khác a_1), a_3 : 5 cách , a_4 : 4 cách , a_5: 3 cách
      Vậy có: 6.6.5.4.3 = 2160 (cách)
      b. Chữ số chẵn: a_5 phải là 1 trong các số: 0, 2, 4, 6
      Th1: a_5 = 0 : 1 cách, a_1: 6 cách (chỉ cần khác a5), a_2: 5 cách, a_3 : 4 cách, a_4: 3 cách
      Có: 1.6.5.4.3 = 360 (cách)
      Th2: a_5 \ne 0 : a_5: 3 cách, a_1: 5 cách $ (khác 0 và khác a5) a_2: 5 cách, a_3 : 4 cách, a_4: 3 cách
      Có: 3.5.5.4.3 = 900 (cách)
      Vậy có: 360 + 900 = 1260 (cách)
      c. a_5: 3 cách, a_1: 5 cách, a_2: 5 cách, a_3 : 4 cách, a_4: 3 cách
      d. số đó là 1 số đối xứng thì a_1 = a_5, a_2 = a_4
      Vậy a_1: 6 cách (khác 0) , a_5: 1 cách (bằng a1), a_2: 6 cách, a_4: 1 cách, a_3: 5 cách
      vậy có: 6.6.5 = 180 (cách)

  5. thay giai dum em bai nay ha.
    có mấy cách xếp 5 người đứng thành hàng ngang sao cho A không đứng cạnh B.
    e co xem đáp an la 108 nhưng e không hiêu tai sao.

    • Có thể là đáp án in nhầm đó em.
      Cách 1:
      A,B có điều kiện nên ta sẽ sắp xếp trước.
      A ở vị trí 1: xếp
      B không đứng cạnh A thì B không ở vị trí thứ 2. Suy ra có 3 cách xếp. (3, 4 hoặc 5)
      Xếp 3 người còn lại vào 3 vị trí. Có 3! cách.
      A ở vị trí 5: 1 cách xếp
      B không đứng cạnh A thì B không ở vị trí thứ 4. Suy ra có 3 cách xếp. (1, 2 hoặc 3)
      Xếp 3 người còn lại vào 3 vị trí. Có 3! cách.
      A ở vị trí 2:
      B không đứng cạnh A thì B không ở vị trí 1 hoặc 3. Suy ra có 2 cách xếp (4 hoặc 5)
      Xếp 3 người còn lại vào 3 vị trí. Có 3! cách.
      tương tự cho vị trí 3 và 4.
      Vậy có: 1 x 3 x 6 + 1 x 3 x 6 + 1 x 2 x 6 + 1 x 2 x 6 + 1 x 2 x 6 = 72 cách.
      Cách 2:
      Số cách xếp 5 người vào 5 vị trí: 5! = 120 (cách)
      Số cách xếp A, B đứng cạnh nhau. {1,2}, {2,3}, {3,4}, (4,5}: 4 cách
      Hoán đổi vị trí của A, B: 2 cách
      Xếp 3 người vào 3 vị trí còn lại: 3! = 6 cách
      Vậy số cách A, B không đứng cạnh nhau: 120 – 4 x 2 x 6 = 72 cách.

  6. còn 1 cách nữa bạn à:
    Đầu tiên ,sx 5 người, tất cả có 5! = 120 (cách)
    Sau đó, cho A đứng cạnh B, ta coi thành có 4 người (A,B cạnh nhau coi là 1 người), ta có : 2 x4! = 24 (cách) ( hoán đổi vị trí A và B nên phải nhân thêm 2)
    Cuối cùng, số cách A,B ko cạnh nhau là : 120 – 48 =72 cách

  7. Thầy cho em hỏi với: Thầy giáo có 3 quyển sách khác nhau, cho 3 bạn mượn vào 3 ngày khác nhau. Hỏi có bao nhiêu cách cho 3 bạn mượn sao cho không bạn nào phải đọc lại cuốn sách đã mượn trước. Đáp số là 2 mà em thấy chỉ liệt kê ra cũng được 3 cách rồi

  8. Thưa thầy, cảm ơn thầy đã giúp em. Hôm nay em muốn hỏi thầy bài toán này ạ, em làm mà không ra.
    Cho đa giác đều A1, A2…..A2n (n>= 2, n nguyên) nội tiếp đường tròn (0). Biết rằng số tam giác có các đỉnh là 3 trng 2n điểm A1, A2….A2n nhiều gấp 20 lần số hình chữ nhậtcó các đỉnh là 4 trong 2n điểm A1, A2….A2n. Tìm n.
    em nghĩ thế này không biết có đúng không nữa:
    Số tam giác được tạo tự 3 đỉnh là tổ hợp chập 3 của 2n: (*)
    Số HCn được tạo từ 4 đỉnh là tổ hợp chập 4 của 2n: (**)
    Theo bài ra thì (*)=20 (**). Thầy cho em một cách giải với ạ. Cảm ơn thầy

    • Rất tiếc là em nghĩ chưa chính xác. Số HCN không thể là tổ hợp chập 4 của 2n được. Nếu em chọn như thế thì mới là chọn 4 đỉnh bất kỳ, và tứ giác tạo bởi 4 đỉnh bất kỳ chưa chắc là HCN.
      Ví dụ: với hình lục giác đều, nếu em chọn 4 đỉnh liền nhau thì không thể tạo thành HCN được.
      Để giải bài này, em chú ý tính chất đối xứng của đa giác đều sau:
      Nếu đa giác đều có 2n đỉnh nội tiếp đường tròn tâm O thì đỉnh thứ i và đỉnh thứ n+i đối xứng nhau qua tâm O. Như vậy, đa giác đều có 2n đỉnh sẽ có n đường chéo.
      Ngoài ra nếu HCN ABCD nội tiếp đường tròn tâm O thì đường chéo AC và BD phải cắt nhau tại tâm O.
      Như vậy, để chọn HCN thì thay vì chọn đỉnh, em sẽ chọn 2 đường chéo bất kỳ của đa giác đều. Số HCN sẽ là: nC2.
      Vậy 2nC3 = 20*(nC2). Suy ra: n = 8

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s