

A085680


Size of largest code of length n and constant weight 2 that can correct a single adjacent transposition.


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, 67, 72, 77, 83, 89, 95, 101, 107, 114, 121, 128, 135, 142, 150, 158, 166, 174, 182, 191, 200, 209, 218, 227, 237, 247
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,3


COMMENTS

Form a graph whose nchoose2 vertices correspond to the binary vectors of length n with exactly two 1's and n2 0's in each vector.
Join two vertices u and v by an edge if v can be obtained from u by transposing a pair of adjacent coordinates.
a(n) is the maximal size of a subset S of the vertices such that the distance between every pair of vertices in S is at least 3.
For n=4 the graph is
...........1001
........../....\
11001010......01010011
..........\..../
...........0110
so a(4) = 2 (use 1100 and 0011 as the set S, or 1100 and 0101).  N. J. A. Sloane, Mar 15 2017
From Luis Manuel Rivera, Mar 15 2017: (Start)
This sequence also arises in the problem of determining the 2packing number of certain graphs (the 2token graph of a path with n vertices).
Let G be a graph of order n and let k be an integer such that 1 <= k <= n1. The ktoken graph F_k(G) of G is defined to be the graph with vertex set all ksubsets of V(G), where two vertices are adjacent in F_k(G) whenever their symmetric difference is an edge of G.
A 2packing of a graph G is a subset S of V(G) such that d(u, v) >= 3, for every pair of distinct vertices u, v in S. The 2packing number of G is the maximum cardinality of a 2packing of G.
For n != 2, A085680(n) is also the 2packing number of F_2(P_n), where P_n is the path graph with vertex set {1, ..., n} and edge set {{i, i+1} : 1 <= i <= n1}. The bijection f between the two graphs is given as follows: for A in V(F_2(P_n)), f(A)=a_1 ... a_n, where a_i=1 iff i in A.
This comment is based on joint work with my colleagues José Manuel Gómez Soto, Jesus Leaños, and Luis Manuel Ríos Castro. (End)
From Luis Manuel Rivera, Mar 23 2017: (Start)
My colleagues and I have obtained the following lower bounds for a(n)=A085680(n), n >= 10:
a(n) >= (n^2n+20)/10, for n == 0 or 1 mod 5,
a(n) >= (n^2n+18)/10, for n == 2 or 4 mod 5.
a(n) >= (n^2n+14)/10, for n == 3 mod 5.
In all cases, this lower bound coincides with the 50 values that are presently known. We conjecture that these formulas are in fact the exact values for a(n). (End)


LINKS

Table of n, a(n) for n=2..50.
J. M. Gomez Soto, J. Leanos, L. M. RíosCastro, and L. M. Rivera, On an errorcorrecting code problem
Luis Manuel Rivera, Some properties of token graphs, 2018.
N. J. A. Sloane, Challenge Problems: Independent Sets in Graphs


FORMULA

It appears that the second differences eventually have period 5: 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, ... However, this is only a conjecture. If true, it would imply the g.f. (1x+x^2x^10+x^11)/((1x)^2*(1x^5)).  Rob Pratt, Mar 15 2017


CROSSREFS

Column 2 of A085684.
Sequence in context: A062413 A064313 A011865 * A253186 A321195 A249020
Adjacent sequences: A085677 A085678 A085679 * A085681 A085682 A085683


KEYWORD

nonn,more


AUTHOR

N. J. A. Sloane, Jul 16 2003


EXTENSIONS

a(26)a(38) from Rob Pratt, Mar 15 2017
a(39)a(50) from Rob Pratt, Mar 19 2017


STATUS

approved



