A304979 The nonzero terms of the cogrowth sequence of (Z/5Z)^*2 = * with respect to the generating set {(x,1), (1,y)}.

1, 2, 12, 92, 792, 7302, 70464, 702536, 7178568, 74771570, 790906012, 8472417384, 91724327928, 1001987961834, 11030476949952, 122247789508992, 1362840516623944, 15272530735735338, 171946029518128956, 1943927810200670820, 22059590401383177792, 251183781609841838444

Offset: 0

Author

Marni Mishna, May 22 2018

Keywords

• nonn

Comments

The number of paths on the Cayley graph of ((Z/5Z)^*2, {(x,1), (1,y)} which start and end at the identity.

a(n) is the number of words of length 5n over the alphabet {x,y} that reduce to the empty string upon iteratively removing factors of x^5 and y^5. For n=2, the a(2)=12 words of length 10 that reduce to the empty string are x^10, y^10, x^i y^5 x^(5-i), for i=1..5, and y^i x^5 y^(5-i), for i=1..5.

Links

• J. P. Bell and M. J. Mishna, On the Complexity of the Cogrowth Sequence, arXiv:1805.08118 [math.CO], 2018-2019.

Crossrefs

Related cogrowth sequences (Z/2Z)^*2: A126869; (Z/3Z)^*2: A047098; (Z/4Z)^*2: A107026.

Programs

Mathematica

terms = 22;
A[] = 0; Do[A[x] = (1 + 4 A[x] + 6 A[x]^2 + 4 A[x]^3 + A[x]^4 + 32 x A[x]^5)/(1 + A[x])^4 + O[x]^terms // Normal, {terms}];
CoefficientList[A[x], x] (* Jean-François Alcover, Nov 16 2018 *)

Formula

G.f.: A(x) satisfies 32*x*A(x)^5 - (A(x)-1)*(A(x)+1)^4 = 0.

a(n) satisfies the recurrence (2120000*(5*n+1))*(5*n+2)*(5*n+3)*(5*n+4)*a(n) + (250*(160980199*n^4 + 1129209134*n^3 + 2872721885*n^2 + 3155706646*n + 1267579560))*a(n+1) - (50*(109722203*n^4 + 959367613*n^3 + 3144281425*n^2 + 4572924587*n + 2485585548))*a(n+2) + (60*(4290021*n^4 + 51502996*n^3 + 243316306*n^2 + 532456081*n + 451079946))*a(n+3) - (3*(2673299*n^4 + 44756419*n^3 + 283571239*n^2 + 805783469*n + 866093430))*a(n+4) + (4008*(n+5))*(4*n+17)*(2*n+9)*(4*n+19)*a(n+5) = 0.

a(n) ~ 5^(5*n + 1/2) / (9 * sqrt(Pi) * n^(3/2) * 2^(8*n - 3/2)). - Vaclav Kotesovec, Oct 24 2023

a(n) = binomial(5*n,n) - 3 * Sum_{k=0..n-1} binomial(5*n,k). - Seiichi Manyama, Apr 05 2024