重排數(shù)與限對排列的若干關系式

楊艾欣

重排問題與限對排列問題是組合數(shù)學中一類重要的排列計數(shù)問題，這一系列看似毫無關聯(lián)的的計數(shù)問題，實際上彼此間蘊含著微妙的關系，但目前關于這類問題的研究成果不多.再者，要深入研究這一系列的組合數(shù)通常需要借用其遞推關系甚至彼此間的一些關系式，因此本文通過觀察表格及定義式等方面尋找這些重要的關系式，為后續(xù)更深入的研究提供一定的基礎.

一、定義與引理

首先給出這兩個問題中的若干定義與引理：

引理1.1 在1，2…，n的排列中，沒有一個元排保位的排列個數(shù)為D■，且D■=n！·■■，n≥0.

定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n-1稱為對子.

引理1.1 1，2，…，n在的排列中，沒有對子的排列個數(shù)為Q■，且Q■=（n-1）！·■■，n≥1.

定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n稱為圓對子，約定（n，n+1）=（n，1）.

引理1.3 在1，2，…，n的排列中，沒有圓對子的排列個數(shù)為Rn，且Rn=n！.■■，n≥1.

定義1.3 1，2，…，n的排列中，首尾兩個元素相接，形成逆時針方向的一個排列稱為圓排列.

引理1.4 在1，2，…，n的排列中，沒有對子的圓排列個數(shù)為■■，且■n=（n-1）！.■■，n≥1.

引理1.5 在1，2，…，n的排列中，沒有圓對子的圓排列個數(shù)為■，且

■=（-1）n+n！.■■，n≥1.

二、Dn，Qn，Rn，■■，■，之間的一些關系

筆者通過觀察Dn，Qn，Rn，■■，■的特殊值（見下表），發(fā)現(xiàn)Dn，Qn，Rn，■■，■之間存在某些關系.

發(fā)現(xiàn)的結論如下：

定理2.1 D■與Q■的關系：

Q■=D■+D■ （1）

Q■=（n+2）Dn+（-1）n+1 （2）

D■=nQ■ （3）

證明：根據(jù)D■與Q■的表示式知，

Q■=n！·■■（n+1-i）=

（n+1）！·■■+n！·■■

=（n+1）！·■■ - （-1）■+n！·■■-（-1）■

=D■+D■

（1）式得證.

Q■=n！·■■（n+1-i）=

（n+1）！·■■+n！·■■

=（n+1）！·■■+

n！·■■-（-1）■=

（n+2）·n！·■■-（-1）■

=（n+2）D■+（-1）■

（2）式得證.

定理2.2 Dn與Rn的關系：Rn=Dn-（-1）n （4）

定理2.3 Dn與■■的關系：Dn= ■■ （5）

定理2.4 Dn與■的關系：Dn= ■+■■ （6）

定理2.5 Qn與Rn的關系：Qn+1 =Rn+ Rn+1 （7）

定理2.6 Qn與■■的關系：Qn=■■+■■ （8）

定理2.7 Qn與■的關系：

■■+■■=nQn （9）

定理2.8 Rn與■■的關系：Rn=n■■ （10）

■■=Rn+（-1）n （11）

定理2.9 Rn與■的關系：Rn+1 =（n+1）（■+■■） （12）

注：以上定理2.2～2.9的證明均容易通過相應的定義式，利用定理2.1的證明方法證得結論，此處不再累贅.

三、Dn，Qn，Rn，■■，■的一些遞推關系

引理3.1 Dn的遞推關系：

Dn+1 =（n+1）Dn+（-1）n+1（13）

Dn+2 =（n+1）（Dn+1+Dn）（14）

定理3.1 Qn的遞推關系：

Qn+2 +（n+1）Qn+1+nQn（15）

n（n+2）Qn=（n+1）Qn+1+（-1）n+1（16）

證明：（2）式代入（1）式即證得（16）式.

定理3.2 Rn的遞推關系：

Rn+1=（n+1）·R■+（-1）■（17）

