The Division Principle

Combinatorics · Axiom Academy

Learning to correct for overcounting by recognizing when objects are counted multiple times Imagine we want to count handshakes at a party. If we ask each person "how many hands did you shake?", we get a number. But there's a problem! When Alice shakes hands with Bob, both Alice and Bob count this as one of their handshakes. So we've counted the same handshake twice. The Division Principle states: If a set of objects is arranged into groups such that every object appears in exactly k groups, then the number of distinct objects is: In our handshake example: if 10 people each shake hands with 3 others, we count 10 × 3 = 30 "handshake instances". But each handshake involves 2 people, so it's counted twice. The actual number of handshakes is 30 ÷ 2 = 15. 3. Example: Circular Arrangements How many ways can we seat 4 people around a circular table? If we arranged them in a line, there would be 4! = 24 arrangements. But around a circle, rotations are considered the same. The arrangement (A, B, C, D) is the same as (B, C, D, A) and (C, D, A, B) and (D, A, B, C). Each circular arrangement corresponds to exactly 4 linear arrangements (one for each starting position). By the Division Principle: 4. Connection to Equivalence Classes The Division Principle is really about equivalence classes . When we say "rotations are the same", we're partitioning arrangements into groups where members of each group are considered equivalent.

This is the written version of the interactive lesson above. See the full Combinatorics course.