1 Introduction

Levenshtein [7] first proposed the sequence reconstruction problem in 2001. In this scene, a sequence is transmitted through multiple channels and a decoder receives all the distinct outputs. Levenshtein [7, 8] determined the minimum number of transmission channels required to exactly recover the transmitted sequence. We denote by V and \(\rho : V\times V\rightarrow \mathbb {N}\) a set of all sequences and a distance metric in V, respectively. In this model, Levenshtein [7] proved that the minimum number of transmission channels has to be greater than the largest intersection of two balls where their centers belong to V,

$$N(n,d,r)=\max\limits_{x_{1},x_{2}\in V, \rho(x_{1},x_{2})\geq d}\{|B_{r}(x_{1})\cap B_{r}(x_{2})|\},$$
(1)

where Br(x) = {y ∈ V |ρ(x,y) ≤ r} is a ball of radius r centered in x and n is the length of sequences in V. We refer to this problem of determining the value of N(n,d,r) as the sequence reconstruction problem.

Levenshtein [7] studied the sequence reconstruction problem for several channels with some distances such as the Hamming distance, the Johnson graphs and the other metric distances. Later, this problem was discussed in the context of permutations [4,5,6, 12] and some other general error graphs [9, 10]. The deletion/insertion case was also explored in [11] for insertions and in [1, 2, 13] for deletions.

The sequence reconstruction problem over permutations has received a considerable attention in the literature. In particular, Konstantinova in [4, 5] solved this problem over permutations with reversal errors. The reconstruction problem for permutations with transposition errors was discussed in [6, 10]. The reconstruction problem over permutations under the Kendall τ-distance was studied for some special cases of d and r in [6, 12]. Specifically, Konstantinova et al. in [6] proved that N(n,1,1) = 2 and N(n,1,2) = 2(n − 1). Yaakobi et al. in [12] solved that \(N(n,2r,r)=\binom {2r}{r}\) for r ≤ n/4 and presented some properties of N(n,d,r).

In this paper, we discuss the reconstruction problem for permutations on n elements from their erroneous patterns which are distorted by at most three Kendall τ-errors. First, we present some upper bounds on the values of \(\max \limits _{x_{1},x_{2}\in V, \rho (x_{1},x_{2})= d}\{|B_{r}(x_{1})\cap B_{r}(x_{2})|\}\) for d = 2,3,4,5,6 and r = 3. Next, we determine that N(n,1,3) = N(n,2,3) = n2 − n for any n ≥ 3.

The rest of this paper is organized as follows. In Section 2, we formally give the definitions of the sequence reconstruction problem and permutations under the Kendall τ-metric. In Section 3, we find the exact values of N(n,d,3) when d = 1 and 2. Section 4 concludes this paper.

2 Preliminaries

In this section, we present some definitions and notations of the sequence reconstruction problem and permutations with the Kendall τ-errors mentioned in [12] and [16].

We denote by \(\mathcal {S}_{n}\) the set of all permutations over [n] = {1,2,...,n − 1,n}. Let \(\pi \in \mathcal {S}_{n}\) be a permutation and π := [π(1),π(2),...,π(n)]. For two permutations \(\sigma ,\pi \in \mathcal {S}_{n}\), their multiplication π ∘ σ is defined as the composition of σ on π, that is, π ∘ σ(i) = σ(π(i)) for all i ∈ [n]. Thus, \(\mathcal {S}_{n}\) under this definition of multiplication is a noncommutative group of size \(|\mathcal {S}_{n}|=n!\). Assume \(B\subset \mathcal {S}_{n}\) and \(\alpha \in \mathcal {S}_{n}\), let α ∘ B = {α ∘β|β∈ B} and B ∘ α = {β∘α|β∈ B}. We denote by 𝜖n := [1,2,...,n] and π− 1 the identity element of \(\mathcal {S}_{n}\) and the inverse element of π, respectively. For an unordered pair of distinct numbers i,j ∈ [n], this pair (i,j) is called an inversion in a permutation π if i < j and simultaneously π− 1(i) > π− 1(j). For convenience, we denote by Iv(π) the set of all inversions in π. For example, let π = [3,1,2], then Iv(π) = {(1,3),(2,3)}.

For any permutation \(\pi =[\pi (1),\pi (2),...,\pi (i),\pi (i+1),...\pi (n)]\in \mathcal {S}_{n}\), an adjacent transposition is an exchange of two adjacent elements π(i),π(i + 1), resulting in the permutation [π(1),π(2),...,π(i + 1),π(i),...π(n)] for some 1 ≤ i ≤ n − 1. For any two permutations \(\sigma ,\pi \in \mathcal {S}_{n}\), the Kendall τ-distance between two permutations π,σ, defined as dK(π,σ), is the minimum number of adjacent transpositions required to obtain the permutation σ from π. The expression for dK(π,σ) [3] is as follows:

$$d_{K}(\sigma,\pi)=|\{(i,j):\sigma^{-1}(i)<\sigma^{-1}(j)\wedge\pi^{-1}(i)>\pi^{-1}(j)\}|.$$
(2)

The Kendall τ-weight of \(\pi \in \mathcal {S}_{n}\), denoted by wK(π), is defined as the Kendall τ-distance between π and the identity permutation 𝜖n. For example, the Kendall τ-distance between 𝜖3 and π = [3,1,2] is 2, since we can do the adjacent transpositions \([1,2,3]\rightarrow [1,3,2]\rightarrow [3,1,2].\) The Kendall τ-metric is right invariant [15], that is, for every three permutations \(\alpha ,\upbeta ,\sigma \in \mathcal {S}_{n}\), we have

$$d_{K}(\alpha\circ\sigma,\upbeta\circ\sigma)=d_{K}(\alpha,\upbeta).$$
(3)

Given any permutation \(\pi \in \mathcal {S}_{n}\), we denote by \({B_{K}^{n}}(\pi ,r):=\{\sigma \in \mathcal {S}_{n}|d_{K}(\sigma ,\pi ) \leq r\}\) and \({S_{K}^{n}}(\pi ,r):=\{\sigma \in \mathcal {S}_{n}|d_{K}(\sigma ,\pi )= r\}\) the Kendall τ-ball and the Kendall τ-sphere of radius r centered at π, respectively. The size of the Kendall τ-ball or the τ-sphere of radius r does not depend on the center of the ball or sphere under the Kendall τ-metric. Thus, we denote by \({B_{K}^{n}}(r)\) and \({S_{K}^{n}}(r)\) the size of \({B_{K}^{n}}(\pi ,r)\) and \({S_{K}^{n}}(\pi ,r)\), respectively.

