login
The number of orbits of triples of {1,2,...,n} under the action of the dihedral group of order 2n.
7

%I #28 Jan 11 2021 22:37:25

%S 1,4,5,10,13,20,25,34,41,52,61,74,85,100,113,130,145,164,181,202,221,

%T 244,265,290,313,340,365,394,421,452,481,514,545,580,613,650,685,724,

%U 761,802,841,884,925,970,1013,1060,1105,1154,1201,1252

%N The number of orbits of triples of {1,2,...,n} under the action of the dihedral group of order 2n.

%C In other words, a(n) is the number of equivalence classes of length 3 words with an alphabet of size n where equivalence is up to rotation or reflection of the alphabet. For example when n is 3, the word 112 is equivalent to 223 and 331 by rotation of the alphabet, and these are equivalent to 332, 221 and 113 by reflection of the alphabet. - _Andrew Howroyd_, Jan 17 2020

%H Andrew Howroyd, <a href="/A236283/b236283.txt">Table of n, a(n) for n = 1..1000</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-2,1).

%F Conjectures from _Colin Barker_, Jan 21 2014: (Start)

%F a(n) = (5 + 3*(-1)^n + 2*n^2)/4.

%F a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4).

%F G.f.: -x*(2*x^3-3*x^2+2*x+1) / ((x-1)^3*(x+1)).

%F (End)

%F From _Andrew Howroyd_, Jan 17 2020: (Start)

%F The above conjectures are true and can be derived from the following formulas for even and odd n.

%F a(n) = (n-2)*(n + 2)/2 + 4 for even n.

%F a(n) = (n-1)*(n + 1)/2 + 1 for odd n.

%F (End)

%F a(n) = A081352(n - 1) - A116940(n - 1). - _Miko Labalan_, Nov 12 2016

%e For n = 3 there are 5 orbits of triples:

%e [[1,1,1], [2,2,2], [3,3,3]],

%e [[1,1,2], [2,2,3], [1,1,3], [3,3,1], [3,3,2], [2,2,1]],

%e [[1,2,1], [2,3,2], [1,3,1], [3,1,3], [3,2,3], [2,1,2]],

%e [[1,2,2], [2,3,3], [1,3,3], [3,1,1], [3,2,2], [2,1,1]],

%e [[1,2,3], [2,3,1], [1,3,2], [3,1,2], [3,2,1], [2,1,3]].

%o (GAP)

%o a:=function(n)

%o local g,orbs;

%o g:=DihedralGroup(IsPermGroup,2*n);

%o orbs := OrbitsDomain(g, Tuples( [ 1 .. n ], 3), OnTuples );

%o return Size(orbs);

%o end;;

%o (PARI) a(n) = {(5 + 3*(-1)^n + 2*n^2)/4} \\ _Andrew Howroyd_, Jan 17 2020

%Y Cf. A236332 (4-tuples).

%K nonn,easy

%O 1,2

%A _W. Edwin Clark_, Jan 21 2014