MGU Mathematics Series — Combinatorics
Part V: Graphs, Designs, and Capstone Applications
Latin Squares · Block Designs · Symmetry · Burnside's Lemma
Chapter 13 of 14
MGU Mathematics Series  ·  Combinatorics  ·  Library Textbook Edition

Chapter 13:
Designs, Finite Structures,
and Symmetry

Latin squares, block designs, finite geometries, tournament schedules, symmetry groups, and Burnside's Lemma — the combinatorics of structure, balance, and equivalence

■ Math Level: Combinatorics ■

■ 14 Sections  •  Part V of 5 ■

Follows Chapter 12: Graph Counting  ·  Prepares students for Chapter 14: Capstone Applications

Chapter 13 — Front Matter

Purpose and Overview

This chapter studies combinatorics from a different angle than simple counting. In earlier chapters, the central question was: how many arrangements or selections are there? In this chapter, the question expands: can an arrangement satisfying certain rules even be built, and when are two arrangements really the same thing?

These are the questions of combinatorial design theory and symmetry. They arise naturally in scheduling tournaments fairly, designing scientific experiments so every treatment pair is compared the same number of times, constructing codes, arranging symbols in grids without repetition in any row or column, and counting colorings where rotating or reflecting a figure does not produce a genuinely new pattern.

This chapter introduces the major ideas at an accessible level. Students who continue into abstract algebra, coding theory, experimental design, graph theory, or discrete mathematics will encounter all of these ideas again in greater depth.

Opening Question

A pharmaceutical researcher wants to compare four experimental drugs. She has enough resources to test each pair of drugs together exactly once, and she wants each drug to appear in the same number of tests. She also wants each test group to contain exactly two drugs. Can she build a schedule satisfying all these conditions? If she relabels the drugs, does that produce a genuinely new schedule, or just a renamed version of the same one? These questions require the ideas of this chapter.

14Sections
11Objectives
18Key Terms
6Worked Examples

Learning Objectives

  1. 1Explain what a combinatorial design is and why designs require conditions beyond simple counting.
  2. 2Construct and verify Latin squares of small orders.
  3. 3Explain what a block design is and what the parameters v, b, r, k, and λ mean.
  4. 4Determine whether a block design with given parameters is feasible based on necessary conditions.
  5. 5Construct and analyze round-robin tournament schedules for small numbers of teams.
  6. 6Explain what a finite geometry is at a preview level.
  7. 7Explain what it means for two arrangements to be equivalent under a symmetry.
  8. 8List the symmetries of regular polygons and simple three-dimensional objects.
  9. 9Apply Burnside's Lemma to count the number of truly distinct arrangements under a set of symmetries.
  10. 10Recognize when symmetry changes a counting answer.
  11. 11Connect design theory to scheduling, coding, and experimental applications.
Chapter 13 — Contents

Sections at a Glance

Sections 13.1 – 13.3
What Is a Design? Conditions and Latin Squares
Combinatorial Designs · Structured Arrangements · Latin Squares · Orthogonal Squares
Section 13.1

What a Combinatorial Design Is

In earlier chapters, the central problems of counting asked for the number of ways to arrange or select objects from a set. Chapter 3 counted ordered arrangements. Chapter 4 counted unordered selections. Chapter 6 distributed objects into boxes. These techniques answer the question how many?

A combinatorial design asks a different question. It asks whether an arrangement satisfying a collection of balance conditions can exist, and if so, what it looks like. The arrangement itself is the object of study, not merely its count.

To understand why balance conditions matter, consider a sports league with six teams. The league wants every pair of teams to play each other exactly once. It also wants every team to play the same total number of games. Can such a schedule be built? How many games will each team play? How many total games will there be? These are structural questions — not answered by listing all possible pairings, but by reasoning about what conditions any valid schedule must satisfy.

What Makes a Design

A combinatorial design is a collection of subsets, called blocks, chosen from a finite set of objects or points, such that every object and every pair of objects appears in the design with a controlled frequency. The power of this framework is that it connects counting, algebra, and structure.

Section 13.2

Arranging Objects Under Conditions

Condition TypeWhat It RequiresExample
FrequencyEach object appears a prescribed number of timesEvery team plays exactly 5 games
Pair coverageEvery pair appears together a prescribed number of timesEvery pair of treatments tested together exactly twice
SeparationCertain objects must not appear togetherTwo chemically reactive compounds never in the same trial
UniformityEvery block must have the same sizeEvery test group has exactly 3 participants