For two integers d and r, let I(n,d,r) be the size of the largest intersection of two balls of radius r and distance d between their centers. That is,

$$I(n,d,r)=\max\limits_{\pi,\sigma\in \mathcal{S}_{n},d_{K}(\pi,\sigma)=d}|{B_{K}^{n}}(\sigma,r)\cap {B_{K}^{n}}(\pi,r)|.$$
(4)

Similarly, let N(n,d,r) be the size of the maximum intersection two balls of radius r and distance at least d between their centers. That is,

$$N(n,d,r)=\max\limits_{l\geq d}I(n,l,r).$$
(5)

Assume that a permutation π ∈ C is transmitted over N channels, where \(C\subset \mathcal {S}_{n}\) and dK(π,β) ≥ d for any two distinct π,β∈ C, there are at most r errors on each channel, and all the channel outputs are different from each other. Then, Levenshtein [7] proved that the minimum number of channels that guarantees the existence of a decoder that will successfully decode any transmitted codeword is given by N(n,d,r) + 1, where the distance between any two distinct codewords is at least d. It was shown in [6] that N(n,1,1) = 2 and N(n,1,2) = 2(n − 1).

Based on the above definitions and notations, we will determine the exact values of N(n,d,3) for d = 1,2 in the following section.

3 The exact values of N(n,d,3) for d = 1,2

In this section, we will give some upper bounds on the values of I(n,d,3) for d ∈ [6] and determine the exact values of N(n,d,3) for d = 1,2. In order to obtain these results, we need some lemmas as follows. The values of I(n,1,r) have been determined by Yaakobi et al. in [12] in the following lemma.

Lemma 1

[12, Theorem 5] For r ≥ 2, the values of I(n,1,r) satisfy the following recursive formula

$$I(n,1,r)=2{B_{K}^{n}}(r-1)-I(n,1,r-1),$$
(6)

where I(n,1,1) = 2.

Yaakobi et al. in [12] also proposed some properties of I(n,2,r). Given two permutations \(\alpha ,\upbeta \in \mathcal {S}_{n}\) such that dK(α,β) = 2, there are two options:

  1. 1)

    There is only a single permutation σ such that dK(α,σ) = dK(β,σ) = 1.

  2. 2)

    There are two distinct permutations σ,π such that dK(α,σ) = dK(β,σ) = dK(α,π) = dK(β,π) = 1.

If the first option holds then we say that α and β are of type I, and otherwise, we say they are of type II. When α and β are of type II, Yaakobi et al. in [12] gave the following result.

Lemma 2

[12, Lemma 8] Assume that α,β satisfy dK(α,β) = 2 and they are of type II. Then, \(|{B_{K}^{n}}(\alpha ,r)\cap {B_{K}^{n}}(\upbeta ,r)|=I(n,1,r)\).

By Lemma 2 and (5), we clearly obtain the following lemma.

Lemma 3

For any r ≥ 1, we have N(n,1,r) = N(n,2,r).

Proof

By Lemma 2, we have N(n,2,r) ≥ I(n,1,r) for any r ≥ 1. Hence, we can obtain that N(n,1,r) = N(n,2,r) for any r ≥ 1. □

Since N(n,1,1) = 2 and N(n,1,2) = 2(n − 1) in [6], then we have that N(n,2,1) = 2 and N(n,2,2) = 2(n − 1). In the following, we will determine the exact values of N(n,d,3) for d = 1,2.

Wang et al. in [14] gave the recursive formula of \({B_{K}^{n}}(r)\) and the exact values of \({B_{K}^{n}}(r)\) for r = 2,3 as follows. Here, we have \({B_{K}^{n}}(0)=1\) and \({B_{K}^{n}}(1)=n\).

Lemma 4

[14, Theorem 1] For all n ≥ 3, we have \({B_{K}^{n}}(2)=\frac {n^{2}+n-2}{2}\) and \({B_{K}^{n}}(3)=\frac {(n+1)(n^{2}+2n-6)}{6}\).

By Lemmas 1 and 4, we obtain

$$\begin{array}{@{}rcl@{}} I(n,1,1)&=&2,\\ I(n,1,2)&=&2{B_{K}^{n}}(1)-I(n,1,1)=2n-2,\\ I(n,1,3)&=&2{B_{K}^{n}}(2)-I(n,1,2)=n^{2}-n. \end{array}$$
(7)

When α,β satisfy dK(α,β) = 2 and they are of type II, we have

$$|{B_{K}^{n}}(\alpha,3)\cap {B_{K}^{n}}(\upbeta,3)|=I(n,1,3)=n^{2}-n.$$
(8)

To obtain the values of I(n,2,3), we now compute the exact value of \(|{B_{K}^{n}}(\alpha ,3)\cap {B_{K}^{n}}(\upbeta ,3)|\) when α,β satisfy dK(α,β) = 2 and they are of type I. We start in the next lemma.

Lemma 5

Let n,r,d be integers and \(\alpha ,\upbeta \in \mathcal {S}_{n}\) such that dK(α,β) = d. Then there exists some permutation \(\gamma \in \mathcal {S}_{n}\) of weight wK(γ) = d such that \(|{B_{K}^{n}}(\alpha ,r)\cap {B_{K}^{n}}(\upbeta ,r)|=|{B_{K}^{n}}(\epsilon _{n},r)\cap {B_{K}^{n}}(\gamma ,r)|\).

Proof

Let γ =β ∘α− 1. If \(\sigma \in {B_{K}^{n}}(\alpha ,r)\cap {B_{K}^{n}}(\upbeta ,r)\), then we have dK(α,σ) ≤ r and dK(β,σ) ≤ r. Since the Kendall τ-metric is right invariant, then dK(𝜖n,σ ∘ α− 1) = dK(α,σ) ≤ r and dK(β∘α− 1,σ ∘ α− 1) = dK(β,σ) ≤ r. Hence, \(\sigma \circ \alpha ^{-1}\in {B_{K}^{n}}(\epsilon _{n},r)\cap {B_{K}^{n}}(\gamma ,r)\) and \(|{B_{K}^{n}}(\alpha ,r)\cap {B_{K}^{n}}(\upbeta ,r)|\leq |{B_{K}^{n}}(\epsilon _{n},r)\cap {B_{K}^{n}}(\gamma ,r)|\). Similarly, we also have \(|{B_{K}^{n}}(\alpha ,r)\cap {B_{K}^{n}}(\upbeta ,r)|\geq |{B_{K}^{n}}(\epsilon _{n},r)\cap {B_{K}^{n}}(\gamma ,r)|\). So, we clearly obtain \(|{B_{K}^{n}}(\alpha ,r)\cap {B_{K}^{n}}(\upbeta ,r)|= |{B_{K}^{n}}(\epsilon _{n},r)\cap {B_{K}^{n}}(\gamma ,r)|\). □

