|
%I #21 Mar 20 2020 10:04:24
%S 1,1,2,1,2,4,1,2,4,7,1,2,4,6,12,1,2,4,6,12,21,1,2,4,6,10,20,37,1,2,4,
%T 6,10,17,38,65,1,2,4,6,10,16,28,66,114,1,2,4,6,10,16,26,49,124,200,1,
%U 2,4,6,10,16,26,42,84,224,351,1,2,4,6,10,16,26,42,70,148,424,616
%N Number A(n,k) of binary words of length n with k times as many occurrences of subword 101 as occurrences of subword 010; square array A(n,k), n>=0, k>=0, read by antidiagonals.
%C A(n,n) is the number of binary words of length n avoiding both subwords 101 and 010. A(4,4) = 10: 0000, 0001, 0011, 0110, 0111, 1000, 1001, 1100, 1110, 1111.
%H Alois P. Heinz, <a href="/A303696/b303696.txt">Antidiagonals for n = 0..200, flattened</a>
%F ceiling(A(n,n)/2) = A000045(n+1).
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, ...
%e 2, 2, 2, 2, 2, 2, 2, ...
%e 4, 4, 4, 4, 4, 4, 4, ...
%e 7, 6, 6, 6, 6, 6, 6, ...
%e 12, 12, 10, 10, 10, 10, 10, ...
%e 21, 20, 17, 16, 16, 16, 16, ...
%e 37, 38, 28, 26, 26, 26, 26, ...
%e 65, 66, 49, 42, 42, 42, 42, ...
%e 114, 124, 84, 70, 68, 68, 68, ...
%e 200, 224, 148, 116, 110, 110, 110, ...
%e 351, 424, 263, 196, 178, 178, 178, ...
%p b:= proc(n, t, h, c, k) option remember; `if`(abs(c)>k*n, 0,
%p `if`(n=0, 1, b(n-1, [1, 3, 1][t], 2, c-`if`(h=3, k, 0), k)
%p + b(n-1, 2, [1, 3, 1][h], c+`if`(t=3, 1, 0), k)))
%p end:
%p A:= (n, k)-> b(n, 1$2, 0, min(k, n)):
%p seq(seq(A(n, d-n), n=0..d), d=0..14);
%t b[n_, t_, h_, c_, k_] := b[n, t, h, c, k] = If[Abs[c] > k n, 0, If[n == 0, 1, b[n - 1, {1, 3, 1}[[t]], 2, c - If[h == 3, k, 0], k] + b[n - 1, 2, {1, 3, 1}[[h]], c + If[t == 3, 1, 0], k]]];
%t A[n_, k_] := b[n, 1, 1, 0, Min[k, n]];
%t Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* _Jean-François Alcover_, Mar 20 2020, from Maple *)
%Y Columns k=0-3 give: A005251(n+3), A164146, A303430, A307795.
%Y Main diagonal gives A128588(n+1).
%Y Cf. A000045, A307796.
%K nonn,tabl
%O 0,3
%A _Alois P. Heinz_, Apr 28 2018
|