The approach to structured arrangements follows a consistent pattern: identify the objects and blocks; state the conditions precisely; derive necessary numerical conditions from algebra; check whether those conditions can be satisfied; then attempt to construct an example. Steps one through four are accessible at this level. The construction step can range from straightforward for small cases to an open research problem for large ones.

Necessary conditions from double counting are especially useful. If a condition must hold for a design to exist, any design with those parameters must satisfy it. But satisfying a necessary condition does not guarantee the design exists — it only rules out immediate impossibility.

Section 13.3

Latin Squares

Definition — Latin Square

A Latin square of order n is an n × n grid filled with n distinct symbols such that each symbol appears exactly once in every row and exactly once in every column.

The simplest nontrivial example is a Latin square of order 2, using symbols 1 and 2. A Latin square of order 3 uses symbols 1, 2, and 3 in a 3 × 3 grid. The name comes from the work of Leonhard Euler, who studied them in the eighteenth century using Latin letters.

Order 2
1
2
2
1
Order 3
1
2
3
2
3
1
3
1
2
Order 4 (cyclic)
0
1
2
3
1
2
3
0
2
3
0
1
3
0
1
2

Counting Latin Squares

Order nNumber of Latin Squares
11
22
312
4576
5+Grows very rapidly; no simple closed formula
Cyclic Construction

Place symbols 0, 1, 2, …, n−1 in the first row. For each subsequent row, shift all symbols one position to the right, wrapping around. This works for any n and produces a valid Latin square, though not the only one of order n.

Example 13.3.1
Verifying a Latin square of order 4
  • ProblemDetermine whether the 4×4 grid below is a valid Latin square using symbols A, B, C, D.
  • Grid A B C D B A D C C D A B D C B A
  • ThinkA grid is a Latin square if and only if each symbol appears exactly once in every row and exactly once in every column. Check rows, then columns.
  • Analyze Row 1: A, B, C, D — all four symbols, each once. ✓
    Row 2: B, A, D, C — all four symbols, each once. ✓
    Row 3: C, D, A, B — all four symbols, each once. ✓
    Row 4: D, C, B, A — all four symbols, each once. ✓

    Column 1: A, B, C, D — all four symbols, each once. ✓
    Column 2: B, A, D, C — all four symbols, each once. ✓
    Column 3: C, D, A, B — all four symbols, each once. ✓
    Column 4: D, C, B, A — all four symbols, each once. ✓
Answer: The grid is a valid Latin square of order 4 using symbols {A, B, C, D}.

Applications of Latin Squares

DomainHow Latin Squares Are Used
Experimental designAssign n treatments across n time periods and n subjects so every treatment appears once in each row and column, controlling for two confounders simultaneously
SudokuA completed Sudoku is a 9×9 Latin square with the additional constraint that each 3×3 subsquare also contains each symbol exactly once
SchedulingModel round-robin schedules when each participant must face each other participant and each time slot must be filled exactly once
Error-correcting codesFamilies of codes can be constructed using Latin squares and their orthogonal counterparts

Orthogonal Latin Squares

Two Latin squares of order n are called orthogonal if, when one is superimposed on the other, every ordered pair of symbols appears exactly once across the n² cells. Pairs of orthogonal Latin squares are especially useful in experimental design, where two independent factors each need to be controlled, and in certain constructions of codes and designs.

Square 1
0
1
2
1
2
0
2
0
1
Square 2
0
1
2
2
0
1
1
2
0
Superimposed (pairs)
(0,0)
(1,1)
(2,2)
(1,2)
(2,0)
(0,1)
(2,1)
(0,2)
(1,0)

All nine ordered pairs (0,0) through (2,2) appear exactly once. These two squares are orthogonal.

Sections 13.4 – 13.7
Tournaments, Block Designs, and Finite Geometries
Round-Robin Schedules · BIBD Parameters · Fano Plane · Projective Planes
Section 13.4

Tournament Schedules

A round-robin tournament is a competition in which every pair of participants plays each other exactly once. This is one of the most natural structured combinatorial objects: a schedule for the complete graph Kn, where each edge represents a game.

Round-Robin Facts

For n teams, the total number of games is the number of pairs:

C(n, 2) = n(n−1) / 2

Each team plays n − 1 games. If n is even: n − 1 rounds of n/2 games each, with no team idle. If n is odd: n rounds of (n−1)/2 games each, with one team sitting out each round.