To compute the value of \(|{B_{K}^{n}}(\alpha ,3)\cap {B_{K}^{n}}(\upbeta ,3)|\), by Lemma 5, we only consider α = 𝜖n and dK(𝜖n,β) = 2 such that 𝜖n,β are of type I. For convenience, the i-th adjacent transposition, denoted by ei, exchanges the elements in positions i and i + 1 and keeps all other elements fixed for any 1 ≤ i ≤ n − 1.

Lemma 6

Let \(\upbeta \in \mathcal {S}_{n}\). Then 𝜖n,β are of type II if and only if β = ei ∘ ej for some i,j ∈ [n − 1] and |i − j|≥ 2. Moreover, 𝜖n,β are of type I if and only if β = ei ∘ ei+ 1 or ei+ 1 ∘ ei for some i ∈ [n − 2].

Proof

When 𝜖n,β are of type II, we have dK(𝜖n,β) = 2. Thus, β = ei ∘ ej for i≠j and i,j ∈ [n − 1]. If |i − j|≥ 2, it follows that 𝜖n,β are of type II. When |i − j| = 1, without loss of generality, we let j = i + 1. Then, we only have a permutation ei such that dK(𝜖n,ei) = dK(ei ∘ ei+ 1,ei+ 1) = 1. Hence, 𝜖n and β are not of type II. So, 𝜖n,β are of type II if and only if β = ei ∘ ej for some i,j ∈ [n − 1] and |i − j|≥ 2. Similarly, 𝜖n,β are of type I if and only if β = ei ∘ ei+ 1 or ei+ 1 ∘ ei for some i ∈ [n − 2]. □

When dK(𝜖n,β) = 2 and they are of type I, by Lemma 6, then β = ei ∘ ei+ 1 or ei+ 1 ∘ ei for some i ∈ [n − 2]. For convenience, we call this kind of permutation the type I for i ∈ [n − 2]. Now, we give some lemmas in the following.

Lemma 7

Let \(\alpha \in \mathcal {S}_{n}\). Then, it follows that

$$w_{K}(\alpha)=|Iv(\alpha)|.$$
(9)

Proof

By the definition of wK(α), we have that wK(α) = dK(𝜖n,α) = |{(i,j) : i < j ∧ α− 1(i) > α− 1(j)}|. Further, due to the definition of Iv(α), it follows that Iv(α) = {(i,j) : i < j ∧ α− 1(i) > α− 1(j)}. Hence, we have wK(α) = |Iv(α)|. □

For example, let π = [3,1,2]. Then we have that Iv(π) = {(1,3),(2,3)}. Hence, wK(π) = |Iv(π)| = 2.

Lemma 8

Let \(\alpha ,\upbeta \in \mathcal {S}_{n}\). Then, we have that

$$\begin{array}{@{}rcl@{}} d_{K}(\alpha,\upbeta)&=&|(Iv(\alpha)\cup Iv(\upbeta)\big)\backslash \big(Iv(\alpha)\cap Iv(\upbeta)\big)|\\ &=&|Iv(\alpha)\cup Iv(\upbeta)|-|Iv(\alpha)\cap Iv(\upbeta)|\\ &=&|Iv(\alpha)|+|Iv(\upbeta)|-2|Iv(\alpha)\cap Iv(\upbeta)|. \end{array}$$
(10)

Proof

By the definition of dK(α,β), it follows that \(d_{K}(\alpha ,\upbeta )=|\{(i,j):\alpha ^{-1}(i)<\alpha ^{-1}(j)\wedge {\upbeta }^{-1}(i)>{\upbeta }^{-1}(j)\}|\). Let \((i_{1},j_{1})\in \{(i,j):\alpha ^{-1}(i)<\alpha ^{-1}(j)\wedge {\upbeta }^{-1}(i)>{\upbeta }^{-1}(j)\}\). Then, α− 1(i1) < α− 1(j1) and \({\upbeta }^{-1}(i_{1})>{\upbeta }^{-1}(j_{1})\). If i1 < j1, then it follows that (i1,j1) ∈ Iv(β) and (i1,j1)∉Iv(α). If i1 > j1, then we have that (i1,j1) ∈ Iv(α) and (i1,j1)∉Iv(β). Thus, (i1,j1) ∈(Iv(α) ∪ Iv(β))∖(Iv(α) ∩ Iv(β)). Similarly, let (i1,j1) ∈(Iv(α) ∪ Iv(β))∖(Iv(α) ∩ Iv(β)), we also have that \((i_{1},j_{1})\in \{(i,j):\alpha ^{-1}(i)<\alpha ^{-1}(j)\wedge {\upbeta }^{-1}(i)>{\upbeta }^{-1}(j)\}\). Hence, it follows that

$$\begin{array}{@{}rcl@{}} \{(i,j):\alpha^{-1}(i)<\alpha^{-1}(j)\wedge{\upbeta}^{-1}(i)&>&{\upbeta}^{-1}(j)\}\\ &=&(Iv(\alpha)\cup Iv(\upbeta)\big)\backslash \big(Iv(\alpha)\cap Iv(\upbeta)\big). \end{array}$$

Further, we obtain that dK(α,β) = |(Iv(α)∪Iv(β))∖(Iv(α)∩Iv(β))| = |Iv(α)∪Iv(β)|−|Iv(α)∩Iv(β)| = |Iv(α)|+|Iv(β)|− 2|Iv(α)∩Iv(β)|. □

For example, let α = [3,1,2] and β = [2,1,3]. Then it follows that Iv(α) = {(1,3),(2,3)} and Iv(β) = {(1,2)}. It is easily obtained that Iv(α) ∩ Iv(β) = ∅. Hence, dK(α,β) = |Iv(α)| + |Iv(β)|− 2|Iv(α) ∩ Iv(β)| = 2 + 1 = 3.

