%I #55 May 13 2022 19:57:43

%S 1,5,20,70,240,810,2730,9180,30870,103770,348840,1172610,3941730,

%T 13249980,44539470,149717970,503272440,1691734410,5686712730,

%U 19115706780,64256852070,215997400170,726068516040,2440656636210,8204191055730,27578131979580,92703029288670

%N a(n) is the number of distinct reduced words of length n in the Coxeter group of "Apollonian reflections" in three dimensions.

%C Definition means that all possible length-reducing cancellations have been applied and words that are equal are counted only once.

%C This group has five generators, satisfying (S_i)^2 = (S_i S_j)^3 = I.

%C ABA and BAB are equal, so are counted as only one distinct word.

%H K. Brockhaus, <a href="/A154638/b154638.txt">Table of n, a(n) for n = 0..1000</a>

%H R. L. Graham, J. C. Lagarias, C. L. Mallows, Allan Wilks and C. Yan, <a href="http://arxiv.org/abs/math/0010324">Apollonian circle Packings: Geometry and Group Theory III Higher Dimensions</a>, arXiv:math/0010324 [math.MG], 2001-2005.

%H R. L. Graham, J. C. Lagarias, C. L. Mallows, Allan Wilks and C. Yan, <a href="http://dx.doi.org/10.1007/s00454-005-1197-8">Apollonian circle Packings: Geometry and Group Theory III Higher Dimensions</a>, Discrete and Computational Geometry 35: 37-72 (2006).

%H C. L. Mallows, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL12/Mallows/mallows8.html">Growing Apollonian packings</a>, J. Integer Sequences 12, article 09.2.1 (2009)

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3, 3, -6).

%F There's a handy program (or rather, a constellation of programs), kbmag by Derek Holt et al., which can be used as a package within GAP or as a free-standing program, to try to find an automatic structure for a group. I entered this presentation, and it produced an automatic structure, which implies the growth function is rational: (1 + 2*X + 2*X^2 + X^3)/(1 - 3*X - 3*X^2 + 6*X^3), as reported by kbgrowth. _John Cannon_ also found this g.f. - _William P. Thurston_, Nov 22 2009

%F Recurrence: for n >= 1, a(n+3) = 3*a(n+2) + 3*a(n+1) - 6*a(n) with a(0..3)={1,5,20,70}. - _Zak Seidov_, Dec 07 2009

%e There are 80 squarefree words of length 3, but 20 of these fall into 10 equal pairs (e.g., ABA = BAB). So a(3)=70.

%t CoefficientList[Series[(z^3 + 2 z^2 + 2 z + 1)/(6 z^3 - 3 z^2 - 3 z + 1), {z, 0, 100}], z] (* _Vladimir Joseph Stephan Orlovsky_, Jun 24 2011 *)

%t Join[{1},LinearRecurrence[{3,3,-6},{5,20,70},30]] (* _Harvey P. Dale_, Nov 16 2011 *)

%o (Magma) /* gives growth function and terms of sequence - from _Klaus Brockhaus_, Feb 13 2010 */

%o G := Group< s1, s2, s3, s4, s5 | [ s1^2, s2^2, s3^2, s4^2, s5^2, (s1*s2)^3, (s1*s3)^3, (s1*s4)^3, (s1*s5)^3, (s2*s3)^3, (s2*s4)^3, (s2*s5)^3, (s3*s4)^3, (s3*s5)^3, (s4*s5)^3 ] >;

%o A := AutomaticGroup(G);

%o f<x> := GrowthFunction(A); f;

%o T := PowerSeriesRing(Integers(), 27);

%o Eltseq(T!f);

%o (PARI) a(n)=if(n,([0,1,0;0,0,1;-6,3,3]^n*[5/6;5;20])[1,1],1) \\ _Charles R Greathouse IV_, Jun 11 2015

%Y For other sequences relating to the 3-dimensional case, see A154638-A154645.

%K nonn,easy

%O 0,2

%A _Colin Mallows_, Jan 13 2009

%E Corrected and extended with g.f. by _John Cannon_ and _William P. Thurston_, Nov 22 2009

%E Edited by _N. J. A. Sloane_, Nov 22 2009