|
| |
|
|
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 n-choose-2 vertices correspond to the binary vectors of length n with exactly two 1's and n-2 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
........../....\
1100--1010......0101--0011
..........\..../
...........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 2-packing number of certain graphs (the 2-token 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 <= n-1. The k-token graph F_k(G) of G is defined to be the graph with vertex set all k-subsets of V(G), where two vertices are adjacent in F_k(G) whenever their symmetric difference is an edge of G.
A 2-packing 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 2-packing number of G is the maximum cardinality of a 2-packing of G.
For n != 2, A085680(n) is also the 2-packing 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 <= n-1}. 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, Jesús 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^2-n+20)/10, for n == 0 or 1 mod 5,
a(n) >= (n^2-n+18)/10, for n == 2 or 4 mod 5.
a(n) >= (n^2-n+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
|
|
|
|
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. (1-x+x^2-x^10+x^11)/((1-x)^2*(1-x^5)). - Rob Pratt, Mar 15 2017
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