Lemma 9

For n ≥ r ≥ 3, we have \(|{B_{K}^{n}}(\epsilon _{n},r)\cap {B_{K}^{n}}(e_{i}\circ e_{i+1},r)|=|{B_{K}^{n}}(\epsilon _{n},r)\cap {B_{K}^{n}}(e_{i+1}\circ e_{i},r)|=|{B_{K}^{n}}(e_{i},r)\cap {B_{K}^{n}}(e_{i+1},r)|=|{B_{K}^{n}}(\epsilon _{n},r-1)\cup {B_{K}^{n}}(e_{i}\circ e_{i+1}\circ e_{i},r-2)|\).

Proof

Since the Kendall τ-metric is right invariant, we have \(|{B_{K}^{n}}(\epsilon _{n},r)\cap {B_{K}^{n}}(e_{i}\circ e_{i+1},r)|=|{B_{K}^{n}}(\epsilon _{n},r)\cap {B_{K}^{n}}(e_{i+1}\circ e_{i},r)|=|{B_{K}^{n}}(e_{i},r)\cap {B_{K}^{n}}(e_{i+1},r)|\). Next, we prove that \(|{B_{K}^{n}}(e_{i},r)\cap {B_{K}^{n}}(e_{i+1},r)|=|{B_{K}^{n}}(\epsilon _{n},r-1)\cup {B_{K}^{n}}(e_{i}\circ e_{i+1}\circ e_{i},r-2)|\). First, we discuss \(({B_{K}^{n}}(e_{i},r)\cap {B_{K}^{n}}(e_{i+1},r))\subset ({B_{K}^{n}}(\epsilon ,r-1)\cup {B_{K}^{n}}(e_{i}\circ e_{i+1}\circ e_{i},r-2))\). Let \(\gamma \in {B_{K}^{n}}(e_{i},r)\cap {B_{K}^{n}}(e_{i+1},r)\), and assume that \(\gamma \notin {B_{K}^{n}}(\epsilon _{n},r-1)\). By (10), we have

$$d_{K}(\gamma,e_{i})= \begin{cases} |Iv(\gamma)|-1,&\text{if $(i,i+1)\in Iv(\gamma)$,}\\ |Iv(\gamma)|+1,&\text{if $(i,i+1)\notin Iv(\gamma)$.} \end{cases}$$
(11)

Since dK(γ,ei) ≤ r and |Iv(γ)|≥ r by assumption, it follows that (i,i + 1) ∈ Iv(γ). Similarly, we also have that (i + 1,i + 2) ∈ Iv(γ). By the definition of Iv(γ) and (i,i + 1),(i + 1,i + 2) ∈ Iv(γ), we have that γ− 1(i) > γ− 1(i + 1) and γ− 1(i + 1) > γ− 1(i + 2). Hence, γ− 1(i) > γ− 1(i + 2). So, (i,i + 2) ∈ Iv(γ). Therefore, (i,i + 1),(i + 1,i + 2),(i,i + 2) ∈ Iv(γ). It is easily verified that Iv(ei ∘ ei+ 1 ∘ ei) = {(i,i + 1),(i + 1,i + 2),(i,i + 2)}. By (10), it follows that

$$d_{K}(\gamma,e_{i}\circ e_{i+1}\circ e_{i})=|Iv(\gamma)|+3-6=|Iv(\gamma)|-3.$$
(12)

By (i,i + 1) ∈ Iv(γ) and \(\gamma \in {B_{K}^{n}}(e_{i},r)\), we have dK(γ,ei) = |Iv(γ)|− 1 ≤ r. Hence, |Iv(γ)|≤ r + 1. By (12), it follows that dK(γ,ei ∘ ei+ 1 ∘ ei) ≤ r − 2. So, we have \(\gamma \in {B_{K}^{n}}(\epsilon _{n},r-1)\cup {B_{K}^{n}}(e_{i}\circ e_{i+1}\circ e_{i},r-2)\). Similarly, when \(\gamma \in {B_{K}^{n}}(\epsilon _{n},r-1)\cup {B_{K}^{n}}(e_{i}\circ e_{i+1}\circ e_{i},r-2)\), we also obtain that \(\gamma \in {B_{K}^{n}}(e_{i},r)\cap {B_{K}^{n}}(e_{i+1},r)\). Therefore, we prove that \(|{B_{K}^{n}}(e_{i},r)\cap {B_{K}^{n}}(e_{i+1},r)|=|{B_{K}^{n}}(\epsilon _{n},r-1)\cup {B_{K}^{n}}(e_{i}\circ e_{i+1}\circ e_{i},r-2)|\). □

When β is the type I, by Lemma 9, we can find the value of \(|{B_{K}^{n}}(\epsilon _{n},3)\cap {B_{K}^{n}}(\upbeta ,3)|\).

Lemma 10

When β is the type I, for n ≥ r ≥ 3, we have

$$|{B_{K}^{n}}(\epsilon_{n},3)\cap {B_{K}^{n}}(\upbeta,3)|={B_{K}^{n}}(2)+{B_{K}^{n}}(1)-2=\frac{n^{2}+3n-6}{2}.$$
(13)

Proof

By Lemma 9, we have \(|{B_{K}^{n}}(\epsilon _{n},3)\cap {B_{K}^{n}}(\upbeta ,3)|=|{B_{K}^{n}}(\epsilon _{n},2)|+|{B_{K}^{n}}(e_{i}\circ e_{i+1}\circ e_{i},1)|-|{B_{K}^{n}}(\epsilon _{n},2)\cap {B_{K}^{n}}(e_{i}\circ e_{i+1}\circ e_{i},1)|\) for some i ∈ [n − 2]. For all i ∈ [n − 2], it is easily verified that \({B_{K}^{n}}(\epsilon _{n},2)\cap {B_{K}^{n}}(e_{i}\circ e_{i+1}\circ e_{i},1)=\{e_{i}\circ e_{i+1},e_{i+1}\circ e_{i}\}\). Then, we have \(|{B_{K}^{n}}(\epsilon _{n},2)\cap {B_{K}^{n}}(e_{i}\circ e_{i+1}\circ e_{i},1)|=2\). Thus, we can obtain that \(|{B_{K}^{n}}(\epsilon _{n},3)\cap {B_{K}^{n}}(\upbeta ,3)|={B_{K}^{n}}(2)+{B_{K}^{n}}(1)-2\). By Lemma 4, we have \({B_{K}^{n}}(2)=\frac {n^{2}+n-2}{2}\) and \({B_{K}^{n}}(1)=n\). So, we have \(|{B_{K}^{n}}(\epsilon _{n},3)\cap {B_{K}^{n}}(\upbeta ,3)|={B_{K}^{n}}(2)+{B_{K}^{n}}(1)-2=\frac {n^{2}+3n-6}{2}\). □

