正整數(shù)n的分部量不小于2的有序分拆數(shù)

唐保祥,任韓

(1.天水師范學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，甘肅 天水 741001；2.華東師范大學(xué)數(shù)學(xué)系，上海 200062)

正整數(shù)的分拆理論是組合數(shù)學(xué)的研究課題之一，此問題在密碼學(xué)，化學(xué)，生物學(xué)，統(tǒng)計(jì)學(xué)等學(xué)科中有廣泛應(yīng)用。目前，一些學(xué)者研究分部量有限制條件的有序和無序分拆數(shù)，分拆恒等式的組合證明等方面取得了豐富的研究成果[1-7]。本文利用遞推的方法給出了各分部量不大于2和各分部量不小于2分拆分拆的顯式計(jì)數(shù)公式，并給出了各分部量不大于3和4的分拆數(shù)的遞推式，而且可以類似地給出了正整數(shù)n的各分部量是2,或3,或4的分拆數(shù)的遞推式[8-10]。

1 結(jié)果及其證明

定理1設(shè)f(n)是正整數(shù)n的各分部量為1或2的分拆數(shù);g(n+2)是正整數(shù)n+2的各分部量不小2的分拆數(shù)，則

(i)f(n)=g(n+2);

證明(i) 設(shè)An是正整數(shù)n的各分部量是1或2的所有分拆形成的集合;Bn+2是正整數(shù)n+2的各分部量不小2的分拆形成的集合。下面證明:|An|=|Bn+2|。

正整數(shù)的一個(gè)分拆唯一對(duì)應(yīng)著各項(xiàng)是正整數(shù)的一個(gè)有限項(xiàng)的數(shù)列，所以在證明中為了說話方便，就把An和Bn+2中的元素就說成一個(gè)數(shù)列。

?x∈An,在數(shù)列x的最后一項(xiàng)之后添加一項(xiàng)2,所得的數(shù)列記為y,再把y中每個(gè)2之前的相繼出現(xiàn)的若干個(gè)1加到這個(gè)2上成為一項(xiàng)，所得的數(shù)列記為z，則z∈Bn+2。如，1,2,1,1,2→1,2,1,1,2,2→3,4,2。

對(duì)x1,x2∈An,當(dāng)x1≠x2時(shí)，設(shè)x1=(an,an-1,…,a2,a1),x2=(bm,am-1,…,b2,b1),其中ai=1,或2,bj=1,或2,則z1=(an,an-1,…,a2,a1,2),z2=(bm,am-1,…,b2,b1,2)。假設(shè)n≤m,在a1與b1,a2與b2,…,an與bn中第一個(gè)不相等的數(shù)對(duì)是ak與bk,不妨設(shè)ak=1,bk=2,無論是a1=b1=a2=b2=…=ak-1=bk-1=1,或2,則由z1,z2的定義知，z1≠z2,且z1,z2∈Bn+2。這樣就確定了An到Bn+2的一個(gè)單射，使得f(x)=z。

因此f是An到Bn+2的一個(gè)雙射。故|An|=|Bn+2|,即f(n)=g(n+2)。

易知f(1)=1,f(2)=2。故

定理2(i) 設(shè)正整數(shù)n的各分部量不大于3的有序分拆數(shù)為σ(n),則

σ(n)=σ(n-1)+σ(n-2)+σ(n-3)

其中n≥4,σ(1)=1,σ(2)=2,σ(3)=4;

(ii) 設(shè)正整數(shù)n的各分部量不大于4的有序分拆數(shù)為τ(n),則

τ(n)=τ(n-1)+τ(n-2)+

τ(n-3)+τ(n-4)

其中n≥5,τ(1)=1,τ(2)=2,τ(3)=4,τ(4)=15。

