重排數(shù)與限對(duì)排列的若干關(guān)系式
2014-03-28 04:22:46楊艾欣
師道·教研 2014年1期
楊艾欣
重排問題與限對(duì)排列問題是組合數(shù)學(xué)中一類重要的排列計(jì)數(shù)問題，這一系列看似毫無(wú)關(guān)聯(lián)的的計(jì)數(shù)問題，實(shí)際上彼此間蘊(yùn)含著微妙的關(guān)系，但目前關(guān)于這類問題的研究成果不多.再者，要深入研究這一系列的組合數(shù)通常需要借用其遞推關(guān)系甚至彼此間的一些關(guān)系式，因此本文通過觀察表格及定義式等方面尋找這些重要的關(guān)系式，為后續(xù)更深入的研究提供一定的基礎(chǔ).
一、定義與引理
首先給出這兩個(gè)問題中的若干定義與引理：
引理1.1 在1，2…，n的排列中，沒有一個(gè)元排保位的排列個(gè)數(shù)為D■，且D■=n！·■■，n≥0.
定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n-1稱為對(duì)子.
引理1.1 1，2，…，n在的排列中，沒有對(duì)子的排列個(gè)數(shù)為Q■，且Q■=（n-1）！·■■，n≥1.
定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n稱為圓對(duì)子，約定（n，n+1）=（n，1）.
引理1.3 在1，2，…，n的排列中，沒有圓對(duì)子的排列個(gè)數(shù)為Rn，且Rn=n！.■■，n≥1.
定義1.3 1，2，…，n的排列中，首尾兩個(gè)元素相接，形成逆時(shí)針方向的一個(gè)排列稱為圓排列.
引理1.4 在1，2，…，n的排列中，沒有對(duì)子的圓排列個(gè)數(shù)為■■，且■n=（n-1）！.■■，n≥1.
引理1.5 在1，2，…，n的排列中，沒有圓對(duì)子的圓排列個(gè)數(shù)為■，且
■=（-1）n+n！.■■，n≥1.
二、Dn，Qn，Rn，■■，■，之間的一些關(guān)系
筆者通過觀察Dn，Qn，Rn，■■，■的特殊值（見下表），發(fā)現(xiàn)Dn，Qn，Rn，■■，■之間存在某些關(guān)系.
發(fā)現(xiàn)的結(jié)論如下：
定理2.1 D■與Q■的關(guān)系：
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的關(guān)系：Rn=Dn-（-1）n （4）
定理2.3 Dn與■■的關(guān)系：Dn= ■■ （5）
定理2.4 Dn與■的關(guān)系：Dn= ■+■■ （6）
定理2.5 Qn與Rn的關(guān)系：Qn+1 =Rn+ Rn+1 （7）
定理2.6 Qn與■■的關(guān)系：Qn=■■+■■ （8）
定理2.7 Qn與■的關(guān)系：
■■+■■=nQn （9）
定理2.8 Rn與■■的關(guān)系：Rn=n■■ （10）
■■=Rn+（-1）n （11）
定理2.9 Rn與■的關(guān)系：Rn+1 =（n+1）（■+■■） （12）
注：以上定理2.2～2.9的證明均容易通過相應(yīng)的定義式，利用定理2.1的證明方法證得結(jié)論，此處不再累贅.
三、Dn，Qn，Rn，■■，■的一些遞推關(guān)系
引理3.1 Dn的遞推關(guān)系：
Dn+1 =（n+1）Dn+（-1）n+1（13）
Dn+2 =（n+1）（Dn+1+Dn）（14）
定理3.1 Qn的遞推關(guān)系：
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的遞推關(guān)系：
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 ■■的遞推關(guān)系：
■■=n■■+（-1）n （20）
■■=n（■■+ ■■）（21）
證明：（10）式代入（11）式即可證得（20）式.
（8）式代入（3）式得Dn+1=n·（■■+ ■■），（5）式代入上式即證得（21）式.
定理3.4 ■的遞推關(guān)系：
■■+■■=（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）式.
責(zé)任編輯 羅 峰e(cuò)ndprint
重排問題與限對(duì)排列問題是組合數(shù)學(xué)中一類重要的排列計(jì)數(shù)問題，這一系列看似毫無(wú)關(guān)聯(lián)的的計(jì)數(shù)問題，實(shí)際上彼此間蘊(yùn)含著微妙的關(guān)系，但目前關(guān)于這類問題的研究成果不多.再者，要深入研究這一系列的組合數(shù)通常需要借用其遞推關(guān)系甚至彼此間的一些關(guān)系式，因此本文通過觀察表格及定義式等方面尋找這些重要的關(guān)系式，為后續(xù)更深入的研究提供一定的基礎(chǔ).
一、定義與引理
首先給出這兩個(gè)問題中的若干定義與引理：
引理1.1 在1，2…，n的排列中，沒有一個(gè)元排保位的排列個(gè)數(shù)為D■，且D■=n！·■■，n≥0.
定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n-1稱為對(duì)子.
引理1.1 1，2，…，n在的排列中，沒有對(duì)子的排列個(gè)數(shù)為Q■，且Q■=（n-1）！·■■，n≥1.
定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n稱為圓對(duì)子，約定（n，n+1）=（n，1）.
引理1.3 在1，2，…，n的排列中，沒有圓對(duì)子的排列個(gè)數(shù)為Rn，且Rn=n！.■■，n≥1.
定義1.3 1，2，…，n的排列中，首尾兩個(gè)元素相接，形成逆時(shí)針方向的一個(gè)排列稱為圓排列.
引理1.4 在1，2，…，n的排列中，沒有對(duì)子的圓排列個(gè)數(shù)為■■，且■n=（n-1）！.■■，n≥1.
引理1.5 在1，2，…，n的排列中，沒有圓對(duì)子的圓排列個(gè)數(shù)為■，且
■=（-1）n+n！.■■，n≥1.
二、Dn，Qn，Rn，■■，■，之間的一些關(guān)系
筆者通過觀察Dn，Qn，Rn，■■，■的特殊值（見下表），發(fā)現(xiàn)Dn，Qn，Rn，■■，■之間存在某些關(guān)系.
發(fā)現(xiàn)的結(jié)論如下：
定理2.1 D■與Q■的關(guān)系：
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的關(guān)系：Rn=Dn-（-1）n （4）
定理2.3 Dn與■■的關(guān)系：Dn= ■■ （5）
定理2.4 Dn與■的關(guān)系：Dn= ■+■■ （6）
定理2.5 Qn與Rn的關(guān)系：Qn+1 =Rn+ Rn+1 （7）
定理2.6 Qn與■■的關(guān)系：Qn=■■+■■ （8）
定理2.7 Qn與■的關(guān)系：
■■+■■=nQn （9）
定理2.8 Rn與■■的關(guān)系：Rn=n■■ （10）
■■=Rn+（-1）n （11）
定理2.9 Rn與■的關(guān)系：Rn+1 =（n+1）（■+■■） （12）
注：以上定理2.2～2.9的證明均容易通過相應(yīng)的定義式，利用定理2.1的證明方法證得結(jié)論，此處不再累贅.
三、Dn，Qn，Rn，■■，■的一些遞推關(guān)系
引理3.1 Dn的遞推關(guān)系：
Dn+1 =（n+1）Dn+（-1）n+1（13）
Dn+2 =（n+1）（Dn+1+Dn）（14）
定理3.1 Qn的遞推關(guān)系：
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的遞推關(guān)系：
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 ■■的遞推關(guān)系：
■■=n■■+（-1）n （20）
■■=n（■■+ ■■）（21）
證明：（10）式代入（11）式即可證得（20）式.
（8）式代入（3）式得Dn+1=n·（■■+ ■■），（5）式代入上式即證得（21）式.
定理3.4 ■的遞推關(guān)系：
■■+■■=（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）式.
責(zé)任編輯 羅 峰e(cuò)ndprint
重排問題與限對(duì)排列問題是組合數(shù)學(xué)中一類重要的排列計(jì)數(shù)問題，這一系列看似毫無(wú)關(guān)聯(lián)的的計(jì)數(shù)問題，實(shí)際上彼此間蘊(yùn)含著微妙的關(guān)系，但目前關(guān)于這類問題的研究成果不多.再者，要深入研究這一系列的組合數(shù)通常需要借用其遞推關(guān)系甚至彼此間的一些關(guān)系式，因此本文通過觀察表格及定義式等方面尋找這些重要的關(guān)系式，為后續(xù)更深入的研究提供一定的基礎(chǔ).
一、定義與引理
首先給出這兩個(gè)問題中的若干定義與引理：
引理1.1 在1，2…，n的排列中，沒有一個(gè)元排保位的排列個(gè)數(shù)為D■，且D■=n！·■■，n≥0.
定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n-1稱為對(duì)子.
引理1.1 1，2，…，n在的排列中，沒有對(duì)子的排列個(gè)數(shù)為Q■，且Q■=（n-1）！·■■，n≥1.
定義1.2 1，2，…，n的排列中，形如（i，i﹢1），i=1，2，…，n稱為圓對(duì)子，約定（n，n+1）=（n，1）.
引理1.3 在1，2，…，n的排列中，沒有圓對(duì)子的排列個(gè)數(shù)為Rn，且Rn=n！.■■，n≥1.
定義1.3 1，2，…，n的排列中，首尾兩個(gè)元素相接，形成逆時(shí)針方向的一個(gè)排列稱為圓排列.
引理1.4 在1，2，…，n的排列中，沒有對(duì)子的圓排列個(gè)數(shù)為■■，且■n=（n-1）！.■■，n≥1.
引理1.5 在1，2，…，n的排列中，沒有圓對(duì)子的圓排列個(gè)數(shù)為■，且
■=（-1）n+n！.■■，n≥1.
二、Dn，Qn，Rn，■■，■，之間的一些關(guān)系
筆者通過觀察Dn，Qn，Rn，■■，■的特殊值（見下表），發(fā)現(xiàn)Dn，Qn，Rn，■■，■之間存在某些關(guān)系.
發(fā)現(xiàn)的結(jié)論如下：
定理2.1 D■與Q■的關(guān)系：
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的關(guān)系：Rn=Dn-（-1）n （4）
定理2.3 Dn與■■的關(guān)系：Dn= ■■ （5）
定理2.4 Dn與■的關(guān)系：Dn= ■+■■ （6）
定理2.5 Qn與Rn的關(guān)系：Qn+1 =Rn+ Rn+1 （7）
定理2.6 Qn與■■的關(guān)系：Qn=■■+■■ （8）
定理2.7 Qn與■的關(guān)系：
■■+■■=nQn （9）
定理2.8 Rn與■■的關(guān)系：Rn=n■■ （10）
■■=Rn+（-1）n （11）
定理2.9 Rn與■的關(guān)系：Rn+1 =（n+1）（■+■■） （12）
注：以上定理2.2～2.9的證明均容易通過相應(yīng)的定義式，利用定理2.1的證明方法證得結(jié)論，此處不再累贅.
三、Dn，Qn，Rn，■■，■的一些遞推關(guān)系
引理3.1 Dn的遞推關(guān)系：
Dn+1 =（n+1）Dn+（-1）n+1（13）
Dn+2 =（n+1）（Dn+1+Dn）（14）
定理3.1 Qn的遞推關(guān)系：
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的遞推關(guān)系：
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 ■■的遞推關(guān)系：
■■=n■■+（-1）n （20）
■■=n（■■+ ■■）（21）
證明：（10）式代入（11）式即可證得（20）式.
（8）式代入（3）式得Dn+1=n·（■■+ ■■），（5）式代入上式即證得（21）式.
定理3.4 ■的遞推關(guān)系：
■■+■■=（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）式.
責(zé)任編輯 羅 峰e(cuò)ndprint
猜你喜歡
政工學(xué)刊(2025年2期)2025-02-07 00:00:00
小學(xué)生學(xué)習(xí)指導(dǎo)(低年級(jí))(2021年9期)2021-10-14 07:57:00
語(yǔ)數(shù)外學(xué)習(xí)·高中版中旬(2021年1期)2021-09-10 07:22:44
中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2019年10期)2019-11-25 07:34:00
小學(xué)生學(xué)習(xí)指導(dǎo)(低年級(jí))(2019年9期)2019-09-25 07:43:28
飛天(2019年6期)2019-07-08 03:40:25
小學(xué)生學(xué)習(xí)指導(dǎo)(低年級(jí))(2018年9期)2018-09-26 05:59:46
——《古對(duì)今》教學(xué)活動(dòng)設(shè)計(jì)
小學(xué)教學(xué)設(shè)計(jì)(語(yǔ)文)(2018年5期)2018-02-22 16:34:39
中學(xué)化學(xué)(2017年6期)2017-10-16 20:44:33
中學(xué)生數(shù)理化·七年級(jí)數(shù)學(xué)人教版(2016年4期)2016-11-19 08:41:24
