Generalized Parking Functions, Tree Inversions, and Multicolored Graphs
Generalized Parking Functions, Tree Inversions, and Multicolored Graphs
复制标题
DOI：
10.1006/aama.2001.0754
复制
发表时间：
2001-08
期刊：
影响因子：
--
通讯作者：
C. Yan
中科院分区：
文献类型：
--
作者：
C. Yan
与 (a,b,b,...,b) 形式的正整数向量关联的广义 x-parking 函数是正整数序列 (a"1,a"2,...,a"n)，其非递减重排 b"[email protected]?b"[email protected][email protected]?b"n 满足 b"[email protected]?a+(i-1)b。x-parking 函数集有 与 [n] 上有根 b 森林的序列集具有相同的基数。我们在这两个集合之间构建双射。通过生成函数分析，我们证明了 x-parking 函数的补集的和枚举器与有根 b-森林序列的逆枚举器相同。有根森林序列和 x-parking 函数之间的组合对应关系也以深度优先搜索和 彩色图上的广度优先搜索。
A generalized x-parking function associated to a positive integer vector of the form (a,b,b,...,b) is a sequence (a"1,a"2,...,a"n) of positive integers whose nondecreasing rearrangement b"[email protected]?b"[email protected][email protected]?b"n satisfies b"[email protected]?a+(i-1)b. The set of x-parking functions has the same cardinality as the set of sequences of rooted b-forests on [n]. We construct a bijection between these two sets. We show that the sum enumerator of complements of x-parking functions is identical to the inversion enumerator of sequences of rooted b-forests by generating function analysis. Combinatorial correspondences between the sequences of rooted forests and x-parking functions are also given in terms of depth-first search and breadth-first search on multicolored graphs.