2025-11-13T02:34:11.179731

Combinatorics of positional colored compositions

Li, Wang

We consider colored compositions where only some parts are allowed different colors, depending on their locations in the composition. The counting sequences are obtained through generating functions. Connections to many other combinatorial objects are discussed, with combinatorial arguments provided and generalized for these observations.

academic

Combinatorics of positional colored compositions

基本信息

论文ID: 2511.08529
标题: Combinatorics of positional colored compositions
作者: Andrew Li (Princeton University), Hua Wang (Georgia Southern University)
分类: math.CO (Combinatorics)
发表时间: 2025年11月11日 (arXiv预印本)
论文链接: https://arxiv.org/abs/2511.08529
关键词: integer compositions, colored compositions, combinatorial proofs
MSC分类: 05A17, 11B37

摘要

本文研究位置着色组合（positional colored compositions），即根据部分在组合中的位置决定是否允许着色的整数组合。作者通过生成函数获得计数序列，并发现这些序列与多种其他组合对象存在深刻联系，为这些联系提供了双射证明和推广。

研究背景与动机

研究问题

本文研究的核心问题是：当整数组合中只有特定位置的部分允许n-着色时，如何进行计数，以及这类结构与其他组合对象的关系。

问题重要性

理论意义：整数组合是组合数学的基础对象，n-着色组合自2000年由Agarwal引入以来已有广泛研究。位置着色组合作为新的变体，丰富了这一研究领域。
连接性：通过研究发现，位置着色组合与限制颜色的组合、(n choose 2)-着色组合、三进制字符串、二进制字符串、321-避免可分离排列等多个组合对象等价，揭示了不同组合结构间的深层联系。
方法论价值：通过生成函数和双射证明，为组合计数提供了新的工具和视角。

现有方法的局限性

已有研究主要关注所有部分都着色或限制特定颜色的组合
缺乏基于位置的着色规则的系统研究
不同组合对象间的等价关系尚未充分挖掘

研究动机

作者通过OEIS（在线整数序列百科）发现某些计数序列的重合，从而探索位置着色组合与其他组合结构的内在联系，并通过组合论证提供深刻理解。

核心贡献

引入位置着色组合概念：定义了(m,k)-n-着色组合，其中位置为k (mod m)的部分进行n-着色，其他部分不着色。
推导生成函数：
- 给出EVEN着色组合（偶数位置着色）的生成函数
- 给出ODD着色组合（奇数位置着色）的生成函数
- 提供一般(m,k)-n-着色组合的生成函数
建立多个双射关系：
- EVEN着色组合与限制颜色2的n-着色组合
- ODD着色组合与(n choose 2)-着色组合
- EVEN着色组合与特定三进制字符串
- EVEN着色组合与二进制字符串的runs乘积和
- EVEN着色组合与321-避免可分离排列
提供组合恒等式的双射证明：证明了e(k+1) = e(k) + o(k)等恒等式，并推广到一般情形。
发现新的组合等价关系：揭示了看似无关的组合对象间的深层联系。

方法详解

任务定义

基本概念：

组合（composition）：正整数的有序和。例如，3的组合有：1+1+1, 1+2, 2+1, 3
n-着色组合：组合中每个大小为k的部分可以从1到k中选择一个颜色，用下标表示
(m,k)-n-着色组合：位置为k (mod m)的部分进行n-着色，其他部分不着色

特殊情况：

EVEN着色组合：(2,0)-n-着色组合，即偶数位置着色
ODD着色组合：(2,1)-n-着色组合，即奇数位置着色

生成函数方法

基本构建块

非着色部分的生成函数： $x + x^2 + x^3 + \cdots = \frac{x}{1-x}$
n-着色部分的生成函数： $x + 2x^2 + 3x^3 + \cdots = \frac{x}{(1-x)^2}$

这是因为大小为k的部分有k种颜色选择。

EVEN着色组合

分两种情况：

奇数个部分：至少一个非着色部分，后接任意多对（着色部分+非着色部分） $\frac{x}{1-x} \sum_{i=0}^{\infty} \left(\frac{x^2}{(1-x)^3}\right)^i = \frac{x(1-x)^2}{(1-x)^3 - x^2}$
偶数个部分：正数对（着色部分+非着色部分） $\sum_{i=1}^{\infty} \left(\frac{x^2}{(1-x)^3}\right)^i = \frac{x^2}{(1-x)^3 - x^2}$