Example 13.4.1
Scheduling a six-team round-robin tournament
  • ProblemSchedule a round-robin tournament for 6 teams (labeled 1–6) into rounds. How many rounds? How many games per round?
  • ThinkSince n = 6 is even, there are n − 1 = 5 rounds, each with n/2 = 3 games. Fix team 6 and rotate the remaining 5 teams through a cycle.
  • Analyze Round 1: (6 vs 1), (2 vs 5), (3 vs 4) Round 2: (6 vs 2), (3 vs 1), (4 vs 5) Round 3: (6 vs 3), (4 vs 2), (5 vs 1) Round 4: (6 vs 4), (5 vs 3), (1 vs 2) Round 5: (6 vs 5), (1 vs 4), (2 vs 3)
  • CheckTotal games: 5 × 3 = 15 = C(6,2). ✓ Each team plays in every round. ✓ Each pair plays exactly once. ✓
A 6-team round-robin schedules into 5 rounds of 3 simultaneous games, with every team active each round.
Section 13.5

Block Designs as an Introduction

BIBD — Balanced Incomplete Block Design

A BIBD consists of a set V of v points and b blocks, each of size k, such that every point appears in exactly r blocks and every pair of distinct points appears together in exactly λ blocks. The five parameters (v, b, r, k, λ) specify the structure completely.

Necessary Condition 1: bk = vr (double count point-block incidences)

Necessary Condition 2: r(k−1) = λ(v−1) (count pairs through a fixed point)

Necessary ≠ Sufficient

Satisfying both necessary conditions does not guarantee a design exists. Some parameter sets pass both conditions but no design with those parameters can be constructed. Always treat the conditions as a filter that rules out impossibility, not a proof of existence.

Example 13.5.1
Checking necessary conditions — the Fano plane
  • ProblemA researcher wants v = 7 treatments in blocks of size k = 3, with every pair appearing in exactly λ = 1 block. Is this feasible?
  • ThinkIdentify the parameters and derive the unknowns b and r using the necessary conditions.
  • Derive From Condition 2: r(k−1) = λ(v−1) → r · 2 = 1 · 6 → r = 3
    From Condition 1: bk = vr → b · 3 = 7 · 3 → b = 7
  • Analyze Parameters: (v, b, r, k, λ) = (7, 7, 3, 3, 1) Condition 1: bk = 21 = vr = 21 ✓ Condition 2: r(k−1) = 3·2 = 6 = λ(v−1) = 1·6 ✓
  • InterpretBoth necessary conditions hold. This design does exist — it is the Fano plane, one of the most important objects in combinatorics. Its 7 blocks are: {1,2,4}, {2,3,5}, {3,4,6}, {4,5,7}, {5,6,1}, {6,7,2}, {7,1,3}.
Answer: Parameters (7, 7, 3, 3, 1) pass both necessary conditions. The design exists as the Fano plane.

The Fano Plane — Block Listing

BlockPointsBlockPoints
B₁{1, 2, 4}B₅{5, 6, 1}
B₂{2, 3, 5}B₆{6, 7, 2}
B₃{3, 4, 6}B₇{7, 1, 3}
B₄{4, 5, 7}

Verify: each point 1–7 appears in exactly 3 blocks, and each pair appears in exactly 1 block.

Section 13.6

Balanced Designs as an Introduction

The word "balanced" in design theory has a precise meaning: a design is balanced if every pair of points appears together in the same number λ of blocks. Balance ensures that no pair of objects is treated more or less favorably than any other pair.

Why does balance matter? In a clinical trial comparing v treatments, a balanced design ensures that the comparison between any two treatments is based on the same amount of data. No treatment pair gets more information than another, controlling bias and allowing fair statistical analysis.

Some designs have a further property: their blocks can be partitioned into parallel classes, where each parallel class contains every point exactly once. Such a design is called resolvable. The round-robin tournament from Section 13.4 is resolvable — the rounds form parallel classes since every team plays in every round.

Section 13.7

Finite Geometries as a Preview

A finite geometry is a mathematical structure consisting of a finite set of points and a finite collection of lines (subsets of points) satisfying specified incidence conditions: (1) any two distinct points lie on exactly one common line; (2) any two distinct lines meet in exactly one point; (3) there exist at least four points, no three collinear. These conditions are analogues of Euclidean geometry in a finite setting.

The Fano plane from Section 13.5 is the smallest finite projective plane, called PG(2,2). A finite projective plane of order q has exactly q² + q + 1 points and q² + q + 1 lines, with q + 1 points on every line and q + 1 lines through every point.

Finite Projective Plane of Order q

When q is a prime or prime power, a projective plane of order q always exists. Its parameters as a BIBD are:

v = b = q² + q + 1, r = k = q + 1, λ = 1

For q = 2: the Fano plane. For q = 3: 13 points, 13 lines, 4 points per line. Whether finite projective planes of non-prime-power order exist is one of the great open questions in combinatorics.

