Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 36 ยท Permutations and Combinations

Partial Permutations and Circular Arrangements

Count ordered selections of k items from n with P(n,k), then arrangements around a circle and bracelets. Includes Python checks for every formula.

Arranging all n items gives n!. Often you only arrange some of them: three finalists out of ten runners, or a four-letter code from twenty symbols. This lesson covers selections of k items in order, and then arrangements around a circle, where rotations count as the same.

k-permutations

The number of ways to choose and order k items from n distinct items is written P(n, k) (also nPk or (n)_k):

P(n, k) = n ยท (n-1) ยท ... ยท (n-k+1) = n! / (n-k)!

Reason with the product rule: n options for the first place, n-1 for the second, down to n-k+1 for the k-th. Multiplying the missing tail (n-k)! in the numerator and denominator turns it into the factorial fraction.

Example: gold, silver and bronze among 10 runners: P(10, 3) = 10 x 9 x 8 = 720.

Python P(n, k) formula versus listing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python 3.8 and later has math.perm(n, k) built in. Special cases worth remembering: P(n, 0) = 1, P(n, 1) = n, P(n, n) = n! and P(n, k) = 0 if k > n.

Codes with and without repetition

Compare two situations. A 4-symbol code from 20 symbols with repeats allowed uses the product rule: 20^4 = 160,000. If every symbol must be different, it is P(20, 4) = 20 x 19 x 18 x 17 = 116,280. The first answer counts functions; the second counts injective functions, as in Counting Functions and Subsets.

Python With and without repetition

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Circular permutations

Seat n people at a round table. If the seats are not marked, rotating everyone one place gives the same arrangement. Each seating therefore appears n times among the n! linear orders, so the division rule gives:

(n-1)! circular arrangements.

Another way to see it: fix one person in a seat (this kills the rotation symmetry) and arrange the other n - 1 people: (n-1)!.

For n = 5 this is 24, far fewer than 120.

Python Circular arrangements

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bracelets and reflections

Now suppose the objects are beads on a necklace you can flip over. A reflection also gives the "same" bracelet, so each circular arrangement is counted twice (once as itself, once as its mirror image), as long as n >= 3 and all beads are different. The count becomes (n-1)! / 2. For 6 different beads: 5! / 2 = 60.

Python Bracelets of distinct beads

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

flowchart LR
    L["Linear: n!"] -->|"divide by n rotations"| C["Circular: (n-1)!"]
    C -->|"divide by 2 reflections"| B["Bracelet: (n-1)!/2"]

Each symmetry you ignore divides the count, provided it acts without fixed points.

The bracelet formula assumes distinct beads and n >= 3. With repeated colours some arrangements are symmetric under rotation or flip, and the simple division fails; counting such objects needs Burnside's lemma, a more advanced tool.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is P(7, 3)?

    7 x 6 x 5 = 210.
  2. 2. How many ways can 6 people sit at a round table (rotations equal)?

    (6-1)! = 120.
  3. 3. How many different 3-letter codes with all letters distinct from 26 letters?

    26 x 25 x 24 = 15,600.
  4. 4. Why divide by 2 for a bracelet of distinct beads?

    Each circular arrangement and its mirror image are one bracelet.

Summary

  • P(n, k) = n! / (n-k)! counts ordered selections of k from n distinct items.
  • With repetition allowed the count is n^k instead.
  • Round-table arrangements number (n-1)!; bracelets of distinct beads (n-1)!/2.
  • Symmetries are handled with the division rule.

Next: Combinations