总生成函数： $F_e(x) = \frac{x^3 - x^2 + x}{-x^3 + 2x^2 - 3x + 1}$

对应OEIS序列A034943。

ODD着色组合

类似分析得到生成函数： $F_o(x) = \frac{x}{-x^3 + 2x^2 - 3x + 1}$

对应OEIS序列A095263。

一般(m,k)-n-着色组合

按部分数量模m分三种情况：

0 (mod m)：每m个部分中有1个着色、m-1个非着色
j (mod m), 1≤j≤k-1：j个非着色部分加上情况1
ℓ (mod m), k≤ℓ≤m-1：ℓ-1个非着色部分+1个着色部分加上情况1

双射构造方法

本文的核心技术创新在于构造了多个精巧的双射。

与限制颜色2的组合的双射（定理3.1）

映射方向1（限制颜色2 → EVEN着色）：

从左到右处理每个部分
对于奇数位置的着色部分p_c（c≥3），拆分为：(c-2) + (p-c+2)_2
奇数位置颜色为1的部分去掉颜色

逆映射：

对于偶数位置的颜色2部分q_2，与前一个部分p合并为(p+q)_{p+2}

例子：3_3, 1_1, 6_4, 4_4 → 1, 2_2, 1, 6_4, 2, 2_2

与(n choose 2)-着色组合的双射（定理3.2）

这是ODD着色组合与(n choose 2)-着色组合（每个部分有两个不同的spot）之间的双射。

映射（ODD着色 → (n choose 2)-着色）：

偶数个部分：每两个相邻tile合并为一个tile，保持spots位置，最后tile扩展一个无spot单元
奇数个部分：先在末尾添加一个spotted单元，然后执行上述操作

逆映射：在第二个spot之前切割每个tile，删除最后一个单元。

与三进制字符串的双射（定理3.3）

EVEN着色组合 ↔ 限制连续数字、不以2开头、不以0结尾的三进制字符串

映射规则（基于spotted tiling表示）：

tile内部的线 → 1
spot前的线 → 0
spot后的线 → 2
奇数位置部分末尾的线 → 1

约束保证：

0后面只能是0或2
1后面只能是1或0
不能以2开头（0必须在第一个2之前）
不能以0结尾

与二进制字符串的双射（定理3.4）

EVEN着色组合的数量 = 所有k长二进制字符串中1-runs长度乘积的总和

映射：

在二进制串前加0
连续的0或1子串映射为相应大小的部分
0子串 → 奇数位置部分（非着色）
1子串 → 偶数位置部分（着色）
每个EVEN着色组合对应的颜色选择数 = 偶数位置部分大小的乘积

与321-避免可分离排列的双射（定理3.7）

使用标记二叉树结构：

映射（排列 → EVEN着色组合）：

对于每个负节点：左子树a个叶子+右子树b个叶子 → 着色部分(a+b-1)_a（偶数位置）
负节点间的c个连续递增叶子 → 非着色部分c+1（奇数位置）

逆映射：

奇数位置部分减1 → 负节点间的叶子数
偶数位置部分加1并按颜色分配 → 负节点下的叶子分布

实验设置

数据验证

本文是纯理论组合数学论文，没有传统意义上的实验。验证方式包括：

OEIS序列验证：通过OEIS数据库验证计数序列
- A034943：EVEN着色组合
- A095263：ODD着色组合
小规模枚举验证：通过手工枚举小整数的情况验证公式
双射正确性：通过具体例子展示双射的构造过程

理论工具

生成函数理论
双射证明方法
Spotted tiling可视化表示

实验结果

主要结果

本文的"结果"体现在建立的等价关系：

定理3.1：EVEN着色组合 ≡ 限制颜色2的n-着色组合
- 提供了基于spotted tiling的构造性双射
定理3.2：ODD着色组合(k) ≡ (n choose 2)-着色组合(k+1)
- 解释了OEIS中观察到的序列关系
推论1：ODD着色组合(k) ≡ 01-和12-避免的长度k-1三进制字符串
- 间接建立了与文献3的联系
定理3.3：EVEN着色组合(k) ≡ 限制连续数字的特定三进制字符串(长度k)
定理3.4：EVEN着色组合(k+1) = Σ(k长二进制串中1-runs长度乘积)
定理3.5：ODD着色组合(k) = Σ(以1开头的k长二进制串中1-runs长度乘积)
定理3.7：EVEN着色组合(k) ≡ 321-避免可分离排列(k)