By (8) and (13), we can obtain the following theorem.

Theorem 1

For n ≥ 3, we have

$$I(n,2,3)=n^{2}-n.$$
(14)

Proof

When α,β satisfy dK(α,β) = 2 and they are of type II, by (8), we have \(|{B_{K}^{n}}(\alpha ,3)\cap {B_{K}^{n}}(\upbeta ,3)|=n^{2}-n\). When α,β satisfy dK(α,β) = 2 and they are of type I, by Lemma 5 and (13), we can obtain that \(|{B_{K}^{n}}(\alpha ,3)\cap {B_{K}^{n}}(\upbeta ,3)|=\frac {n^{2}+3n-6}{2}\). Hence, we have \(I(n,2,3)=\max \limits \{\frac {n^{2}+3n-6}{2},n^{2}-n\}=n^{2}-n\) for all n ≥ 3. □

We will present the upper bounds of I(n,d,3) for d = 3,4,5,6 as follows. To get these properties, we need some lemmas.

When wK(β) = 2 or 3, the forms of β and the inversions of β are given in the following lemma.

Lemma 11

Let n ≥ 3 and \(\upbeta \in \mathcal {S}_{n}\). When wK(β) = 2, then β = ei ∘ ei+ 1 or ei+ 1 ∘ ei for some i ∈ [n − 2], or ej ∘ ei for some i,j ∈ [n − 1] and |i − j|≥ 2. When wK(β) = 3, then β = ek ∘ ei ∘ ei+ 1 for some k ∈ [n − 1], i ∈ [n − 2], and k≠i, or ek ∘ ei+ 1 ∘ ei for some k ∈ [n − 1], i ∈ [n − 2], and k≠i + 1, or ek ∘ ej ∘ ei for some i,j,k ∈ [n − 1], |i − j|≥ 2, and k≠i or j. Moveover, when wK(β) = 2, the inversions of β may be (i,i + 1) or (i,i + 2) for some i ∈ [n − 1]. When wK(β) = 3, the inversions of β may be (i,i + 1), (i,i + 2), or (i,i + 3) for some i ∈ [n − 1].

Proof

When wK(β) = 2, if β is of type I, then β = ei ∘ ei+ 1 or ei+ 1 ∘ ei for some i ∈ [n − 2]. Hence, the inversions of β are (i,i + 1) and (i,i + 2), or (i,i + 2) and (i + 1,i + 2). If β is of type II, then β = ej ∘ ei for some |i − j|≥ 2. Thus, the inversions of β are (i,i + 1) and (j,j + 1). So, when wK(β) = 2, then β = ei ∘ ei+ 1 or ei+ 1 ∘ ei for some i ∈ [n − 2], or ej ∘ ei for some i,j ∈ [n − 1] and |i − j|≥ 2. Moreover, the inversions of β may be (i,i + 1) or (i,i + 2) for some i ∈ [n − 1].

Similarly, when wK(β) = 3, by using the forms of the permutation of weight 2, then β = ek ∘ ei ∘ ei+ 1 for some k ∈ [n − 1], i ∈ [n − 2], and k≠i, or ek ∘ ei+ 1 ∘ ei for some k ∈ [n − 1], i ∈ [n − 2], and k≠i + 1, or ek ∘ ej ∘ ei for some i,j,k ∈ [n − 1], |i − j|≥ 2, and k≠i or j. When β = ek ∘ ei ∘ ei+ 1 for some k ∈ [n − 1], i ∈ [n − 2], and k≠i, then (i,i + 2),(i + 1,i + 2) ∈ Iv(β). If k = i + 2, then Iv(β) = {(i,i + 2),(i + 1,i + 2),(i + 1,i + 3)}. If k = i + 1, then Iv(β) = {(i,i + 1),(i,i + 2),(i + 1,i + 2)}. If k = i − 1, then Iv(β) = {(i,i + 2),(i + 1,i + 2),(i − 1,i + 2)}. If k≠i − 1,i,or i + 2, then Iv(β) = {(i,i + 2),(i + 1,i + 2),(k,k + 1)}.

When β = ek ∘ ei+ 1 ∘ ei for some k ∈ [n − 1], i ∈ [n − 2], and k≠i + 1, then (i,i + 1),(i,i + 2) ∈ Iv(β). If k = i + 2, then Iv(β) = {(i,i + 1),(i,i + 2),(i,i + 3)}. If k = i, then Iv(β) = {(i,i + 2),(i + 1,i + 2),(i,i + 1)}. If k = i − 1, then Iv(β) = {(i,i + 1),(i,i + 2),(i − 1,i + 1)}. If k≠i − 1,i + 1,or i + 2, then Iv(β) = {(i,i + 1),(i,i + 2),(k,k + 1)}.

When β = ek ∘ ej ∘ ei for some i,j,k ∈ [n − 1], |i − j|≥ 2, and k≠i or j, then (i,i + 1),(j,j + 1) ∈ Iv(β). It is easily verified that β = ek ∘ ej ∘ ei = ek ∘ ei ∘ ej. For convenience, let i < j. If j − i = 2 and k = (i + j)/2, then Iv(β) = {(i,i + 1),(j,j + 1),(k − 1,k + 2)}. If |k − i|≥ 2 and |k − j|≥ 2, then Iv(β) = {(i,i + 1),(j,j + 1),(k,k + 1)}. If k = i − 1, then β = ek ∘ ej ∘ ei = ei− 1 ∘ ei ∘ ej and Iv(β) = {(i − 1,i + 1),(i,i + 1),(j,j + 1)}. If k = j + 1, then β = ek ∘ ej ∘ ei = ej+ 1 ∘ ej ∘ ei and Iv(β) = {(i,i + 1),(j,j + 1),(j,j + 2)}. If k = i + 1 and j − i > 2, then β = ek ∘ ej ∘ ei = ei+ 1 ∘ ei ∘ ej and Iv(β) = {(i,i + 1),(j,j + 1),(i,i + 2)}. If k = j − 1 and j − i > 2, then β = ek ∘ ej ∘ ei = ej− 1 ∘ ej ∘ ei and Iv(β) = {(i,i + 1),(j,j + 1),(j − 1,j + 1)}.

