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.

Pólya enumeration counts edge-set orbits on the 2-subsets of [n]

Statement

Let $E_{n} = [n]^{2}$ be the set of two-element subsets of $[n]$ , and let $S_{n}$ act on $E_{n}$ by

$σ \cdot {i, j} : = {σ (i), σ (j)} .$

$F_{n} (x) : = \sum_{O} x^{∣ A ∣},$

where the sum runs over the $S_{n}$ -orbits $O$ of edge-sets $A \subseteq E_{n}$ and, for each orbit $O$ , $A$ denotes any member of $O$ (so $∣ A ∣$ is well defined), then

$F_{n} (x) = Z_{S_{n} ↷ E_{n}} (1 + x, 1 + x^{2}, \dots, 1 + x^{∣ E_{n} ∣}) .$

Facts & Assumptions

Given: an integer $n \geq 0$ .

[F1]

A subset $A \subseteq E_{n}$ is exactly a $0$ - $1$ colouring of the pair set $E_{n}$ : colour a pair black when it lies in $A$ and white otherwise.

[L1]

The pair set $E_{n}$ is finite, with $∣ E_{n} ∣ = (\binom{n}{2})$ (A finite set with $n$ elements has exactly $(\binom{n}{2})$ two-element subsets, and $2 (\binom{n}{2}) = n (n - 1)$ ).

[L2]

Weighted Pólya enumeration evaluates the orbit inventory at the power sums of the colour weights (The weighted pattern inventory is the cycle index evaluated at the power sums).

Proof

technique · direct

1.1F1L1

By [F1], edge-sets on $[n]$ are exactly colourings of the finite set $E_{n}$ by the two colours white and black. The induced action of $S_{n}$ on those colourings is exactly the relabelling action on edge-sets.

2.1step 1.1algebra

Give white weight $1$ and black weight $x$ . Then the weight of a colouring corresponding to $A \subseteq E_{n}$ is precisely $x^{∣ A ∣}$ . The $d$ -th power sum of the two colour weights is therefore $1^{d} + x^{d} = 1 + x^{d}$ .

3.1step 2.1L2∎

Apply [L2] to the action of $S_{n}$ on the colourings of $E_{n}$ . By step 2.1, the resulting pattern inventory is exactly $Z_{S_{n} ↷ E_{n}} (1 + x, 1 + x^{2}, \dots, 1 + x^{∣ E_{n} ∣})$ , and by the definition of weight it is also exactly $\sum_{O} x^{∣ A ∣} = F_{n} (x)$ , where for each orbit $O$ the symbol $A$ denotes any member of $O$ .

Depends on

Used by

There are 11 S₄-orbits of edge-sets on the pairs of [4] Example

Dependency tree · two levels

19 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

Applied Combinatorics, Section 15.5: Applications of Pólya's Enumeration Formula (standard reference, not scraped)