恒等式证明

定理3.6：对于任意k≥1, ℓ≥2, 1≤m≤ℓ-1： $c_{m,k+1}(\ell+1) = c_{m,k+1}(\ell) + c_{m,k}(\ell)$

特殊情况e(k+1) = e(k) + o(k)的组合证明：

EVEN着色组合(k+1)首部分为1 → 删除得ODD着色组合(k)
EVEN着色组合(k+1)首部分>1 → 减1得EVEN着色组合(k)
这给出了双射到不相交并集

案例分析

例1（定理3.1）：

限制颜色2：3_3, 1_1, 6_4, 4_4
映射过程：3_3拆为1+2_2；1_1保持；6_4保持；4_4拆为2+2_2
结果：1, 2_2, 1, 6_4, 2, 2_2（EVEN着色）

例2（定理3.2）：

ODD着色：4_2 + 3_1 + 5_4 + 2_1 + 1_1 = 15
映射到(n choose 2)-着色：7_{2,5} + 7_{4,6} + 2_{1,2} = 16

例3（定理3.3）：

EVEN着色：1 + 2_i + 1 + 6_j + 4（i∈{1,2}, j∈{1,...,6}）
映射到三进制串：00200002221111

例4（定理3.7）：

321-避免可分离排列：(1,2,6,7,3,4,5,8,9,10,12,13,11)
通过二叉树表示映射到：3 + 4_2 + 4 + 2_2

理论发现

统一框架：位置着色组合为多个看似无关的组合对象提供了统一的计数框架
生成函数的威力：通过生成函数的分析，能够系统地处理位置依赖的着色规则
双射的构造性：所有双射都是构造性的，提供了对象间转换的明确算法
可视化的重要性：Spotted tiling表示在构造双射中起到关键作用

理论贡献：
- 定义并研究了位置着色组合这一新的组合对象
- 通过生成函数获得了精确的计数公式
- 建立了与至少6类其他组合对象的等价关系
方法论贡献：
- 展示了生成函数在处理位置依赖规则中的有效性
- 提供了多个精巧的双射构造，丰富了组合证明技术
- Spotted tiling表示被证明是强有力的可视化和构造工具
连接性发现：
- 揭示了限制颜色组合、(n choose 2)-着色组合、三进制字符串、二进制字符串runs、可分离排列等对象的深层联系
- 这些联系不仅是计数上的等价，更有明确的双射构造

局限性

一般情况未充分探索：
- 第2.3节给出了(m,k)-n-着色组合的生成函数，但与其他组合对象的联系仅限于m=2的情况
- 一般m值下的组合解释尚待研究
部分证明的间接性：
- 推论1（ODD着色组合与三进制字符串）是通过定理3.2和文献3间接得到的
- 直接的组合证明可能提供更深刻的洞察
推广的系统性：
- 虽然给出了定理3.6的推广，但其他结果的推广尚不系统
- 限制其他颜色组合的情况（如第3.1节提到的）未充分研究
计算复杂性：
- 未讨论生成和枚举这些组合的算法复杂性
- 双射的计算效率未分析

未来方向

论文第4节明确提出：

一般位置着色组合的组合解释：
- 研究(m,k)-n-着色组合与其他组合对象的联系
- 寻找一般m,k值下的双射
推论1的直接证明：
- 构造ODD着色组合与01-和12-避免三进制字符串的直接双射
- 推广此结果到其他情况
限制颜色的位置着色组合：
- 结合第3.1节的想法，研究限制特定颜色的位置着色组合
- 探索这类组合的有趣性质
其他位置规则：
- 考虑更复杂的位置依赖着色规则
- 如：着色依赖于部分大小和位置的组合
算法和计算方面：
- 开发高效的生成和枚举算法
- 研究随机采样方法

深度评价

优点

概念创新性强：
- 位置着色组合是自然且有意义的推广
- 统一了多个已知的组合对象
- 开辟了新的研究方向
技术严谨性高：
- 生成函数推导清晰完整
- 双射构造详细且可验证
- 所有主要结果都有严格证明
双射构造精巧：
- 与321-避免可分离排列的双射（定理3.7）特别巧妙，利用了二叉树结构
- 与三进制字符串的双射（定理3.3）优雅地利用了spotted tiling的线分割
- 与二进制字符串runs的联系（定理3.4）揭示了深刻的计数原理
可视化效果好：
- Spotted tiling表示直观清晰
- 图示（如图2-6）有效辅助理解
- 例子选择恰当，覆盖关键情况
连接性丰富：
- 建立了与6类不同组合对象的等价关系
- 每个联系都有组合意义
- 为未来研究提供了多个切入点
写作清晰度高：
- 结构组织合理，从特殊到一般
- 定义明确，符号一致
- 证明思路清晰，易于跟随

