Polya Enumeration Calculator

Enter the number of positions and colors to count distinct circular colorings up to rotation.

Result

130
729
6
3

How it is calculated

The tool counts circular colorings of n positions with k colors where rotating a pattern does not make it new (reflections are not merged). By Burnside's lemma the answer is (1 ÷ n) × Σ φ(d) × kn/d, summed over every divisor d of n, where φ(d) is Euler's totient: the count of numbers from 1 to d that share no factor with d. It also shows the raw total kn before any rotations are merged.

The arithmetic is done on exact big integers and the results are printed with thousands separators, so large results do not lose digits (4 colors on 12 positions give 1,398,500 patterns). Both inputs must be whole numbers: n from 1 to 30 and k from 1 to 1,000,000,000. A decimal, a zero or a value outside those limits gives no result. With one color the answer is always 1. Flipping the necklace over is counted as different, so the result is for rotations only.

Worked example

Beads on a bracelet: n = 6 positions, k = 3 colors. Total colorings 36 = 729. Divisors of 6 are 1, 2, 3, 6 with φ = 1, 1, 2, 2. Terms: 1 × 36 = 729, 1 × 33 = 27, 2 × 32 = 18, 2 × 31 = 6. Sum = 780. Divide by n: 780 ÷ 6 = 130 distinct patterns up to rotation, out of 729 raw colorings.

Try this example →

Common mistakes

  • Expecting mirror images to be merged. Only rotations are treated as the same, so a pattern and its reflection can be counted twice. Counting bracelets that can be flipped needs a different formula.
  • Dividing the total kn by n. That gives 121.5 for 6 positions and 3 colors, because many patterns (like all one color) are unchanged by rotation and are not counted n times.
  • Entering the number of colors you actually use in a pattern. k is the number of colors available, and a pattern is allowed to leave some of them out.
  • Typing n above 30 or a decimal such as 5.5. Both give no result: the tool refuses a fractional count of positions or colors instead of rounding it.
  • Assuming positions are on a line. For beads in a row the count is simply kn; the rotation merging applies only to a closed circle.

Sources

About this calculator

Pólya enumeration counts how many genuinely distinct ways there are to color n positions arranged in a circle with k colors, treating rotations of the same pattern as identical rather than counting them separately. It works via Burnside's lemma: the count equals the average, over every rotation, of the number of colorings that rotation leaves unchanged — which simplifies to (1/n)·Σ φ(d)·k^(n/d) summed over the divisors d of n, using Euler's totient function φ.

This is the classic “how many distinct necklaces” problem from combinatorics, and the same math shows up wherever you need to count arrangements under a symmetry group — computer scientists counting distinct circular data structures, and chemists counting distinct molecular isomers of ring-shaped compounds where rotating the ring doesn't create a new molecule.

Was this helpful?

You can pick up to 3 reactions.

Comments

  • Be the first to comment.

Popular calculators

All Calculators