How many $n$-pointed stars are there?
$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:
And I think there are twelve 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
$endgroup$
add a comment |
$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:
And I think there are twelve 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
$endgroup$
add a comment |
$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:
And I think there are twelve 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
$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:
And I think there are twelve 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
combinatorics combinatorial-geometry algebraic-combinatorics
asked Nov 6 '18 at 8:48
vdbeekvdbeek
535
535
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$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!
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.
$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 default0
) 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 havep=[2,4,1,3,5]
andi=2
, it plops a 0 on the end, then subtractsp[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 the0
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 fixp
and leti
varycycle(p,i)
gives all of the rotated copies ofp
? 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 frompermutations
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
add a comment |
$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.
$endgroup$
add a comment |
$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.
$endgroup$
$begingroup$
A000939 is what you want. You must have missed two 6-stars.
$endgroup$
– Empy2
Nov 6 '18 at 11:31
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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!
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.
$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 default0
) 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 havep=[2,4,1,3,5]
andi=2
, it plops a 0 on the end, then subtractsp[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 the0
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 fixp
and leti
varycycle(p,i)
gives all of the rotated copies ofp
? 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 frompermutations
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
add a comment |
$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!
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.
$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 default0
) 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 havep=[2,4,1,3,5]
andi=2
, it plops a 0 on the end, then subtractsp[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 the0
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 fixp
and leti
varycycle(p,i)
gives all of the rotated copies ofp
? 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 frompermutations
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
add a comment |
$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!
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.
$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!
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.
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 default0
) 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 havep=[2,4,1,3,5]
andi=2
, it plops a 0 on the end, then subtractsp[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 the0
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 fixp
and leti
varycycle(p,i)
gives all of the rotated copies ofp
? 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 frompermutations
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
add a comment |
$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 default0
) 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 havep=[2,4,1,3,5]
andi=2
, it plops a 0 on the end, then subtractsp[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 the0
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 fixp
and leti
varycycle(p,i)
gives all of the rotated copies ofp
? 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 frompermutations
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
add a comment |
$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.
$endgroup$
add a comment |
$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.
$endgroup$
add a comment |
$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.
$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.
answered Nov 7 '18 at 0:34
TravisTravis
64.5k769151
64.5k769151
add a comment |
add a comment |
$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.
$endgroup$
$begingroup$
A000939 is what you want. You must have missed two 6-stars.
$endgroup$
– Empy2
Nov 6 '18 at 11:31
add a comment |
$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.
$endgroup$
$begingroup$
A000939 is what you want. You must have missed two 6-stars.
$endgroup$
– Empy2
Nov 6 '18 at 11:31
add a comment |
$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.
$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.
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
add a comment |
$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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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