Privacy Policy Cookie Policy Terms and Conditions Toán học tổ hợp – Wikipedia tiếng Việt

Toán học tổ hợp

Bách khoa toàn thư mở Wikipedia

Toán học tổ hợp (hay giải tích tổ hợp, đại số tổ hợp, lý thuyết tổ hợp) là một ngành toán học rời rạc, nghiên cứu về các cấu hình kết hợp các phần tử của một tập hữu hạn phần tử. Các cấu hình đó là các hoán vị, chỉnh hợp, tổ hợp,... các phần tử của một tập hợp.

Mục lục

[sửa] Các bài toán cơ bản

  1. Bài toán đếm: Đếm các cấu hình thỏa mãn nhứng tính chất nào đó
  2. Bài toán liệt kê tổ hợp: Liệt kê tất cả các cấu hình thỏa mãn một tính chất nào đó
  3. Bài toán tìm kiếm: Tìm kiếm một hoặc một số cấu hình thỏa mãn một tính chất nào đó
  4. Bài toán tồn tại: Chỉ ra sự tồn tại/không tồn tại một cấu hình tổ hợp thoả mãn một tính chất nào đó
  5. Bài toán sinh ngẫu nhiên

[sửa] Một số cấu hình chính

Cho tập hữu hạn gồm n phần tử A ={a1,a2,...,an}

  • Chỉnh hợp lặp chập k của n phần tử đó là một bộ sắp thứ tự k phần tử của A, các phần tử có thể lấy lặp lại.
  • Chỉnh hợp (không lặp) chập k (0\le k \le n) của n phần tử đó là một bộ sắp thứ tự k phần tử của A, các phần tử đôi một khác nhau.
  • Hoán vị của n phần tử đã cho là một cách sắp xếp các phần tử của nó trên đường thẳng.
  • Hoán vị vòng quanh của n phần tử đã cho là một cách sắp xếp các phần tử của nó trên đường tròn.
  • Tổ hợp chập k các phần tử của A (0\le k \le n)là một tâp con k phần tử (0<=k<=n) của tập A.
  • Chỉnh hợp lặp với tần số cho trước k1,k2,...,kn là chỉnh hợp lăp chập k với k = k1 + k2 + ... + kn trong đó a1 xuất hiện đúng k1 lần, a2 xuất hiện k2 lần, an xuất hiên kn lần.
  • Tổ hợp bội hay tổ hợp lặp chập k các phần tử của một tập hợp n phần tử là một các lấy ra k lần (k \ge 0) các phần tử của một tập hợp, trong đó mỗi phần tử có thể lấy ra nhiều lần.
  • Ví dụ cho A = {1,2,3,4,5,6,7} và k = 5
    • Các chỉnh hợp lặp chập 5 của 7 phần tử có thể là: 24355, 11111, 22334, 43215,...
    • Các chỉnh hợp không lặp chập 5 của 6 như: 12345, 23456, 73241...
    • Các tổ hợp chập 5 như : {1,2,3,4,5}, {2,3,4,5,6}, {3,4,5,6,7}...
    • Chỉnh hợp lặp 22324557777 là chỉnh hợp lặp với tần số 0,3,1,1,2,0,4

[sửa] Một số công thức tính

  1. Công thức tính số các chỉnh hợp lặp chập k của n phần tử là F(n,k) = nk
  2. Công thức tính số các chỉnh hợp chập k của n phần tử làA(n,k)=\frac {n!}{(n-k)!}
  3. Công thức tính số các hoán vị của n phần tử là P(n) = n!
  4. Công thức tính số các hoán vị vòng quanh của n phần tử là Q(n) = (n − 1)!
  5. Công thức tính số các tổ hợp chập k của n phần tử làC(n,k)=\frac {n!}{k!(n-k)!}
  6. Công thức tính số các chỉnh hợp lặp của n phần tử với tần số k1,k2,...,kn\frac {k!}{k_1!*k_2!*..*k_n!} với k = k1! * k2! * .. * kn!
  7. Với n và k cho trước thì số các bộ tần số k1,k2,..,kn có thể có là C_{n+k-1}^{k-1}

[sửa] Bài toán liệt kê

[sửa] Thứ tự từ điển

Trong các bộ từ điển, các từ được liệt kê theo thứ tự được gọi là thứ tự từ điển. Cho hai từ dưới dạng xâu của các kí tự

x = x1x2...xm
y = y1y2...yn

Từ x được gọi là đứng trước từ y theo thứ tự từ điển nếu tồn tại chỉ số i, 1 \le i\le min \{m,\,n\} sao cho

\forall j\le i\,:\, x_j =y_j
xj + 1 đứng trước yj + 1

Chú ý: Nếu j>m thì ta coi xj là kí tự rỗng, tương tự nếu j>n thì coi yj là kí tự rỗng, kí tự rỗng đứng trươc mọi kí tự khác.

[sửa] Liệt kê các hoán vị của tập n phần tử

Việc liệt kê toàn bộ các hoán vị của tập X = {x1,x2,...,xm} được quy về việc liệt kê tất cả n! hoán vị của tập chỉ số {1,2,...,n}. Ta sẽ liệt kê các hoán vị của n số tự nhiên {1,2,...,n} theo thứ tự từ điển. Nhận xét rằng, khi xếp theo thứ tự từ điển, hoán vị đứng trước tiên sẽ là hoán vị (1,2,3,...,n − 1,n), hoán vị đứng cuối cùng sẽ là hoán vị (n,n − 1,...,2,1). Ví dụ với n=5, hoán vị đứng đầu là (1,2,3,4,5), đứng cuối là (5,4,3,2,1). Trong hoán vị đầu tiên mỗi số đều nhỏ hơn số đứng ngay sau nó, trong hoán vị cuối cùng thì ngược lại. Vậy kế tiếp sau hoán vị đầu tiên là hoán vị nào?

