|
%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
|