證明(i) 設(shè)Ai表示正整數(shù)i的各分部量不大于3的有序分拆的集合，當(dāng)n≥4時(shí)，Ai≠?,i=n-3,n-2,n-1,且Ai∩Aj=?(n-3≤i

故|An-3∪An-2∪An-1|=|An-3|+|An-2|+|An-1|≤|An|。

另一方面，?z=(d1,d2,d3,…,dq)∈An,若d1=3,則(d2,d3,…,dq)∈An-3;若d1=2,則(d2,d3,…,dq)∈An-2;若d1=1,則(d2,d3,…,dq)∈An-1。

故|An|≤|An-3∪An-2∪An-1|=|An-3|+|An-2|+|An-1|≤|An|。

所以|An|=|An-1|+|An-2|+|An-3|,即

σ(n)=σ(n-1)+σ(n-2)+σ(n-3)

當(dāng)1≤n≤6時(shí)，各分部量不大于3的有序分拆如下:

n=1→1。 共1個(gè)。

n=2→1,1; 2。 共2個(gè)。

n=3→2,1; 1,1,1; 1,2; 3。 共4個(gè)。

n=4→3,1;2,1,1; 2,2;1,2,1;1,1,1,1;1,1,2;1,3。共7個(gè)。

n=5→3,1,1;3,2;2,2,1;2,1,1,1;2,1,2;2,3;1,3,1;1,2,1,1;1,2,2;1,1,2,1;1,1,1,1,1;1,1,1,2;1,1,3。共13個(gè)。

n=6→3,2,1;3,1,1,1;3,1,2;3,3;2,3,1;2,2,1,1;2,2,2;2,1,2,1;2,1,1,1,1;2,1,1,2;2,1,3;

1,3,1,1;1,3,2;1,2,2,1;1,2,1,1,1;1,2,1,2;1,2,3;1,1,3,1;1,1,2,1,1;1,1,2,2;1,1,1,2,1;1,1,1,1,1,1;1,1,1,1,2;1,1,1,3。共24個(gè)。

故σ(1)=1,σ(2)=2,σ(3)=4。

(ii) 的證明類似于(i)。

定理3(i) 設(shè)正整數(shù)n的各分部量是2,或3的有序分拆數(shù)為φ(n),則

φ(n)=φ(n-2)+φ(n-3)

其中n≥5,φ(2)=1,φ(3)=1。

(ii) 設(shè)正整數(shù)n的各分部量是2,或3,或4的有序分拆數(shù)為δ(n),則

δ(n)=δ(n-2)+δ(n-3)+δ(n-4)

其中n≥6,δ(2)=1,δ(3)=1,δ(4)=2。

證明僅證明(ii)。設(shè)Ai表示正整數(shù)i的各分部量是2,或3,或4的有序分拆的集合，當(dāng)n≥6時(shí)，Ai≠?,i=n-4,n-3,n-2,且Ai∩Aj=?(n-4≤i

故|An-4∪An-3∪An-2|=|An-4|+|An-3|+|An-2|≤|An|。

另一方面，?z=(d1,d2,d3,…,dq)∈An,若d1=4,則(d2,d3,…,dq)∈An-4;若d1=3,則(d2,d3,…,dq)∈An-3;若d1=2,則(d2,d3,…,dq)∈An-2。

故|An|≤|An-4∪An-3∪An-2|=|An-4|+|An-3|+|An-2|≤|An|。

所以|An|=|An-4|+|An-3|+|An-2|,即

δ(n)=δ(n-2)+δ(n-3)+δ(n-4)

當(dāng)2≤n≤8時(shí)，各分部量是2,或3,或4的有序分拆如下:

n=2→2。 共1個(gè)。

n=3→3。 共1個(gè)。

n=4→2,2;4。 共2個(gè)。

n=5→3,2;2,3。 共2個(gè)。

n=6→4,2;3,3;2,2,2;2,4。共4個(gè)。

n=7→4,3;3,2,2;3,4;2,3,2;2,2,3。 共5個(gè)。

n=8→4,2,2;4,4;3,3,2;3,2,3;2,4,2;2,3,3;2,2,2,2;2,2,4。 共8個(gè)。

故δ(2)=1,δ(3)=1,δ(4)=2。

2 結(jié) 語

定理2和定理3的證明思想，給出了生成正整數(shù)n的各分部量滿足一定要求的正整數(shù)所有有序分拆的算法。因?yàn)檫f推式的解是正整數(shù)n的指數(shù)表達(dá)式，所以求各分部量滿足這些的算法無有效算法。