Conference rusure::math

    OK, whats wron this looks too easy.
    
               ((2**n) - 2*(n-2))
    
    -Joe

    That's the number of {0, 1}^n strings which do not *start* with 000 or
    111.

				    Topher

f(1) = 2, f(2) = 4, and for n > 2:

		f(n) = f(n-1) + f(n-2)

I.e. its twice Fibonnacci(n+1).

My method doesn't generalize, though: consider the f(n) strings of length n.
You can append a 0 or 1 to the fdiff(n) of them whose last two bits are
different, but can only append the inverse of the last bit to the fsame(n) of
them whose last two bits are the same. Considering the last two bits of the 
resultant strings, you get:

	fdiff(n+1) = fdiff(n) + fsame(n) = f(n)
	fsame(n+1) = fdiff(n)

Adding, f(n+1) = f(n) + fdiff(n) = f(n) + f(n-1).

This kind of thing just happens to relate to Coding Theory, which is used in
communications and storage; for instance, the RLL(1,7) code used in many
modern disk drives encodes sectors into a subset of the set of strings which
do not contain the substrings '11' or '0000000'. The lim(n->inf) log2(f(n))/n
is the upper bound of the "rate" of such a code.

The actual rate of the RLL(1,7) we use is 2/3 - how close is that to its
upper bound?

    i wrote a program to find all patterns that do not have a pattern of 
    length at least K inside a string of length n.

i.e. it find strings that do not have say "111" in string of length n.
    
to find strings that do not have have say "111" OR "000" , i need to 
multiply by 2 the results from "111" and REMOVE the common patterns.
    
    iam still stuck on this OR part. but it is at least leass than 2*find(k,n)
    where find() is the program output (next page) ..ok that is close
    enough for tonite, tommorrow nite iam sure i'll get the next part :-)
    
no imperical formula, but this is some results for different length of substr:

for substr of length 4
n        number of patterns that dont include "1111" ONLY 
4         15
5         29
6         56
7         108
8         208
9         401
10        773
11        1490
12        2872

for substr of length 3:
 n   number of patterns that dont contain this "111" ONLY
 3                  7
 4                 13
 5                 24
 6                 44
 7                 81
 8                149
 9                274
 10               504
 11               927
 12               1705
    
    

    /* program to return how many pattern do not have a pattern of at
       least length k in a string of length n */
    
#include math.h
#include stdio.h

main()
{

int i,k,j,n;

  printf("Enter length of subsrt >");
  scanf("%d",&k);
  printf("Enter length of total string i.e n >");
  scanf("%d",&n);

  if(k<0 || n<0)
    {
    printf("huh? length cant be <0 ");
    exit(1);
    }

  if(k==0)
   {
    i=0;
    goto common_exit;
   }

  if(n==0)
    {
     printf("those that dont contain the substr pattern = %d",0);
     exit(1);
    }

  i= find(k,n);


common_exit:
  printf("those that dont contain the substr pattern = %d",
         (int) pow ( (double)2,(double)(n)) - i );

}

find(int k, int n)
/* finds how many patterns that include at least  K bits either on or off 
   inside a bit string of length n
*/
{


 int i,t,h,j,d;
 t=0;

 if(n<k)
   {
   printf("error, n must be larger than subsrt length\n");
   exit(1);
   }

 if(n==k)
   return 1;

 for(i=0;i<(n-k)+1;i++)
    {
    if( (n-k) == i)
       d=0;
    else
       d= (int) pow ( (double)2,(double)(n-k-i));

    t= t + d;
    j= i- 1;
    if(j>= 1)
      {
       if(j>= k)
         {
          int v;
          h= find(k,j);
          v= (int) pow ( (double)2,(double)(j))  -h;
          v= (d==0?1:d)*v;
          t= (t-d) + v;
         }
       else
        t= (t-d) + (d==0?1:d)* ((int) pow( (double)2,(double)(j))) ;
      }
    if( (i== (n-k)) && i==1)
      t++;
   }
return t;
}   

    

    Another place this problem arises is in generating the channel code
    for the audio compact disc.  The so-called "eight-fourteen" code
    maps each byte to 14 bits, so that long runs of zeroes and ones will not
    occur both within and between 14 bit words.

    One reason for this was to minimize low frequency energy in the
    channel code as the optical read heads are servoed off this signal.
    With less low frequency noise the servoes can be sped up without
    being jittered by the data itself.

    - Jim

.3> strings which do not contain the substrings '11' or '0000000'.

Let fab(n) be the number of such strings of length n ending with 'ab'.  Then
	f00(n) = f00(n-1) + f10(n-1) - f10(n-6)
	f01(n) = f00(n-1) + f10(n-1)
	f10(n) = f01(n-1) + f11(n-1)
	f11(n) = 0
	f = f00 + f01 + f10 + f11
And let
	f0 = f00 + f10
	f1 = f01 + f11

With a little simple math:
	f0(n) = f0(n-1) + f1(n-1) - f10(n-6)
	f1(n) = f0(n-1)
Now,	f10(k) = f01(k-1) = f0(k-2), so

	f0(n) = f0(n-1) + f0(n-2) - f0(n-8), and
	f(n) = f0(n-1) + f0(n-1) + f0(n-2) - f0(n-8)

The rate of f is the same as the rate of f0, which is the largest root of:

	x^(n) = x^(n-1) + x^(n-2) - x^(n-8).

(largest root = root with the largest *magnitude*).


The roots are:

	 .45587317996136381 � .77845802203893291 i	(mag=.90211820083892207)
	-.33677096199640055 � .83530814163878028 i	(mag=.90064108963116583)
	-.91410490491552158 � .34226418918007819 i	(mag=.97608019772235474)
	1.5900053739011166 = R0

And so	f(n) ~ K * R0**n, for some constant K.
Finally,
	lim(n->inf) log2(f(n))/n = ( n*log2(R0)+log2(K) )/n
		= log2(R0) = .66903164153943545

This is about half a percent more than 2/3.

    generalization 1:
    
    enumerate the binary sequences of length K in which there are no "runs"
    which exceed length m, where m <= K
    
    
    generalization 2:
    
    Suppose we have beads which are one of r colors. Given K and m where
    0 < m <= L how many sequences of beads are there in which there are no
    "runs" of beads of a given color which exceed m in lenght.  The binary
    question posted in the base note is the 2 color version of this
    generalized question.
    
    

    consider generalization 1.
    
    Let R(m,K), m, K positive integers  be the set of all partitions of K
    into sums of the for SUM(i= 1,r)J-sub-r where r >= ROOF(K/r) and 
    J-sub_r is a positive integer. The total number of sequences from {0,1} of
    length K which has no  run exceeding m in length, is 2*R(m,K);
    
    R(m,K) = SUM (j = 1,m)R(m,K-j)  and we note that
    
    R(m,n) where n <= m is PART(n) where PART(n) is the number of
    partitions of n into non zero summands.  Applying a Fibonocci like
    recursion should produce the desired result.