MGU Library Connection
  • Coding Theory and Cryptography — finite projective planes and Hamming codes
  • Discrete Mathematics — combinatorial structures and incidence geometry
  • Abstract Algebra — the algebraic foundations of finite fields and geometries
Sections 13.8 – 13.11
Symmetry and Equivalent Arrangements
Labeled vs. Distinct · Rotations and Reflections · Orbits · Group Actions
Section 13.8

Symmetry in Counting

Everything in Chapters 3 through 12 counted labeled arrangements. When permutations counted seating arrangements, each person was considered distinct. When combinations counted committees, the people were distinguishable. But many real counting problems ask for something different: how many essentially different arrangements are there, where two arrangements count as the same if one can be transformed into the other by some natural symmetry?

ProblemNaive CountWhat Symmetry Does
Faces of a cube painted with 2 colors, rotations considered same2⁶ = 64Many paintings are equivalent rotations of each other
Necklace of 6 beads in 2 colors, rotations and flips considered same2⁶ = 64Necklace can be rotated and flipped; many coincide
3 objects at vertices of equilateral triangle, rotations considered same3! = 6Rotations by 120° and 240° identify some arrangements

In each case, symmetry reduces the number of distinct arrangements below the naive count. To count correctly, we need to know: for each symmetry transformation, how many arrangements look the same after that transformation is applied?

Section 13.9

Rotations and Reflections

Symmetries of a Regular n-gon

A regular n-gon has exactly 2n symmetries:

n rotations — by 0°, 360°/n, 2·360°/n, …, (n−1)·360°/n. The 0° rotation is the identity.

n reflections — flip across each of the n axes of symmetry.

The collection of all symmetries of a regular n-gon is called the dihedral group of order 2n.

FigureRotationsReflectionsTotal Symmetries
Equilateral triangle0°, 120°, 240°3 axes (vertex through opposite midpoint)6
Square0°, 90°, 180°, 270°Horizontal, vertical, 2 diagonal axes8
Regular pentagon0°, 72°, 144°, 216°, 288°5 axes through vertex and opposite midpoint10
Regular hexagon0°, 60°, 120°, 180°, 240°, 300°3 through opposite vertices + 3 through edge midpoints12
Section 13.10

Equivalent Arrangements

Two arrangements of objects on a symmetric figure are equivalent if one arrangement can be transformed into the other by applying a symmetry of the figure. The orbit of an arrangement A under a group of symmetries G is the set of all arrangements obtainable from A by applying some symmetry in G.

Two arrangements are equivalent if and only if they belong to the same orbit. The number of truly distinct arrangements equals the number of orbits.

Example 13.10.1
Equivalent colorings of a triangle — direct orbit analysis
  • ProblemColor the vertices of an equilateral triangle using 2 colors (R, B). Two colorings are equivalent if one can be rotated to match the other. How many distinct colorings are there?
  • ThinkWithout symmetry: 2³ = 8 labeled colorings. Rotations by 0°, 120°, 240° may make some equivalent. Group the 8 colorings into orbits.
  • Analyze Orbit 1: {(R,R,R)} — rotating all-red gives all-red.
    Orbit 2: {(R,R,B), (B,R,R), (R,B,R)} — these three are rotations of each other.
    Orbit 3: {(R,B,B), (B,R,B), (B,B,R)} — these three are rotations of each other.
    Orbit 4: {(B,B,B)} — all-blue is fixed by all rotations.
  • CheckTotal arrangements: 1 + 3 + 3 + 1 = 8. ✓ All 8 colorings are accounted for in exactly 4 orbits.
Answer: There are 4 distinct colorings under rotation symmetry — one all-red, one all-blue, one with two reds, one with two blues.
Section 13.11

Group Actions as an Introduction

The mathematical framework formalizing symmetries acting on arrangements is called a group action. A group G is a collection of symmetry transformations that is closed under composition, contains the identity, and contains an inverse for every element.

For counting purposes, the key concept is a fixed arrangement. For a symmetry g ∈ G, an arrangement A is fixed by g if applying g to A leaves A unchanged: g · A = A. Denote by |Fix(g)| the number of arrangements fixed by symmetry g.

Symmetry TypeWhat It Fixes
IdentityEvery arrangement — always contributes the full count |S| to the Burnside sum
Rotation by 360°/nOnly arrangements where all positions in each rotation cycle have the same value
ReflectionOnly arrangements symmetric across the reflection axis — paired positions must match
Sections 13.12 – 13.13
Burnside's Lemma and Applications
Statement · Method · Three Worked Examples · Designs in Practice
Section 13.12

