/sci/ - Science & Math

[Anonymous No.6755428]

Hi /sci/
Ran into a weird graph problem in a programming project...
If I have a n-sided regular polygon, how many ways can two colors be used to color the sides if rotational symmetries are ignored?
Image is the n=6 case, and unless I'm missing one, it looks like there are 13 ways.
Any advice on finding a generic f(n) formula would be swell.

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755450]

>>6755428
1+(n^2 +1)/n + (n^2 - 1)/n

should work.
n@1=3

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755457]

>>6755428
this is because
1ab
axy
byx
so you get
S[2xx, 2xy, 2yy]
ignoring symmetry: (1/2)S
[xx,xy,yy]
[00, 1, 2]
or
[2, 1, 00]

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755467]

>>6755428
for 4

[Anonymous No.6755469]

>>6755467
>>6755457
>>6755450
>>6755450
>>6755457

So this?
<span class="math">1+\frac{n^2+1}{n}+\frac{n^2-1}{n}[/spoiler]

I'm experimenting with different n now, thank you...

[Anonymous No.6755474]

>>6755467
I think there are only 6 for n = 4... The diagonal lines in your image aren't "sides." And the two-vertical and two-horizontal are rotations of each other.

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755475]

>>6755469
something like that, yes
http://en.wikipedia.org/wiki/Rolle's_theorem

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755480]

>>6755474

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755485]

>>6755480
10000001
01000010
00100100
00011000
00111100
01111110
11111111
01010101
10101010

[Anonymous No.6755491]

>>6755469
>>6755475
I think that simplifies to 2n + 1... Which is correct for n = 6...

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755498]

>>6755474
>>6755480
middle one should be red/blue.
https://www.khanacademy.org/math/precalculus/seq_induction/infinite-geometric-series/v/infinite-geometric-series

for 4/(.5) you'd get 8. for the geometric mean of the 2n+1 formula i gave you, with this, you'd get 12. the average would then be 6.

however because you are using a permutation of base2 (on/off) on n vertices the 2n+1 formula works best.

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755501]

>>6755498
>>6755485
>>6755480
>>6755475
>>6755467
>>6755457
>>6755428
6_sides.png

my sides are in ORBIT

[Anonymous No.6755510]

>>6755501
ha
Well if anyone has any ideas, here are n = 3 and n = 4 to maybe better illustrate the question.

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755526]

>>6755510
100001
010010
001100
011110
111111
101010
010101

1+(3^2-1)/3 +(3^2+1)/3 = 7

6/(1-0.5) = 12

2(12*7)^((1/4)) = 6.055..
(1/3)(12*7)^(1/2) = 3.055..

6_sides

[]
[][][][][]
....[]

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755531]

>>6755526
1 Corinthians 12 7-11
7 To each is given the manifestation of the Spirit for the common good.
8 To one is given through the Spirit the utterance of wisdom, and to another the utterance of knowledge according to the same Spirit,
9 to another faith by the same Spirit, to another gifts of healing by the one Spirit,
10 to another the working of miracles, to another prophecy, to another the discernment of spirits, to another various kinds of tongues, to another the interpretation of tongues.
11 All these are activated by one and the same Spirit, who allots to each one individually just as the Spirit chooses.


1 John 4 7-12
7 Beloved, let us love one another, because love is from God; everyone who loves is born of God and knows God.
8 Whoever does not love does not know God, for God is love.
9 God’s love was revealed among us in this way: God sent his only Son into the world so that we might live through him.
10 In this is love, not that we loved God but that he loved us and sent his Son to be the atoning sacrifice for our sins.
11 Beloved, since God loved us so much, we also ought to love one another.
12 No one has ever seen God; if we love one another, God lives in us, and his love is perfected in us.

0 0000
1 0110
2 1001
3 1111
0 00000
1 00100
2 01010
3 10001
4 10101
5 11011
6 11111
0 000000
1 001100
2 010010
3 100001
4 101101
5 110011
6 111111
0 0000000
1 0001000 11011 00100 101101 010010
2 0010100 10001 10001 100001 011110
3 0100010 01010 10101 010010 101101 1001
4 1000001 00100 11011 001100 110011 0110
5 1001001 01010 10101 001100 110011 0110
6 1010101 10001 01110 010010 101101 1001
7 1100011 10101 01010 100001 011110
8 1110111 11011 00100 101101 010010
9 1111111

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755539]

>>6755531
>>6755526
..[][]......[][]
[][][][]..[][][][]
...[]...[]...[]...
...[]...[]...[]...
[][][][]..[][][][]
..[][].......[]

