A094829 Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 9 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 1, s(2n+1) = 6.

1, 6, 27, 109, 417, 1548, 5644, 20349, 72846, 259579, 922209, 3269889, 11579032, 40967400, 144863001, 512050438, 1809503019, 6393427173, 22587086305, 79791176292, 281856708180, 995606748757, 3516721295214

Offset: 2

Author

Herbert Kociemba, Jun 13 2004

Keywords

• nonn
• easy

Comments

In general, a(n) = (2/m)*Sum_{r=1..m-1} sin(r*j*Pi/m)*sin(r*k*Pi/m)*(2*cos(r*Pi/m))^(2n+1) counts (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < m and |s(i)-s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = j, s(2n+1) = k.

a(n)/a(n-1) tends to 3.53208888...; = 2 + 2*cos(2*Pi/9) = A332438. - Gary W. Adamson, May 29 2008

From Wolfdieter Lang, Mar 27 2020: (Start)

The explicit form is written in terms of r = rho(9) = 2*cos(Pi/9) = A332437 as a Binet - de Moivre type formula a(n+2) = r^(2*(n+1))*(A(r) + Bp(r)*Cp(r)^(n+1)) + Bm(r)*Cm(r)^(n+1)), with A(r) = (1/9)*(2 + 5*r -r^2), approx. 0.87387081, Bp(r) = (1/18)*((14*r^2 - 5*r - 42)*sqrt(3*(3*r + 1)*(r - 1)) + r^2 - 5*r - 2) = (1/9)*(8 - r - 4*r^2), approx. -0.88974898, Cp(r) = (1/2)*(9*r^2 - 3*r - 26)*(3*r - 1 + sqrt(3*(3*r+1)*(r-1))) = 32 + 4*r - 11*r^2, approx. 0.66456322, Bm(r) = (1/18)*(-(14*r^2 - 5*r - 42)*sqrt(3*(3*r + 1)*(r - 1)) + r^2 - 5*r - 2) = (1/9)*(-10 -4*r + 5*r^2), approx. 0.01587816, and Cm(r) = (1/2)*(9*r^2 - 3*r - 26)*(3*r - 1 - sqrt(3*(3*r + 1)*(r - 1))) = 21 + 2*r - 7*r^2, approx. 0.03414828, for n >= 0.

Proof by partial fraction decomposition of the g.f. using the roots of 1 - 6*x + 9*x^2 - x^3 written in terms of r, which are X1(r) = 1/r^2 = 9 + r - 3*r^2, approx. 0.28311858, Xp(r) = (r/2)*(3*r - 1 + sqrt((3*(3*r+1))*(r-1))) = 1 + 2*r + r^2, approx. 8.29085937, Xm(r) = (r/2)*(3*r - 1 - sqrt((3*(3*r + 1))*(r - 1))) = -1 - 3*r + 2*r^2, approx. 0.42602205. Xp(r)*Xm(r) = r^2. The reduction with the minimal polynomial of r = rho(9), i.e., C(9, x) = x^3 - 3*x - 1 (see A187360) has been used to avoid all powers of r larger than 2. The reciprocal roots turn out to be the roots of the minimal polynomial of r^2, see A332438. 1/X1(r) = r^2, 1/Xp(r) = 2 - r, and 1/Xm(r) = 4 + r - r^2.

This proves the above stated limit of a(n+3)/a(n+2) for n to infinity, namely r^2 = A332438, approx. 3.53208889.

(End)

Links

• Michael De Vlieger, Table of n, a(n) for n = 2..1825
• László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
• Index entries for linear recurrences with constant coefficients, signature (6,-9,1).

Crossrefs

Cf. A080938, A094256, A332437, A332438.

Programs

Mathematica

Drop[CoefficientList[Series[x^2/(1 - 6 x + 9 x^2 - x^3), {x, 0, 24}], x], 2] (* Michael De Vlieger, Aug 05 2021 *)

Formula

a(n) = (2/9)*Sum_{r=1..8} sin(r*Pi/9)*sin(2*r*Pi/3)*(2*cos(r*Pi/9))^(2*n+1), for n >= 2.

a(n) = 6*a(n-1) - 9*a(n-2) + a(n-3).

G.f.: x^2/(1 - 6x + 9x^2 - x^3).

For the explicit form of a(n+2), for n >= 0, see a comment above. - Wolfdieter Lang, Mar 26 2020