5
$\begingroup$

Take $n$ equally spaced points on a circle. Connect them by a cycle(circuit) with $n$ line segments. Two cycles are considered equivalent if same when rotated or reflected. How many cycles are there?

for n = 2, 3, 4, 5

It can also be viewed as integer sequence.

Take an integer sequence $a_i(1 \leq i \leq n, \: 1 \leq a_i \leq n, \: a_i \neq a_j)$. Two sequences $a_n, \: b_n$ are considered equivalent if there exists some integers $k, \: l$ such that $a_i \equiv b_{i+l \bmod n}+k(\bmod n)$ or $a_{i+l} \equiv -b_{i+l \bmod n}+k(\bmod n)$

|cite|improve this question
$\endgroup$
  • $\begingroup$ What are your thoughts? What do you get for $n = 6$? $\endgroup$ – John Hughes Nov 11 '15 at 12:54
  • 1
    $\begingroup$ Have you tried finding the numbers for say $n=1$ to $n=15$ and putting the sequence at o.e.i.s.? Maybe your sequence is there. $\endgroup$ – coffeemath Nov 11 '15 at 12:59
  • $\begingroup$ @coffeemath: Using a naive approach I had trouble even for $n=9$, but fortunately the numbers up to $n=8$ were enough to uniquely identify the sequence. And the description was enough to know that it's the right one. $\endgroup$ – MvG Nov 12 '15 at 21:58
  • $\begingroup$ The $+l$ in the left hand side of the second congruence seems wrong to me. Since you are talking about the equivalence of two sequneces, shouldn't these be $a$ and $b$ or similar? And how about an order reversal? Shouldn't you also include a case for $a_i\equiv b_{l-i\bmod n}+k\pmod n$ or similar? $\endgroup$ – MvG Nov 13 '15 at 0:57
2
$\begingroup$

This is A000940. The numbers grow fairly quickly, so for many applications, looking up a number in that list might be enough. I'll quote the terms up to the 20-gon:

 3                1
 4                2
 5                4
 6               12
 7               39
 8              202
 9             1219
10             9468
11            83435
12           836017
13          9223092
14        111255228
15       1453132944
16      20433309147
17     307690667072
18    4940118795869
19   84241805734539
20 1520564059349452

I used the following naive python code to enumerate the first few items and identify the sequence:

import itertools

def f(n):
    r = set()
    for p in itertools.permutations(range(n)):
        # cyclical shifts, correspond to a change in starting point:
        s = set(p[i:] + p[:i] for i in range(n))
        # include the reversed tuples, traverse path in opposite direction:
        s |= set([tuple(reversed(i)) for i in s])
        # modulo-add an integer to all elements, represents a rotation:
        s = set(tuple((i + k) % n for k in j) for i in range(n) for j in s)
        # also modulo-negate the elements, represents a reflection:
        s |= set(tuple(n - j - 1 for j in i) for i in s)
        s = frozenset(s)
        r.add(s)
    return r

for n in range(1, 10):
    print("{} {}".format(n, len(f(n))))

Hmmm. Come to think of it, that Maple code given there could indeed be read as a formula:

$$f(n)= \frac1{4n^2}\left( \sum_{d\mid n}\left(\left(\varphi\left(\frac nd\right)\right)^2 \cdot d!\cdot\left(\frac nd\right)^d\right) +\begin{cases} 2^{\frac{n-1}2}\cdot n^2\cdot\left(\frac{n-1}2\right)! & \text{for $n$ odd} \\ 2^{\frac{n}2}\cdot\frac{n(n+6)}4\cdot\left(\frac{n}2\right)! & \text{for $n$ even} \end{cases} \right)$$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I think OP wants to count two the same if they differ by an element of the dihedral group (which includes the reflections). There's an oeis entry for this also, oeis.org/A000940 (I havden't checked more into it...) $\endgroup$ – coffeemath Nov 13 '15 at 0:04
  • $\begingroup$ @coffeemath: You are right. I thought I had that covered, while in fact I only had changes in path traversal direction accounted for. (Interestingly, without those either, one ends up in [oeis.org/A002619](A002619). I wonder whether there is an easy way to see that connection.) Will have to edit my answer. $\endgroup$ – MvG Nov 13 '15 at 0:26
  • $\begingroup$ @coffeemath: One could of course assume that my original answer is still correct, because you get those same counts of you consider reflected versions the same, but don't allow reversing the path direction. (The two are essentially equivalent, it depends on how you map index and value to position on circle and on path.) As it stands now, the question doesn't mention path reversals, and the attempted formalization clearly only expresses a change of starting point, not a reversal. So it's currently asking for oriented cycles. But somehow I doubt that's intentional, so I keep my edited answer. $\endgroup$ – MvG Nov 13 '15 at 1:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.