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,6

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.

Links

Table of n, a(n) for n=0..31.

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

Example

  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.

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

Prog

(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)}")

Crossrefs

Cf. A001006, A011782, A125107.

Sequence in context: A003296 A053545 A049612 * A211842 A304134 A318946

Adjacent sequences: A377656 A377657 A377658 * A377661 A377662 A377663

Keyword

nonn,new

Author

Peter Luschny, Nov 28 2024

Status

approved