Rn+2=（n+1）（Rn+Rn+1）+（-1）（n+1）（18）

（n+1）（n+2）Rn+n（n+2）Rn+1=（n+1）Rn+2

（19）

證明：根據(jù)Rn的定義式，

Rn+1=（n+1）！·■■=

（n+1）n！·■■+（-1）■

=（n+1）R■+（-1）■

證得（17）式.

同理，根據(jù)定義式可以證得（18）（19）式.

定理3.3 ■■的遞推關系：

■■=n■■+（-1）n （20）

■■=n（■■+ ■■）（21）

證明：（10）式代入（11）式即可證得（20）式.

（8）式代入（3）式得Dn+1=n·（■■+ ■■），（5）式代入上式即證得（21）式.

定理3.4 ■的遞推關系：

■■+■■=（n+1）（■+■■）（22）

（n+1）■+n■■+（-1）n+1=■■（23）

■■+（-1）n=■（24）

證明：由（5）代入（6），可得■■=■+■■，再代入（9）式，可得■■+■■=（n+1）（■+■■），得證（22）式.

由（4）式代入（6），得Rn+（-1）n=■+■■，再由（12）式代入上式得證（23）式.

由（10）式代入Rn=+（-1）n=■+■■，得n■■+（-1）n=■+■■，再代入（9）式整理可得（24）式.

責任編輯 羅 峰endprint

重排問題與限對排列問題是組合數(shù)學中一類重要的排列計數(shù)問題，這一系列看似毫無關聯(lián)的的計數(shù)問題，實際上彼此間蘊含著微妙的關系，但目前關于這類問題的研究成果不多.再者，要深入研究這一系列的組合數(shù)通常需要借用其遞推關系甚至彼此間的一些關系式，因此本文通過觀察表格及定義式等方面尋找這些重要的關系式，為后續(xù)更深入的研究提供一定的基礎.

一、定義與引理

首先給出這兩個問題中的若干定義與引理：

引理1.1 在1，2…，n的排列中，沒有一個元排保位的排列個數(shù)為D■，且D■=n！·■■，n≥0.

定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n-1稱為對子.

引理1.1 1，2，…，n在的排列中，沒有對子的排列個數(shù)為Q■，且Q■=（n-1）！·■■，n≥1.

定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n稱為圓對子，約定（n，n+1）=（n，1）.

引理1.3 在1，2，…，n的排列中，沒有圓對子的排列個數(shù)為Rn，且Rn=n！.■■，n≥1.

定義1.3 1，2，…，n的排列中，首尾兩個元素相接，形成逆時針方向的一個排列稱為圓排列.

引理1.4 在1，2，…，n的排列中，沒有對子的圓排列個數(shù)為■■，且■n=（n-1）！.■■，n≥1.

引理1.5 在1，2，…，n的排列中，沒有圓對子的圓排列個數(shù)為■，且

■=（-1）n+n！.■■，n≥1.

二、Dn，Qn，Rn，■■，■，之間的一些關系

筆者通過觀察Dn，Qn，Rn，■■，■的特殊值（見下表），發(fā)現(xiàn)Dn，Qn，Rn，■■，■之間存在某些關系.

發(fā)現(xiàn)的結論如下：

定理2.1 D■與Q■的關系：

Q■=D■+D■ （1）

Q■=（n+2）Dn+（-1）n+1 （2）

D■=nQ■ （3）

證明：根據(jù)D■與Q■的表示式知，

Q■=n！·■■（n+1-i）=

（n+1）！·■■+n！·■■

=（n+1）！·■■ - （-1）■+n！·■■-（-1）■

=D■+D■

（1）式得證.

Q■=n！·■■（n+1-i）=

（n+1）！·■■+n！·■■

=（n+1）！·■■+

n！·■■-（-1）■=

（n+2）·n！·■■-（-1）■

=（n+2）D■+（-1）■

（2）式得證.

定理2.2 Dn與Rn的關系：Rn=Dn-（-1）n （4）

