多限相鄰排列問題初步探索

詹高娃

(華南師范大學數學科學學院，廣東廣州510631)

多限相鄰排列問題初步探索

詹高娃

(華南師范大學數學科學學院，廣東廣州510631)

本文研究限定相鄰元素的排列問題，由單組的限鄰問題推廣多組限鄰問題，并得到集合中若干個不相交子集之間的限鄰排列問題的解決辦法，其中多次用到容斥原理、集合的交并運算和歸納與猜想原理，并對定理進行了初步的推廣與應用.

限鄰排列；線性排列；圓排列

0 引言

比如我們日常生活中經常遇到的排座位問題，某幾個同學一定要相鄰而坐或某幾個同學一定不能相鄰而坐；夫妻做圓桌吃飯時需要夫妻相鄰或分開坐等等.這些問題在涉及排列問題中經常遇到，但是解決這些問題的通法尚未有人總結.這是本文所要解決的主要問題.

定義1對多組元素分別進行限鄰控制然后排列在同一行（圈）的排列方式稱為多限鄰排列，即把要排列的n個元素組成的集合分為k個不相交的子集，其中每一個子集的元素要相鄰（或不相鄰）排列的排列方式.多限鄰排列可分為多限相鄰排列和多限不相鄰排列兩種情況.

例如，集合A={a1，a2，a3，a4，a5}，其中a1，a2，a3必須相鄰排列的排列，我們可以把集合A分為三個相交的集合{a1，a2，a3}，{a4}和{a5}，其中集合{a1，a2，a3}中元素全排列的方法數有3!種，{a4}中元素全排列的方法數有1!，{a5}中元素的全排列方法數為1!，所以集合A中{a1，a2，a3}相鄰排列的方法數為3！1！1！.

引理3 n個相異元素的圓全排列方法數為（n-1）！.

1 限鄰線性排列

1.1 限相鄰線性排列

設A={a1，a2，…，an}是一個n元集，易得集合A中a1，a2相鄰排列的排列方法數為2!（n-1）！，集合A中a1，a2，a3相鄰排列的排列方法數為3!（n-2）！；由歸納證明可知：集合A中a1，a2，…，ak（1≤k≤n）相鄰排列的排列方法數為L（n，k）=k!（n-k+1）!.

定理1設A={a1，a2，…，an}是一個n元集，其中，且，則集合A中的元素相鄰排列的方法數為.

證明：分析可知，本題可采用“捆綁法”解決，分三步走：第一步，對Ai（i=1，2，…，k）作全排列，其排列方法數為ri!（i=1，2，…，k）；第二步，對A1，A2，…，Ak這k個集合作全排列，其排列方法數為k!；第三步，利用乘法原則可知，集合A的排列方法數為.

推論1設A={a1，a2，…，an}是一個n元集，其中，且，則集合A中的元素相鄰排列的方法數為

例1設A，B，…，J這十位同學一起照相，要求A，B，C，D這四位同學相鄰站在一起，而且E，F，G這三位同學也要相鄰站在一起，請問：總共有多少種排列方法數？

分析：此題可參照定理1，把A，B，C，D這四位同學看成是一組，E，F，G這三位同學看成一組，再把剩下的三位同學分別看成三組，此題可理解為求五組元素相鄰排列的方法數.

1.2 限不相鄰線性排列

設A={a1，a2，…，an}是一個n元集，易得集合A中a1，a2不相鄰排列的排列方法數為；集合A中a1，a2，a3兩兩不相鄰排列的排列方法數為；由歸納證明可知：集合A中a1，a2，…，ak（1≤k≤n）兩兩不相鄰排列的排列方法數為.

定理2設A={a1，a2，…，an}是一個n元集，其中，，

證明：用S表示A的全排列之集，以Si（i=1，2，…，k）表示A中Ai（i=1，2，…，k）的元素全相鄰排列的全排列之集，依題意需要求.

推論2設A={a1，a2，…，an}是一個n元集，其中，且i，j∈1，2，…，k），，則集合A中Ai（i=1，2，…，k）元素不全相鄰排列的方法數為

例2設A，B，…，F這六位同學一起照相，要求A，B，C這三位同學不能全部相鄰站在一起，D，E，F這三位同學也不能全部相鄰站在一起，請問：總共有多少種排列方法數？

規定：沒有指明排列方式的排列默認為線性排列.

2 限鄰圓排列

2.1 限相鄰圓排列

設A={a1，a2，…，an}是一個n元集，易得集合A中a1，a2相鄰排列的圓排列方法數為2!（n-2）!；集合A中a1，a2，a3相鄰排列的圓排列方法數為3!（n-3）!；由歸納證明知，集合A中a1，a2，…，ak（1≤k≤n）相鄰排列的圓排列方法數為R（n，k）=k!（n-k）!.

定理3設A={a1，a2，…，an}是一個n元集，其中，且i，j∈1，2，…，k），，則集合A中Ai（i=1，2，…，k）的元素相鄰排列的圓排列方法數為

其證法與定理1類似.

推論3設A={a1，a2，…，an}是一個n元集，其中，且i，j∈1，2，…，k），，那么集合A中Ai（i=1，2，…，k）的元素相鄰排列的圓排列方法數為

例3設A，B，…，J這十位同學坐圓桌吃飯，要求A，B，C，D這四位同學相鄰坐在一起，而且E，F，G這三位同學也要相鄰坐在一起，請問：總共有多少種排列方法數？

2.2 限不相鄰圓排列

設A={a1，a2，…，an}是一個n元集，易得集合A中a1，a2不相鄰排列的圓排列方法數為；集合A中a1，a2，a3兩兩不相鄰的排列圓排列方法數為；由歸納證明知，集合A中a1，a2，…，ak（1≤k≤n）兩兩不相鄰排列的圓排列方法數為

定理4設A={a1，a2，…，an}是一個n元集，其中，且i，j∈1，2，…，k），，則集合A中Ai（i=1，2，…，k）的元素不全相鄰排列的圓排列方法數為

其證法與定理2類似.

推論4設A={a1，a2，…，an}是一個n元集，其中，且i，j∈1，2，…，k），，則集合A中Ai（i=1，2，…，k）的元素不全相鄰排列的圓排列方法數為

例4設三對夫妻坐圓桌吃飯，要求夫妻雙方不能坐在相鄰的位置，請問：總共有多少種排座位的方法數？

總結：本文只是考慮了相異元限鄰排列計數問題，該課題可由相異元推廣到可重復排列計數問題，也就是讓集合中元素可重復排列.

[1]曹汝成.組合數學[M].第二版.廣州：華南理工大學出版社，2012.

[2]潘承洞，潘承彪.初等數論[M].第三版.北京：北京大學出版社，2013.M ulti-Set of Lim it Adjacent Prelim inary Exploration

ZHAN Gaowa
（South China Normal University,Guangzhou，510631 Guangdong,China）

In this paper,the permutation problem of limit adjacent elements is studied. The single set of limit problem is extended to multi-set of limit problem by using inclusion-exclusion principle,collection of occurring simultaneously and principle of induction and conjecture frequently.A solution to deal with limit adjacent arrangement problems about collection of several disjoint subsets is achieved.Preliminary popularization and application of the theorem are also studied.

limit neighborhood adjacent；linear adjacent；round adjacent

O 157

A

1001-4217（2015）02-0034-05

2014-09-30

詹高娃（1992-），女，廣東饒平人，研究生競賽數學方向在讀.E-mail：2841254805@qq.com