Circular Permutations | Free Discrete Mathematics Lesson (4 College Credits) | UPI Study

UPI Study › Courses › Discrete Mathematics › Free lessons › Lesson 5.6 Free with a free account

Circular Permutations

Discrete Mathematics · Chapter 5: Counting Methods and Basic ProbabilitySection 5.6 · lesson 32 of 878 min · free with a free account

← Probability of Permutation EventsNext lesson: Combinations and Unordered Selections →

Earn 4 college credits for Discrete MathematicsRecommended for credit by NCCRS · Math 230 · self-paced · one payment, lifetime access
Enroll in Discrete Mathematics · $250 →Download the syllabus (PDF)

In this lesson

Arrangements around a circle, where rotating the whole thing changes nothing.

  • Define rotational equivalence
  • Derive the circular permutation formula 2 ways
  • Count ring configurations
  • Decide when reflections should also count as the same

Transcript

Everything said in the video, section by section (1,121 words). Read along, or search it.

Counting Methods and Basic Probability

Circular Permutations

Section five point four counted arrangements in a line, where the first position is genuinely different from the second. This section counts arrangements around a circle, where rotating the whole arrangement changes nothing that actually matters. The question is how many distinct arrangements remain, once that rotational freedom is accounted for.

The Opening Problem

A Ring With No Starting Point

Consistent hashing is a technique distributed caches and databases use to spread data across a set of servers. Each server is placed at a position on a conceptual ring. A piece of data goes to whichever server comes next, going clockwise from the data's hash value. Only the relative clockwise order of the servers affects routing. Which server happens to be drawn at the top of the ring isn't a meaningful distinction. The ring has no actual starting point. Rotate every server's position by the same amount, and the ring behaves identically for routing. Even though, written out as a left-to-right list, it would look like a different sequence altogether.

Definition

Rotational Equivalence

Arranging n distinct items in a line gives n factorial orderings. That's because every position is distinguishable from every other. Swapping the items in positions one and two always gives a genuinely different list. A circular arrangement removes that distinction between positions. No position is intrinsically first. Here's the key definition. Two circular arrangements of the same items are rotationally equivalent, and count as the same, if one can be produced from the other by a rotation. Every item moves the same number of positions around the circle. Nobody's neighbors change, and neither does the clockwise order.

Figure 1

Rotations Versus Genuinely New Neighbors

Here are three arrangements of five servers. Arrangements one and two list the same servers, in the same clockwise order. A, B, C, D, E, and back to A. Arrangement two simply starts from a different position. They're rotations of each other, so they count as one circular arrangement. Arrangement three is different. B and C have swapped their relative order, so the neighbors genuinely change. That makes it a distinct circular arrangement.

Counting the Clusters

Each Circle Gives Exactly n Lines

Rotational equivalence groups the n factorial linear arrangements into clusters, each representing the same circular arrangement. Counting the size of each cluster counts the circular arrangements. Start from any circular arrangement, and read it off as a line, starting at any of the n items. That gives at most n linear arrangements. And those n lines are all genuinely different. Suppose two different starting points gave the identical list. Then the arrangement would have to repeat itself after some number of positions, strictly between zero and n. That would force at least two of the items to be identical. But all n items are distinct. So every circular arrangement of n distinct items corresponds to exactly n distinct linear arrangements.

Theorem

The Circular Permutation Formula

Since the n factorial linear arrangements split evenly into clusters of exactly n, the number of circular arrangements is n factorial over n. That's n minus one, factorial. n minus one, times n minus two, and so on, down to one. That's the circular permutation formula. It counts distinct circular arrangements of n distinct items, where rotations are considered identical.

A Second Way to See It

Fix One Item, Then Arrange the Rest

There's a second, equivalent way to see the same count. Instead of counting rotations and dividing them out afterward, remove them directly. Fix one specific item's position. Say, always place server A at the top. That eliminates rotation as a source of difference entirely, since every arrangement is now read from the same fixed point. The remaining n minus one items then fill the other positions in any linear order relative to A. That's n minus one factorial ways, by ordinary linear counting. With five servers, the other four fill four positions in four factorial, twenty-four ways. That matches the formula, and it's often the faster way to compute the answer in practice.

