|
|
A154638
|
|
a(n) is the number of distinct reduced words of length n in the Coxeter group of "Apollonian reflections" in three dimensions.
|
|
2315
|
|
|
1, 5, 20, 70, 240, 810, 2730, 9180, 30870, 103770, 348840, 1172610, 3941730, 13249980, 44539470, 149717970, 503272440, 1691734410, 5686712730, 19115706780, 64256852070, 215997400170, 726068516040, 2440656636210, 8204191055730, 27578131979580, 92703029288670
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
Definition means that all possible length-reducing cancellations have been applied and words that are equal are counted only once.
This group has five generators, satisfying (S_i)^2 = (S_i S_j)^3 = I.
ABA and BAB are equal, so are counted as only one distinct word.
|
|
LINKS
|
|
|
FORMULA
|
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
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
|
|
EXAMPLE
|
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.
|
|
MATHEMATICA
|
Join[{1}, LinearRecurrence[{3, 3, -6}, {5, 20, 70}, 30]] (* Harvey P. Dale, Nov 16 2011 *)
|
|
PROG
|
(Magma) /* gives growth function and terms of sequence - from Klaus Brockhaus, Feb 13 2010 */
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 ] >;
A := AutomaticGroup(G);
f<x> := GrowthFunction(A); f;
T := PowerSeriesRing(Integers(), 27);
Eltseq(T!f);
(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
|
|
CROSSREFS
|
For other sequences relating to the 3-dimensional case, see A154638-A154645.
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|