# [seqfan] Re: recurrences for pattern avoiding binary strings A164387 to A164494

Robert Israel israel at math.ubc.ca
Fri Jun 4 22:20:18 CEST 2010

```Verifying these recurrences in a unified way is quite
straightforward. For two 3-digit binary strings s = (s1,s2,s3) and
t = (t1,t2,t3), let c(s,t) = 1 if (s2,s3) = (t1,t2) and (s1,s2,s3,t3)
is an allowed string, 0 otherwise.  Let x_s(n) be the number of
allowed n-digit strings starting with s.  Then
x_s(n+1) = sum_t c(s,t) x_t(n).  Write this system as X(n+1) = C X(n)
where X(n) is an 8-component column vector and C is an 8 x 8 matrix.
The minimal polynomial of C, C^m + sum_{j=0}^{m-1} p_j C^j = 0,
corresponds to a recurrence relation
X(n+m) + sum_{j=0}^{m-1} p_j X(n+j) = 0 with m <= 8,
a(n) = sum_s x_s(n) also satisfies this same recurrence.
Now we don't really need to calculate the p_j, because any
linear combination F(i) = sum_{j=0}^r b_j a_{i+j} = 0
also satisfies the same recurrence.  So if
F(0) = F(1) = ... = F(7) = 0, we will have F(n) = 0 for all
integers n > 7.

Robert Israel                                israel at math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel
University of British Columbia            Vancouver, BC, Canada

On Fri, 4 Jun 2010, Richard Mathar wrote:

>
> All sequences below, counting binary numbers w/o specified fixed substrings,
> seem to have linear recurrences - well known I presume but I have no proof
> (so I'll not try to include them in the index of the linear recurrences):
>
> A164387 a(n)= +a(n-1) +a(n-2) +a(n-4) -a(n-5)
> A164388 a(n)= +a(n-1) +a(n-2) +a(n-3) -a(n-5)
> A164389 a(n)= +a(n-1) +2*a(n-3) +a(n-4)
> A164390 a(n)= +a(n-1) +a(n-2) +a(n-4) +a(n-6)
> A164391 a(n)= +a(n-1) +a(n-2) +a(n-3) -a(n-5) -a(n-6)
> A164392 a(n)= +2*a(n-1) -a(n-3) +a(n-4) -a(n-5)
> A164393 a(n)= +2*a(n-1) -2*a(n-4) +a(n-5)
> A164394 a(n)= +2*a(n-1) -a(n-2) +a(n-3)
> A164395 a(n)= +2*a(n-1) -a(n-2) +2*a(n-3) -2*a(n-4)
> A164396 a(n)= +2*a(n-1) -a(n-3) +a(n-5) -a(n-6)
> A164397 a(n)= +2*a(n-1) -2*a(n-4) +a(n-6)
> A164398 a(n)= +2*a(n-1) -a(n-4)
> A164399 a(n)= +2*a(n-1) -a(n-2) +2*a(n-3) -2*a(n-4)
> A164400 a(n)= +2*a(n-1) -2*a(n-4) +a(n-5)
> A164401 a(n)= +2*a(n-1) -a(n-2) +a(n-3) +a(n-6)
> A164402 a(n)= +2*a(n-1) -2*a(n-3) +2*a(n-4)
> A164403 a(n)= +2*a(n-1) -a(n-3) +a(n-5)
> A164404 a(n)= +2*a(n-1) -2*a(n-3) +2*a(n-4)
> A164405 a(n)= +2*a(n-1) -a(n-3) +a(n-6)
> A164406 a(n)= +2*a(n-1) -a(n-2) +2*a(n-3) -2*a(n-4) -a(n-6)
> A164407 a(n)= +a(n-1) +a(n-2) +a(n-4)
> A164408 a(n)= +a(n-1) +a(n-2) +a(n-3) -a(n-4)
> A164409 a(n)= +2*a(n-1) -a(n-2) +a(n-3)
> A164410 a(n)= +a(n-1) +2*a(n-3)
> A164411 a(n)= +a(n-1) +a(n-2) +a(n-5)
> A164412 a(n)= +a(n-1) +a(n-2) +a(n-3) -a(n-4) -a(n-5)
> A164413 a(n)= +a(n-1) +a(n-2)
> A164414 a(n)= +a(n-1) +2*a(n-3)
> A164415 a(n)= +a(n-1) +a(n-2) +a(n-3) -a(n-4)
> A164416 a(n)= +a(n-2) +2*a(n-3) +2*a(n-4) +a(n-5)
> A164417 a(n)= +a(n-1) +a(n-2) +a(n-4) +a(n-5) -a(n-6) -a(n-7)
> A164418 a(n)= +a(n-1) +a(n-3) +a(n-4) +a(n-5) +a(n-6) +a(n-7)
> A164419 a(n)= +a(n-1) +a(n-2) -a(n-3) +a(n-4) +a(n-5) +a(n-6)
> A164420 a(n)= +a(n-1) +a(n-2) -a(n-6)
> A164421 a(n)= +a(n-1) +a(n-2) +a(n-5)
> A164422 a(n)= +a(n-1) +a(n-3) +a(n-4) +a(n-5)
> A164423 a(n)= +a(n-1) +a(n-2) +a(n-6) +a(n-7)
> A164424 a(n)= +2*a(n-1) -a(n-2) +a(n-4) -a(n-6)
> A164425 a(n)= +a(n-1) +a(n-3) +a(n-4) +a(n-5)
> A164426 a(n)= +a(n-1) +2*a(n-3) -a(n-5) -a(n-6) -a(n-7)
> A164427 a(n)= +a(n-1) +a(n-2) +a(n-4) -a(n-5)
> <skip leap jump frog A-number range>
> A164460 a(n)= +2*a(n-1) -a(n-3) -a(n-4) +a(n-5) +a(n-6) -a(n-7)
> A164461 a(n)= +a(n-1) +a(n-2) +a(n-3) -2*a(n-4)
> A164462 a(n)= +2*a(n-1) -a(n-2) +a(n-3) -a(n-5)
> <skip A-number range>
> A164480 a(n)= +2*a(n-1) -a(n-3)
> A164481 a(n)= +2*a(n-1) -a(n-3) -a(n-4) +2*a(n-5) -a(n-6)
> A164482 a(n)= +a(n-1) +a(n-2) -a(n-4)
> A164483 a(n)= +2*a(n-1) -a(n-2) +2*a(n-3) -3*a(n-4) +a(n-6)
> A164484 a(n)= +2*a(n-1) -3*a(n-4) +2*a(n-5)
> <skip A-number range>
> A164490 a(n)= +2*a(n-1) -2*a(n-3) +2*a(n-4) -a(n-5)
> A164491 a(n)= +a(n-1) +a(n-2) +a(n-5) +a(n-6)
> A164492 a(n)= +2*a(n-1) -a(n-2) +a(n-4) +a(n-7)
> A164493 a(n)= +2*a(n-1) -a(n-2) +a(n-3) -a(n-4) +a(n-5) +a(n-7)
> A164494 a(n)= +2*a(n-1) -a(n-2) +a(n-3)
>
> I presume the irregularities in the recurrences indicate how
> far the substrings that are avoided have common overlapping substrings.
>
> RJM
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

```