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

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

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

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

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 * A377660 A377661 A377662

Keyword

nonn

Author

Peter Luschny, Nov 28 2024

Status

approved