15 hands
4 more than 11
8 more than 7

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755544]

>>6755539
>>6755531

[Anonymous No.6755545]

my guess would be that if there is an expression for it, then it is a recursive one

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755554]

>>6755544
>>6755526
>09/14/14-7-19:44:11
>>6755501
>09/14/14-7-19:30:44
>>6755539
>15 hands
>4 more than 11
>8 more than 7

[Anonymous No.6755566]

here q(k) is the number of partitions of the integer k into distinct parts

http://mathworld.wolfram.com/PartitionFunctionQ.html

also for mathematica

Table[Sum[PartitionsQ[k], {k, 1, n}], {n, 1, 10}]

{1, 2, 4, 6, 9, 13, 18, 24, 32, 42}

why? I leave it to you as a combinatorial excercise :^)

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755573]

>>6755566
http://en.wikipedia.org/wiki/Gauge_transformation#Classical_gauge_theory

[Anonymous No.6755582]

>>6755566
There it is
Thanks anon

[Anonymous No.6755649]

>>6755582

could you draw me a pentagon like you draw others

I think I'm wrong :(

[Anonymous No.6755667]

>>6755649
I think this is right...

[Anonymous No.6755670]

>>6755649
>>6755667
btw, I'm writing a C program to give me the answer for any given n... so in a few minutes I'll be able to tell you for sure

[Anonymous No.6755681]

>>6755667

its not right :( my formula gives 9 for pentagon sorry

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755688]

>>6755667
2(n^2 + n)/n - (n-1)

[Anonymous No.6755698]

>>6755681

also, the problem is that you find all non-isomorphic subgraphs of a cycle graph and finding those subgraphs is very non-trivial. I'll try to figure something

[Anonymous No.6755700]

>>6755681
i can't think of the ninth possibility though.

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755702]

>>6755698

[Anonymous No.6755703]

>>6755700

lol, I mean my formula is not right! your drawing is correct.

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755704]

>>6755698
>>6755702

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755706]

>>6755704
>>6755702

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755716]

>>6755712
>>6755707
>>6755604
>>6755706

[Anonymous No.6755783]

>>6755703

welp I got it, you just use polya enumeration tm.

find generating function for dihedral group D_n then use 1+x as your two colors, then sum all coef. and that's it

for D_6 you get 13 just like it should, because it excludes reflections too.
http://en.wikipedia.org/wiki/P%C3%B3lya_enumeration_theorem

there is also an example for n=3 on wiki lol

http://en.wikipedia.org/wiki/Cycle_index


so there is no nice formula for this, sorry.

[Anonymous No.6755805]

>>6755783
Cool, I just got my program working. A program is technically a "formula," anyway. :)

Turns out I was wrong for n = 6. There are actually 14 possibilities. I missed one in the middle column.

[Anonymous No.6755812]

>>6755783
>>6755805
Oh, right, I was not including reflections. If you do include them, then there are 14 for n = 6. If not, then there are 13.

[Anonymous No.6755828]

>>6755812

yeah. here is the formula from Polya enumeration tm. for excluded rotations only. it's a sum over divisors of n.


and mathematica code

Table[(1/n) Sum [EulerPhi[d]*2^(n/d), {d, Divisors[n]}], {n, 1, 15}]

gives a table for first 15 n's.

{2, 3, 4, 6, 8, 14, 20, 36, 60, 108, 188, 352, 632, 1182, 2192}

as you can see they agree.

could you post the code? I would like to see it

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755837]

>>6755805
>>6755812
>>6755783
https://www.youtube.com/watch?v=CzzZkkiJMv8

1 3 5 7 11 13 17
1 1 a 001
1 3 b 003
1 5 c 005
1 7 d 007
1 11 e 011
1 13 f 013
1 17 g 017
3 3 h 009
3 5 i 015
3 7 j 021
3 11 k 033
3 13 l 039
3 17 m 051
5 5 n 025
5 7 o 035
5 11 p 055
5 13 q 065
5 17 r 085
7 7 s 049
7 11 t 077
7 13 u 091
7 17 v 119
11 11 w 121
11 13 x 143
11 17 y 187
13 13 z 169
13 17 . 221
17 17 289


1 1 3 003 a
1 1 5 005 b
1 1 7 007 c
1 1 11 011 d
1 3 3 009 e
1 3 5 015 f
1 3 7 021 g
1 3 11 033 h
1 5 5 025 i
1 5 7 035 j
1 5 11 055 k
1 7 7 049 l
1 7 11 077 m
1 11 11 121 n
3 3 5 045 o
3 3 7 063 p
3 3 11 099 q
3 5 5 075 r
3 5 7 105 s
3 5 11 343 t
3 7 7 147 u
3 7 11 231 v
5 5 7 175 w
5 5 11 275 x
5 7 7 245 y
5 7 11 385 z
5 11 11 605 ,
7 7 11 539 .
7 11 11 847

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755838]

