重排数与限对排列的若干关系式

杨艾欣

重排问题与限对排列问题是组合数学中一类重要的排列计数问题，这一系列看似毫无关联的的计数问题，实际上彼此间蕴含着微妙的关系，但目前关于这类问题的研究成果不多.再者，要深入研究这一系列的组合数通常需要借用其递推关系甚至彼此间的一些关系式，因此本文通过观察表格及定义式等方面寻找这些重要的关系式，为后续更深入的研究提供一定的基础.

一、定义与引理

首先给出这两个问题中的若干定义与引理：

引理1.1 在1，2…，n的排列中，没有一个元排保位的排列个数为D■，且D■=n！·■■，n≥0.

定义1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n-1称为对子.

引理1.1 1，2，…，n在的排列中，没有对子的排列个数为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的排列中，没有圆对子的排列个数为Rn，且Rn=n！.■■，n≥1.

定义1.3 1，2，…，n的排列中，首尾两个元素相接，形成逆时针方向的一个排列称为圆排列.

引理1.4 在1，2，…，n的排列中，没有对子的圆排列个数为■■，且■n=（n-1）！.■■，n≥1.

引理1.5 在1，2，…，n的排列中，没有圆对子的圆排列个数为■，且

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

二、Dn，Qn，Rn，■■，■，之间的一些关系

笔者通过观察Dn，Qn，Rn，■■，■的特殊值（见下表），发现Dn，Qn，Rn，■■，■之间存在某些关系.

发现的结论如下：

定理2.1 D■与Q■的关系：

Q■=D■+D■ （1）

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

D■=nQ■ （3）

证明：根据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）

证明：根据Rn的定义式，

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

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

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

证得（17）式.

同理，根据定义式可以证得（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

重排问题与限对排列问题是组合数学中一类重要的排列计数问题，这一系列看似毫无关联的的计数问题，实际上彼此间蕴含着微妙的关系，但目前关于这类问题的研究成果不多.再者，要深入研究这一系列的组合数通常需要借用其递推关系甚至彼此间的一些关系式，因此本文通过观察表格及定义式等方面寻找这些重要的关系式，为后续更深入的研究提供一定的基础.

一、定义与引理

首先给出这两个问题中的若干定义与引理：

引理1.1 在1，2…，n的排列中，没有一个元排保位的排列个数为D■，且D■=n！·■■，n≥0.

定义1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n-1称为对子.

引理1.1 1，2，…，n在的排列中，没有对子的排列个数为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的排列中，没有圆对子的排列个数为Rn，且Rn=n！.■■，n≥1.

定义1.3 1，2，…，n的排列中，首尾两个元素相接，形成逆时针方向的一个排列称为圆排列.

引理1.4 在1，2，…，n的排列中，没有对子的圆排列个数为■■，且■n=（n-1）！.■■，n≥1.

引理1.5 在1，2，…，n的排列中，没有圆对子的圆排列个数为■，且

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

二、Dn，Qn，Rn，■■，■，之间的一些关系

笔者通过观察Dn，Qn，Rn，■■，■的特殊值（见下表），发现Dn，Qn，Rn，■■，■之间存在某些关系.

发现的结论如下：

定理2.1 D■与Q■的关系：

Q■=D■+D■ （1）

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

D■=nQ■ （3）

证明：根据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）

证明：根据Rn的定义式，

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

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

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

证得（17）式.

同理，根据定义式可以证得（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

重排问题与限对排列问题是组合数学中一类重要的排列计数问题，这一系列看似毫无关联的的计数问题，实际上彼此间蕴含着微妙的关系，但目前关于这类问题的研究成果不多.再者，要深入研究这一系列的组合数通常需要借用其递推关系甚至彼此间的一些关系式，因此本文通过观察表格及定义式等方面寻找这些重要的关系式，为后续更深入的研究提供一定的基础.

一、定义与引理

首先给出这两个问题中的若干定义与引理：

引理1.1 在1，2…，n的排列中，没有一个元排保位的排列个数为D■，且D■=n！·■■，n≥0.

定义1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n-1称为对子.

引理1.1 1，2，…，n在的排列中，没有对子的排列个数为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的排列中，没有圆对子的排列个数为Rn，且Rn=n！.■■，n≥1.

定义1.3 1，2，…，n的排列中，首尾两个元素相接，形成逆时针方向的一个排列称为圆排列.

引理1.4 在1，2，…，n的排列中，没有对子的圆排列个数为■■，且■n=（n-1）！.■■，n≥1.

引理1.5 在1，2，…，n的排列中，没有圆对子的圆排列个数为■，且

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

二、Dn，Qn，Rn，■■，■，之间的一些关系

笔者通过观察Dn，Qn，Rn，■■，■的特殊值（见下表），发现Dn，Qn，Rn，■■，■之间存在某些关系.

发现的结论如下：

定理2.1 D■与Q■的关系：

Q■=D■+D■ （1）

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

D■=nQ■ （3）

证明：根据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）

证明：根据Rn的定义式，

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

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

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

证得（17）式.

同理，根据定义式可以证得（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