Burnside's Lemma as a Preview

Burnside's Lemma

Let G be a group of symmetries acting on a set S of arrangements. The number of truly distinct arrangements (the number of orbits) is:

Distinct arrangements = (1 / |G|) · Σ |Fix(g)|

That is: the average number of arrangements fixed by each symmetry in G equals the number of distinct arrangements.

Procedure: (1) List all symmetries and count |G|. (2) For each symmetry g, count |Fix(g)|. (3) Sum all |Fix(g)| values. (4) Divide by |G|.

Why It Works (Intuition)

Each orbit contributes exactly 1 to the count of distinct arrangements. Burnside's Lemma shows that each orbit contributes exactly |G| to the total sum Σ|Fix(g)|. Dividing by |G| gives the number of orbits — the number of distinct arrangements.

Example 13.12.1
Colorings of a triangle under rotations — Burnside's Lemma
  • ProblemColor the vertices of an equilateral triangle with 2 colors. Using Burnside's Lemma with the 3 rotations as symmetries, find the number of distinct colorings.
  • SetupRotation group: |G| = 3. Total labeled colorings: 2³ = 8.
  • Analyze r₀ (0° — identity): All 8 colorings fixed. |Fix(r₀)| = 8.
    r₁ (120°): Cycles all three vertices (1→2→3→1). Need c₁ = c₂ = c₃. Only 2 arrangements fixed. |Fix(r₁)| = 2.
    r₂ (240°): Same cycle structure. |Fix(r₂)| = 2.
  • Apply Distinct colorings = (1/3)(8 + 2 + 2) = 12/3 = 4
  • CheckMatches the direct orbit analysis in Example 13.10.1. ✓
Answer: 4 distinct 2-colorings of the triangle's vertices under rotation symmetry.
Example 13.12.2
Colorings of a square under full symmetry (rotations and reflections)
  • ProblemColor the vertices of a square with 2 colors (R, B). Count distinct colorings where two are the same if one can be rotated or reflected to match the other.
  • SetupFull symmetry group of the square: |G| = 8 (4 rotations + 4 reflections). Total labeled colorings: 2⁴ = 16.
  • Analyze r₀ (0° identity): All 16 fixed. |Fix| = 16.
    r₁ (90°): Cycles (1→2→3→4→1). Need all equal. |Fix| = 2.
    r₂ (180°): Pairs (1↔3), (2↔4). Need c₁=c₃ and c₂=c₄. Two free choices. |Fix| = 4.
    r₃ (270°): Same as r₁. |Fix| = 2.
    s₁ (horizontal): Pairs (1↔4), (2↔3). Two free choices. |Fix| = 4.
    s₂ (vertical): Pairs (1↔2), (3↔4). Two free choices. |Fix| = 4.
    s₃ (main diagonal, fixes vertices 1 & 3): Pairs (2↔4). Three free choices: c₁, c₃, c₂. |Fix| = 8.
    s₄ (anti-diagonal, fixes vertices 2 & 4): Pairs (1↔3). |Fix| = 8.
  • Apply Sum = 16 + 2 + 4 + 2 + 4 + 4 + 8 + 8 = 48 Distinct = 48 / 8 = 6
  • CheckThe result is a whole number. ✓ Plausible: 16 labeled colorings, 8 symmetries, 6 truly distinct patterns.
Answer: There are 6 genuinely distinct 2-colorings of the square's vertices under full symmetry (rotations and reflections).
Example 13.12.3
Necklace counting — 6 beads, 2 colors
  • ProblemA necklace has 6 beads in a circle, each colored red or blue. Two necklaces are the same if one can be rotated or flipped to match the other. How many distinct necklaces?
  • SetupFull symmetry group of a 6-bead necklace: 6 rotations + 6 reflections, so |G| = 12. Total labeled colorings: 2⁶ = 64.
  • Rotations r₀ (0° identity): |Fix| = 64.
    r₁ (60°): Cycles all 6 positions. Need all equal. |Fix| = 2.
    r₂ (120°): Two 3-cycles (1,3,5) and (2,4,6). Need c₁=c₃=c₅ and c₂=c₄=c₆. Two free choices. |Fix| = 4.
    r₃ (180°): Three 2-cycles (1↔4),(2↔5),(3↔6). Three free choices. |Fix| = 8.
    r₄ (240°): Same as r₂. |Fix| = 4.
    r₅ (300°): Same as r₁. |Fix| = 2.
  • Reflections 3 axes through opposite vertices (fix 2 vertices, swap 2 pairs): 4 free choices. Each gives |Fix| = 16.
    3 axes through opposite edge midpoints (swap 3 pairs): 3 free choices. Each gives |Fix| = 8.
  • Apply Rotations sum: 64 + 2 + 4 + 8 + 4 + 2 = 84 Reflections sum: 3(16) + 3(8) = 48 + 24 = 72 Total: 84 + 72 = 156 Distinct = 156 / 12 = 13
