Cộng đồng công nghệ

Giải tích tổ hợp (Combinatorics or Combinatorial analysis) là một ngành toán học về các phương pháp phân loại, sắp xếp và đếm.

A) Nguyên tắc tổng và tích (Rules of sum and product)

Nguyên tắc tổng

            Nếu mỗi sự kiện E_i có m_i cách xảy ra, thì có tổng các m_i cách để có đúng một trong những sự kiện Ei xảy ra

Ví dụ Có 8 con đường từ A đến B

            Có 12 con đường từ A đến C

            Có 8 + 12 con đường từ A đến B hoặc C

Nguyên tắc tích

            Nếu mỗi sự kiện E_i có m_i cách xảy ra, thì có tích m_i cách để tất cả các sự kiện E_i cùng xảy ra      

Ví dụ: 6 * 6 * 6 là kết quả khi gieo 3 con súc sắc

Một con súc sắc có thể ra 6 mặt, nếu 3 con súc sắc gieo đồng thời thì sẽ có 6*6*6 kết quả

Ví dụ: 9*10*10 số gồm 3 chữ số

B) Hoán vị (Permutation)

Định nghĩa   

      Một hoán vị của n vật phân biệt là một dãy theo thứ tự của n vật ấy

            Một r - hoán vị  của n vật phân biệt là một dãy theo thứ tự của r vật trong n vật

Định lý

      Số r - hoán vị của n vật phân biệt

                  P(n, r) = n(n-1)…(n-r+1) = n! / (n-r)!

      Số hoán vị của n vật phân biệt:

                  P(n, n) = n!

      Chứng minh

      Có n cách chọn vật cho vị trí 1

      Có n-1 cách chọn vật cho vị trí 2

      …

      Có n-r+1 cách chọn vật cho vị trí r

Dùng nguyên tắc tích => P(n, r) = n(n-1)…(n-r+1)

Ví dụ: Có bao nhiêu cách phân công 6 người làm 4 việc mà mỗi người chỉ làm một việc

            P(6, 4) = 6 * 5 * 4 * 3 = 360

Bởi vì có 6 cách chọn người cho việc 1, 5 cách chọn người cho việc 2, 4 cách chọn người cho việc 3, và 3 cách chọn người cho việc 4

Định lý

            Số r - hoán vị có lặp của n vật phân biệt là n^r

            Chứng minh

            Vì có lặp nên có n cách chọn vật cho bất kỳ vị trí nào

Ví dụ: Nếu mỗi người có thể làm 1, 2, 3 hay 4 việc thì số cách phân công là 6⁴

Ví dụ: Số dãy 8 bit là 2⁸

(Số 8-hoán vị của 2 vật 0,1)

Ví dụ: Có bao nhiêu cách xếp 10 người thành một hàng trong đó có 4 phụ nữ đứng liền nhau ?

Bởi vì có 7 cách xếp vị trí cho 4 phụ nữ liền nhau, có 6 cách xếp vị trí cho người thứ năm, có 5 cách xếp vị trí cho người thứ sáu, có 4 cách xếp vị trí cho người thứ bảy, có 3 cách xếp vị trí cho người thứ tám, có 2 cách xếp vị trí cho người thứ chín, có 1 cách xếp vị trí cho người thứ mười, vì vậy có 7! cách sắp xếp

Số hoán vị 4 phụ nữ là 4!

Dùng nguyên tắc tích => có tất cả 7! * 4! cách sắp xếp

Ví dụ: Có bao nhiêu cách xếp 9 người đứng thành hàng trong đó có 2 người đặc biệt không đứng liền nhau

            9! – 8! * 2!

 Ví dụ : Xếp thành vòng tròn

            (n-1) !

Định lý

Số hoán vị của n vật trong đó :

            n1 vật đầu là a1

            n2 vật đầu là a2

            …

            np vật đầu là ap

là n ! / (n1! n2! ... np !)

Ví dụ : Có bao nhiêu cách xếp m banh đỏ và n banh xanh trong 1 hàng

            (m+n) ! / (m! * n!)

Bởi vì số hoán vị các bi đỏ là m!, số hoán vị các bi xanh là n!, dùng nguyên tắc tích, số hoán vị các bi xanh và đỏ là m!*n!

Số hoán vị của m+n bi là (m+n)!

Ví dụ: Có bao nhiêu dãy 8 bít chứa 3 số 0

Dãy chứa 3 số 0, 5 số 1 => 8! /(3! 5!)

C) Tổ hợp (Combination)

Định nghĩa:Một r-tổ hợp của n vật phân biệt là một tập hợp gồm r vật trong n vật ấy (không kể thứ tự)

Định lý: Số r-tổ hợp của n vật là:

            C^r_n= P(n,r)/r! =n!/(r!(n-r)!)

Ví dụ:

Số dãy 8 bít chứa 3 số 0, xem như chọn 3 vị trí trong 8 vị trí cho số 0

            C³₈ = 8!/ (3!(8-3)!) = 8! / (3! 5!)

Số cách chọn trong số 6 câu hỏi, cho 2 phần, trong đó mỗi phần có ít nhất 2 câu.

Phương án                  Số câu hỏi trong phần 1                  Số câu hỏi trong phần 2

1                                  2                                                          4                                             

2                                  3                                                          3

3                                  4                                                          2

            C²₆ C⁴₄ + C³₆ C³₃ + C⁴₆ C²₂

Định lý:

          C^r_n = C^r_n-1 + C^r-1_n-1

D) Tổ hợp có lặp (Combination with Repetition)

Định lý: Số r-tổ hợp có lặp từ n vật

            C^r_n-1+r  = (n-1+r)! / (r! (n-1)!)

Ví dụ: Có bao nhiêu cách mua 6 tô phở trong 4 loại phở gà, tái, gân, tái nạm

            C⁶_4-1+6 = C⁶₉  = 9! / (6! 3!) = 84

Ví dụ: Có bao nhiêu cách tạo đĩa trái cây chứa 4 quả trong 3 loại: cam, xoài, lê

Ví dụ: Có bao nhiêu cách chọn 5 tờ bạc trong các loại giấy bạc 200, 500, 1000, 2000, 5000, 10000, 50000?