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.

4 thoughts on “Hoán vị tròn”

  1. thầy ơi thấy có thể giải thích thêm ví dụ 3.1 c không ạ?
    nếu em đánh số từ 1 đến 8 cho các vị trí, em chia các bạn 4 trong 5 nam trước vào các vị trí 1 3 5 7 thì có 5.4.3.2 cách, còn bạn còn lại có 4 cách các bạn nữ còn lại là 3!
    Em vẫn không hiểu lắm về dạng này, thầy giảng giúp em với ạ!

      1. Em chào thầy ạ!
        Sau khi đọc lại và tìm hiểu thêm thì em hiểu như thế này.
        Chia 5 bạn nam trước ta được 4! còn lại các vị trí thõa các bạn nam xen kẽ nữ là 5.4.3=5A3

        Có một cách làm của các bạn khác nhưng kết kết quả ra gấp đôi là 2880, các bạn làm như sau:
        Gọi S là tât cả các trường hợp có thể xảy ra
        A là các bạn nữ ngồi cạnh nhau
        B là các bạn nữ không ngồi cạnh nhau
        ta có S=A+B =>B=7!-3C2.6!=2880

        có bước trung gian là cách chia, cách nghĩ của em như sau:
        Ban đầu nếu cố định 1 nhóm 5 bạn theo thứ tự nam nữ nam nữ nam thì đối với nữ em có số cách chọn là : 3C2.2!, các bạn nam là là : 5C3.3!. Còn lại 3 vị trí em xếp theo nam nam nữ, nữ nam nam và nam nữ nam , em coi nam nam là một hoán vị vị trí là 2!, hoán vị vị trí giữa hai nam là 2!.
        Như vậy có đúng không ạ? Em có một câu hỏi là nếu em không coi nam nam là một thì em chia vị trí giữa hai nam, sau đó có 3 cách để chia vị trí của 3 bạn thì khác nhau như thế nào vậy ạ?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s