>>6755837
>>6755828
>>6755805
#include <stdio.h>
#include <math.h>

int main(void)
{

//Input Variables
float n, pa, d, rim, hub, bore;

//Output variables
float p, a, od, b, dr, tc, i, f;

//ask for input
printf("All input values are in inches\n");
printf("\nPlease input the value for N: ");
scanf("%f", &n);
printf("\nPlease input the value for PA: ");
scanf("%f", &pa);
printf("\nPlease input the value for D: ");
scanf("%f", &d);
printf("\nPlease input the value for Rim: ");
scanf("%f", &rim);
printf("\nPlease input the value for Hub: ");
scanf("%f", &hub);
printf("\nPlease input the value for Bore: ");
scanf("%f", &bore);

//Run calculations
p= n/d;
a= 1/p;
od= d+(2*a);
b= 1.157/p;
dr= d-(2*b);
tc= d*sin(90/n);
i= d/8;
f= b/7;

//inform user that dick sucking is not optional
printf("Suck my dick. \n");

//output payment for whoring out
printf("p: %.3f \na: %.3f \nod: %.3f \nb: %.3f \ndr: %.3f \ntc: %.3f \ni: %.3f \nf: %.3f", p, a, od, b, dr, tc, i, f);

return 1;
}

[Anonymous No.6755874]

>>6755828
Here's the code:
http://pastebin.com/4gfKnXyF

Those commented-out "printf" lines were to help me keep track of things... you can un-comment them if you want to see each combination being tested.

[Anonymous No.6755886]

>>6755874

that's some really nice code there, thanx

[Anonymous No.6755906]

>>6755428
Shouldn't there be 4 choices in your picture where there is 3 sides of each color?

When side 1,2 and 5 are colored (named from the top clockwise), that is not rotationally symmetric to 1,2 and 4, but rather it has line symmetry.

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755930]

>>6755906
>Shouldn't there be 4 choices in your picture where there is 3 sides of each color?

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755935]

>>6755930
>http://pastebin.com/4gfKnXyF
>>6755906

[Anonymous No.6755938]

>>6755906

read the thread pls, he forgot one, but accidentally gave an example with excluded reflections too

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755954]

>>6755930
>>6755935
>>6755938
captcha: Monthly apbeli

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6755977]

>>6755954
>>6755935
>>6755930
||..41.7.14..||^2
(7x+i)^2 + (7y-i)^2 = (i*7z)^2

(7x+i)^2 + (7y-i)^2 = (i*7z)^2
(49x^2 + 14ix - 1) + (49y^2 - 14iy + 1) = -49z^2
(49x^2 + 14ix) + (49y^2 - 14iy) + 49z^2 = 0
x/y=x+y=z
(x/y)^2 = (x+y)^2 = z^2
x^2 + 2xy + y^2 = z^2

(49x^2 + 14ix) + (49y^2 - 14iy) = -49x^2 - 84xy - 49y^2

(98x^2 + 14ix) + (98y^2 - 14iy) + 84xy = 0

x(98x + 14i + 84) + y(98y - 14i + 84) = 0

z(98x + 98y +84)=0
14z(7x+7y+6)=0
z(7x+7y+6)=0
7xz + 7yz + 6z = 0
z(7z + 7z) + 6z = 0
14z^2 + 6z = 0
7z^2 = -6z

(7x + i) + (7y - i) = -6(x/y)
x/y=phi
-6z = -9.70..
7z^2 = 18.32..
-6z^2 = -15.7082..
7z = 11.326..
7z^2/-6z = 1.88770632021..
-6z^2/7z = -1.38688..
(7z^2/(-6z))/(-6z^2/(7z^2))=(136.11..)

famous number "3131.5" of http://einsteingravity.com/ = 23*(136.11..)

because -5(7,4,1,2,3)=0

www.redmoonrapture.com/2014-2015.html

captcha: ngngards cyclically

[Dr. John D10Hoistr-ApryN01N Ti(...) !SSDoCt0rTo No.6756039]

>>6755977
called it, kaito.
sayonara
one fish, too fish
captcha: Roche zonessol

[Anonymous No.6756219]

If n is odd, f(n) = (2^n +2n - 2)/n. It's complicated for even n.

[Anonymous No.6756230]

>>6756219
not for odd n (doesn't work for 9), it's for n that is prime.