Answer: There are 13 distinct 2-colored necklaces with 6 beads, under rotations and reflections.
Section 13.13

Designs in Experiments, Codes, and Scheduling

DomainDesign Idea UsedWhat It Achieves
Clinical trialsBIBD with v treatments, k per block, λ = 1 or 2Every treatment pair compared the same number of times; controls bias
Agricultural experimentsLatin square for 2 confounders (rows = soil strips, columns = time blocks)Simultaneously controls for two sources of variation
Hamming codeStructure related to the Fano plane7-bit codewords; can detect and correct single-bit errors
Tournament schedulingRound-robin BIBD with λ = 1 (single) or λ = 2 (double)Every pair plays exactly the same number of times; resolvable into rounds
Course schedulingResolvable BIBD or Latin squareDistribute courses so no student has two required courses at the same time
MGU Library Connection
  • Operations Research — resolvable designs for scheduling and resource allocation
  • Probability and Statistics — Latin square and BIBD experimental design
  • Cryptography and Coding Theory — Hamming codes, finite geometry, and Reed-Solomon codes
  • Discrete Mathematics — block designs, graph theory, and combinatorial structures
Section 13.14

Common Design and Symmetry Mistakes

Mistake 1 — Ignoring symmetry when it applies
Count all 2⁴ = 16 colorings of a square's vertices; that is the answer.

Error: When the problem says rotations or reflections are considered "the same," Burnside's Lemma is required. Naive counts overcount by treating equivalent arrangements as distinct. Correct: apply Burnside's Lemma; the answer is 6, not 16.

Mistake 2 — Applying symmetry when it does not apply
Seating 6 people in 6 specific labeled chairs: divide by 6 for rotational symmetry.

Error: If chairs are labeled and fixed in space, every arrangement is distinct. Burnside's Lemma is only needed when symmetric arrangements are genuinely considered equivalent. Labeled, positioned chairs do not qualify.

Mistake 3 — Miscounting fixed arrangements
For a 120° rotation of a triangle, many colorings where adjacent vertices agree are fixed.

Error: A rotation that cycles all n positions fixes only arrangements where all positions in each cycle have the same value — not all arrangements where adjacent positions happen to agree. Identify cycles explicitly before counting.

Mistake 4 — Concluding existence from necessary conditions
Both bk = vr and r(k−1) = λ(v−1) hold, therefore the BIBD exists.

Error: These are necessary conditions, not sufficient ones. Some parameter sets pass both but no design with those parameters exists. The conditions rule out impossibility; existence requires explicit construction or a separate theorem.

Mistake 5 — Confusing Latin squares with Sudoku
A Latin square requires each symbol once per row, per column, and once per subsquare.

Error: A Latin square requires only the row and column conditions. Sudoku adds a third condition (3×3 subsquare blocks). Every completed Sudoku is a Latin square, but not every Latin square is a valid Sudoku.

Mistake 6 — Treating orthogonal squares as just two valid Latin squares
Two squares are orthogonal if each is individually a valid Latin square.

Error: Orthogonality is a relationship between two squares, not a property of each individually. When superimposed, every ordered pair of symbols must appear exactly once across all n² cells. Two valid Latin squares are not necessarily orthogonal.

Mistake 7 — Forgetting the identity in Burnside's Lemma
Apply Burnside's Lemma using only the non-identity symmetries.

Error: The identity is always in the group. It fixes every arrangement, so its contribution is |S| — always the largest single term in the Burnside sum. Omitting it produces a wrong total and wrong final count.

Mistake 8 — Checking only rows (or only columns) to verify a Latin square
Check that every row is a permutation of the symbols; conclude it is a Latin square.

Error: Both conditions must hold. It is easy to construct a grid where every row is valid but some column repeats a symbol. Always verify rows and columns independently.

Chapter 13 — Back Matter

Chapter Summary

Key Terms Review

