Người ta trang trí một bảng ô vuông 4 x 4 (như hình 1) bởi các ngôi sao và các bông hoa giống nhau. Mỗi ô vuông nhỏ được dán một ngôi sao hoặc một bông hoa, sao cho trong mỗi hàng hoặc mỗi cột của bảng ô vuông đều có 2 ngôi sao và 2 bông hoa (tham khảo một cách dán trong hình 2). Có tất cả bao nhiêu cách trang trí bảng ô vuông thỏa mãn yêu cầu trên?
Coi mỗi ngôi sao tương ứng với số 1 và bông hoa tương ứng với số 0.
Bài toán quy về đếm số ma trận kích thước $4 \times 4$ chỉ gồm các chữ số 0 và 1 sao cho tổng mỗi hàng và mỗi cột đều bằng 2.
Sử dụng các mẫu hàng đối lập để phân chia trường hợp.
Một hàng của bảng có 4 ô, số cách chọn 2 ô dán ngôi sao là $C_{4}^{2} = 6$ cách.
Tương ứng với 6 cách này, ta có 6 mẫu hàng.
Chia 6 mẫu hàng này thành 3 cặp đối lập (tổng hai hàng trong một cặp là một hàng toàn ngôi sao, nghĩa là ngôi sao ở hàng này sẽ tương ứng với bông hoa ở hàng kia tại cùng một vị trí cột):
Cặp 1: (1, 1, 0, 0) và (0, 0, 1, 1).
Cặp 2: (1, 0, 1, 0) và (0, 1, 0, 1).
Cặp 3: (1, 0, 0, 1) và (0, 1, 1, 0).
Để tổng mỗi cột của bảng bằng 2, bốn hàng của bảng phải được tạo thành từ việc chọn ra hai cặp đối lập. Có hai trường hợp xảy ra:
Trường hợp 1: Bốn hàng được chọn từ cùng một cặp đối lập (mỗi mẫu hàng trong cặp xuất hiện 2 lần).
Số cách chọn một cặp từ 3 cặp: 3 cách.
Với mỗi cách chọn, số hoán vị của 4 hàng (trong đó có 2 cặp hàng giống nhau) là 6 cách.
Số cách cho trường hợp này: 3 . 6 = 18 cách.
Trường hợp 2: Bốn hàng được chọn từ hai cặp đối lập khác nhau (mỗi mẫu hàng trong hai cặp được chọn xuất hiện đúng 1 lần).
Số cách chọn hai cặp từ 3 cặp: $C_{3}^{2} = 3$ cách.
Với mỗi cách chọn, ta có 4 hàng đôi một khác nhau nên số hoán vị là: 4! = 24 cách.
Số cách cho trường hợp này: 3 . 24 = 72 cách.
Vậy có 18 + 72 = 90 cách trang trí thỏa mãn yêu cầu.
Danh sách bình luận