Worked Example 1

Consistent-Hashing Ring Configurations

So how many distinct ways are there to arrange five distinct servers around a consistent-hashing ring, where rotating the whole ring doesn't change routing? Here n is five. So it's four factorial, which is twenty-four distinct ring configurations. That's far fewer than the one hundred twenty linear orderings, which we'd count if position on the ring meant something in itself. The code confirms it. The factorial of n minus one prints twenty-four. And one hundred twenty linear arrangements, divided by five, also gives twenty-four.

Advanced Note

When Mirror Images Are the Same Too

Here's an advanced note. The circular formula accounts for rotations only. It still treats a clockwise arrangement and its mirror image, the same items in reverse, as different. For some physical arrangements, reversal is also a symmetry. A necklace strung with distinct beads can be lifted off and turned over. That reverses the direction the beads are read in, but the necklace is indistinguishable from the original. When both rotations and reflections count as the same, each rotation-only arrangement pairs up with exactly one other, its mirror image. So the count halves, to n minus one factorial over two, for n at least three. For a necklace of six distinct beads, that's one hundred twenty over two, or sixty designs. But this adjustment isn't automatic. A hashing ring can't be flipped in any sense that matters. The algorithm fixes what clockwise means, and reversing it would route every request to a different server. Whether to divide by two depends on whether reflection is a genuine symmetry of the situation, not on whether things happen to be arranged in a circle.

Comparison

Linear, Circular, Reflective

This table compares the three kinds of arrangement. Linear arrangements count n factorial. Only identical, position-by-position lists are the same. Ordering tasks in a run sequence is a typical case. Circular arrangements, with rotation only, count n minus one factorial. Rotations of each other are the same. A hashing ring, or a round-robin turn order, are typical cases. And circular arrangements with reflection count half that. Rotations or mirror images are the same, like a necklace or bracelet that can be turned over.

Takeaways

No First Seat at a Round Table

To summarize. Circular arrangements differ from linear ones because a circle has no distinguished starting position. Rotating an entire arrangement gives one that's considered identical. Each circular arrangement of distinct items matches exactly n linear ones, one per starting point. So there are n minus one factorial circular arrangements. Fixing one item and arranging the rest gives the same count directly. And reflective symmetry is a separate adjustment, dividing by two. It applies only when reversing direction is genuinely meaningless. Here's something to think about. A network engineer counts ring configurations for seven servers as six factorial over two, which is three hundred sixty. They reason that reversing the ring's direction should count as the same, just like flipping a necklace. Explain why that's wrong for ring routing, even though dividing by two is right for a necklace of the same seven beads. What property of the situation decides it?

About Discrete Mathematics at UPI Study

Discrete Mathematics (Math 230) is a self-paced online course of 87 video lessons in 13 chapters, from logic and proof to counting, probability, graph theory and trees. It carries a NCCRS credit recommendation for 4 semester credits.

Every lesson transcript is free on pages like this one, and the videos are free with a free UPI Study account. Enrolling adds a practice quiz after each lesson, the graded work and final exam that earn the credit, lifetime access, and an official transcript on completion. UPI Study has helped over 130,000 students with college credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Enroll now → Course details Download the syllabus Every course with PRO →

Why take it here

Why students take Discrete Mathematics with UPI Study

The math behind computer scienceDiscrete Mathematics is the mathematics of computer science: logic, proofs, sets, counting, probability and graphs underpin algorithms, data structures, cryptography and databases. Completing it now lets you qualify for those courses at your university.
Credit at a fraction of the priceThe same 4 credits can cost $750 or more at a US college. Here it is one payment, self-paced, with lifetime access.
Finish your degree soonerTransfer credits reduce the courses you still owe, so you can graduate earlier or lighten a heavy semester.
Strengthen an applicationA completed college-level course on an official transcript shows admissions and scholarship committees you can do the work.
Study on your own scheduleNo start dates, no deadlines. Watch the lessons, practice, and take the final when you are ready.
130,000+students helped with college creditsACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Where the credit goes

