cp's OEIS Frontend

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

%I A154638 #55 May 13 2022 19:57:43
%S A154638 1,5,20,70,240,810,2730,9180,30870,103770,348840,1172610,3941730,
%T A154638 13249980,44539470,149717970,503272440,1691734410,5686712730,
%U A154638 19115706780,64256852070,215997400170,726068516040,2440656636210,8204191055730,27578131979580,92703029288670
%N A154638 a(n) is the number of distinct reduced words of length n in the Coxeter group of "Apollonian reflections" in three dimensions.
%C A154638 Definition means that all possible length-reducing cancellations have been applied and words that are equal are counted only once.
%C A154638 This group has five generators, satisfying (S_i)^2 = (S_i S_j)^3 = I.
%C A154638 ABA and BAB are equal, so are counted as only one distinct word.
%H A154638 K. Brockhaus, <a href="/A154638/b154638.txt">Table of n, a(n) for n = 0..1000</a>
%H A154638 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 A154638 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 A154638 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 A154638 <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3, 3, -6).
%F A154638 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 A154638 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 A154638 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 A154638 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 A154638 Join[{1},LinearRecurrence[{3,3,-6},{5,20,70},30]] (* _Harvey P. Dale_, Nov 16 2011 *)
%o A154638 (Magma) /* gives growth function and terms of sequence - from _Klaus Brockhaus_, Feb 13 2010 */
%o A154638 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 A154638 A := AutomaticGroup(G);
%o A154638 f<x> := GrowthFunction(A); f;
%o A154638 T := PowerSeriesRing(Integers(), 27);
%o A154638 Eltseq(T!f);
%o A154638 (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 A154638 For other sequences relating to the 3-dimensional case, see A154638-A154645.
%K A154638 nonn,easy
%O A154638 0,2
%A A154638 _Colin Mallows_, Jan 13 2009
%E A154638 Corrected and extended with g.f. by _John Cannon_ and _William P. Thurston_, Nov 22 2009
%E A154638 Edited by _N. J. A. Sloane_, Nov 22 2009