A Bijection between Necklaces and Multisets with Divisible Subset Sum
A Bijection between Necklaces and Multisets with Divisible Subset Sum
复制标题
DOI：
10.37236/7804
复制
发表时间：
2018-02
期刊：
影响因子：
--
通讯作者：
Swee Hong Chan
中科院分区：
文献类型：
--
作者：
Swee Hong Chan
考虑这两个不同的组合对象：(1)长度为$n$的项链，其颜色最多为$q$;(2)以$n$为模的整数多集，其子集和可被$n$整除，且每个元素的多重性严格小于$q$。我们证明，如果$q$和$n$互为互素数，这两个对象具有相同的基数。此外，当$q$是素数幂时，我们通过将项链视为大小为$q$的有限域上的循环多项式来构造这两个对象之间的双射。专门研究$q=2$回答了Richard Stanley （enumative Combinatorics Vol. 1, Chapter 1, problem 105(b)）提出的一个客观问题。
Consider these two distinct combinatorial objects: (1) the necklaces of length $n$ with at most $q$ colors, and (2) the multisets of integers modulo $n$ with subset sum divisible by $n$ and with the multiplicity of each element being strictly less than $q$. We show that these two objects have the same cardinality if $q$ and $n$ are mutually coprime. Additionally, when $q$ is a prime power, we construct a bijection between these two objects by viewing necklaces as cyclic polynomials over the finite field of size $q$. Specializing to $q=2$ answers a bijective problem posed by Richard Stanley (Enumerative Combinatorics Vol. 1 Chapter 1, Problem 105(b)).