login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Table of n, a(n) for n=2..50.

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.

License Agreements, Terms of Use, Privacy Policy. .

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