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

詹高娃

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

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

詹高娃

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

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

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

0 引言

比如我們?nèi)粘Ｉ钪薪?jīng)常遇到的排座位問題，某幾個(gè)同學(xué)一定要相鄰而坐或某幾個(gè)同學(xué)一定不能相鄰而坐；夫妻做圓桌吃飯時(shí)需要夫妻相鄰或分開坐等等.這些問題在涉及排列問題中經(jīng)常遇到，但是解決這些問題的通法尚未有人總結(jié).這是本文所要解決的主要問題.

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

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

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

1 限鄰線性排列

1.1 限相鄰線性排列

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

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

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

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

例1設(shè)A，B，…，J這十位同學(xué)一起照相，要求A，B，C，D這四位同學(xué)相鄰站在一起，而且E，F(xiàn)，G這三位同學(xué)也要相鄰站在一起，請(qǐng)問：總共有多少種排列方法數(shù)？

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

1.2 限不相鄰線性排列

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

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

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

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

例2設(shè)A，B，…，F(xiàn)這六位同學(xué)一起照相，要求A，B，C這三位同學(xué)不能全部相鄰站在一起，D，E，F(xiàn)這三位同學(xué)也不能全部相鄰站在一起，請(qǐng)問：總共有多少種排列方法數(shù)？

規(guī)定：沒有指明排列方式的排列默認(rèn)為線性排列.

2 限鄰圓排列

2.1 限相鄰圓排列

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

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

其證法與定理1類似.

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

例3設(shè)A，B，…，J這十位同學(xué)坐圓桌吃飯，要求A，B，C，D這四位同學(xué)相鄰坐在一起，而且E，F(xiàn)，G這三位同學(xué)也要相鄰坐在一起，請(qǐng)問：總共有多少種排列方法數(shù)？

2.2 限不相鄰圓排列

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

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

其證法與定理2類似.

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

例4設(shè)三對(duì)夫妻坐圓桌吃飯，要求夫妻雙方不能坐在相鄰的位置，請(qǐng)問：總共有多少種排座位的方法數(shù)？

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

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

[2]潘承洞，潘承彪.初等數(shù)論[M].第三版.北京：北京大學(xué)出版社，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-），女，廣東饒平人，研究生競賽數(shù)學(xué)方向在讀.E-mail：2841254805@qq.com