Cách giải bài toán có số đứng cạnh nhau

Gọi số phải tìm là Mn. Xếp cho các bà trước(cứ xếp một ghế thì một ghế để trống dành cho các ông), số cách xếp cho các bà là 2n! cách. Gọi số cách xếp cho các ông ứng với một cách xếp các bà là Un ta được số cách xếp là:

Mn= 2n! x Un.

Vấn đề còn lại là tính số Un. Đánh số các bà (đã xếp) từ 1đến n,đánh số các ông tương ứng với các bà (ông i là chồng bà i), sau đó đánh số các ghế trống theo nguyên tắc: ghế số i nằm giữa bà i và bà i+1 (các phép cộng được hiểu lấy modul n nghĩa là n +1 = 1). Mỗi cách xếp các ông được biểu diễn bằng một phép thế ϕ trên tập {1, 2,.., n } với qui ước ϕ(i) = j có nghĩa là ghế i được xếp cho ông j. Theo giả thiết ϕ phải thoả mãn:

ϕ(i)≠i và ϕ(i) ≠ i+1 (**)

Như vậy, Un là số tất cả các phép thế ϕ thoả mãn điều kiện (**). Trong toán học gọi Un là số phân bố .

Xét tập hợp tất cả các phép thế ϕ của { 1, 2,.., n }. Trên tập này ta gọi Pi là tính chất ϕ(i) = i, Qi là tính chất ϕ(i) = i+1. Đặt Pn+i= Qi, theo nguyên lý bù trừ tương ứng với 2n tính chất Pi ta có:

[You must be registered and logged in to see this image.]

Trong đó Nk là tổng số tất cả các phép thế thoả mãn k tính chất lấy từ 2n tính chất đang xét. Cần chú ý rằng, không thể xảy ra đồng thời thoả mãn Pi và Qi hoặc đồng thời thoả mãn Pi+1và Qi. Do đó trong các phép lấy ra k tính chất từ 2n tính chất đang xét cần thêm vào điều kiện: Pi và Qi hoặc Pi+1 và Qi không được đồng thời có mặt.

Gọi số các cách này là g(2n, k) (nói riêng g(2n,k) = 0 khi k > n). Với mỗi cách lấy ra k tính chất như vậy (k ≤ n) ta có (n - k)! phép thế thoả mãn chúng. Từ đó ta nhận được:

Nk = g(2n, k) (n-k)! và: Un = n! - g(2n, 1).(n - 1)! + g(2n, 2).(n - 2)! -...+(-1)ng(2n, n) (***)

Bây giờ chúng ta phải tính các hệ số g(2n,k), k = 1, 2,.., n. Xếp 2n tính chất đang xét trên vòng tròn theo thứ tự P1, Q1, P2, Q2,.., Pn, Qn, ta thấy rằng g(2n,k) chính là số cách lấy k phần tử trong 2n phần tử xếp thành vòng tròn sao cho không có hai phần tử nào kề nhau cùng được lấy ra. Để tính g(2n,k) ta áp dụng

Bài viết hướng dẫn phương pháp giải bài toán đếm trong chủ đề hoán vị – chỉnh hợp – tổ hợp, bao gồm bài toán đếm số, bài toán xếp đồ vật, bài toán phân chia công việc, bài toán đếm liên quan đến hình học.

Phương pháp: Dựa vào quy tắc cộng, quy tắc nhân và các khái niệm hoán vị, chỉnh hợp, tổ hợp.

Một số dấu hiệu giúp chúng ta nhận biết được hoán vị, chỉnh hợp hay tổ hợp. 1. Hoán vị: Các dấu hiệu đặc trưng để giúp ta nhận dạng một hoán vị của $n$ phần tử là: • Tất cả $n$ phần tử đều phải có mặt. • Mỗi phần tử xuất hiện một lần. • Có thứ tự giữa các phần tử. 2. Chỉnh hợp: Ta sẽ sử dụng khái niệm chỉnh hợp khi: • Cần chọn $k$ phần tử từ $n$ phần tử, mỗi phần tử xuất hiện một lần. • $k$ phần tử đã cho được sắp xếp thứ tự. 3. Tổ hợp: Ta sử dụng khái niệm tổ hợp khi: • Cần chọn $k$ phần tử từ $n$ phần tử, mỗi phần tử xuất hiện một lần. • Không quan tâm đến thứ tự $k$ phần tử đã chọn.

