A396508 - OEIS

%I #33 Jul 11 2026 22:37:31

%S 1,1,4,3,14,14,59,61,256,278,1151,1280,5269,5967,24450,28049,114564,

%T 132746,540851,631642,2568523,3018929,12256952,14482690,58723951,

%U 69697187,282298202,336323743,1360966618,1626750122,6577540727,7884583033,31858039948,38284835162

%N Number of palindromic special Motzkin paths of weight n.

%C Equivalently, a(n) is the number of palindromic words over the alphabet {c, c'} union {A_r: r >= 0}, where c contributes i1=1, c' contributes i2=1, and A_r contributes j=1 and k=r. If i1, i2, j, k are the total statistics of the word, then the required conditions are i1+2*i2+2*k = n-1 and i2+j+2*k = n.

%C The block A_r corresponds to the special Motzkin path block a*d^r*b. Thus the words above encode palindromic special Motzkin paths of height at most 1.

%D J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge University Press, 2003.

%D P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math. 32 (1980), 125-161.

%D S. Fu and B. Gao, Lattice paths and the Prouhet-Thue-Morse sequence, Theoret. Comput. Sci. 1022 (2024), Article 114885.

%D H. Furstenberg, Algebraic functions over finite fields, J. Algebra 7 (1967), 271-277.

%D B. Gao, Lattice Paths and the Prouhet-Thue-Morse Sequence, Master's thesis, Chongqing University, 2023.

%F a(n) == A010060(n) (mod 2) for n >= 1.

%F For m >= 1, a(2*m) == (-1)^(m-1)*Sum_{i=0..m-1} C(i) (mod 5), where C(i) is the i-th Catalan number.

%F G.f.: x/(1-x^2)*sqrt((1-x^2)/(1-5*x^2)) + (1+x)/(2*(1+x^2))*(sqrt((1-x^2)/(1-5*x^2))-1).

%F Let E(x) = Sum_{m>=1} a(2*m)*x^m and O(x) = Sum_{m>=0} a(2*m+1)*x^m. Then E(x) = Y(x)/(1+x), O(x) = (1+2*Y(x))/(1-x) + Y(x)/(1+x), where Y(0)=0 and Y(x)^2+Y(x)=x/(1-5*x); that is, Y(x) = (sqrt((1-x)/(1-5*x))-1)/2.

%F Let b(m)=a(2*m), with b(0)=0. Then b(1)=1, b(2)=3, and, for m>=2, (m+1)*b(m+1) = (5*m+1)*b(m) + (m+7)*b(m-1) - 5*(m-1)*b(m-2).

%F For m>=1, a(2*m+1) = 1+3*b(m)+4*Sum_{i=1..m-1} b(i).

%F For m>=1, a(2*m) = Sum_{r+s+h=m, r>=1} (-1)^(r-1+h)*C(r-1)*binomial(s+r-1,r-1)*5^s.

%e Let b(m)=a(2*m). Since b(1)=1 and b(2)=3, the recurrence with m=2 gives 3*b(3) = 11*b(2)+9*b(1) = 42, so b(3)=14 and a(6)=14. Then a(7)=1+3*b(3)+4*(b(1)+b(2))=1+42+16=59.

%e For m=5, a(10)=278, while (-1)^4*(C_0+C_1+C_2+C_3+C_4)=1+1+2+5+14=23 == 3 (mod 5), and 278 == 3 (mod 5).

%o (Python)

%o def A(N):

%o     b = [0]*(N//2+4)

%o     if N >= 2:

%o         b[1] = 1

%o     if N >= 4:

%o         b[2] = 3

%o     for m in range(2, len(b)-1):

%o         b[m+1] = ((5*m+1)*b[m] + (m+7)*b[m-1] - 5*(m-1)*b[m-2])//(m+1)

%o     s = [0]*len(b)

%o     for m in range(1, len(b)):

%o         s[m] = s[m-1] + b[m]

%o     out = []

%o     for n in range(1, N+1):

%o         if n == 1:

%o             out.append(1)

%o         elif n % 2 == 0:

%o             out.append(b[n//2])

%o         else:

%o             m = (n-1)//2

%o             out.append(1 + 3*b[m] + 4*s[m-1])

%o     return out

%o print(A(40))

%Y Cf. A000108, A010060.

%K nonn,easy,new

%O 1,3

%A _Bing Gao_, Jul 05 2026