Number Of Ways To Loop n Points

By Xah Lee. Date:

Problem

Given n points in space, in how many ways can one connect them together to form a loop? Find a method to list all the ways.

Let n := 4. Label the points from 1 to 4. Different ways can be represented as permutations of integers. For example, {3,2,1,4} will mean connect point 3 to point 2 to point 1, to 4, and back to point 3. There are a total of 3 ways to loop 4 points. They are {{1,2,3,4},{1,2,4,3},{1,3,2,4}}. We have ways[4] = 3, and it's obvious ways[3] = 1. The graphics below shows all possible ways to loop 4 points. Think about it for a while and see if you can come up with a formula for ways[n], and spend an hour to see if you can find a method to list them all.

loop thru n points
Possible loops with 4 points:
loop thru n points
Possible loops with 5 points:
loop thru n points
Possible loops with 6 points:

Solution

Let n := 5. It is obvious that shifting and reversal of a list does not represent new ways, for example, {3,2,1,4,5} and {2,1,4,5,3} are equivalent, and, {3,2,1,4,5} and {5,4,1,2,3} are equivalent. Given n things, there are total of n! permutations. For each permutation, there are n permutations that is itself shifted, counting itself. This reduces the possibility to n!/n == (n-1)!. Each permutation also has two reversals, counting itself. So we have ways[n]:=(n-1)!/2. Starting with n:=3, this function gives the sequence {1,3,12,60,360,2520,20160,181440,1814400,19958400,239500800,3113510400,43589145600,…}. You may look up the sequence in The On-Line Encyclopedia of Integer Sequences™ (OEIS™) @ oeis.org.

To enumerate all all possible lists, we can start with a complete permutations and delete shift and reversal equivalents. Direct method is also possible. Here is an insight to such method. Following that we will work it out slowly.

Notice that we can always rearrange a permutation by shifting and reversal so the following conditions are met:

From this insight comes a method:

  1. The first element of the list will be 1.
  2. Choose an unordered pair of numbers 2 to n. Suppose these are a and b with a < b. Put a in the second position and b in the last.
  3. Take any permutation of the remaining n-3 numbers.

This may be too abstract to understand immediately. We don't expect insights to solve all our math problems. Let's do some reasoning. First, we want to avoid the shifted list. This can be done by always having 1 in the first position. Now we want to avoid reversal. Reversal is a directional thing. We have two directions, or more correctly, two senses. It helps to imagine the numbers arranged around a circle. Notice that if we control two slots in the list, and let the rest run free, we may still get a reversed list. For example, {1,2,x,x,x} and {1,x,x,x,2} are equivalent. If we control three consecutive positions, then reversal cannot come up again. For example, control the first three positions in a list. Suppose we have {a,b,c,x,x}. If we are careful, we can be sure the sequence a,b,c will not appear in any other positions. How shall we let the controled spots permute? Let 1 be fixed on second spot, and we permute first and third spots. Since sequance a,b,c is equal to c,b,a, we also want to make sure the side spots goes only one way by requiring spot 1 < spot 3. So we have {a,b:=1,c,x,x}, and a < c. The x's are permutations of rest of the integers. This explains our algorithm. Note that we fixed a number to the middle of our control spots, but not the first or the third spot because otherwise the unique sequence a,b,c may turn up in other positions. For example, if we fix 1 to the 1st spot and let 2nd and 3rd spots permute, we have {a:=1,b,c,x,x} with b < c. We may generate {1,2,3,5,4} and {1,4,5,3,2}, which are reversals. Other elements may never be generated such as {1,5,4,2,3}.

The loop in n points problem answers my original problem: how many configurations are there in Pascal's Theorem. (See: Conic Sections).

Robert Dickau has done many diagrams related to combinatorics. See: robertdickau.com.

Mathematica graphics code loopNPoints.nb.gz.