ConverterHub

Polya Enumeration Calculator

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

How it is calculated

The tool counts circular colourings of n positions with k colours 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 colours 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 colour 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 colours. Total colourings 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 colourings.

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 colours, because many patterns (like all one colour) are unchanged by rotation and are not counted n times.
  • Entering the number of colours you actually use in a pattern. k is the number of colours 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 colours 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.

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

Loan Calculator

Monthly payment, total interest and full amortization schedule.

Percentage Calculator

Percent change, percent of, and ratio calculations.

Discount Calculator

Calculate final price, savings, and discount amount.

BMI Calculator

Body mass index from height and weight (metric or imperial).

Age Calculator

Compute your exact age in years, months and days from a birth date.

Compound Interest Calculator

Calculate the final amount and interest earned with compounding.

All Calculators