This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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, 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^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 J. M. Gomez Soto, J. Leanos, L. M. Ríos-Castro, and L. M. Rivera, On an error-correcting code problem Sofía Ibarra, Luis Manuel Rivera, The automorphism groups of some token graphs, arXiv:1907.06008 [math.CO], 2019. 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. (1-x+x^2-x^10+x^11)/((1-x)^2*(1-x^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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified October 22 14:44 EDT 2019. Contains 328318 sequences. (Running on oeis4.)