Các dạng toán thường gặp và ví dụ minh họa Dạng toán 1. Bài toán đếm số Ví dụ 1. Từ các chữ số $0, 1, 2, 3, 4, 5, 6$ có thể lập được bao nhiêu số chẵn, mỗi số có $5$ chữ số khác nhau trong đó có đúng hai chữ số lẻ và $2$ chữ số lẻ đứng cạnh nhau?

Gọi$A$ là số tự nhiên có hai chữ số lẻ khác nhau lấy từ các số $0, 1, 2, 3, 4, 5, 6.$ Số cách chọn được $A$ là $A_{3}^{{2}=6$. Số chẵn có $5$ chữ số khác nhau, trong đó có đúng hai chữ số lẻ và $2$ chữ số lẻ đứng cạnh nhau phải chứa $A$ và ba trong $4$ chữ số $0, 2, 4, 6.$ Gọi $\overline{abcd}$ $(a, b, c, d \in \{ A,0,2,4,6\})$ là số thỏa mãn yêu cầu bài toán. • Trường hợp 1: Nếu $a=A$ thì có $1$ cách chọn $a$ và $A_{4}}{3}$ cách chọn $b, c, d$. • Trường hợp 2: Nếu $a \ne A$ thi có $3$ cách chọn $a.$ + Nếu $b=A$ có $1$ cách chọn $b$ và $A_{3}^{{2}$ cách chọn $c,d$. + Nếu $c=A$ có $1$ cách chọn $c$ và $A_{3}}{2}$ cách chọn $b,d$.

Vậy có $A_{3}^{{2}\left( A_{4}}{3}+3\left( 1.A_{3}^{2}+1.A_{3}{2} \right) \right)=360$ số thỏa mãn yêu cầu bài toán.

- Trong mỗi trường hợp áp dụng quy tắc nhân và dùng quy tắc cộng để cộng các trường hợp lại với nhau.

Lời giải chi tiết:

Các chữ số có 5 chữ số khác nhau lâp từ tập A là 6.6.5.4.3 = 2160 số \( \Rightarrow {n_\Omega } = 2160.\)

Gọi sô cần tìm là \(\overline {abcde} \) ta có e = 0 hoặc e = 5 (do số đó phải chia hết cho 5)

+) e = 0. Chọn vị trí cho 3 số 1, 2, 3 có 2 cách chọn, ngoài ra trong ba số 1, 2, 3 còn có 3! = 6 hoán vị trong đó. Cuối cùng ta chọn số còn lại có 3 cách chọn. Vậy số các số thuộc trường hợp này là: 2.6.3 = 36 số.

+) e = 5 và 1, 2, 3\( \in bcd\), ba số này có 3! = 6 hoán vị. Vì \(a \ne 0\) nên a có 2 cách chọn. Vậy trong trường hợp này có 6.2 = 12 số.

+) e = 5 và 1, 2, 3 \( \in abc\), ba số này có 3! = 6 hoán vị. Số cách chọn d là 3 cách. Vậy trong trường hợp này có 6.3 = 18 số.

Gọi A là biến cố: “Số tự nhiên gồm 5 chữ số khác nhau sao cho số đó chia hết cho 5 và các chữ số 1, 2, 3 luôn có mặt đứng cạnh nhau” thì \({n_A} = \) 36 + 12 + 18 = 66.

Vậy xác suất cần tìm là \(P\left( A \right) = {{{n_A}} \over {{n_\Omega }}} = {{66} \over {2160}} = {{11} \over {360}}.\)