[seqfan] Re: easy? graph question
Neil Sloane
njasloane at gmail.com
Thu Mar 16 00:27:55 CET 2017
Rob's exact values correspond to the g.f. (1-x+x^2-x^10+x^11)/((1-x)^2*(1-x^5))
(which is somewhat simpler than what Bob Wilson found, but is
presumably equivalent to it)
It might be interesting to stare at the actual optimal sets of vectors
(the "codes")
at the particular lengths where the differences jump by 1.
There is more there chance that these are unique, and maybe
there will be an obvious pattern.
These would be the codes of lengths
9, 14, 19, 24, 29, ..., of sizes
9, 20, 36, 57, 83, ...
Best regards
Neil
Neil J. A. Sloane, President, OEIS Foundation.
11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
Phone: 732 828 6098; home page: http://NeilSloane.com
Email: njasloane at gmail.com
On Wed, Mar 15, 2017 at 7:03 PM, Neil Sloane <njasloane at gmail.com> wrote:
> I've updated A085680 (including a hopefully clearer definition).
>
> Note that the distance being used is not Hamming distance, of course.
> Best regards
> Neil
>
> Neil J. A. Sloane, President, OEIS Foundation.
> 11 South Adelaide Avenue, Highland Park, NJ 08904, USA.
> Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ.
> Phone: 732 828 6098; home page: http://NeilSloane.com
> Email: njasloane at gmail.com
>
>
>
> On Wed, Mar 15, 2017 at 5:46 PM, Benoît Jubin <benoit.jubin at gmail.com> wrote:
>> Dear Neil,
>>
>> I had a little trouble understanding your definition, in particular
>> the phrase "maximal number of nodes that are separated by at least
>> three edges".
>>
>> As a mathematician not familiar with codes, I would propose : "a(n) is
>> the maximal cardinality of a set of such n-tuples whose members are at
>> distance at least three from each other" (or something similar, in
>> better English!).
>>
>> Best regards,
>> Benoît
>>
>>
>>
>>
>>
>>
>>
>>
>> On Wed, Mar 15, 2017 at 7:25 PM, Neil Sloane <njasloane at gmail.com> wrote:
>>> Dear Seq Fans, Someone just asked me to explain A085680, which is:
>>>
>>>
>>> Size of largest code of length n and constant weight 2 that can
>>> correct a single adjacent transposition. The data line gives only
>>> these values, with offset 2:
>>>
>>> 1, 1, 2, 3, 4, 6, 7, 9, 11, 13, 15, 17, 20, 23, 26, 29, 32, 36, 40,
>>> 44, 48, 52, 57, 62
>>>
>>> I just added an explanation, as follows:
>>>
>>> Look at the set of n-choose-2 binary vectors of length n with exactly
>>> two 1's and n-2 0's in each vector.
>>>
>>> If we can get a vector v from a vector u by swapping 2 adjacent
>>> coordinates, say that u and v are adjacent.
>>>
>>> a(n) is the maximal number of nodes in the resulting graph that are
>>> separated by at least three edges.
>>>
>>> For n=4 the graph is
>>>
>>> .................1001
>>>
>>> ................../....\
>>>
>>> 1100--1010......0101--0011
>>>
>>> ..................\..../
>>>
>>> ..................0110
>>>
>>> so a(4) = 2 (use 1100 and 0011 as the code, or 1100 and 0101).
>>>
>>> More terms, anyone?
>>>
>>> --
>>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
More information about the SeqFan
mailing list