From: "Russell Easterly" Subject: Re: Paths of binary strings Date: Wed, 21 Feb 2001 02:43:04 GMT Newsgroups: sci.math.research Summary: Number of possible Gray codes of length n? "Ola Veshta" wrote in message news:ww031ve5p8hr@forum.mathforum.com... > Given n let a "path" be a sequence: > > a_1,a_2,...a_m (for some m >= n) such that each a_i is a binary string > of size n, > a_i and a_(i+1) are different in exactly one bit for 1 <= i <= m-1, > all the a_i are different (there are no loops in the path), > a_1 = 000...000 the string of n times 0, > a_m = 111...111 the string of n times 1 . > > For example when n=2 there are only 2 paths (both with m=3): > 00,01,11 and 00,10,11 . > > Starting with n=3 there are also paths that change from the bit 1 to > the 0 like : 000,100,110,010,011,111 (here m=6). > > Given n what is the number of different paths ? > > Thanks, > Ola > Your describing a Gray code and asking how many there are. I can give you a minimum number. Given a sequence of Gray codes you can always create another sequence of Gray codes by swapping columns. N=2 ab ba 00 00 01 10 11 11 10 01 N=3 abc acb bac bca cba cab 000 000 000 000 000 000 001 010 001 010 100 100 011 011 101 110 110 101 010 001 100 100 010 001 110 101 110 101 011 011 111 111 111 111 111 111 101 110 011 011 101 110 110 100 010 001 001 010 So there must be at least N! possible Gray counters with N bits. This may not be all of them. Russell - 2 many 2 count ============================================================================== From: David desJardins Subject: Re: Paths of binary strings Date: 20 Feb 2001 19:01:49 -0800 Newsgroups: sci.math.research Ola Veshta writes: > a_1,a_2,...a_m (for some m >= n) such that each a_i is a binary string > of size n, > a_i and a_(i+1) are different in exactly one bit for 1 <= i <= m-1, > all the a_i are different (there are no loops in the path), > a_1 = 000...000 the string of n times 0, > a_m = 111...111 the string of n times 1 . > Given n what is the number of different paths ? I doubt a closed form is known. I computed the first few terms: 1,2,18,6432,18651552840. Of course, n! divides the nth term. Other than that, there is no obvious structure. This sequence isn't in Sloane's on-line encyclopedia of integer sequences (but I can submit it). David desJardins