[seqfan] Re: easy? graph question

Rob Pratt Rob.Pratt at sas.com
Wed Mar 15 22:45:34 CET 2017


The next several terms (n = 26 to 38) are:
67, 72, 77, 83, 89, 95, 101, 107, 114, 121, 128, 135, 142

The second differences appear to be eventually 5-periodic:
1, 0, 0, 0, 0, 1, 0, 0, 0, 0, ...

If so, the subsequent terms up through n = 50 would be:
150, 158, 166, 174, 182, 191, 200, 209, 218, 227, 237, 247

-----Original Message-----
From: SeqFan [mailto:seqfan-bounces at list.seqfan.eu] On Behalf Of Neil Sloane
Sent: Wednesday, March 15, 2017 2:25 PM
To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
Subject: [seqfan] easy? graph question

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/


More information about the SeqFan mailing list