A323598 "Word binomial coefficient" for (x|y) where y is the first n symbols of the Thue-Morse sequence (A010060) and x is the first 2n symbols.

1, 1, 2, 3, 7, 15, 32, 52, 126, 225, 554, 995, 2446, 5386, 11808, 19869, 49025, 109837, 245854, 425227, 1064505, 2413233, 5466912, 9592348, 24178488, 45073812, 113262740, 208166868, 518091370, 1155428876, 2571714336, 4419410606, 11038230966, 20406919817

Offset

0,3

Comments

The "word binomial coefficient" (x|y) is the number of ways that y can be a (scattered) subsequence of x.

Links

Robert Israel, Table of n, a(n) for n = 0..200

Example

a(4) = 7 because there are 7 ways 0110 can be a subsequence of 01101001.

Maple

f:= proc(x, y)
     option remember;
     local n, m, Res, L, j, t;
     n:= nops(x); m:= nops(y);
     if n < m then return 0
     elif n = m then if x = y then return 1 else return 0 fi
     elif m = 0 then return 1 fi;
     L:= select(j -> x[j] = y[1], [$1..n-m+1]);
     add(procname(x[j+1..-1], y[2..-1]), j=L);
end proc:
TM:= StringTools[Explode](StringTools:-ThueMorse(200)):
seq(f(TM[1..2*n], TM[1..n]), n=0..100); # Robert Israel, Jan 20 2019

Mathematica

f[x_, y_] := f[x, y] = Module[{n, m, L}, n = Length[x]; m = Length[y]; Which[n < m, Return[0], n == m, If[x == y, Return[1], Return [0]], m == 0, Return[1], True, L = Select[Range[n-m+1], x[[#]] == y[[1]]&]; Sum[f[x[[j+1;; -1]], y[[2;; -1]]], {j, L}]]];
TM = ThueMorse[Range[200]];
Join[{1}, Table[f[TM[[1;; 2*n]], TM[[1;; n]]], {n, 0, 100}]] (* Jean-François Alcover, Sep 18 2022, after Robert Israel *)

Crossrefs

Cf. A010060, A323597.

Sequence in context: A153010 A076993 A076698 * A078007 A368410 A358734

Adjacent sequences: A323595 A323596 A323597 * A323599 A323600 A323601

Keyword

nonn

Author

Jeffrey Shallit, Jan 18 2019

Status

approved