TheoremStatement: Literature-sourcedProof: Literature-sourcedaudited 2026-08-28

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The weighted pattern inventory is the cycle index evaluated at the power sums

Statement

Let a finite group $G$ act on a finite set $X$ , let $C$ be a finite colour set, let $R$ be a commutative ring, and let $w : C \to R$ be a weight function. For each $d \geq 1$ , put

$p_{d} : = \sum_{c \in C} w (c)^{d} .$

Then

$∣ G ∣ I_{G} (X, C; w) = \sum_{g \in G} \prod_{d \geq 1} p_{d}^{j_{d} (g)} .$

If moreover the scalar $1 / ∣ G ∣$ is defined in $R$ (in particular if $R$ is a commutative $Q$ -algebra), then equivalently

$I_{G} (X, C; w) = Z_{G} (p_{1}, p_{2}, \dots, p_{∣ X ∣}) .$

Facts & Assumptions

Given: the action $G ↷ X$ , the colour set $C$ , and the weight function $w : C \to R$ .

[F1]

The pattern inventory is the sum of the common orbit weights of the colouring orbits, and the induced action preserves colouring weights (Colourings, weight functions, and the pattern inventory).

[L1]

The weighted sum of the colourings fixed by one group element factors as $\prod_{d} p_{d}^{j_{d} (g)}$ (Fixed colourings factor by cycle type).

[L2]

Cauchy-Frobenius orbit counting averages fixed-point counts for any finite group action (Cauchy-Frobenius orbit counting: $∣ G ∣ ∣ X / G ∣ = \sum_{g \in G} ∣ X^{g} ∣$ for a finite group action).

Proof

technique · direct

1.1F1L2

Because weights are preserved on orbits by [F1], the colouring set $C^{X}$ splits into finitely many $G$ -stable blocks according to the value $u$ of $wt (f)$ . For one such value $u$ , let $C_{u}$ be the set of colourings of weight $u$ . Applying [L2] to the induced action on the finite set $C_{u}$ gives $∣ G ∣ ∣ C_{u} / G ∣ = \sum_{g \in G} ∣ C_{u}^{g} ∣$ .

2.1step 1.1F1

Multiply the identity of step 1.1 by $u$ and sum over all weight values $u$ . The left-hand side becomes $∣ G ∣ I_{G} (X, C; w)$ by [F1], while the right-hand side becomes $\sum_{g \in G} \sum_{\begin{array}{c} f : X \to C \\ g \cdot f = f \end{array}} wt (f)$ .

3.1step 2.1L1∎

Replace the inner weighted fixed-colouring sum in step 2.1 by [L1]. This gives $∣ G ∣ I_{G} (X, C; w) = \sum_{g \in G} \prod_{d \geq 1} p_{d}^{j_{d} (g)}$ . When $1 / ∣ G ∣$ is defined in $R$ , divide by $∣ G ∣$ to obtain $I_{G} (X, C; w) = Z_{G} (p_{1}, p_{2}, \dots, p_{∣ X ∣})$ .

Depends on

Used by

The substitution xᵢ=xⁱ can erase colour-profile information Counterexample
Pattern inventory of square colourings by number of red vertices Example
FALSE: every weight substitution collapses the pattern inventory to the plain orbit count False statement
Pólya enumeration counts edge-set orbits on the 2-subsets of [n] Theorem

Dependency tree · two levels

15 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Ben Lynn, Polya Theory: Pólya's Inventory Theorem (standard reference, not scraped)