Therefore, when wK(β) = 3, the inversions of β may be (i,i + 1), (i,i + 2), or (i,i + 3) for some i ∈ [n − 1]. □

Now, given two distinct inversions I1,I2, we estimate the size of \(S_{(3,I_{1},I_{2})}^{n}:=\{\upbeta \in \mathcal {S}_{n}|w_{K}(\upbeta )=3,I_{i}\in Iv(\upbeta )~\text {for~all}~i\in [2]\}\) and the size of \(S_{(2,I_{1})}^{n}:=\{\upbeta \in \mathcal {S}_{n}|w_{K}(\upbeta )=2,I_{1}\in Iv(\upbeta )\}\), respectively.

Lemma 12

Assume that \(S_{(3,I_{1},I_{2})}^{n}\) and \(S_{(2,I_{1})}^{n}\) are defined as above. Then, we have

$$\begin{array}{@{}rcl@{}} |S_{(3,I_{1},I_{2})}^{n}|\leq (n-2)~~\text{for all}~n\geq 4, \end{array}$$
(15)
$$\begin{array}{@{}rcl@{}} |S_{(2,I_{1})}^{n}|\leq (n-2)~~\text{for all}~n\geq 4. \end{array}$$
(16)

Proof

By Lemma 11, we will discuss the value of \(|S_{(3,I_{1},I_{2})}^{n}|\) according to the forms of I1,I2. Let \(\upbeta \in S_{(3,I_{1},I_{2})}^{n}\). Then I1,I2 ∈ Iv(β) and |Iv(β)| = 3. If I1,I2 has one form of (i,i + 3), by Lemma 11, then β must be ei ∘ ei+ 1 ∘ ei+ 2, ei+ 2 ∘ ei+ 1 ∘ ei, or ei+ 1 ∘ ei ∘ ei+ 2. Hence, when I1,I2 has one form of (i,i + 3), we have that

$$|S_{(3,I_{1},I_{2})}^{n}|\leq 3.$$
(17)

If I1,I2 has one form of (i,i + 2), then (i,i + 2) ∈ Iv(β). For convenience, let I1 = (i,i + 2). By Lemma 11, Iv(β) must contain two inversions (i,i + 1),(i,i + 2) or (i,i + 2),(i + 1,i + 2). When {I1,I2} = {(i,i + 1),(i,i + 2)}, by the proof of Lemma 11, it follows that β = ek ∘ ei+ 1 ∘ ei for some k ∈ [n − 1], i ∈ [n − 2], and k≠i + 1. Since k ∈ [n − 1] and k≠i + 1, the number of this kind of β is n − 2. Hence, \(|S_{(3,I_{1},I_{2})}^{n}|=n-2\). Similarly, when {I1,I2} = {(i,i + 2),(i + 1,i + 2)}, then β = ek ∘ ei ∘ ei+ 1 for some k ∈ [n − 1], i ∈ [n − 2], and k≠i. Thus, we also have that \(|S_{(3,I_{1},I_{2})}^{n}|=n-2\). Then, when {I1,I2} = {(i,i + 1),(i,i + 2)} or {(i,i + 2),(i + 1,i + 2)}, it follows that

$$|S_{(3,I_{1},I_{2})}^{n}|=n-2.$$
(18)

When {I1,I2}≠{(i,i + 1),(i,i + 2)} or {(i,i + 2),(i + 1,i + 2)}, then I2≠(i,i + 1) or (i + 1,i + 2). Since I1,I2 ∈ Iv(β) and Iv(β) must contain two inversions (i,i + 1),(i,i + 2) or (i,i + 2),(i + 1,i + 2), it follows that Iv(β) must be {(i,i + 1),(i,i + 2),I2} or {(i + 1,i + 2),(i,i + 2),I2}. Hence, we have that

$$|S_{(3,I_{1},I_{2})}^{n}|\leq 2.$$
(19)

If I1 = (i,i + 1) and I2 = (j,j + 1), then (i,i + 1),(j,j + 1) ∈ Iv(β). For convenience, let j > i. When j − i = 1, we have that (i,i + 1),(i + 1,i + 2) ∈ Iv(β). By Lemma 11, then (i,i + 2) ∈ Iv(β). Hence, we have that

$$|S_{(3,I_{1},I_{2})}^{n}|=1.$$
(20)

When j − i ≥ 2, by the proof of Lemma 11, it follows that β = ek ∘ ej ∘ ei for some k ∈ [n − 1] and k≠i or j. Thus, it follows that

$$|S_{(3,I_{1},I_{2})}^{n}|=n-3.$$
(21)

By the above discussion, we obtain that

$$|S_{(3,I_{1},I_{2})}^{n}|\leq (n-2)~~\text{for all}~n\geq 4.$$

Next, we will discuss the value of discuss the value of \(|S_{(2,I_{1})}^{n}|\) according to the forms of I1. Let \(\upbeta \in S_{(2,I_{1})}^{n}\). Then I1 ∈ Iv(β) and |Iv(β)| = 2. If I1 = (i,i + 2), by Lemma 11, then β = ei ∘ ei+ 1 or ∘ ei+ 1 ∘ ei. Hence, when I1 = (i,i + 2), we have that \(|S_{(2,I_{1})}^{n}|=2\). If I1 = (i,i + 1), by Lemma 11, then β = ei ∘ ej for some j ∈ [n − 1] and j≠i. Hence, \(|S_{(2,I_{1})}^{n}|=n-2\). So, we also have that

$$|S_{(2,I_{1})}^{n}|\leq (n-2)~~\text{for all}~n\geq 4.$$

□

By Lemma 12, we can obtain the following lemma.

Lemma 13

For n ≥ 6, we have

$$I(n,3,3)\leq 6n-7.$$
(22)

Proof

