广义Pòlya组合计数方法

A Generalized Form of Polya's Counting Method

文中引入了P-置换图的概念．作为置换群的指标多项式和函数等价类配置多项式的推广形式分别定义了P-置换图的容量指标多项式与色权多项式,并给出了递归公式和相关定理,由此建立了计算P-置换图的色权多项式的一般方法和P-置换图的色轨道多项式的表达公式．Polya计数定理是这一公式当约束图是空图时的特例．最后给出了P-置换图的色权多项式的一些基本性质和两个计算实例．

The P-permutation graphs, or simply P-graphs, are introduced. The chromatic weight polynomial of a P-graph, or the chromatic orbit weight polynomial of a graph, as a generalized form of the inventory of a set of equivalence classes of functions, and the capacity index of a P-graph, as a generalized form of the cycle index of a permutation group P, are defined. Other relevant notions such as partition graphs, SC-graphs, etc. are discussed. Reduction Formulas and other Theorems as tools for calculating the chromatic weight polynomial of a P-graph are obtained. The expressions of the chromatic weight polynomial of P-graphs are also established. Pblya＇s Theorem can be got from the expressions as a special case when the graph is empty. Finally, some elementary properties of the chromatic weight polynomials of P-graphs are presented.