combinatorial design
An arrangement of objects into blocks satisfying specified balance or regularity conditions on frequency and pair coverage.
Latin square
An n×n grid filled with n symbols such that each symbol appears exactly once in every row and exactly once in every column.
order
The value n in a Latin square — the grid is n×n and uses n distinct symbols.
orthogonal Latin squares
Two Latin squares of the same order where superimposition produces every ordered pair exactly once across all n² cells.
BIBD
Balanced incomplete block design. Parameters (v, b, r, k, λ): v points, b blocks of size k, each point in r blocks, each pair in λ blocks.
necessary conditions
bk = vr and r(k−1) = λ(v−1). Both must hold for a BIBD to exist, but satisfying them does not guarantee existence.
Fano plane
The BIBD with parameters (7,7,3,3,1); the smallest finite projective plane PG(2,2); 7 points and 7 blocks of size 3.
round-robin tournament
A schedule where every pair of participants plays exactly once. For n teams: C(n,2) total games, n−1 rounds when n is even.
resolvable design
A block design whose blocks can be partitioned into parallel classes, each containing every point exactly once.
finite geometry
A geometry with finitely many points and lines satisfying incidence conditions (any two points on one line; any two lines meet in one point).
symmetry
A transformation mapping a figure to itself. For a regular n-gon: n rotations and n reflections, totaling 2n symmetries.
orbit
The set of all arrangements equivalent to a given arrangement under a group of symmetries. Number of orbits = number of distinct arrangements.
fixed arrangement
An arrangement A such that symmetry g maps A to itself: g·A = A. Denoted |Fix(g)| for the count of all such arrangements.
Burnside's Lemma
Distinct arrangements = (1/|G|) Σ |Fix(g)|. The average number of arrangements fixed by each symmetry equals the number of orbits.
dihedral group
The group of symmetries of a regular n-gon, consisting of n rotations and n reflections, with total order 2n.
group action
A formal assignment of symmetry transformations to arrangements so that each symmetry g sends arrangement A to g·A.

Concept Review Questions

  1. What does it mean for a design to be balanced? Give an example of a balanced design and a non-balanced arrangement.
  2. State the two necessary conditions for a BIBD with parameters (v, b, r, k, λ). Explain where each comes from using double counting.
  3. What is a Latin square? State its two defining conditions precisely.
  4. How many symmetries does a regular hexagon have? List them by type.
  5. State Burnside's Lemma in words and in symbols.
  6. What is a fixed arrangement under a symmetry g? Give a simple example.
  7. Why does the identity symmetry always contribute |S| to the Burnside sum?
  8. What is the difference between a rotation and a reflection as symmetries of a polygon?
  9. What is an orbit? Why does the number of orbits equal the number of distinct arrangements?
  10. How does a finite projective plane of order q connect to a block design?
Practice ALatin Square Practice
  1. Determine whether the following 3×3 grid is a valid Latin square using symbols 1, 2, 3: 1 2 3 3 1 2 2 3 1
  2. Construct a Latin square of order 5 using the cyclic construction with symbols 0, 1, 2, 3, 4.
  3. Fill in the blanks to complete this 4×4 Latin square: A B _ D B _ D A _ D A B D A B _
  4. Verify that the two 3×3 squares in Section 13.3 form an orthogonal pair by listing all nine superimposed pairs and confirming each appears exactly once.
Practice BDesign Interpretation
  1. A BIBD has parameters v = 10, k = 4, λ = 2. Compute r and b using the necessary conditions.
  2. Check whether the parameters (v, b, r, k, λ) = (6, 10, 5, 3, 2) satisfy both necessary conditions for a BIBD.
  3. List the 7 blocks of the Fano plane given in Section 13.5. Verify that each point 1–7 appears in exactly 3 blocks.
  4. A double round-robin tournament (every pair plays twice) has 5 teams. How many total games? How many per team?
  5. A league wants v = 9 players, k = 3 players per game, λ = 1. Find r and b. Do the necessary conditions allow such a design?
  6. A researcher designs an experiment with 13 treatments in blocks of size 4, with λ = 1. Find all parameters and verify feasibility.
Practice CSymmetry Counting Practice
  1. List all symmetries of an equilateral triangle (rotations and reflections). Count them and confirm the total is 2n for n = 3.
  2. Color the vertices of an equilateral triangle with 3 colors. Without symmetry: how many labeled colorings? Under rotation symmetry only: apply Burnside's Lemma.
  3. Using Burnside's Lemma, count the number of distinct 2-colorings of the vertices of a regular pentagon under rotation symmetry only.
  4. A bracelet uses 4 beads, each red or blue. A bracelet can be rotated and flipped. Use Burnside's Lemma to count distinct bracelets.
  5. Color the edges (not vertices) of an equilateral triangle using 2 colors. How many distinct colorings under the full symmetry group?