Universities that work with NCCRS

Discrete Mathematics carries a NCCRS credit recommendation. These universities work with NCCRS; some are UPI Study's signed partners. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.

Thomas Edison State UniversityThomas Edison State UniversitySigned partnerUniversity of the PeopleUniversity of the PeopleSigned partnerCharter Oak State CollegeCharter Oak State CollegeSigned partnerStrayer UniversityStrayer UniversitySigned partnerColumbia Southern UniversityColumbia Southern UniversitySigned partnerIndiana TechIndiana TechSigned partnerPenn StatePenn StateWorks with NCCRSSouthern New Hampshire UniversitySouthern New Hampshire UniversityWorks with NCCRSSUNYSUNYWorks with NCCRS +many more cooperating universitiesFind my college →

Find my college → Not listed? Ask Athena in the corner of this page, or book a 15-minute call.

FAQ

Questions students ask us

About Circular Permutations

What does rotational equivalence mean in circular permutations?
Two circular arrangements of the same items are rotationally equivalent if rotating one by some number of positions produces the other. Every item shifts the same amount, so each person's neighbors and the clockwise order stay unchanged. Equivalent arrangements count as one, because a circle has no distinguished starting position.
Why is the number of circular permutations of n distinct objects (n-1)!?
The count is (n-1)! because the n! linear arrangements group into clusters of exactly n that all represent the same circle. Each circle can be read as a line starting at any of its n items, and those lines are all different. So the number of circles is n!/n = (n-1)!.
How do you count seating arrangements around a round table by fixing one person?
Fix one person at a particular seat, then arrange the other n-1 people in the remaining seats in any order, giving (n-1)! arrangements. Fixing that person removes rotation as a source of difference. For 5 distinct items, the other 4 can be arranged in 4! = 24 ways, which matches 5!/5.
When do you divide circular permutations by 2 for reflections?
Divide by 2 only when a mirror image counts as the same arrangement, giving (n-1)!/2 for n \ge 3. A necklace of 6 distinct beads can be flipped over, so there are 120/2 = 60 designs. If reversing direction changes the situation, such as clockwise routing on a hashing ring, do not divide.

About the Discrete Mathematics course

How many college credits is Discrete Mathematics?
Discrete Mathematics (Math 230) carries a NCCRS credit recommendation for 4 semester credits. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities.
How much does Discrete Mathematics cost and what is included?
$250, paid once, with lifetime access: all 87 video lessons, a practice quiz after each, the graded work and final exam, and an official transcript when you finish. Students who want several courses choose UPI Study PRO instead.
Which universities accept UPI Study credits?
UPI Study has signed partner agreements with universities such as Thomas Edison State University, University of the People and Charter Oak State College, and works with universities such as Penn State, SNHU and SUNY. ACE and NCCRS have over 2,100 cooperating colleges that will consider accepting credits; the final decision is with the universities. Use "Find my college" on this page to check yours.
How long does Discrete Mathematics take?
It is self-paced with no deadlines. The 87 lessons total about 13 hours of video; most students add reading and practice time and finish in a few weeks to a few months, on their own schedule.
How are the exams done?
Quizzes and assignments are online in the course. The final exam is taken online with proctoring; a person on the UPI Study team checks assignments, usually within two days.
How do my credits reach my college?
When the course shows 100% complete, request the official transcript from your dashboard. It is sent to the college you name, and you can send it to more than one. Check your college first with "Find my college" on this page, or ask Athena.

Ready for the full course? Earn 4 credits in Discrete Mathematics.

87 video lessons, a quiz after each one, and the graded work that earns the credit. Recommended for credit by NCCRS.

Enroll in Discrete Mathematics →Download the syllabusEvery course with PRO →
Discrete Mathematics
4 credits · NCCRSEnroll →