On this page
Questions like "In how many ways can 5 strips of a flag be coloured with 4 colours so that no two neighbouring strips match?" are standard Class 11 counting practice. You need the multiplication principle, applied one region at a time, plus one extra idea for rings.
How many ways can you colour a row of regions so neighbours differ?
The NCERT Class 11 textbook states the fundamental principle of counting: "If an event can occur in m different ways, following which another event can occur in n different ways, then the total number of occurrence of the events in the given order is m×n."
Colour the row from left to right:
The first region can take any of the k colours.
The second region can take anything except the first region's colour, so k−1 choices.
Every later region touches only the one just before it, so it also has k−1 choices, whatever colours came earlier.
A row of n regions therefore has k(k−1)^(n−1) colourings with neighbours different, which is the path-graph formula on Wolfram MathWorld's chromatic polynomial page.
Worked example: 5 flag strips and 4 colours give 4 × 3 × 3 × 3 × 3 = 324 ways.
Why doesn't the same trick work for a ring?
In a ring, the last region touches both the region before it and region 1. If those two match, the last region has k−1 choices; if they differ, it has k−2. The multiplication principle needs a fixed number of choices at each step, so a single product fails.
The common wrong answer is k(k−1)^(n−2)(k−2). For a ring of 4 regions and 3 colours it gives 3 × 2 × 2 × 1 = 12, but the true count is 18. It gives the last region too few choices whenever regions 1 and 3 share a colour.
How do you count ring colourings region by region?
Cut the ring between the last region and region 1, and it becomes a row. Write C(n) for the number of good ring colourings. Each good row colouring is one of two kinds:
Ends different: this is exactly a good ring colouring. There are C(n) of these.
Ends the same: glue region 1 and region n into one region and you get a good ring of n−1 regions. There are C(n−1) of these.
So k(k−1)^(n−1) = C(n) + C(n−1). Start from a ring of 3, where every region touches the other two, so C(3) = k(k−1)(k−2). Then build up. With k = 4:
C(3) = 4 × 3 × 2 = 24
C(4) = 4 × 27 − 24 = 84
C(5) = 4 × 81 − 84 = 240
C(6) = 4 × 243 − 240 = 732
The closed form is (k−1)^n + (−1)^n(k−1), the cycle-graph formula given in Wikipedia's chromatic polynomial article and on MathWorld. Check it for n = 6 and k = 4: 3^6 + 3 = 732. You can also check that it obeys the recurrence: adding the formulas for n and n−1, the (−1) terms cancel and (k−1)^n + (k−1)^(n−1) = k(k−1)^(n−1). Our guide to finding the nth term of a recurrence relation covers the same idea.
What about a ring with a centre region?
Picture a disc divided into a central circle and n sectors around it. The centre touches every sector. Colour it first, in k ways, and the sectors form a ring that can use only the other k−1 colours. With 5 colours and 4 sectors, that is 5 × C(4) with 4 colours, or 5 × 84 = 420 ways.
If your answer still disagrees with the key, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer, so you can see which step went wrong.
Where does this way of counting come from?
George D. Birkhoff treated the number of colourings as a polynomial in the number of colours in his 1912 paper A Determinant Formula for the Number of Ways of Coloring a Map. Wikipedia's chromatic polynomial article notes he hoped to prove the four colour theorem by showing the count is always positive with 4 colours. The proof came by another route: read how Appel and Haken proved the four colour theorem by computer, or try four colour map colouring on a map of India.
A four-step checklist for any adjacent-regions question
Draw each region as a dot; join dots whose regions share a border.
Find an order where each new region touches only one coloured region. Then multiply: k, then k−1 each time.
If a region closes a loop, split into "ends same" and "ends different", or use the ring formula.
Test with 2 colours or 3 regions, where you can list every colouring.
If the counting basics feel shaky, the Fermi Concept Library covers every concept in mathematics, each with its own lesson and its place in the map.
