﻿ 关于正整数不含分部量2的有序分拆的几个组合双射
 文章快速检索 高级检索
 浙江大学学报(理学版)  2017, Vol. 44 Issue (3): 261-265  DOI:10.3785/j.issn.1008-9497.2017.03.002 0

引用本文 [复制中英文]

[复制中文]
GUO Yuhong, WANG Rujun. Several combinatorial bijections about compositions without 2's of positive integers[J]. Journal of Zhejiang University(Science Edition), 2017, 44(3): 261-265. DOI: 10.3785/j.issn.1008-9497.2017.03.002.
[复制英文]

文章历史

Several combinatorial bijections about compositions without 2's of positive integers
GUO Yuhong , WANG Rujun
School of Mathematics and Statistics, Hexi University, Zhangye 734000, Gansu Province, China
Abstract: Using the conjugate of compositions, we present combinatorial bijective proofs of the recurrence relation of the self-inverse compositions without 2's of even 2k, 2's of odd 2k+1, and without 2's of positive integer n, respectively. In addition, we also obtain the combinatorial bijection of an identity which was obtained by MUNAGI relating to the number of the compositions without 2's of positive integer n. The methods used in this paper are different from the proofs of MUNAGI.
Key words: compositions of positive integer    the conjugate of compositions    the self-inverse compositions    combinatorial bijection    relation
0 引言

1919年，MACMAHON[1]首次定义了正整数的有序分拆，即把正整数n表示成一些正整数的有序和, 其中的每一项叫该分拆的分部量.例如, 4的有序分拆有4, 3+1, 1+3, 2+2, 2+1+1, 1+2+1, 1+1+2, 1+1+1+1，共8个.也可以将相同的分部量写成幂, 将有序分拆表示成向量的形式.例如, 上述4的8个有序分拆是: (4), (3, 1), (1, 3), (22), (12, 2), (1, 2, 1), (2, 12), (14). MACMAHON[1]给出了有序分拆的一些性质和表示图, 称为Zig-Zag graph, 类似于无序分拆的Ferres graph, 即将有序分拆每个分部量ni依次用一行含有ni个的点来表示, 但要求下一行的第1个点与上一行的最后一个点对齐.例如分拆(6, 3, 1, 2, 2) 的Zig-Zag graph见图 1.

 图 1 Zig-Zag图 Fig. 1 Zig-Zag graph

MUNAGI[2-3]给出了包括Zig-Zag graph在内的5种求有序分拆的共轭分拆方法, 本文只介绍direc detection of conjugates(简称DD)法, 是一种比较宽泛直接的表示法, 即正整数的任意一个有序分拆通常有2种形式:

(1)C=(1a1, b1, 1a2, b2, 1a3, b3，…), a1>0, ai≥0, i>1; bi≥2, i≥1;

(2)E=(b1, 1a1, b2, 1a2, b3, 1a3, …), ai≥0, bi≥2.

(3)C′=(a1+1, 1b1-2, a2+2, 1b2-2, a3+2，…); a1>0, ai≥0, i>1; bi≥2, i≥1;

(4)E′=(1b1-1, a1+2, 1b2-2, a2+2, …), ai≥0, bi≥2.