Let \(\upbeta \in \mathcal {S}_{n}\) be a permutation such that wK(β) = 3 and \(I(n,3,3)=|{B_{K}^{n}}(\epsilon _{n},3)\cap {B_{K}^{n}}(\upbeta ,3)|\). For convenience, let Iv(β) = {I1,I2,I3}. Obviously, we have \({B_{K}^{n}}(\epsilon _{n},3)\cap {B_{K}^{n}}(\upbeta ,3)=\cup _{i=0}^{3}\{\gamma |w_{K}(\gamma )=i,d_{K}(\gamma ,\upbeta )\leq 3\}\). We estimate the value of |{γ|wK(γ) = i,dK(γ,β) ≤ 3}| for each 0 ≤ i ≤ 3 as follows.

First, we consider the value of |{γ|wK(γ) = 3,dK(γ,β) ≤ 3}|. Suppose Iv(γ) = {a,b,c}. By Lemma 8, then we have dK(γ,β) = |Iv(γ)| + |Iv(β)|− 2|(Iv(β) ∩ Iv(γ))|. Hence, we get dK(γ,β) = 6 − 2|(Iv(β) ∩ Iv(γ))|. When dK(γ,β) ≤ 3, then we have |(Iv(β) ∩ Iv(γ))| = 2 or 3. If |(Iv(β) ∩ Iv(γ))| = 3, the number of γ is 1. If |(Iv(β) ∩ Iv(γ))| = 2, then Iv(γ) contains two elements of {I1,I2,I3}. By Lemma 12, the number of this kind of γ is at most \(\binom {3}{2}(n-2)\). Since β ∈{γ|wK(γ) = 3,Iv(γ) contains two elements of {I1,I2,I3}}, then we have

$$|\{\gamma|w_{K}(\gamma)=3,d_{K}(\gamma,\upbeta)\leq 3\}|\leq 3(n-2)-2=3n-8.$$
(23)

Next, we compute |{γ|wK(γ) = 2,dK(γ,β) ≤ 3}|. Suppose Iv(γ) = {a,b}. When dK(γ,β) ≤ 3, then we get |(Iv(β) ∩ Iv(γ))| = 1 or 2. If |(Iv(β) ∩ Iv(γ))| = 2, the number of γ is at most \(\binom {3}{2}=3\). If |(Iv(β) ∩ Iv(γ))| = 1, then Iv(γ) contains one element of {I1,I2,I3}. By Lemma 12, the number of this kind of γ is at most \(\binom {3}{1}(n-2)\). Hence, we have

$$|\{\gamma|w_{K}(\gamma)=2,d_{K}(\gamma,\upbeta)\leq 3\}|\leq 3(n-2)+3=3n-3.$$
(24)

Finally, we clearly obtain that |{γ|wK(γ) = 1,dK(γ,β) ≤ 3}|≤ 3 and |{γ|wK(γ) = 0,dK(γ,β) ≤ 3}|≤ 1. Therefore, by (23)-(24), we have

$$I(n,3,3)=\sum\limits_{i=0}^{3}|\{\gamma|w_{K}(\gamma)=i,d_{K}(\gamma,\upbeta)\leq 3\}|\leq 6n-7.$$

□

Lemma 14

For n ≥ 6, we have

$$I(n,4,3)\leq 6n-8.$$
(25)

Proof

Let \(\upbeta \in \mathcal {S}_{n}\) be a permutation such that wK(β) = 4 and \(I(n,4,3)=|{B_{K}^{n}}(\epsilon _{n},3)\cap {B_{K}^{n}}(\upbeta ,3)|\). For convenience, let Iv(β) = {I1,I2,I3,I4}. Clearly, we have \({B_{K}^{n}}(\epsilon _{n},3)\cap {B_{K}^{n}}(\upbeta ,3)=\cup _{i=0}^{3}\{\gamma |w_{K}(\gamma )=i,d_{K}(\gamma ,\upbeta )\leq 3\}\). Next, we estimate the size of |{γ|wK(γ) = i,dK(γ,β) ≤ 3}| for each 0 ≤ i ≤ 3 by the different kind of Iv(β). Suppose I1 = (i1,j1) ∈ Iv(β) is an inversion with the maximum value of |i1 − j1|.

Now, we consider the value of |{γ|wK(γ) = 3,dK(γ,β) ≤ 3}|. For convenience, Iv(γ) = {a,b,c}. By Lemma 8, then we have dK(γ,β) = |Iv(γ)| + |Iv(β)|− 2|(Iv(β) ∩ Iv(γ))|. Hence, we get dK(γ,β) = 7 − 2|(Iv(β) ∩ Iv(γ))|. When dK(γ,β) ≤ 3, we have that |(Iv(β) ∩ Iv(γ))| = 2 or 3. Thus, Iv(γ) contains at least two elements of {I1,I2,I3,I4}. If |j1 − i1|≥ 4, then I1∉Iv(γ). By Lemma 12, the number of this kind of γ is at most \(\binom {3}{2}(n-2)\). Hence, we have that

$$|\{\gamma|w_{K}(\gamma)=3,d_{K}(\gamma,\upbeta)\leq 3\}|\leq \binom{3}{2}(n-2)=3n-6.$$
(26)

If |j1 − i1| = 3, then I1 may be an element of Iv(γ). When I1 ∈ Iv(γ), by (17), it follows that the number of this kind of γ is at most 3. When I1∉Iv(γ), by (26), we have that the number of this kind of γ is at most 3n − 6. Hence, we have that

$$|\{\gamma|w_{K}(\gamma)=3,d_{K}(\gamma,\upbeta)\leq 3\}|\leq \binom{3}{2}(n-2)+3=3n-3.$$
(27)

If |j1 − i1| = 2, then I1 may be an element of Iv(γ). For convenience, let I1 = (i1,j1) = (i,i + 2). Consider {(i,i + 1),(i + 1,i + 2)}⊂ Iv(β). When I1 ∈ Iv(γ), by (18) and (19), the number of this kind of γ is at most 2(n − 2) + 2. Moreover, if (i,i + 1),(i + 1,i + 2) ∈ Iv(γ), then I1 = (i,i + 2) ∈ Iv(γ). Thus, when I1∉Iv(γ), by Lemma 12, the number of this kind of γ is at most 2(n − 2). Hence, when |j1 − i1| = 2 and {(i,i + 1),(i + 1,i + 2)}⊂ Iv(β), we have that

$$|\{\gamma|w_{K}(\gamma)=3,d_{K}(\gamma,\upbeta)\leq 3\}|\leq 4(n-2)+2=4n-6.$$
(28)

