A377659 a(n) = Motzkin(n) - 2^(n - 1 + 0^n) = A001006(n) - A011782(n).

0, 0, 0, 0, 1, 5, 19, 63, 195, 579, 1676, 4774, 13463, 37739, 105442, 294188, 820699, 2291243, 6405310, 17937140, 50327731, 141498983, 398666071, 1125566111, 3184339189, 9026625285, 25636264044, 72940663938, 207889060481, 593474349373, 1696848600299, 4858687934567

Offset: 0

Author

Peter Luschny, Nov 28 2024

Keywords

• nonn

Comments

These are the Motzkin words of length n - 1 over the alphabet 0, 1, 2,... that contain at least one digit greater than 1. See the Sage program below.

An analogous construction with the Catalan numbers can be found in A125107.

Examples

			  N:       0, 1, 2, 3, 4,  5,  6,   7,   8,   9, ...
  A001006: 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, ...
  A011782: 1, 1, 2, 4, 8, 16, 32,  64, 128, 256, ...
  a:       0, 0, 0, 0, 1,  5, 19,  63, 195, 579, ...
.
For n = 5 the 5 Motzkin words of length 4 that have at least one term > 1 are:
  1221, 1211, 1210, 1121, 0121.
For n = 6 the 19 Motzkin words of length 5 that have at least one term > 1 are:
  12321, 12221, 12211, 12210, 12121, 12111, 12110, 12101, 12100, 11221, 11211, 11210, 11121, 10121, 01221, 01211, 01210, 01121, 00121.
		

Links

• Paolo Xausa, Table of n, a(n) for n = 0..1000

Crossrefs

Cf. A001006, A011782, A125107.

Programs

Maple

gf := (1 - x - (1-2*x-3*x^2)^(1/2)) / (2*x^2) - (1 - x) / (1 - 2*x):
ser := series(gf, x, 35): seq(coeff(ser, x, n), n = 0..30);
# Alternative:
a := n -> hypergeom([-n/2 + 1/2, -n/2], [2], 4) - 2^(n - 1 + 0^n);
seq(simplify(a(n)), n = 0..29);

Mathematica

A377659[n_] := If[n < 4, 0, HypergeometricPFQ[{-n/2, -n/2 + 1/2}, {2}, 4] - 2^(n - 1)];
Array[A377659, 50, 0] (* Paolo Xausa, Dec 04 2024 *)

Python

from itertools import islice
show = lambda f, n: print(list(islice(f(), n)))
def aGen():
    a, b, n, z = 1, 2, 2, 1
    yield 0
    while True:
        yield b//n - z
        n += 1; z *= 2
        a, b = b, (3*(n-1)*n*a + (2*n-1)*n*b)//((n+1)*(n-1))
show(aGen, 31)

SageMath

# Generates Motzkin words (for illustration only).
def motzkin_words(n):
     return IntegerListsLex(length=n+1, min_slope=-1, max_slope=1,
                ceiling=[0]+[+oo for i in range(n-1)]+[0])
def MWList(n, show=True):
    c = 0
    for w in motzkin_words(n):
        if any(p > 1 for p in w):
            c += 1
            if show: print(''.join(map(str, w[1:-1])))
    return c
for n in range(8): print(f"[{n}] -> {MWList(n)}")

Formula

a(n) = [x^n] (1 - x - (1 - 2*x - 3*x^2)^(1/2)) / (2*x^2) - (1 - x) / (1 - 2*x).

a(n) = hypergeom([-n/2, -n/2 + 1/2], [2], 4) - 2^(n - 1 + 0^n).