How many $n$-pointed stars are there?












7












$begingroup$


Say we have $n$ distinct points spaced evenly in a circle. Define a star as a connected graph with these points as vertices and with $n$ edges, no two having the same endpoints. We think of two stars as being equivalent if they differ only by a rotation (if they differ by a reflection I consider them as different objects). I'd like to know how many different stars there are on $n$ points.



For example there are only two 4-pointed stars: a square and a bowtie. There are four 5-pointed stars:
5-pointed stars



And I think there are twelve 6-pointed stars:
6-pointed stars
(I'm not completely sure that I have exhausted the possibilities for 6 points).



A quick search of the online encyclopedia of integer sequences hasn't revealed any obvious candidates.



Another way to phrase the question:
Let $rho = (1 2 ldots n)in S_n$. Say that two permutations $sigma, tauin S_n$ are equivalent if $sigma = rho^{-k}taurho^k$ for some $k$. How many equivalence classes contain order $n$ permutations?










share|cite|improve this question









$endgroup$

















    7












    $begingroup$


    Say we have $n$ distinct points spaced evenly in a circle. Define a star as a connected graph with these points as vertices and with $n$ edges, no two having the same endpoints. We think of two stars as being equivalent if they differ only by a rotation (if they differ by a reflection I consider them as different objects). I'd like to know how many different stars there are on $n$ points.



    For example there are only two 4-pointed stars: a square and a bowtie. There are four 5-pointed stars:
    5-pointed stars



    And I think there are twelve 6-pointed stars:
    6-pointed stars
    (I'm not completely sure that I have exhausted the possibilities for 6 points).



    A quick search of the online encyclopedia of integer sequences hasn't revealed any obvious candidates.



    Another way to phrase the question:
    Let $rho = (1 2 ldots n)in S_n$. Say that two permutations $sigma, tauin S_n$ are equivalent if $sigma = rho^{-k}taurho^k$ for some $k$. How many equivalence classes contain order $n$ permutations?










    share|cite|improve this question









    $endgroup$















      7












      7








      7


      1



      $begingroup$


      Say we have $n$ distinct points spaced evenly in a circle. Define a star as a connected graph with these points as vertices and with $n$ edges, no two having the same endpoints. We think of two stars as being equivalent if they differ only by a rotation (if they differ by a reflection I consider them as different objects). I'd like to know how many different stars there are on $n$ points.



      For example there are only two 4-pointed stars: a square and a bowtie. There are four 5-pointed stars:
      5-pointed stars



      And I think there are twelve 6-pointed stars:
      6-pointed stars
      (I'm not completely sure that I have exhausted the possibilities for 6 points).



      A quick search of the online encyclopedia of integer sequences hasn't revealed any obvious candidates.



      Another way to phrase the question:
      Let $rho = (1 2 ldots n)in S_n$. Say that two permutations $sigma, tauin S_n$ are equivalent if $sigma = rho^{-k}taurho^k$ for some $k$. How many equivalence classes contain order $n$ permutations?










      share|cite|improve this question









      $endgroup$




      Say we have $n$ distinct points spaced evenly in a circle. Define a star as a connected graph with these points as vertices and with $n$ edges, no two having the same endpoints. We think of two stars as being equivalent if they differ only by a rotation (if they differ by a reflection I consider them as different objects). I'd like to know how many different stars there are on $n$ points.



      For example there are only two 4-pointed stars: a square and a bowtie. There are four 5-pointed stars:
      5-pointed stars



      And I think there are twelve 6-pointed stars:
      6-pointed stars
      (I'm not completely sure that I have exhausted the possibilities for 6 points).



      A quick search of the online encyclopedia of integer sequences hasn't revealed any obvious candidates.



      Another way to phrase the question:
      Let $rho = (1 2 ldots n)in S_n$. Say that two permutations $sigma, tauin S_n$ are equivalent if $sigma = rho^{-k}taurho^k$ for some $k$. How many equivalence classes contain order $n$ permutations?







      combinatorics combinatorial-geometry algebraic-combinatorics






      share|cite|improve this question













      share|cite|improve this question











      share|cite|improve this question




      share|cite|improve this question










      asked Nov 6 '18 at 8:48









      vdbeekvdbeek

      535




      535






















          3 Answers
          3






          active

          oldest

          votes


















          7












          $begingroup$

          What we seek are: nontrivial cyclic permutations, with shifts and reversals counting as identical.



          Without the shift requirement, there are $(N-1)!$ different cyclic permutations. Shifting allows us to reduce that by up to a factor of $2N$, though not every permutation will be so accommodating. For instance, while there are six different cyclic 4-permutations, two of them (0123 and 0321) appear as identical squares and four (0132, 0213, 0231, and 0312) appear as bowties. Technically there's a maximal 8-fold symmetry but, as shown, nothing gets us there on $N=4$. The smallest that that happens to is on $N=6$: they must be free of both rotation and reflection symmmetries, like your fourth and fifth drawings.



          For relatively small $N$, we don't have to worry too terribly much about optimizations (they exist but many of them would also require pruning of the permutation tree before it reaches full length to be useful, which is complex), so we'll just write some code and see what happens.



          The code is here; edit line 3 (N = 6) to see different sizes. https://ideone.com/5PSyOJ



          Your diagram is missing two entries for $N=6$, shown here, ACEBDF and ABECFD. I find it interesting that they are not mirror images of each other!



          Two polygons: ACEBDF and ABECFD



          For $N$ from $4$ through $10$, we get $2, 4, 14, 54, 332, 2246,$ and $18264$ distinct polygons. This is OEIS entry A000939, Number of inequivalent n-gons.






          share|cite|improve this answer









          $endgroup$













          • $begingroup$
            Thanks for going above and beyond! Do you mind explaining the cycle function in your code?
            $endgroup$
            – vdbeek
            Nov 7 '18 at 0:06






          • 1




            $begingroup$
            So, cycle works like this: it takes a permutation (which at this point is lacking the default 0) and an index, and rotates the whole thing around so that we get another permutation with the original index as the new permutation start. So if I have p=[2,4,1,3,5] and i=2, it plops a 0 on the end, then subtracts p[2]=1 from everything (now we've got [1,3,0,2,4,-1]), then mods those by 6 ([1,3,0,2,4,5]), then cycles it around so the 0 is at the beginning/end and then removes it so we're back to the normal state, which is [2,4,5,1,3]
            $endgroup$
            – Dan Uznanski
            Nov 7 '18 at 0:51










          • $begingroup$
            Ahhh so if we fix p and let i vary cycle(p,i) gives all of the rotated copies of p? If this is the case we must be computing the same thing a lot. Is it possible to speed up the calculations by removing the rotated cycles from permutations while still inside the for loop?
            $endgroup$
            – vdbeek
            Nov 7 '18 at 1:16








          • 1




            $begingroup$
            Indeed: we can store permutations we've found via cycle and reversal and check incoming permutations against that. ...But this has a downside: we now must store all those permutations! This gets untenably large quite quickly. Other optimizations include cutting off when we know that other versions will be smaller - since we enumerate permutations in lexicographic order, anything we find where the first element of the cycle is not the shortest can be cut short - and we can cut off whole sections of the permutation tree this way. But that means rewriting permutations to check substrings...
            $endgroup$
            – Dan Uznanski
            Nov 7 '18 at 1:56



















          4












          $begingroup$

          Deriving the general formula for this sequence (and its reflection-insensitive analogue) is precisely the content of:




          Golomb, S.W.; Welch, L.R., "On the enumeration of polygons", Amer. Math. Monthly, 67 (1960), 349-353.




          The authors derive the result as a clever application of Burnside's Lemma, giving for the count of $n$-pointed stars
          $$
          E(n)
          =
          left{
          begin{array}{ll}
          F(n) , & textrm{$n$ odd}\
          F(n) + displaystyle{frac{1}{2 n^2} cdot 2^{n / 2} {n choose 2} {n choose 2}!}, & textrm{$n$ even}
          end{array}
          right. ,
          $$

          where
          $$F(n) := frac{1}{2 n^2} sum_{d mid n} phi^2left(frac{n}{d}right) d! left(frac{n}{d}right)^d .$$
          Here, $phi$ is the Euler totient function.



          As Dan Uznanski's answer has pointed out, this is OEIS A000939, Number of inequivalent n-gons.



          Remark As Empy2's answer observes, the procedure for computing should be easier for prime $n$. Indeed, for odd primes $p$ the above formula simplifies to
          $$E(p) = frac{1}{2 p} [(p - 1)^2 + (p - 1)!] .$$ It follows from the fact that $E(p)$ is an integer that $p mid [(p - 1)^2 + (p - 1)!]$, and rearranging gives $$(p - 1)! equiv -1 pmod p ,$$ which recovers one direction of Wilson's Theorem.






          share|cite|improve this answer









          $endgroup$





















            3












            $begingroup$

            There are $6!=720$ cycles for $n=7$. Three patterns have 7-fold symmetry, and are covered by 2 cycles each - forwards and backwards. All the others have no symmetry and are covered by 14 cycles each - forwards, backwards and seven rotations. So there are $6/2+714/14=54$ patterns for $n=7$.

            Composite $n$ are trickier of course.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              A000939 is what you want. You must have missed two 6-stars.
              $endgroup$
              – Empy2
              Nov 6 '18 at 11:31












            Your Answer








            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "69"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: true,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: 10,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            noCode: true, onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2986900%2fhow-many-n-pointed-stars-are-there%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            3 Answers
            3






            active

            oldest

            votes








            3 Answers
            3






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            7












            $begingroup$

            What we seek are: nontrivial cyclic permutations, with shifts and reversals counting as identical.



            Without the shift requirement, there are $(N-1)!$ different cyclic permutations. Shifting allows us to reduce that by up to a factor of $2N$, though not every permutation will be so accommodating. For instance, while there are six different cyclic 4-permutations, two of them (0123 and 0321) appear as identical squares and four (0132, 0213, 0231, and 0312) appear as bowties. Technically there's a maximal 8-fold symmetry but, as shown, nothing gets us there on $N=4$. The smallest that that happens to is on $N=6$: they must be free of both rotation and reflection symmmetries, like your fourth and fifth drawings.



            For relatively small $N$, we don't have to worry too terribly much about optimizations (they exist but many of them would also require pruning of the permutation tree before it reaches full length to be useful, which is complex), so we'll just write some code and see what happens.



            The code is here; edit line 3 (N = 6) to see different sizes. https://ideone.com/5PSyOJ



            Your diagram is missing two entries for $N=6$, shown here, ACEBDF and ABECFD. I find it interesting that they are not mirror images of each other!



            Two polygons: ACEBDF and ABECFD



            For $N$ from $4$ through $10$, we get $2, 4, 14, 54, 332, 2246,$ and $18264$ distinct polygons. This is OEIS entry A000939, Number of inequivalent n-gons.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Thanks for going above and beyond! Do you mind explaining the cycle function in your code?
              $endgroup$
              – vdbeek
              Nov 7 '18 at 0:06






            • 1




              $begingroup$
              So, cycle works like this: it takes a permutation (which at this point is lacking the default 0) and an index, and rotates the whole thing around so that we get another permutation with the original index as the new permutation start. So if I have p=[2,4,1,3,5] and i=2, it plops a 0 on the end, then subtracts p[2]=1 from everything (now we've got [1,3,0,2,4,-1]), then mods those by 6 ([1,3,0,2,4,5]), then cycles it around so the 0 is at the beginning/end and then removes it so we're back to the normal state, which is [2,4,5,1,3]
              $endgroup$
              – Dan Uznanski
              Nov 7 '18 at 0:51










            • $begingroup$
              Ahhh so if we fix p and let i vary cycle(p,i) gives all of the rotated copies of p? If this is the case we must be computing the same thing a lot. Is it possible to speed up the calculations by removing the rotated cycles from permutations while still inside the for loop?
              $endgroup$
              – vdbeek
              Nov 7 '18 at 1:16








            • 1




              $begingroup$
              Indeed: we can store permutations we've found via cycle and reversal and check incoming permutations against that. ...But this has a downside: we now must store all those permutations! This gets untenably large quite quickly. Other optimizations include cutting off when we know that other versions will be smaller - since we enumerate permutations in lexicographic order, anything we find where the first element of the cycle is not the shortest can be cut short - and we can cut off whole sections of the permutation tree this way. But that means rewriting permutations to check substrings...
              $endgroup$
              – Dan Uznanski
              Nov 7 '18 at 1:56
















            7












            $begingroup$

            What we seek are: nontrivial cyclic permutations, with shifts and reversals counting as identical.



            Without the shift requirement, there are $(N-1)!$ different cyclic permutations. Shifting allows us to reduce that by up to a factor of $2N$, though not every permutation will be so accommodating. For instance, while there are six different cyclic 4-permutations, two of them (0123 and 0321) appear as identical squares and four (0132, 0213, 0231, and 0312) appear as bowties. Technically there's a maximal 8-fold symmetry but, as shown, nothing gets us there on $N=4$. The smallest that that happens to is on $N=6$: they must be free of both rotation and reflection symmmetries, like your fourth and fifth drawings.



            For relatively small $N$, we don't have to worry too terribly much about optimizations (they exist but many of them would also require pruning of the permutation tree before it reaches full length to be useful, which is complex), so we'll just write some code and see what happens.



            The code is here; edit line 3 (N = 6) to see different sizes. https://ideone.com/5PSyOJ



            Your diagram is missing two entries for $N=6$, shown here, ACEBDF and ABECFD. I find it interesting that they are not mirror images of each other!



            Two polygons: ACEBDF and ABECFD



            For $N$ from $4$ through $10$, we get $2, 4, 14, 54, 332, 2246,$ and $18264$ distinct polygons. This is OEIS entry A000939, Number of inequivalent n-gons.






            share|cite|improve this answer









            $endgroup$













            • $begingroup$
              Thanks for going above and beyond! Do you mind explaining the cycle function in your code?
              $endgroup$
              – vdbeek
              Nov 7 '18 at 0:06






            • 1




              $begingroup$
              So, cycle works like this: it takes a permutation (which at this point is lacking the default 0) and an index, and rotates the whole thing around so that we get another permutation with the original index as the new permutation start. So if I have p=[2,4,1,3,5] and i=2, it plops a 0 on the end, then subtracts p[2]=1 from everything (now we've got [1,3,0,2,4,-1]), then mods those by 6 ([1,3,0,2,4,5]), then cycles it around so the 0 is at the beginning/end and then removes it so we're back to the normal state, which is [2,4,5,1,3]
              $endgroup$
              – Dan Uznanski
              Nov 7 '18 at 0:51










            • $begingroup$
              Ahhh so if we fix p and let i vary cycle(p,i) gives all of the rotated copies of p? If this is the case we must be computing the same thing a lot. Is it possible to speed up the calculations by removing the rotated cycles from permutations while still inside the for loop?
              $endgroup$
              – vdbeek
              Nov 7 '18 at 1:16








            • 1




              $begingroup$
              Indeed: we can store permutations we've found via cycle and reversal and check incoming permutations against that. ...But this has a downside: we now must store all those permutations! This gets untenably large quite quickly. Other optimizations include cutting off when we know that other versions will be smaller - since we enumerate permutations in lexicographic order, anything we find where the first element of the cycle is not the shortest can be cut short - and we can cut off whole sections of the permutation tree this way. But that means rewriting permutations to check substrings...
              $endgroup$
              – Dan Uznanski
              Nov 7 '18 at 1:56














            7












            7








            7





            $begingroup$

            What we seek are: nontrivial cyclic permutations, with shifts and reversals counting as identical.



            Without the shift requirement, there are $(N-1)!$ different cyclic permutations. Shifting allows us to reduce that by up to a factor of $2N$, though not every permutation will be so accommodating. For instance, while there are six different cyclic 4-permutations, two of them (0123 and 0321) appear as identical squares and four (0132, 0213, 0231, and 0312) appear as bowties. Technically there's a maximal 8-fold symmetry but, as shown, nothing gets us there on $N=4$. The smallest that that happens to is on $N=6$: they must be free of both rotation and reflection symmmetries, like your fourth and fifth drawings.



            For relatively small $N$, we don't have to worry too terribly much about optimizations (they exist but many of them would also require pruning of the permutation tree before it reaches full length to be useful, which is complex), so we'll just write some code and see what happens.



            The code is here; edit line 3 (N = 6) to see different sizes. https://ideone.com/5PSyOJ



            Your diagram is missing two entries for $N=6$, shown here, ACEBDF and ABECFD. I find it interesting that they are not mirror images of each other!



            Two polygons: ACEBDF and ABECFD



            For $N$ from $4$ through $10$, we get $2, 4, 14, 54, 332, 2246,$ and $18264$ distinct polygons. This is OEIS entry A000939, Number of inequivalent n-gons.






            share|cite|improve this answer









            $endgroup$



            What we seek are: nontrivial cyclic permutations, with shifts and reversals counting as identical.



            Without the shift requirement, there are $(N-1)!$ different cyclic permutations. Shifting allows us to reduce that by up to a factor of $2N$, though not every permutation will be so accommodating. For instance, while there are six different cyclic 4-permutations, two of them (0123 and 0321) appear as identical squares and four (0132, 0213, 0231, and 0312) appear as bowties. Technically there's a maximal 8-fold symmetry but, as shown, nothing gets us there on $N=4$. The smallest that that happens to is on $N=6$: they must be free of both rotation and reflection symmmetries, like your fourth and fifth drawings.



            For relatively small $N$, we don't have to worry too terribly much about optimizations (they exist but many of them would also require pruning of the permutation tree before it reaches full length to be useful, which is complex), so we'll just write some code and see what happens.



            The code is here; edit line 3 (N = 6) to see different sizes. https://ideone.com/5PSyOJ



            Your diagram is missing two entries for $N=6$, shown here, ACEBDF and ABECFD. I find it interesting that they are not mirror images of each other!



            Two polygons: ACEBDF and ABECFD



            For $N$ from $4$ through $10$, we get $2, 4, 14, 54, 332, 2246,$ and $18264$ distinct polygons. This is OEIS entry A000939, Number of inequivalent n-gons.







            share|cite|improve this answer












            share|cite|improve this answer



            share|cite|improve this answer










            answered Nov 6 '18 at 12:27









            Dan UznanskiDan Uznanski

            7,24321529




            7,24321529












            • $begingroup$
              Thanks for going above and beyond! Do you mind explaining the cycle function in your code?
              $endgroup$
              – vdbeek
              Nov 7 '18 at 0:06






            • 1




              $begingroup$
              So, cycle works like this: it takes a permutation (which at this point is lacking the default 0) and an index, and rotates the whole thing around so that we get another permutation with the original index as the new permutation start. So if I have p=[2,4,1,3,5] and i=2, it plops a 0 on the end, then subtracts p[2]=1 from everything (now we've got [1,3,0,2,4,-1]), then mods those by 6 ([1,3,0,2,4,5]), then cycles it around so the 0 is at the beginning/end and then removes it so we're back to the normal state, which is [2,4,5,1,3]
              $endgroup$
              – Dan Uznanski
              Nov 7 '18 at 0:51










            • $begingroup$
              Ahhh so if we fix p and let i vary cycle(p,i) gives all of the rotated copies of p? If this is the case we must be computing the same thing a lot. Is it possible to speed up the calculations by removing the rotated cycles from permutations while still inside the for loop?
              $endgroup$
              – vdbeek
              Nov 7 '18 at 1:16








            • 1




              $begingroup$
              Indeed: we can store permutations we've found via cycle and reversal and check incoming permutations against that. ...But this has a downside: we now must store all those permutations! This gets untenably large quite quickly. Other optimizations include cutting off when we know that other versions will be smaller - since we enumerate permutations in lexicographic order, anything we find where the first element of the cycle is not the shortest can be cut short - and we can cut off whole sections of the permutation tree this way. But that means rewriting permutations to check substrings...
              $endgroup$
              – Dan Uznanski
              Nov 7 '18 at 1:56


















            • $begingroup$
              Thanks for going above and beyond! Do you mind explaining the cycle function in your code?
              $endgroup$
              – vdbeek
              Nov 7 '18 at 0:06






            • 1




              $begingroup$
              So, cycle works like this: it takes a permutation (which at this point is lacking the default 0) and an index, and rotates the whole thing around so that we get another permutation with the original index as the new permutation start. So if I have p=[2,4,1,3,5] and i=2, it plops a 0 on the end, then subtracts p[2]=1 from everything (now we've got [1,3,0,2,4,-1]), then mods those by 6 ([1,3,0,2,4,5]), then cycles it around so the 0 is at the beginning/end and then removes it so we're back to the normal state, which is [2,4,5,1,3]
              $endgroup$
              – Dan Uznanski
              Nov 7 '18 at 0:51










            • $begingroup$
              Ahhh so if we fix p and let i vary cycle(p,i) gives all of the rotated copies of p? If this is the case we must be computing the same thing a lot. Is it possible to speed up the calculations by removing the rotated cycles from permutations while still inside the for loop?
              $endgroup$
              – vdbeek
              Nov 7 '18 at 1:16








            • 1




              $begingroup$
              Indeed: we can store permutations we've found via cycle and reversal and check incoming permutations against that. ...But this has a downside: we now must store all those permutations! This gets untenably large quite quickly. Other optimizations include cutting off when we know that other versions will be smaller - since we enumerate permutations in lexicographic order, anything we find where the first element of the cycle is not the shortest can be cut short - and we can cut off whole sections of the permutation tree this way. But that means rewriting permutations to check substrings...
              $endgroup$
              – Dan Uznanski
              Nov 7 '18 at 1:56
















            $begingroup$
            Thanks for going above and beyond! Do you mind explaining the cycle function in your code?
            $endgroup$
            – vdbeek
            Nov 7 '18 at 0:06




            $begingroup$
            Thanks for going above and beyond! Do you mind explaining the cycle function in your code?
            $endgroup$
            – vdbeek
            Nov 7 '18 at 0:06




            1




            1




            $begingroup$
            So, cycle works like this: it takes a permutation (which at this point is lacking the default 0) and an index, and rotates the whole thing around so that we get another permutation with the original index as the new permutation start. So if I have p=[2,4,1,3,5] and i=2, it plops a 0 on the end, then subtracts p[2]=1 from everything (now we've got [1,3,0,2,4,-1]), then mods those by 6 ([1,3,0,2,4,5]), then cycles it around so the 0 is at the beginning/end and then removes it so we're back to the normal state, which is [2,4,5,1,3]
            $endgroup$
            – Dan Uznanski
            Nov 7 '18 at 0:51




            $begingroup$
            So, cycle works like this: it takes a permutation (which at this point is lacking the default 0) and an index, and rotates the whole thing around so that we get another permutation with the original index as the new permutation start. So if I have p=[2,4,1,3,5] and i=2, it plops a 0 on the end, then subtracts p[2]=1 from everything (now we've got [1,3,0,2,4,-1]), then mods those by 6 ([1,3,0,2,4,5]), then cycles it around so the 0 is at the beginning/end and then removes it so we're back to the normal state, which is [2,4,5,1,3]
            $endgroup$
            – Dan Uznanski
            Nov 7 '18 at 0:51












            $begingroup$
            Ahhh so if we fix p and let i vary cycle(p,i) gives all of the rotated copies of p? If this is the case we must be computing the same thing a lot. Is it possible to speed up the calculations by removing the rotated cycles from permutations while still inside the for loop?
            $endgroup$
            – vdbeek
            Nov 7 '18 at 1:16






            $begingroup$
            Ahhh so if we fix p and let i vary cycle(p,i) gives all of the rotated copies of p? If this is the case we must be computing the same thing a lot. Is it possible to speed up the calculations by removing the rotated cycles from permutations while still inside the for loop?
            $endgroup$
            – vdbeek
            Nov 7 '18 at 1:16






            1




            1




            $begingroup$
            Indeed: we can store permutations we've found via cycle and reversal and check incoming permutations against that. ...But this has a downside: we now must store all those permutations! This gets untenably large quite quickly. Other optimizations include cutting off when we know that other versions will be smaller - since we enumerate permutations in lexicographic order, anything we find where the first element of the cycle is not the shortest can be cut short - and we can cut off whole sections of the permutation tree this way. But that means rewriting permutations to check substrings...
            $endgroup$
            – Dan Uznanski
            Nov 7 '18 at 1:56




            $begingroup$
            Indeed: we can store permutations we've found via cycle and reversal and check incoming permutations against that. ...But this has a downside: we now must store all those permutations! This gets untenably large quite quickly. Other optimizations include cutting off when we know that other versions will be smaller - since we enumerate permutations in lexicographic order, anything we find where the first element of the cycle is not the shortest can be cut short - and we can cut off whole sections of the permutation tree this way. But that means rewriting permutations to check substrings...
            $endgroup$
            – Dan Uznanski
            Nov 7 '18 at 1:56











            4












            $begingroup$

            Deriving the general formula for this sequence (and its reflection-insensitive analogue) is precisely the content of:




            Golomb, S.W.; Welch, L.R., "On the enumeration of polygons", Amer. Math. Monthly, 67 (1960), 349-353.




            The authors derive the result as a clever application of Burnside's Lemma, giving for the count of $n$-pointed stars
            $$
            E(n)
            =
            left{
            begin{array}{ll}
            F(n) , & textrm{$n$ odd}\
            F(n) + displaystyle{frac{1}{2 n^2} cdot 2^{n / 2} {n choose 2} {n choose 2}!}, & textrm{$n$ even}
            end{array}
            right. ,
            $$

            where
            $$F(n) := frac{1}{2 n^2} sum_{d mid n} phi^2left(frac{n}{d}right) d! left(frac{n}{d}right)^d .$$
            Here, $phi$ is the Euler totient function.



            As Dan Uznanski's answer has pointed out, this is OEIS A000939, Number of inequivalent n-gons.



            Remark As Empy2's answer observes, the procedure for computing should be easier for prime $n$. Indeed, for odd primes $p$ the above formula simplifies to
            $$E(p) = frac{1}{2 p} [(p - 1)^2 + (p - 1)!] .$$ It follows from the fact that $E(p)$ is an integer that $p mid [(p - 1)^2 + (p - 1)!]$, and rearranging gives $$(p - 1)! equiv -1 pmod p ,$$ which recovers one direction of Wilson's Theorem.






            share|cite|improve this answer









            $endgroup$


















              4












              $begingroup$

              Deriving the general formula for this sequence (and its reflection-insensitive analogue) is precisely the content of:




              Golomb, S.W.; Welch, L.R., "On the enumeration of polygons", Amer. Math. Monthly, 67 (1960), 349-353.




              The authors derive the result as a clever application of Burnside's Lemma, giving for the count of $n$-pointed stars
              $$
              E(n)
              =
              left{
              begin{array}{ll}
              F(n) , & textrm{$n$ odd}\
              F(n) + displaystyle{frac{1}{2 n^2} cdot 2^{n / 2} {n choose 2} {n choose 2}!}, & textrm{$n$ even}
              end{array}
              right. ,
              $$

              where
              $$F(n) := frac{1}{2 n^2} sum_{d mid n} phi^2left(frac{n}{d}right) d! left(frac{n}{d}right)^d .$$
              Here, $phi$ is the Euler totient function.



              As Dan Uznanski's answer has pointed out, this is OEIS A000939, Number of inequivalent n-gons.



              Remark As Empy2's answer observes, the procedure for computing should be easier for prime $n$. Indeed, for odd primes $p$ the above formula simplifies to
              $$E(p) = frac{1}{2 p} [(p - 1)^2 + (p - 1)!] .$$ It follows from the fact that $E(p)$ is an integer that $p mid [(p - 1)^2 + (p - 1)!]$, and rearranging gives $$(p - 1)! equiv -1 pmod p ,$$ which recovers one direction of Wilson's Theorem.






              share|cite|improve this answer









              $endgroup$
















                4












                4








                4





                $begingroup$

                Deriving the general formula for this sequence (and its reflection-insensitive analogue) is precisely the content of:




                Golomb, S.W.; Welch, L.R., "On the enumeration of polygons", Amer. Math. Monthly, 67 (1960), 349-353.




                The authors derive the result as a clever application of Burnside's Lemma, giving for the count of $n$-pointed stars
                $$
                E(n)
                =
                left{
                begin{array}{ll}
                F(n) , & textrm{$n$ odd}\
                F(n) + displaystyle{frac{1}{2 n^2} cdot 2^{n / 2} {n choose 2} {n choose 2}!}, & textrm{$n$ even}
                end{array}
                right. ,
                $$

                where
                $$F(n) := frac{1}{2 n^2} sum_{d mid n} phi^2left(frac{n}{d}right) d! left(frac{n}{d}right)^d .$$
                Here, $phi$ is the Euler totient function.



                As Dan Uznanski's answer has pointed out, this is OEIS A000939, Number of inequivalent n-gons.



                Remark As Empy2's answer observes, the procedure for computing should be easier for prime $n$. Indeed, for odd primes $p$ the above formula simplifies to
                $$E(p) = frac{1}{2 p} [(p - 1)^2 + (p - 1)!] .$$ It follows from the fact that $E(p)$ is an integer that $p mid [(p - 1)^2 + (p - 1)!]$, and rearranging gives $$(p - 1)! equiv -1 pmod p ,$$ which recovers one direction of Wilson's Theorem.






                share|cite|improve this answer









                $endgroup$



                Deriving the general formula for this sequence (and its reflection-insensitive analogue) is precisely the content of:




                Golomb, S.W.; Welch, L.R., "On the enumeration of polygons", Amer. Math. Monthly, 67 (1960), 349-353.




                The authors derive the result as a clever application of Burnside's Lemma, giving for the count of $n$-pointed stars
                $$
                E(n)
                =
                left{
                begin{array}{ll}
                F(n) , & textrm{$n$ odd}\
                F(n) + displaystyle{frac{1}{2 n^2} cdot 2^{n / 2} {n choose 2} {n choose 2}!}, & textrm{$n$ even}
                end{array}
                right. ,
                $$

                where
                $$F(n) := frac{1}{2 n^2} sum_{d mid n} phi^2left(frac{n}{d}right) d! left(frac{n}{d}right)^d .$$
                Here, $phi$ is the Euler totient function.



                As Dan Uznanski's answer has pointed out, this is OEIS A000939, Number of inequivalent n-gons.



                Remark As Empy2's answer observes, the procedure for computing should be easier for prime $n$. Indeed, for odd primes $p$ the above formula simplifies to
                $$E(p) = frac{1}{2 p} [(p - 1)^2 + (p - 1)!] .$$ It follows from the fact that $E(p)$ is an integer that $p mid [(p - 1)^2 + (p - 1)!]$, and rearranging gives $$(p - 1)! equiv -1 pmod p ,$$ which recovers one direction of Wilson's Theorem.







                share|cite|improve this answer












                share|cite|improve this answer



                share|cite|improve this answer










                answered Nov 7 '18 at 0:34









                TravisTravis

                64.5k769151




                64.5k769151























                    3












                    $begingroup$

                    There are $6!=720$ cycles for $n=7$. Three patterns have 7-fold symmetry, and are covered by 2 cycles each - forwards and backwards. All the others have no symmetry and are covered by 14 cycles each - forwards, backwards and seven rotations. So there are $6/2+714/14=54$ patterns for $n=7$.

                    Composite $n$ are trickier of course.






                    share|cite|improve this answer









                    $endgroup$













                    • $begingroup$
                      A000939 is what you want. You must have missed two 6-stars.
                      $endgroup$
                      – Empy2
                      Nov 6 '18 at 11:31
















                    3












                    $begingroup$

                    There are $6!=720$ cycles for $n=7$. Three patterns have 7-fold symmetry, and are covered by 2 cycles each - forwards and backwards. All the others have no symmetry and are covered by 14 cycles each - forwards, backwards and seven rotations. So there are $6/2+714/14=54$ patterns for $n=7$.

                    Composite $n$ are trickier of course.






                    share|cite|improve this answer









                    $endgroup$













                    • $begingroup$
                      A000939 is what you want. You must have missed two 6-stars.
                      $endgroup$
                      – Empy2
                      Nov 6 '18 at 11:31














                    3












                    3








                    3





                    $begingroup$

                    There are $6!=720$ cycles for $n=7$. Three patterns have 7-fold symmetry, and are covered by 2 cycles each - forwards and backwards. All the others have no symmetry and are covered by 14 cycles each - forwards, backwards and seven rotations. So there are $6/2+714/14=54$ patterns for $n=7$.

                    Composite $n$ are trickier of course.






                    share|cite|improve this answer









                    $endgroup$



                    There are $6!=720$ cycles for $n=7$. Three patterns have 7-fold symmetry, and are covered by 2 cycles each - forwards and backwards. All the others have no symmetry and are covered by 14 cycles each - forwards, backwards and seven rotations. So there are $6/2+714/14=54$ patterns for $n=7$.

                    Composite $n$ are trickier of course.







                    share|cite|improve this answer












                    share|cite|improve this answer



                    share|cite|improve this answer










                    answered Nov 6 '18 at 11:11









                    Empy2Empy2

                    33.7k12562




                    33.7k12562












                    • $begingroup$
                      A000939 is what you want. You must have missed two 6-stars.
                      $endgroup$
                      – Empy2
                      Nov 6 '18 at 11:31


















                    • $begingroup$
                      A000939 is what you want. You must have missed two 6-stars.
                      $endgroup$
                      – Empy2
                      Nov 6 '18 at 11:31
















                    $begingroup$
                    A000939 is what you want. You must have missed two 6-stars.
                    $endgroup$
                    – Empy2
                    Nov 6 '18 at 11:31




                    $begingroup$
                    A000939 is what you want. You must have missed two 6-stars.
                    $endgroup$
                    – Empy2
                    Nov 6 '18 at 11:31


















                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Mathematics Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2986900%2fhow-many-n-pointed-stars-are-there%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    How to change which sound is reproduced for terminal bell?

                    Can I use Tabulator js library in my java Spring + Thymeleaf project?

                    Title Spacing in Bjornstrup Chapter, Removing Chapter Number From Contents