Consider {(i,i + 1),(i + 1,i + 2)}⊄Iv(β). When I1 ∈ Iv(γ), by (18) and (19), the number of this kind of γ is at most (n − 2) + 4. When I1∉Iv(γ), by Lemma 12, the number of this kind of γ is at most 3(n − 2). Hence, when |j1 − i1| = 2 and {(i,i + 1),(i + 1,i + 2)}⊄Iv(β), we have that

$$|\{\gamma|w_{K}(\gamma)=3,d_{K}(\gamma,\upbeta)\leq 3\}|\leq 4(n-2)+4=4n-4.$$
(29)

If |j1 − i1| = 1, then I1,I2,I3,I4 may be an element of Iv(γ). By (20) and (21), the number of this kind of γ is at most \(\binom {4}{2}(n-3)\). Hence, when |j1 − i1| = 1, we have that

$$|\{\gamma|w_{K}(\gamma)=3,d_{K}(\gamma,\upbeta)\leq 3\}|\leq \binom{4}{2}(n-3)=6n-18.$$
(30)

Similarly, when |i1 − j1|≥ 2, we have that |{γ|wK(γ) = 2,dK(γ,β) ≤ 3}|≤ 5, |{γ|wK(γ) = 1,dK(γ,β) ≤ 3}|≤ 3 and |{γ|wK(γ) = 0,dK(γ,β) ≤ 3}| = 0. When |i1 − j1| = 1, we obtain that |{γ|wK(γ) = 2,dK(γ,β) ≤ 3}|≤ 6, |{γ|wK(γ) = 1,dK(γ,β) ≤ 3}|≤ 4 and |{γ|wK(γ) = 0,dK(γ,β) ≤ 3}| = 0. By (26)-(29) and the above discussion, when |i1 − j1|≥ 2, it follows that

$$\sum\limits_{i=0}^{3}|\{\gamma|w_{K}(\gamma)=i,d_{K}(\gamma,\upbeta)\leq 3\}|\leq 4n-4+8=4n+4,$$
(31)

for n ≥ 6. By (30) and the above discussion, when |i1 − j1| = 1, it follows that

$$\sum\limits_{i=0}^{3}|\{\gamma|w_{K}(\gamma)=i,d_{K}(\gamma,\upbeta)\leq 3\}|\leq 6n-18 + 10=6n-8.$$
(32)

Therefore, for n ≥ 6, by (31) and (32), we have that

$$I(n,4,3)=\sum\limits_{i=0}^{3}|\{\gamma|w_{K}(\gamma)=i,d_{K}(\gamma,\upbeta)\leq 3\}|\leq 6n-8.$$

□

Lemma 15

For n ≥ 5, we have

$$\begin{array}{@{}rcl@{}} I(n,d,3)&\leq 20~~~\text{if}~d=5~\text{or}~6,\\ I(n,d,3)&=0~~~\text{if}~d\geq 7. \end{array}$$
(33)

Proof

When d = 5, let \(\upbeta \in \mathcal {S}_{n}\) be a permutation such that wK(β) = 5 and \(I(n,5,3)=|{B_{K}^{n}}(\epsilon _{n},3)\cap {B_{K}^{n}}(\upbeta ,3)|\). For convenience, let Iv(β) = {I1,I2,I3,I4,I5}. Next, we estimate the value of |{γ|wK(γ) = i,dK(γ,β) ≤ 3}| for each 0 ≤ i ≤ 3.

Let wK(γ) = i and dK(γ,β) ≤ 3. By Lemma 8, then we have dK(γ,β) = |Iv(γ)| + |Iv(β)|− 2|(Iv(β) ∩ Iv(γ))|. Hence, we obtain that dK(γ,β) = 5 + i − 2|(Iv(β) ∩ Iv(γ))| and 0 ≤|(Iv(β) ∩ Iv(γ))|≤ i for any 0 ≤ i ≤ 3. Since dK(γ,β) ≤ 3, then we have i = 2 or 3, and Iv(γ) ⊂ Iv(β). When i = 2, the number of γ of wK(γ) = 2 is at most \(\binom {5}{2}\). When i = 3, we also have that the number of γ of wK(γ) = 3 is at most \(\binom {5}{3}\). So, we get

$$I(n,5,3)\leq \binom{5}{2}+\binom{5}{3}=20.$$

Similarly, we can obtain that I(n,6,3) ≤ 20 and I(n,d,3) = 0 for all d ≥ 7. □

By Lemmas 13-15, we can summarize up some properties of N(n,d,3) for 3 ≤ d as follows.

Proposition 1

Let n,d be integers. Then we have

$$I(n,d,3)\leq \begin{cases} 6n-7~~&\text{if}~d=3~\text{and}~n\geq 6,\\ 6n-8~~&\text{if}~d=4~\text{and}~n\geq 6,\\ 20~~&\text{if}~d=5~\text{or}~6~\text{and}~n\geq 5,\\ \end{cases}$$

and I(n,d,3) = 0 for all d ≥ 7.

By the above discussion, we can obtain the following theorem. Moreover, the upper bounds on I(4,3,3),I(4,4,3),I(5,3,3),I(5,4,3) will be discussed in the A.

Theorem 2

For all n ≥ 3, we have

$$N(n,1,3)=N(n,2,3)=n^{2}-n.$$
(34)

Proof

By (14), Lemma 3, and Proposition 1, we can obtain that N(n,1,3) = N(n,2,3) = n2 − n for any n ≥ 6. When 3 ≤ n ≤ 5, we have N(3,1,3) = N(3,2,3) = 6,N(4,1,3) = N(4,2,3) = 12,N(5,1,3) = N(5,2,3) = 20. Specifically, more details on the proof of N(n,d,3) for all d = 1,2 and 3 ≤ n ≤ 5 can be found in the A. Therefore, for all n ≥ 3, we have N(n,1,3) = N(n,2,3) = n2 − n. □

4 Conclusions

In this paper, we studied the reconstruction problem for permutations on n elements from their erroneous patterns which are distorted by at most three Kendall τ-errors. Specially, it is shown that n2 − n + 1 erroneous patterns are required in order to reconstruct an unknown permutation from some permutation code of minimum Kendall τ-distance 2 or an arbitrary unknown permutation for any n ≥ 3. That is, we proved that N(n,1,3) = N(n,2,3) = n2 − n for any n ≥ 3.