Hoán vị tròn


Định nghĩa. Cho A là một tập có n phần tử(n\in\mathbb{N}) và 1\leq r\leq n là một số nguyên. Một r-hoán vị tròn của A là một cách xếp r phần tử nào đó của A lên một đường tròn, hai cách xếp được coi là như nhau nếu chúng sai khác nhau một phép quay. Một n-hoán vị tròn của A sẽ gọi đơn giản là một hoán vị tròn của A.

Số hoán vị tròn. Cho A là một tập có n phần tử(n\in\mathbb{N}) và 1\leq r\leq n là một số nguyên. Khi đó số các r-hoán vị tròn của A bằng Q_n^r=\dfrac{A_n^r}{r}. Nói riêng, số các hoán vị tròn của A bằng Q_n^n=(n-1)!.

Chứng minh. Ta sẽ dùng nguyên lý chia để chứng minh công thức này.

Nguyên lý chia. Nếu tập An phần tử được phân hoạch thành các tập hợp có k phần tử thì số khối của phân hoạch bằng \dfrac{n}{k}.

Tập các r-hoán vị tuyến tính có thể phân hoạch thành các phần nhỏ sao cho hai hoán vị tuyến tính thuộc cùng một phần nếu chúng xác định cùng một hoán vị tròn. Vì số các hoán vị tuyến tính trong mỗi phần bằng r nên số các hoán vị tròn bằng Q_n^r=\dfrac{A_n^r}{r}\Box.

Ví dụ 3.1. Có bao nhiêu cách để 5 bé trai và 3 bé gái ngồi quanh một bàn tròn nếu

a)Không có thêm điều kiện gì?

b)Bé trai T_1 và bé gái G_1 không ngồi cạnh nhau?

c)Không có bé gái nào ngồi cạnh nhau?

Đáp số. a)Q_8^8.

b)6!\times 5.

c)4!\times 5\times 4\times 3\Box.

Ví dụ 3.2. Tìm số cách xếp n cặp vợ chồng ngồi quanh một bàn tròn sao cho

a)Đàn ông và đàn bà ngồi xen kẽ nhau;

b)Mỗi người đàn bà ngồi cạnh chồng của cô ấy.

Hướng dẫn. a)Chọn chỗ cho đàn ông trước sau đó đến đàn bà, đáp số (n-1)!\times n!.

b)Coi một cặp là một người, xếp n người này, và sau đó xếp vị trí vợ-chồng, đáp số (n-1)!\times 2^n\Box.

Ví dụ 3.3. Người ta định xếp 6 cậu bé và 5 cô bé ngồi xung quanh một cái bàn. Tìm số cách xếp nếu

a)Không có thêm điều kiện gì;

b)Không có hai cô bé nào ngồi cạnh nhau;

c)Tất cả các cô bé ngồi liền nhau;

d)Cô bé G ngồi cạnh hai cậu bé T_1,T_2.

Đáp số. a)10!.

b)5!\times A_6^5.

c)6!\times 5!.

d)2\times 8!\Box.

Ví dụ 3.4. Cho n,k là các số nguyên dương. Chứng minh rằng có \dfrac{(kn)!}{n^k} cách xếp kn người ngồi xung quanh k cái bàn khác nhau sau cho mỗi bàn có n người.

Hướng dẫn. Chọn một n-hoán vị tròn xếp vào bàn 1, sau đó bàn 2,…\Box.