[sửa] Hoán vị kế tiếp của một hoán vị (theo thứ tự từ điển)

Giả sử có hoán vị

x = (x1,x2,...,xn − 1,xn) của n số 1,2,...,n.
  • Thuật toán sinh hoán vị kế tiếp
    1. Tìm từ bên phải sang chỉ số i sao cho xi − 1 < xi.
    2. Nếu không tìm thấy thì trả lời x là hoán vị cuối cùng, không có hoán vị kế tiếp.
    3. Nếu có i như vậy:
      • đổi chỗ xi − 1 cho phần tử nhỏ nhất trong các giá trị xi,...,xn và lớn hơn xj − 1
      • sắp xếp các giá trị xi,...,xn theo thứ tự tăng dần.

Ví dụ: với n=5

  • kế tiếp của hoán vị (1,2,3,4,5) là hoán vị (1,2,3,5,4)
  • kế tiếp của hoán vị (1,2,3,5,4) là hoán vị (1,2,4,3,5)
  • kế tiếp của hoán vị (1,2,4,3,5) là hoán vị (1,2,4,5,3)
...
  • kế tiếp của hoán vị (5,4,3,1,2) là hoán vị (5,4,3,2,1)

[sửa] Thuật toán liệt kê tất cả các hoán vị của n số 1,2,...,n

  1. Khới tạo: x = (1,2,...,n)
  2. Tìm x' là hoán vị kế tiếp của x
  3. Nếu không tìm được thì dừng.
  4. Nếu thấy,thay x bằng x' quay lại 2.

Ví dụ: Liệt kê 24 hoán vị của 1,2,3,4 theo thứ tự từ điển

1234, 1243, 1324, 1342, 1423, 1432,
2134, 2143, 2314, 2341, 2413, 2431,
3124, 3142, 3214, 3241, 3412, 3421,
4123, 4132, 4213, 4231, 4312, 4321.

[sửa] Liệt kê các tổ hợp chập k của tập n phần tử

[sửa] Ví dụ

Cho tập A gồm 5 chữ số hệ thập phân A={1,2,3,4,5}

  1. Số các số tự nhiên 4 chữ số lập thành từ 5 chữ số trên là 54 = 625.
  2. Số các số tự nhiên gồm 3 chữ số khác nhau lập thành từ 5 chữ số trên là A_5^3= \frac {5!}{2!} = 60.
  3. Số các tập con 3 phần tử cua 5 chữ số trên là C_5^3=\frac {5!}{2!3!}=10.
  4. Số các hoán vị của 5 số đó là 5! = 120.
  5. Số các hoán vị vòng quanh là Q(n) = 4! = 24.
  6. Số các hoán vị khác nhau có thể có khi hoán vị các chữ cái trong từ XAXAM là \frac {5!} {2!2!1!} =30.
  7. Số cách chia 7 chiếc kẹo cho 4 trẻ em là C_{7+4-1}^3=\frac {10!} {3!7!}=120.

Static Wikipedia (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Static Wikipedia 2007 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu -

Static Wikipedia 2006 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu

Static Wikipedia February 2008 (no images)

aa - ab - af - ak - als - am - an - ang - ar - arc - as - ast - av - ay - az - ba - bar - bat_smg - bcl - be - be_x_old - bg - bh - bi - bm - bn - bo - bpy - br - bs - bug - bxr - ca - cbk_zam - cdo - ce - ceb - ch - cho - chr - chy - co - cr - crh - cs - csb - cu - cv - cy - da - de - diq - dsb - dv - dz - ee - el - eml - en - eo - es - et - eu - ext - fa - ff - fi - fiu_vro - fj - fo - fr - frp - fur - fy - ga - gan - gd - gl - glk - gn - got - gu - gv - ha - hak - haw - he - hi - hif - ho - hr - hsb - ht - hu - hy - hz - ia - id - ie - ig - ii - ik - ilo - io - is - it - iu - ja - jbo - jv - ka - kaa - kab - kg - ki - kj - kk - kl - km - kn - ko - kr - ks - ksh - ku - kv - kw - ky - la - lad - lb - lbe - lg - li - lij - lmo - ln - lo - lt - lv - map_bms - mdf - mg - mh - mi - mk - ml - mn - mo - mr - mt - mus - my - myv - mzn - na - nah - nap - nds - nds_nl - ne - new - ng - nl - nn - no - nov - nrm - nv - ny - oc - om - or - os - pa - pag - pam - pap - pdc - pi - pih - pl - pms - ps - pt - qu - quality - rm - rmy - rn - ro - roa_rup - roa_tara - ru - rw - sa - sah - sc - scn - sco - sd - se - sg - sh - si - simple - sk - sl - sm - sn - so - sr - srn - ss - st - stq - su - sv - sw - szl - ta - te - tet - tg - th - ti - tk - tl - tlh - tn - to - tpi - tr - ts - tt - tum - tw - ty - udm - ug - uk - ur - uz - ve - vec - vi - vls - vo - wa - war - wo - wuu - xal - xh - yi - yo - za - zea - zh - zh_classical - zh_min_nan - zh_yue - zu