定理2.3 Dn與■■的關系：Dn= ■■ （5）

定理2.4 Dn與■的關系：Dn= ■+■■ （6）

定理2.5 Qn與Rn的關系：Qn+1 =Rn+ Rn+1 （7）

定理2.6 Qn與■■的關系：Qn=■■+■■ （8）

定理2.7 Qn與■的關系：

■■+■■=nQn （9）

定理2.8 Rn與■■的關系：Rn=n■■ （10）

■■=Rn+（-1）n （11）

定理2.9 Rn與■的關系：Rn+1 =（n+1）（■+■■） （12）

注：以上定理2.2～2.9的證明均容易通過相應的定義式，利用定理2.1的證明方法證得結論，此處不再累贅.

三、Dn，Qn，Rn，■■，■的一些遞推關系

引理3.1 Dn的遞推關系：

Dn+1 =（n+1）Dn+（-1）n+1（13）

Dn+2 =（n+1）（Dn+1+Dn）（14）

定理3.1 Qn的遞推關系：

Qn+2 +（n+1）Qn+1+nQn（15）

n（n+2）Qn=（n+1）Qn+1+（-1）n+1（16）

證明：（2）式代入（1）式即證得（16）式.

定理3.2 Rn的遞推關系：

Rn+1=（n+1）·R■+（-1）■（17）

Rn+2=（n+1）（Rn+Rn+1）+（-1）（n+1）（18）

（n+1）（n+2）Rn+n（n+2）Rn+1=（n+1）Rn+2

（19）

證明：根據(jù)Rn的定義式，

Rn+1=（n+1）！·■■=

（n+1）n！·■■+（-1）■

=（n+1）R■+（-1）■

證得（17）式.

同理，根據(jù)定義式可以證得（18）（19）式.

定理3.3 ■■的遞推關系：

■■=n■■+（-1）n （20）

■■=n（■■+ ■■）（21）

證明：（10）式代入（11）式即可證得（20）式.

（8）式代入（3）式得Dn+1=n·（■■+ ■■），（5）式代入上式即證得（21）式.

定理3.4 ■的遞推關系：

■■+■■=（n+1）（■+■■）（22）

（n+1）■+n■■+（-1）n+1=■■（23）

■■+（-1）n=■（24）

證明：由（5）代入（6），可得■■=■+■■，再代入（9）式，可得■■+■■=（n+1）（■+■■），得證（22）式.

由（4）式代入（6），得Rn+（-1）n=■+■■，再由（12）式代入上式得證（23）式.

由（10）式代入Rn=+（-1）n=■+■■，得n■■+（-1）n=■+■■，再代入（9）式整理可得（24）式.

責任編輯 羅 峰endprint

重排問題與限對排列問題是組合數(shù)學中一類重要的排列計數(shù)問題，這一系列看似毫無關聯(lián)的的計數(shù)問題，實際上彼此間蘊含著微妙的關系，但目前關于這類問題的研究成果不多.再者，要深入研究這一系列的組合數(shù)通常需要借用其遞推關系甚至彼此間的一些關系式，因此本文通過觀察表格及定義式等方面尋找這些重要的關系式，為后續(xù)更深入的研究提供一定的基礎.

一、定義與引理

首先給出這兩個問題中的若干定義與引理：

引理1.1 在1，2…，n的排列中，沒有一個元排保位的排列個數(shù)為D■，且D■=n！·■■，n≥0.

定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n-1稱為對子.

引理1.1 1，2，…，n在的排列中，沒有對子的排列個數(shù)為Q■，且Q■=（n-1）！·■■，n≥1.

定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n稱為圓對子，約定（n，n+1）=（n，1）.

引理1.3 在1，2，…，n的排列中，沒有圓對子的排列個數(shù)為Rn，且Rn=n！.■■，n≥1.

定義1.3 1，2，…，n的排列中，首尾兩個元素相接，形成逆時針方向的一個排列稱為圓排列.

