A396508 Number of palindromic special Motzkin paths of weight n.

1, 1, 4, 3, 14, 14, 59, 61, 256, 278, 1151, 1280, 5269, 5967, 24450, 28049, 114564, 132746, 540851, 631642, 2568523, 3018929, 12256952, 14482690, 58723951, 69697187, 282298202, 336323743, 1360966618, 1626750122, 6577540727, 7884583033, 31858039948, 38284835162

Offset

1,3

Comments

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.

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.

References

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

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

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

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

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

Links

Table of n, a(n) for n=1..34.

Formula

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

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.

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).

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.

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).

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

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.

Example

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.
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).

Prog

(Python)
def A(N):
    b = [0]*(N//2+4)
    if N >= 2:
        b[1] = 1
    if N >= 4:
        b[2] = 3
    for m in range(2, len(b)-1):
        b[m+1] = ((5*m+1)*b[m] + (m+7)*b[m-1] - 5*(m-1)*b[m-2])//(m+1)
    s = [0]*len(b)
    for m in range(1, len(b)):
        s[m] = s[m-1] + b[m]
    out = []
    for n in range(1, N+1):
        if n == 1:
            out.append(1)
        elif n % 2 == 0:
            out.append(b[n//2])
        else:
            m = (n-1)//2
            out.append(1 + 3*b[m] + 4*s[m-1])
    return out
print(A(40))

Crossrefs

Cf. A000108, A010060.

Sequence in context: A056479 A056480 A284841 * A334752 A197883 A222195

Adjacent sequences: A396505 A396506 A396507 * A396509 A396510 A396511

Keyword

nonn,easy,new

Author

Bing Gao, Jul 05 2026

Status

approved