1 主要结果及证明

 P\left( n, \hat{2} \right)=\left\{ \begin{align} & C\left( k+1, \hat{2} \right), \ \ \ \ n=2k, k\ge 0, \\ & C\left( k+1, \hat{2} \right)+C\left( k-1, \hat{2} \right), \ \ \ \ n=2k+1, k\ge 0, \\ \end{align} \right.

$P\left( n, \hat{2} \right)$的生成函数是

 $\sum\limits_{n=0}^{\infty }{P\left( n, \hat{2} \right)}{{z}^{n}}=\frac{1+z}{1-{{z}^{2}}-{{z}^{3}}}.$

(A)分部量的个数为偶数;

(B)分部量的个数为奇数.

 $P\left( 2k, \hat{2} \right)=C\left( k+1, \hat{2} \right).$

(2) 当n=2k+1时, 也将n的不含分部量2的自反的有序分拆分成2种类型来考查:

(C)中间分部量是3;

(D)中间分部量不是3.

 $P\left( 2k+1, \hat{2} \right)=C\left( k+1, \hat{2} \right)+C\left( k-1, \hat{2} \right).$

 \begin{align} & C\left( n, \hat{2} \right)=2C\left( n-1, \hat{2} \right)-C\left( n-2, \hat{2} \right)+ \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ C\left( n-3, \hat{2} \right), \ \ \ \ \ n>2; \\ & \ \ \ \ \ \ \ C\left( 0, \hat{2} \right)=C\left( 1, \hat{2} \right)=C\left( 2, \hat{2} \right)=1. \\ \end{align}

 \begin{align} & {{P}_{e}}\left( 2k, \hat{2} \right)=2{{P}_{e}}\left( 2k-2, \hat{2} \right)-{{P}_{e}}\left( 2k-4, \hat{2} \right)+ \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {{P}_{e}}\left( 2k-6, \hat{2} \right), \ \ \ \ n>6; \\ & \ \ \ {{P}_{e}}\left( 2, \hat{2} \right)={{P}_{e}}\left( 4, \hat{2} \right)=1, \ \ \ {{P}_{e}}\left( 6, \hat{2} \right)=2. \\ \end{align}

 \begin{align} & P\left( 2k, \hat{2} \right)=2P\left( 2k-2, \hat{2} \right)-P\left( 2k-4, \hat{2} \right)+ \\ & \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ P\left( 2k-6, \hat{2} \right), \ \ \ \ n>6; \\ & \ \ \ P\left( 2, \hat{2} \right)=1, \ \ \ P\left( 4, \hat{2} \right)=2, \ \ \ P\left( 6, \hat{2} \right)=4. \\ \end{align}

(A)2k的首末两端分部量都是1的分拆;

(B)2k的首末两端分部量都是3的分拆;

(C)2k的首末两端分部量都是大于3的分拆, 以及2k-4的分拆.

 \begin{align} & P\left( 2k, \hat{2} \right)+P\left( 2k-4, \hat{2} \right)= \\ & \ \ \ \ \ \ \ 2P\left( 2k-2, \hat{2} \right)+P\left( 2k-6, \hat{2} \right). \\ \end{align}

 \begin{align} & P\left( 2k, \hat{2} \right)=2P\left( 2k-2, \hat{2} \right)-\\ & \ \ \ \ \ \ \ P\left( 2k-4, \hat{2} \right)+P\left( 2k-6, \hat{2} \right). \\ \end{align}

 \begin{align} & P\left( 2k+1, \hat{2} \right)=P\left( 2k, \hat{2} \right)+P\left( 2k-4, \hat{2} \right), \ \ \ \ k>2; \\ & P\left( 1, \hat{2} \right)=P\left( 2, \hat{2} \right)=1, P\left( 3, \hat{2} \right)=2, P\left( 4, \hat{2} \right)=2. \\ \end{align}

(A)中间分部量不等于3;

(B)中间分部量等于3.

(a)中间的分拆(s, 3, s)中s>1;

(b)中间的分拆(s, 3, s)中s=1.

 $P\left( 2k+1, \hat{2} \right)=P\left( 2k, \hat{2} \right)+P\left( 2k-4, \hat{2} \right).$

 \begin{align} & {\text{(4, 3, 3, 3, 4)}}\xrightarrow{{共轭}}{\text{(1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1)}} \\ & \xrightarrow{删中间的\text{(2, 1, 2)}}\text{(1, 1, 1, 2, 1, 1, 2, 1, 1, 1)}\xrightarrow{共轭}\text{(4, 4, 4)}. \\ & \text{(4, 4, 4)}\xrightarrow{共轭}\text{(1, 1, 1, 2, 1, 1, 2, 1, 1, 1)}\xrightarrow{中间添\text{(2, 1, 2)}} \\ & \text{(1, 1, 1, 2, 1, 2, 1, 2, 1, 2, 1, 1, 1)}\xrightarrow{共轭}\text{(4, 3, 3, 3, 4)}. \\ & \text{(1, 1, 4, 1, 3, 1, 4, 1, 1)}\xrightarrow{删中间的\text{(1, 3, 1)}}\text{(1, 1, 4, 4, 1, 1)}. \\ & \text{(1, 1, 4, 4, 1, 1)}\xrightarrow{中间添\text{(1, 3, 1)}}\text{(1, 1, 4, 1, 3, 1, 4, 1, 1)}. \\ \end{align}

 \begin{align} & P\left( n, \hat{2} \right)=P\left( n-2, \hat{2} \right)+P\left( n-3, \hat{2} \right), \ \ \ \ n>3; \\ & P\left( 1, \hat{2} \right)=P\left( 2, \hat{2} \right)=1, P\left( 3, \hat{2} \right)=2. \\ \end{align}

(A)首末两端的分部量等于1;

(B)首末两端的分部量大于1, 包括只含一个分部量的情形.

(a) n为偶数;

(b) n为奇数.

 $\text{(4, 1, 1, 4)}\xrightarrow{共轭}\text{(1, 1, 1, 4, 1, 1, 1)}\xrightarrow{中间\text{-(1, 1, 1)}}\text{(1, 1, 3, 1, 1)};$

11的分拆(5, 1, 5) 产生8的分拆(1, 1, 1, 1, 1, 1, 1, 1) 的过程为

 \begin{align} & \text{(5, 1, 5)}\xrightarrow{共轭}\text{(}{{\text{1}}^{4}}\text{, 3, }{{\text{1}}^{4}}\text{)}\xrightarrow{中间\text{-(1, 1, 1)}}\text{(}{{\text{1}}^{3}}\text{, 2, }{{\text{1}}^{3}}\text{)} \\ & \xrightarrow{\text{2=1+1}}\text{(}{{\text{1}}^{3}}\text{, 1, 1, }{{\text{1}}^{3}}\text{)=(}{{\text{1}}^{8}}\text{);} \\ \end{align}

6的分拆(16)产生9的分拆(4, 1, 4) 的过程为

 \begin{align} & \left( {{1}^{6}} \right)\xrightarrow{合并中间2个1}\left( {{1}^{2}}, 2, {{1}^{2}} \right)\xrightarrow{+\left( 1, 1, 1 \right)}\left( {{1}^{3}}, 3, {{1}^{3}} \right) \\ & \xrightarrow{共轭}\left( 4, 1, 4 \right). \\ \end{align}

(A)最右端的分部量等于1;

(B)最右端的分部量等于3;

(C)最右端的分部量等于5;

(D)最右端的分部量大于3, 但不等于5.

 [1] MACMAHON P A. Combinatory Analysis:Vol 1[M]. Cambridge: Cambridge University Press, 1915. [2] MUNAGI A O. Primary classes of compositions of numbers[J]. Annales Mathematicae et Informaticae, 2013, 41: 193–204. [3] MUNAGI A O. Zig-Zag graphs and partitions identities of A.K. Agarwal[J]. Annals of Combinatorics, 2015, 19(3): 557–566. DOI:10.1007/s00026-015-0276-7 [4] CHINN P, HEUBACH S. Integer sequence related to compositions without 2's[J]. Journal of Integer Sequences, 2003(6): Article 03.2.3.