不足

推广的不完整性：
- 一般(m,k)情况的组合解释缺失
- 第2.3节的生成函数公式未得到充分利用
- 这限制了理论的完整性
部分证明的间接性：
- 推论1依赖文献3的结果
- 直接构造性证明可能更有启发性
- 这也是作者在第4节承认的不足
计算方面的缺失：
- 未讨论算法复杂性
- 未提供实现或代码
- 对于实际应用价值有限
与已有工作的对比不够深入：
- 虽然引用了相关文献，但未详细对比方法和结果
- 本文方法相对于已有方法的优势未充分阐述
应用场景不明确：
- 作为纯理论工作，未讨论实际应用
- 位置着色组合的实际意义未探讨
- 这可能限制读者的兴趣
某些证明细节可以更详细：
- 如定理3.7的逆映射，关于如何从部分大小恢复完整的排列，细节略显不足
- 双射的单射性和满射性有时需要读者自己验证

影响力评估

理论价值高：
- 为整数组合理论贡献了新的变体
- 揭示了多个组合对象间的深层联系
- 生成函数和双射方法具有示范意义
方法论贡献：
- 展示了如何系统地研究位置依赖的组合结构
- Spotted tiling的使用为其他问题提供了工具
- 双射构造技术可以启发类似研究
后续研究潜力大：
- 第4节提出的多个开放问题值得探索
- 可推广到其他类型的组合对象
- 可能与其他数学领域（如代数、拓扑）产生联系
可复现性强：
- 所有构造都是明确的算法
- 生成函数可以用于计算验证
- OEIS序列提供了独立验证途径
教学价值：
- 适合作为组合数学课程的补充材料
- 展示了生成函数和双射证明的威力
- 例子丰富，适合学习

适用场景

组合数学研究：
- 整数组合及其变体的研究者
- 生成函数理论的研究
- 双射组合学的研究
相关领域：
- 可分离排列的研究（与定理3.7相关）
- 字符串组合学（与定理3.3、3.4相关）
- 格路径和tilings理论
教育应用：
- 组合数学课程的案例研究
- 生成函数方法的教学示例
- 双射证明技术的训练
潜在应用（需进一步研究）：
- 编码理论（通过字符串的联系）
- 算法分析（通过排列的联系）
- 概率论（组合结构的随机性质）

参考文献（关键文献）

1 A.K. Agarwal, "n-colour compositions", Indian J. Pure Appl. Math. 31(2000) 1421–1437.

首次引入n-着色组合概念的开创性工作

2 B. Hopkins, H. Wang, "Restricted Color n-color Compositions", Journal of Combinatorics, 12 (2021), 355-377.

研究限制颜色的组合，与本文定理3.1直接相关

3 C. Dedrickson, "Compositions, Bijections, and Enumerations" (2012), Electronic Theses and Dissertations. 17.

建立(n choose 2)-着色组合与三进制字符串的双射，本文推论1的基础

6 B. Hopkins, "Spotted tilings and n-color compositions", Integers 12B (2012) Article A6

引入spotted tiling表示，本文的核心可视化工具

总体评价

这是一篇高质量的组合数学理论论文，具有以下突出特点：

创新性：引入了位置着色组合这一新概念，为整数组合理论提供了有价值的推广。
深度：不仅给出计数公式，更重要的是建立了与多个组合对象的深刻联系，每个联系都有严格的双射证明。
完整性：从定义、生成函数、特殊情况到一般情况，再到与其他对象的联系，逻辑结构完整。
技术性：生成函数推导和双射构造都显示了作者扎实的组合数学功底。
启发性：为后续研究提供了多个明确的方向，具有较强的延续性。

建议改进方向：

补充一般(m,k)情况的组合解释
提供推论1的直接证明
增加算法和计算方面的讨论
探索实际应用场景

总体而言，这是一篇值得发表的优秀论文，对组合数学领域有实质性贡献，特别适合对整数组合、生成函数和双射证明感兴趣的研究者阅读。