A377659 - OEIS

%I #27 Dec 02 2024 17:20:15

%S 0,0,0,0,1,5,19,63,195,579,1676,4774,13463,37739,105442,294188,820699,

%T 2291243,6405310,17937140,50327731,141498983,398666071,1125566111,

%U 3184339189,9026625285,25636264044,72940663938,207889060481,593474349373,1696848600299,4858687934567

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

%C 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.

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

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

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

%e   N:       0, 1, 2, 3, 4,  5,  6,   7,   8,   9, ...

%e   A001006: 1, 1, 2, 4, 9, 21, 51, 127, 323, 835, ...

%e   A011782: 1, 1, 2, 4, 8, 16, 32,  64, 128, 256, ...

%e   a:       0, 0, 0, 0, 1,  5, 19,  63, 195, 579, ...

%e .

%e For n = 5 the 5 Motzkin words of length 4 that have at least one term > 1 are:

%e   1221, 1211, 1210, 1121, 0121.

%e For n = 6 the 19 Motzkin words of length 5 that have at least one term > 1 are:

%e   12321, 12221, 12211, 12210, 12121, 12111, 12110, 12101, 12100, 11221, 11211, 11210, 11121, 10121, 01221, 01211, 01210, 01121, 00121.

%p gf := (1 - x - (1-2*x-3*x^2)^(1/2)) / (2*x^2) - (1 - x) / (1 - 2*x):

%p ser := series(gf, x, 35): seq(coeff(ser, x, n), n = 0..30);

%p # Alternative:

%p a := n -> hypergeom([-n/2 + 1/2, -n/2], [2], 4) - 2^(n - 1 + 0^n);

%p seq(simplify(a(n)), n = 0..29);

%o (Python)

%o from itertools import islice

%o show = lambda f, n: print(list(islice(f(), n)))

%o def aGen():

%o     a, b, n, z = 1, 2, 2, 1

%o     yield 0

%o     while True:

%o         yield b//n - z

%o         n += 1; z *= 2

%o         a, b = b, (3*(n-1)*n*a + (2*n-1)*n*b)//((n+1)*(n-1))

%o show(aGen, 31)

%o (SageMath)

%o # Generates Motzkin words (for illustration only).

%o def motzkin_words(n):

%o      return IntegerListsLex(length=n+1, min_slope=-1, max_slope=1,

%o                 ceiling=[0]+[+oo for i in range(n-1)]+[0])

%o def MWList(n, show=True):

%o     c = 0

%o     for w in motzkin_words(n):

%o         if any(p > 1 for p in w):

%o             c += 1

%o             if show: print(''.join(map(str, w[1:-1])))

%o     return c

%o for n in range(8): print(f"[{n}] -> {MWList(n)}")

%Y Cf. A001006, A011782, A125107.

%K nonn,new

%O 0,6

%A _Peter Luschny_, Nov 28 2024