引理1.4 在1，2，…，n的排列中，沒有對子的圓排列個數(shù)為■■，且■n=（n-1）！.■■，n≥1.

引理1.5 在1，2，…，n的排列中，沒有圓對子的圓排列個數(shù)為■，且

■=（-1）n+n！.■■，n≥1.

二、Dn，Qn，Rn，■■，■，之間的一些關系

筆者通過觀察Dn，Qn，Rn，■■，■的特殊值（見下表），發(fā)現(xiàn)Dn，Qn，Rn，■■，■之間存在某些關系.

發(fā)現(xiàn)的結論如下：

定理2.1 D■與Q■的關系：

Q■=D■+D■ （1）

Q■=（n+2）Dn+（-1）n+1 （2）

D■=nQ■ （3）

證明：根據(jù)D■與Q■的表示式知，

Q■=n！·■■（n+1-i）=

（n+1）！·■■+n！·■■

=（n+1）！·■■ - （-1）■+n！·■■-（-1）■

=D■+D■

（1）式得證.

Q■=n！·■■（n+1-i）=

（n+1）！·■■+n！·■■

=（n+1）！·■■+

n！·■■-（-1）■=

（n+2）·n！·■■-（-1）■

=（n+2）D■+（-1）■

（2）式得證.

定理2.2 Dn與Rn的關系：Rn=Dn-（-1）n （4）

定理2.3 Dn與■■的關系：Dn= ■■ （5）

定理2.4 Dn與■的關系：Dn= ■+■■ （6）

定理2.5 Qn與Rn的關系：Qn+1 =Rn+ Rn+1 （7）

定理2.6 Qn與■■的關系：Qn=■■+■■ （8）

定理2.7 Qn與■的關系：

■■+■■=nQn （9）

定理2.8 Rn與■■的關系：Rn=n■■ （10）

■■=Rn+（-1）n （11）

定理2.9 Rn與■的關系：Rn+1 =（n+1）（■+■■） （12）

注：以上定理2.2～2.9的證明均容易通過相應的定義式，利用定理2.1的證明方法證得結論，此處不再累贅.

三、Dn，Qn，Rn，■■，■的一些遞推關系

引理3.1 Dn的遞推關系：

Dn+1 =（n+1）Dn+（-1）n+1（13）

Dn+2 =（n+1）（Dn+1+Dn）（14）

定理3.1 Qn的遞推關系：

Qn+2 +（n+1）Qn+1+nQn（15）

n（n+2）Qn=（n+1）Qn+1+（-1）n+1（16）

證明：（2）式代入（1）式即證得（16）式.

定理3.2 Rn的遞推關系：

Rn+1=（n+1）·R■+（-1）■（17）

Rn+2=（n+1）（Rn+Rn+1）+（-1）（n+1）（18）

（n+1）（n+2）Rn+n（n+2）Rn+1=（n+1）Rn+2

（19）

證明：根據(jù)Rn的定義式，

Rn+1=（n+1）！·■■=

（n+1）n！·■■+（-1）■

=（n+1）R■+（-1）■

證得（17）式.

同理，根據(jù)定義式可以證得（18）（19）式.

定理3.3 ■■的遞推關系：

■■=n■■+（-1）n （20）

■■=n（■■+ ■■）（21）

證明：（10）式代入（11）式即可證得（20）式.

（8）式代入（3）式得Dn+1=n·（■■+ ■■），（5）式代入上式即證得（21）式.

定理3.4 ■的遞推關系：

■■+■■=（n+1）（■+■■）（22）

（n+1）■+n■■+（-1）n+1=■■（23）

■■+（-1）n=■（24）

證明：由（5）代入（6），可得■■=■+■■，再代入（9）式，可得■■+■■=（n+1）（■+■■），得證（22）式.

由（4）式代入（6），得Rn+（-1）n=■+■■，再由（12）式代入上式得證（23）式.

由（10）式代入Rn=+（-1）n=■+■■，得n■■+（-1）n=■+■■，再代入（9）式整理可得（24）式.

責任編輯 羅 峰endprint