Practice DApplication Problems
  1. Tournament Planning. A sports league wants 8 teams to play in a round-robin tournament. How many total games? How many rounds, with no team idle?
  2. Experimental Design. A chemist wants to compare v = 7 compounds in groups of 3, with every pair tested together exactly once. Can she build such an experiment? If so, how many total tests?
  3. Necklace Design. A jeweler uses 8 distinct beads (no two alike) on a circular necklace. How many distinct necklaces under rotational symmetry only?
  4. Scheduling. A university has 7 exam slots and wants to schedule 7 exams so each pair of exams shares a session exactly once. Identify the design parameters and check feasibility.
  5. Code Preview. A binary code uses codewords of length 7, related to the Fano plane. Each of the 7 positions corresponds to one of the 7 points. Explain how the Fano plane's 7 blocks might define which positions are checked for errors.

Error Analysis

Each problem shows a student's work with an error. Identify the error and write the correct solution.

Problem 1
2-colorings of a square's vertices: 16 colorings ÷ 8 symmetries = 2 distinct colorings.

Identify the error. What is the correct application of Burnside's Lemma, and what is the correct answer?

Problem 2
BIBD (11,11,5,5,2): both conditions satisfied → design exists.

The conditions bk = vr and r(k−1) = λ(v−1) both hold. What error did the student make in the conclusion?

Problem 3
Burnside sum for hexagon rotations (omitting identity): 2+4+8+4+2 = 20. Distinct colorings: 20/5 = 4.

Identify all errors. What is the correct Burnside sum and the correct number of distinct 2-colorings of a hexagon's vertices under rotation?

Problem 4
The grid below is a Latin square because every row is a permutation of {1,2,3}:
1 2 3 / 2 3 1 / 1 3 2

Why is checking rows only insufficient? Is this grid actually a valid Latin square?

Chapter 13 Checkpoint

Chapter 13 Checkpoint
Complete without assistance — assesses all key skills and concepts from Chapter 13
Part A — Concepts
  1. State the two necessary conditions for a BIBD with parameters (v, b, r, k, λ). Where does each condition come from?
  2. Define a Latin square. Give an example of a valid 3×3 Latin square.
  3. State Burnside's Lemma in words and in symbols.
  4. What is an orbit under a symmetry group? Why does counting orbits give the number of distinct arrangements?
  5. How many symmetries does a regular pentagon have? List them by type.
Part B — Skills
  1. Verify whether the grid below is a valid Latin square using symbols {1, 2, 3, 4}: 1 2 3 4 / 2 1 4 3 / 3 4 1 2 / 4 3 2 1
  2. A BIBD has v = 13, k = 4, λ = 1. Compute r and b.
  3. Use Burnside's Lemma to count the number of distinct 2-colorings of the vertices of a square under rotation symmetry only (4 rotations).
Part C — Applications
  1. A professional league has 10 teams and wants a double round-robin (λ = 2). Find all design parameters.
  2. A necklace has 5 beads, each red or blue. Considering both rotations and reflections, use Burnside's Lemma to count distinct necklaces.
Part D — Reasoning
  1. A student claims: "If both necessary conditions for a BIBD are satisfied, the design must exist." Is this correct? Explain your reasoning carefully.
  2. Explain why the identity symmetry always contributes the full number |S| to the Burnside sum, while a rotation through 360°/n for n > 1 typically contributes far fewer fixed arrangements.
Looking Ahead
Chapter 14: Combinatorics Capstone and Applications

Chapter 13 completed the survey of major combinatorial structures: basic counting, permutations, combinations, binomial coefficients, distribution, inclusion-exclusion, pigeonhole arguments, combinatorial proof, recurrence relations, generating functions, graph counting, designs, and symmetry. Chapter 14 brings all of these tools together. It will emphasize choosing the right model for a given counting situation, combining methods when needed, explaining reasoning clearly, and seeing combinatorics as a complete toolkit for discrete modeling. Students will leave the book able to approach unfamiliar finite counting problems with a principled strategy.

MGU Library Connection
  • Abstract Algebra — groups, Burnside's Lemma proof, orbit-stabilizer theorem, Pólya enumeration
  • Coding Theory and Cryptography — finite projective planes, Hamming codes, Reed-Solomon codes
  • Probability and Statistics — Latin square and BIBD experimental design; balanced comparisons
  • Operations Research — resolvable designs, scheduling theory, tournament optimization
  • Discrete Mathematics — block designs, graph theory, combinatorial structures survey
  • MGU Dictionary entries: Latin square, BIBD, Burnside's Lemma, Fano plane, dihedral group

Answers may be placed in the answer key.