|
%I #18 Sep 18 2022 07:59:18
%S 1,1,2,3,7,15,32,52,126,225,554,995,2446,5386,11808,19869,49025,
%T 109837,245854,425227,1064505,2413233,5466912,9592348,24178488,
%U 45073812,113262740,208166868,518091370,1155428876,2571714336,4419410606,11038230966,20406919817
%N "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.
%C The "word binomial coefficient" (x|y) is the number of ways that y can be a (scattered) subsequence of x.
%H Robert Israel, <a href="/A323598/b323598.txt">Table of n, a(n) for n = 0..200</a>
%e a(4) = 7 because there are 7 ways 0110 can be a subsequence of 01101001.
%p f:= proc(x,y)
%p option remember;
%p local n,m, Res, L,j,t;
%p n:= nops(x); m:= nops(y);
%p if n < m then return 0
%p elif n = m then if x = y then return 1 else return 0 fi
%p elif m = 0 then return 1 fi;
%p L:= select(j -> x[j] = y[1], [$1..n-m+1]);
%p add(procname(x[j+1..-1],y[2..-1]),j=L);
%p end proc:
%p TM:= StringTools[Explode](StringTools:-ThueMorse(200)):
%p seq(f(TM[1..2*n],TM[1..n]),n=0..100); # _Robert Israel_, Jan 20 2019
%t 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}]]];
%t TM = ThueMorse[Range[200]];
%t Join[{1}, Table[f[TM[[1;;2*n]], TM[[1;;n]]], {n, 0, 100}]] (* _Jean-François Alcover_, Sep 18 2022, after _Robert Israel_ *)
%Y Cf. A010060, A323597.
%K nonn
%O 0,3
%A _Jeffrey Shallit_, Jan 18 2019
|
